# Designing a Geospatial Proximity Service at Scale

## Blog Details

- **Author**: Naveen R.
- **Date**: September 20, 2026
- **Tags**: geospatial, system design, spatial indexing, database optimization, scalability
- **Read Time**: 20 mins

## Introduction

When a user opens a ride-sharing app and sees nearby drivers, or searches for "coffee shops near me," they're interacting with a geospatial proximity service. Behind that simple interface lies a complex system that must query millions of locations, calculate distances, rank results, and return answers in milliseconds.

This post examines how to design such a system for scale. We'll work through spatial indexing structures with concrete examples, explore database strategies backed by real performance data, tackle the challenges of sharding location data across multiple servers, and implement efficient ranking algorithms. The goal is to build a service that handles millions of queries per second while maintaining sub-100ms response times.

## Understanding the Core Challenge

A proximity service answers questions like "find all restaurants within 2km of my location" or "show me the 10 nearest gas stations." The naive approach of calculating distances to every point in a database becomes prohibitively expensive at scale. With 50 million points of interest, a linear scan performing 50 million distance calculations per query would take seconds, not milliseconds.

The solution requires spatial indexing: data structures that organize locations by proximity, allowing us to eliminate large portions of the search space without examining every point.

![High level architecture of a geospatial proximity service where a mobile app sends nearby requests through the proximity API to a query service backed by a geospatial index, and location updates flow through a location ingest service into a location store that feeds the index.](https://d5osvdbc8um23.cloudfront.net/static-asset/blog_images/system-design-geospatial-proximity/01-high-level-architecture.png)

![Scalable proximity architecture where regional ingress spreads users and drivers across query and ingest fleets, queries read a hot cell cache and geo shards keyed by cell, and ingest publishes to a location update stream that applies changes to the shards.](https://d5osvdbc8um23.cloudfront.net/static-asset/blog_images/system-design-geospatial-proximity/02-scalable-architecture.png)

## Spatial Indexing: Geohash and Quadtrees

![Spatial indexing where a lat long point is passed to a cell encoder that produces either a fixed-grid geohash prefix cell or a density-adaptive quadtree cell, both indexed in a cell to entities map that can expand to adjacent neighbor cells.](https://d5osvdbc8um23.cloudfront.net/static-asset/blog_images/system-design-geospatial-proximity/03-spatial-indexing.png)

### Geohash: Encoding Location as String Prefixes

Geohash converts two-dimensional coordinates into a one-dimensional string through interleaved binary encoding. Crucially, nearby locations share common prefixes, enabling efficient range queries in standard databases.

Let's work through a concrete example. Consider San Francisco's Ferry Building at coordinates (37.7955, -122.3937):

**Step 1: Convert to binary**
- Latitude 37.7955° in range [-90, 90] → binary approximation
- Longitude -122.3937° in range [-180, 180] → binary approximation

**Step 2: Interleave bits**
The algorithm alternates longitude and latitude bits. After interleaving, we group bits into 5-bit chunks and encode using base-32 characters (0-9, b-z excluding a, i, l, o).

The result: `9q8yy` (5-character geohash)

**Precision levels matter significantly:**
- 4 characters = ±20km accuracy
- 6 characters = ±610m accuracy  
- 8 characters = ±19m accuracy
- 10 characters = ±60cm accuracy

For a "nearby coffee shops" query with a 1km radius, 6-character geohashes provide appropriate granularity. The key advantage: all locations within geohash `9q8yy1` are geographically clustered, so a database query `WHERE geohash LIKE '9q8yy1%'` efficiently retrieves candidates.

**The edge case problem:** Geohash cells have sharp boundaries. Two locations 10 meters apart but on opposite sides of a cell boundary share no common prefix. The solution requires checking neighboring cells. For a 6-character geohash, this means querying up to 9 cells (the target cell plus 8 neighbors), which remains far more efficient than scanning the entire dataset.

**Index size reduction:** According to PostGIS benchmarks, geohash indexes consume 70-80% less space than traditional B-tree indexes on separate latitude/longitude columns, because the single string column compresses better and requires fewer index nodes.

### Quadtrees: Hierarchical Space Partitioning

While geohash works well with standard databases, quadtrees provide more flexible spatial partitioning. A quadtree recursively divides two-dimensional space into four quadrants until each leaf node contains fewer than a threshold number of points (commonly 50-100 points).

**Structure:**
- Root node represents the entire map region
- Each internal node has exactly four children (NW, NE, SW, SE quadrants)
- Leaf nodes store actual location points
- Typical max depth: 12-15 levels for city-scale applications

**Query process for radius search:**
1. Start at root node
2. For each node, check if its bounding box intersects the search circle
3. If no intersection, prune entire subtree
4. If intersection, recurse into child nodes
5. At leaf nodes, calculate exact distances to points

**Performance characteristics:**
- Point location: O(log n) average case
- Memory overhead: approximately 40 bytes per node for pointers and bounding box coordinates
- Query efficiency: eliminates 75% of search space at each level on average

The advantage over geohash: quadtrees adapt to data density. In sparse rural areas, nodes remain large. In dense urban areas, deep subdivision creates small cells. Geohash cells maintain fixed size regardless of density.

### R-trees: Optimized for Database Storage

R-trees extend B-trees to spatial data, grouping nearby objects into minimum bounding rectangles (MBRs). PostgreSQL's PostGIS uses R-tree variants (specifically GIST indexes) for spatial queries.

**Key specifications:**
- Node fanout: typically 50-200 entries per node
- Height: usually 3-4 levels for millions of points
- Insertion complexity: O(log n) with periodic rebalancing

For a dataset of 50 million points, an R-tree with fanout 100 requires only log₁₀₀(50,000,000) ≈ 4 levels. A radius query traverses at most 4 levels, examining perhaps 100-400 nodes instead of 50 million points. Benchmarks show R-trees deliver 10-100x faster range queries compared to linear scans for spatial data.

### S2 Geometry: Google's Spherical Approach

Google's S2 library projects the Earth sphere onto a cube, then subdivides each face into a hierarchy of cells using a Hilbert curve. This approach preserves spatial locality better than geohash at cell boundaries.

**Specifications:**
- Cell levels: 0-30 (level 30 represents approximately 1cm² cells)
- Typical operational level: 13-16 for city-scale searches
- Cell ID: 64-bit integer enabling efficient comparison and storage
- Coverage calculation: determines minimum set of cells covering a region

S2's advantage: better handling of large regions and poles, where geohash distortion becomes problematic. The trade-off: increased implementation complexity compared to geohash's string-based simplicity.

## Sharding Location Data

When data exceeds a single server's capacity (typically 50-100 million locations with indexes), sharding distributes locations across multiple database instances.

![Sharding location data where a location write passes through a geo shard router keyed by cell prefix to per-prefix shards, and when a dense city-center cell overloads a shard a worker subdivides the cell and rebalances it to another shard.](https://d5osvdbc8um23.cloudfront.net/static-asset/blog_images/system-design-geospatial-proximity/04-sharding-location.png)

### Geohash-Based Sharding

The most straightforward approach uses geohash prefixes as shard keys. With 2-character prefixes and base-32 encoding, we get 32² = 1,024 possible shards.

**Concrete example with 500 million locations:**

Assume uniform global distribution (unrealistic but illustrative):
- 500,000,000 locations ÷ 1,024 shards = approximately 488,000 locations per shard
- Each shard handles approximately 1/1,024 of query traffic

**Shard assignment:**
```
Location: (37.7955, -122.3937)
Geohash: 9q8yy9b2
Shard key: first 2 characters = "9q"
Shard ID: hash("9q") mod 1024 = 847
Store in: shard_847
```

**The hotspot problem:** Real-world data is not uniform. Urban areas contain far more points of interest than rural areas. A shard covering Manhattan might hold 50 million locations while a shard covering rural Montana holds 50,000. This creates load imbalance.

One common mitigation pattern: consistent hashing with virtual nodes. Each physical shard maps to multiple virtual nodes on the hash ring. High-traffic regions can be assigned more virtual nodes, distributing their load across multiple physical shards. This requires application-level routing logic but provides flexibility to rebalance as data grows.

### Cross-Shard Queries

When a search radius spans multiple geohash cells mapped to different shards, the query coordinator must fan out requests.

**Example scenario:**
- User at (37.7955, -122.3937) searches within 5km
- This radius intersects geohash prefixes: 9q8y, 9q8z, 9q8v, 9q8w
- If these map to different shards, query 4 shards in parallel
- Merge results, sort by distance, return top N

The latency for cross-shard queries equals the slowest shard response (tail latency). With p99 latency of 100ms per shard, a 4-shard fan-out has approximately 100ms p99 (assuming independence), but p99.9 increases significantly. Caching hot regions mitigates this issue.

## Database Strategies and Performance

### PostgreSQL with PostGIS

PostGIS extends PostgreSQL with spatial types and indexes using GIST (Generalized Search Tree), an R-tree variant.

**Setup:**
```sql
CREATE TABLE locations (
    id BIGINT PRIMARY KEY,
    name TEXT,
    geom GEOMETRY(Point, 4326)
);

CREATE INDEX idx_locations_geom ON locations USING GIST(geom);
```

**Query:**
```sql
SELECT id, name, ST_Distance(geom, ST_MakePoint(-122.3937, 37.7955)::geography) as distance
FROM locations
WHERE ST_DWithin(geom, ST_MakePoint(-122.3937, 37.7955)::geography, 5000)
ORDER BY distance
LIMIT 20;
```

**Performance data from PostGIS benchmarks:**
- Index build time: approximately 2-3 minutes per million points
- Query performance: 5-15ms for radius searches under 1km with proper indexing
- Handles 50+ million points efficiently on modern hardware
- Storage overhead: approximately 40% increase with spatial indexes

The GIST index enables the `ST_DWithin` operator to prune the search space efficiently, examining only candidate points within the bounding box before calculating exact distances.

### Redis Geospatial Commands

Redis implements geospatial indexing using sorted sets with geohash encoding internally.

**Setup:**
```
GEOADD locations:sf -122.3937 37.7955 "Ferry Building"
GEOADD locations:sf -122.4194 37.7749 "Golden Gate Park"
```

**Query:**
```
GEORADIUS locations:sf -122.3937 37.7955 5 km WITHDIST COUNT 20
```

**Performance characteristics from Redis documentation:**
- Sub-millisecond response for datasets under 10,000 points
- Under 5ms for 1 million points within 5km radius
- Memory requirement: approximately 70-100 bytes per location including overhead
- Throughput: 100,000+ geospatial queries per second on a single instance

Redis excels for hot data and read-heavy workloads. The trade-off: all data must fit in memory, making it expensive for hundreds of millions of locations. A common pattern is using Redis as a cache layer in front of PostgreSQL, storing only active or frequently queried locations.

### MongoDB Geospatial Indexes

MongoDB supports 2dsphere indexes for spherical geometry queries.

**Setup:**
```javascript
db.locations.createIndex({ location: "2dsphere" })
```

**Query:**
```javascript
db.locations.find({
    location: {
        $near: {
            $geometry: { type: "Point", coordinates: [-122.3937, 37.7955] },
            $maxDistance: 5000
        }
    }
}).limit(20)
```

**Performance:** Typical proximity queries complete in 10-50ms according to MongoDB documentation. For distributed deployments requiring sharding, using geohash prefixes as shard keys enables location-aware data distribution.

## Real-Time Location Updates

Dynamic entities like delivery drivers or ride-share vehicles update their locations every 5-30 seconds. At scale, this creates significant write throughput.

![Real-time location updates where a moving entity sends GPS pings to an update ingest that debounces and coalesces frequent pings, publishing to a location stream that updates cell membership in a live index and the latest position in a cache.](https://d5osvdbc8um23.cloudfront.net/static-asset/blog_images/system-design-geospatial-proximity/05-realtime-updates.png)

**Volume calculation:**
- 100,000 active drivers
- Update every 10 seconds
- Write throughput: 10,000 updates per second

### Write Path Optimization

One common approach: separate hot and cold data. Active entities with frequent updates go to an in-memory store (Redis), while static points of interest remain in the primary database.

**Pattern:**
```
1. Driver updates location
2. Write to Redis (GEOADD) with TTL of 60 seconds
3. Async write to PostgreSQL for historical tracking
4. Queries check Redis first for active entities
5. Fall back to PostgreSQL for static POIs
```

This separation reduces write pressure on the primary database. Redis handles the high-frequency updates, while PostgreSQL maintains the authoritative dataset.

**Update threshold:** To reduce battery drain on mobile devices and server load, updates trigger only when the user moves more than 100-500 meters. This can reduce update frequency by 40-60% in many usage patterns without significantly impacting accuracy.

## Distance Calculation Methods

### Haversine Formula

The Haversine formula calculates great-circle distance between two points on a sphere:

```
a = sin²(Δlat/2) + cos(lat1) × cos(lat2) × sin²(Δlon/2)
c = 2 × atan2(√a, √(1−a))
d = R × c
```

Where R is Earth's radius (6,371 km).

**Characteristics:**
- Accuracy: within 0.5% for distances up to 500km
- Computational cost: 2 sin, 2 cos, 1 sqrt, 1 atan2 operation per calculation
- Use case: standard for applications requiring under 1km precision

For a query returning 100 results, calculating Haversine distance to each candidate location is acceptable. However, for initial filtering across millions of points, faster approximations prove valuable.

### Equirectangular Approximation

For small distances (under 10km) at mid-latitudes, the equirectangular projection provides a fast approximation:

```
x = Δlon × cos(lat_avg)
y = Δlat
d = R × √(x² + y²)
```

**Performance:** This approximation runs 50-100x faster than Haversine because it uses only one cosine operation (which can be pre-computed for the query location) and avoids expensive trigonometric functions.

**Accuracy trade-off:** Error remains under 1% for distances under 10km at mid-latitudes, making it suitable for initial filtering. A typical query pattern:

1. Use equirectangular approximation to filter candidates from spatial index
2. Calculate exact Haversine distance for the top 100-200 candidates
3. Sort by exact distance and return results

This hybrid approach balances performance and accuracy.

## Radius and K-Nearest Neighbor Queries

![Radius and k-nearest queries where a nearby query enters a planner that starts from the center cell of the query location, expands outward through adjacent rings to gather candidate entities from the index, and a distance rank and filter step returns the k nearest.](https://d5osvdbc8um23.cloudfront.net/static-asset/blog_images/system-design-geospatial-proximity/06-knn-queries.png)

### Radius Queries

A radius query finds all locations within a fixed distance. The implementation depends on the spatial index:

**Geohash approach:**
1. Calculate geohash for query point at appropriate precision
2. Query target cell and 8 neighbors
3. Filter candidates by exact distance
4. Sort and return results

**API design considerations from common implementations:**
- Minimum radius: 100m (prevents abuse, ensures meaningful results)
- Maximum radius: 50km (prevents expensive queries scanning large regions)
- Default radius: 1-5km (reasonable for most use cases)
- Result limit: cap at 100-200 results to prevent abuse

### K-Nearest Neighbor (KNN) Queries

KNN queries find the N closest locations regardless of distance. This is more complex than radius queries because we don't know the search radius in advance.

**Implementation approach using spatial indexes:**

For R-tree based systems (like PostGIS):
```sql
SELECT id, name, geom <-> ST_MakePoint(-122.3937, 37.7955)::geometry as distance
FROM locations
ORDER BY distance
LIMIT 10;
```

The `<->` operator uses the spatial index to efficiently find nearest neighbors without scanning all points.

**For geohash-based systems, one possible approach:**
1. Start with small geohash cell (high precision)
2. Query that cell and neighbors
3. If fewer than K results, expand to lower precision (larger cells)
4. Repeat until K results found
5. Calculate exact distances and return top K

This iterative expansion ensures we find K results while minimizing the search space.

## Ranking by Distance and Relevance

Real-world proximity services rarely rank by distance alone. A restaurant 2km away with a 4.8-star rating might rank higher than a 4.0-star restaurant 1km away.

### Multi-Factor Scoring

A common pattern combines multiple signals:

```
score = w1 × distance_score + w2 × rating_score + w3 × popularity_score
```

**Distance scoring:** Convert distance to a 0-1 score, where closer locations score higher. One approach uses exponential decay:

```
distance_score = e^(-distance / decay_factor)
```

With decay_factor = 2000 meters, a location at 0m scores 1.0, at 2000m scores 0.37, and at 4000m scores 0.14.

**Combining signals:** The weights (w1, w2, w3) determine relative importance. For a "nearby restaurants" query, distance might weight 0.5, rating 0.3, and popularity 0.2. These weights are typically tuned through A/B testing and user behavior analysis.

**Implementation consideration:** Multi-factor ranking requires retrieving additional attributes (rating, popularity) for candidate locations. This favors document stores like Elasticsearch or MongoDB where all attributes are co-located, versus joining across tables in relational databases.

### Personalization

Advanced systems incorporate user preferences. A user who frequently visits coffee shops might see cafes ranked higher than restaurants at the same distance. This requires:

1. User preference profile (stored separately)
2. Business category tags
3. Scoring function that boosts preferred categories

The complexity: personalization must happen after spatial filtering but before final ranking, requiring the query coordinator to have access to user profiles.

## Caching Strategies

Caching is essential for achieving sub-100ms latencies at scale. 

### Grid-Based Caching

One common approach divides the map into grid cells (typically 500m-2km squares for urban areas) and caches query results for each cell.

**Pattern:**
```
Cache key: "nearby:9q8yy:radius:1000:limit:20"
Cache value: JSON array of top 20 results
TTL: 5-15 minutes
```

**Effectiveness:** Popular locations can achieve 60-80% cache hit rates, reducing database load by 70%. The TTL balances freshness with hit rate. Shorter TTLs (1-2 minutes) ensure fresher data but lower hit rates. Longer TTLs (15-30 minutes) improve hit rates but risk stale data.

**Memory calculation for San Francisco:**
- City area: approximately 121 km²
- Grid cell size: 1 km²
- Number of cells: 121
- Results per cell: 20 locations × 200 bytes = 4 KB
- Total memory: 121 × 4 KB = 484 KB

Even with multiple radius sizes and categories, total cache memory remains manageable (under 100 MB for a major city).

### Cache Invalidation

When a location updates (new restaurant opens, existing business closes), relevant cache entries must be invalidated. 

One possible approach:
1. Calculate which grid cells contain the location
2. Invalidate cache keys for those cells
3. Next query repopulates cache from database

For static POIs with daily updates, batch invalidation during off-peak hours works well. For dynamic entities (drivers, delivery people), shorter TTLs (30-60 seconds) combined with high tolerance for slightly stale data proves more practical than aggressive invalidation.

## System Architecture and Performance Targets

### Latency Requirements

Based on user experience research, proximity services target:
- p50 (median): under 20ms
- p95: under 50ms
- p99: under 100ms
- p99.9: under 500ms

Meeting these targets requires:
- Spatial indexes (eliminates full table scans)
- Caching layer (handles 60-80% of queries)
- Connection pooling (avoids connection overhead)
- Geographic distribution (reduces network latency)

### Throughput Scaling

**Single optimized server:** 5,000-10,000 queries per second is achievable with proper indexing and hardware.

**With caching layer:** 50,000-100,000 queries per second becomes feasible as most queries hit cache.

**Distributed system:** Properly sharded systems handle 1 million+ queries per second by distributing load across many servers.

### Data Volume Tiers

**Small scale (under 1 million locations):** A single PostgreSQL instance with PostGIS and Redis cache suffices. This handles most city-scale applications.

**Medium scale (1-100 million locations):** Read replicas (3-5 per primary) distribute query load. Redis cache becomes more critical. This tier handles country-scale services.

**Large scale (100 million to 1+ billion locations):** Sharding becomes necessary. Geohash-based sharding with consistent hashing distributes data. Multiple cache layers (application-level, Redis, CDN) reduce database load. This tier handles global services.

## Conclusion

Building a geospatial proximity service that performs well at scale requires careful attention to spatial indexing, database selection, sharding strategy, and caching. The core techniques (geohash for simple range queries, R-trees for complex spatial operations, hybrid distance calculations, grid-based caching) combine to deliver sub-100ms response times even with hundreds of millions of locations.

The key trade-offs:
- Geohash offers simplicity and database compatibility but has edge case issues
- Quadtrees and R-trees provide better spatial partitioning but require specialized storage
- Exact distance calculations (Haversine) ensure accuracy but fast approximations enable efficient filtering
- Strong consistency guarantees correctness but eventual consistency enables better scaling

For most applications, starting with PostgreSQL + PostGIS for persistent storage, Redis for hot data and caching, geohash-based sharding when growth demands it, and a hybrid distance calculation approach (approximation for filtering, exact for final ranking) provides a solid foundation. As scale increases, the system can evolve toward more sophisticated indexing (S2 cells), specialized storage engines, and multi-layer caching while maintaining the core architectural principles.

The next time you search for "coffee near me" and get results in milliseconds, you'll appreciate the spatial indexes, distance calculations, and caching strategies working behind the scenes to make that simple interaction possible.