Design a Geolocation Service: Proximity Search
Proximity search answers a deceptively simple question: 'What's near me?' When you open a ride-sharing app, it finds drivers within 5 minutes. When you search for restaurants, it shows options within...
Key Insights
- Brute-force proximity search using the Haversine formula is O(n) per query—at scale, you need spatial indexing structures like geohashes, quadtrees, or S2 cells to reduce search space by orders of magnitude.
- Redis with its native geospatial commands (GEOADD, GEORADIUS) provides sub-millisecond proximity queries for millions of locations, making it an excellent choice for real-time applications like ride-sharing and delivery.
- Geographic sharding by region handles horizontal scale, but you must account for edge cases at shard boundaries where nearby points live in different partitions.
Introduction & Problem Statement
Proximity search answers a deceptively simple question: “What’s near me?” When you open a ride-sharing app, it finds drivers within 5 minutes. When you search for restaurants, it shows options within 2 miles. When you check store availability, it locates the nearest pickup point.
The technical challenge lies in the constraints. You’re searching through millions of constantly-moving points. Users expect sub-100ms responses. Accuracy matters—showing a restaurant 3 miles away as “nearby” destroys trust. And the data is write-heavy: drivers update their location every few seconds.
This article walks through designing a production-ready geolocation service, from understanding why naive approaches fail to implementing scalable solutions with real code.
Naive Approach & Why It Fails
The intuitive solution is straightforward: store every location with latitude/longitude coordinates, then calculate the distance from the query point to every stored point. Filter to those within your radius.
The Haversine formula calculates great-circle distance between two points on a sphere:
import math
def haversine_distance(lat1: float, lon1: float, lat2: float, lon2: float) -> float:
"""
Calculate distance between two points on Earth in kilometers.
"""
R = 6371 # Earth's radius in kilometers
lat1_rad = math.radians(lat1)
lat2_rad = math.radians(lat2)
delta_lat = math.radians(lat2 - lat1)
delta_lon = math.radians(lon2 - lon1)
a = (math.sin(delta_lat / 2) ** 2 +
math.cos(lat1_rad) * math.cos(lat2_rad) *
math.sin(delta_lon / 2) ** 2)
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
return R * c
def naive_proximity_search(query_lat: float, query_lon: float,
radius_km: float, locations: list) -> list:
"""
O(n) brute force search - don't do this at scale.
"""
results = []
for loc in locations:
distance = haversine_distance(query_lat, query_lon,
loc['lat'], loc['lon'])
if distance <= radius_km:
results.append({**loc, 'distance': distance})
return sorted(results, key=lambda x: x['distance'])
This works fine with 1,000 locations. With 10 million drivers updating positions every 4 seconds, you’re running 2.5 million Haversine calculations per query. At 1,000 queries per second, that’s 2.5 billion calculations per second. Your service collapses.
The fundamental problem: we’re examining every point when we only care about a tiny geographic subset. We need to eliminate candidates before calculating distances.
Geospatial Indexing Strategies
Spatial indexing reduces search space by partitioning geographic data into hierarchical structures. The key insight: if a region is entirely outside your search radius, you can skip every point in that region.
Geohashing encodes latitude/longitude into a string where prefixes represent progressively smaller rectangular regions. Points sharing a prefix are geographically close. A 6-character geohash covers roughly 1.2km × 0.6km.
Quadtrees recursively divide 2D space into four quadrants. Dense areas get subdivided further; sparse areas remain coarse. Query time is O(log n) for well-balanced trees.
R-trees group nearby objects into minimum bounding rectangles, creating a hierarchy. They’re optimized for range queries and used by PostGIS internally.
S2 cells (Google’s library) project the Earth onto a cube, then use a Hilbert curve to map 2D regions to 1D intervals. This preserves locality better than geohashing at region boundaries.
Here’s a practical geohash implementation with neighbor lookup—critical because your search radius often spans multiple cells:
import string
BASE32 = '0123456789bcdefghjkmnpqrstuvwxyz'
def encode_geohash(lat: float, lon: float, precision: int = 6) -> str:
"""
Encode lat/lon to geohash string.
"""
lat_range = (-90.0, 90.0)
lon_range = (-180.0, 180.0)
geohash = []
bits = 0
bit_count = 0
is_lon = True
while len(geohash) < precision:
if is_lon:
mid = (lon_range[0] + lon_range[1]) / 2
if lon >= mid:
bits = (bits << 1) | 1
lon_range = (mid, lon_range[1])
else:
bits = bits << 1
lon_range = (lon_range[0], mid)
else:
mid = (lat_range[0] + lat_range[1]) / 2
if lat >= mid:
bits = (bits << 1) | 1
lat_range = (mid, lat_range[1])
else:
bits = bits << 1
lat_range = (lat_range[0], mid)
is_lon = not is_lon
bit_count += 1
if bit_count == 5:
geohash.append(BASE32[bits])
bits = 0
bit_count = 0
return ''.join(geohash)
def get_neighbors(geohash: str) -> list:
"""
Return the 8 neighboring geohash cells.
Critical for searches near cell boundaries.
"""
# Simplified: in production, use a library like python-geohash
# This demonstrates the concept
directions = [
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)
]
# Decode center, offset, re-encode for each direction
# Implementation omitted for brevity
pass
def geohash_proximity_search(query_lat: float, query_lon: float,
radius_km: float, precision: int = 6) -> list:
"""
Get geohash cells that cover the search radius.
"""
center_hash = encode_geohash(query_lat, query_lon, precision)
# Include center cell and all neighbors
cells_to_search = [center_hash] + get_neighbors(center_hash)
return cells_to_search
The precision level determines cell size. For a 5km search radius, precision 5 (~5km cells) captures candidates efficiently. You still run Haversine on results, but against hundreds of points instead of millions.
System Architecture Design
A production geolocation service separates concerns across specialized components:
┌─────────────┐ ┌─────────────┐ ┌─────────────────┐
│ API Gateway │────▶│ Location │────▶│ Geospatial DB │
│ (Rate Limit)│ │ Service │ │ (Redis/PostGIS)│
└─────────────┘ └─────────────┘ └─────────────────┘
│
▼
┌─────────────┐
│ Cache │
│ (Hot Zones) │
└─────────────┘
Write path (location updates): Client sends GPS coordinates → API gateway validates and rate-limits → Location service updates geospatial index → Optionally publishes to event stream for real-time features.
Read path (proximity queries): Client requests nearby entities → Check cache for hot zones → Query geospatial index → Post-filter and rank results → Return response.
Redis excels here with native geospatial commands. It stores points in a sorted set using geohash-based scoring, enabling O(log n + m) proximity queries where m is result count:
import redis
class GeolocationService:
def __init__(self, redis_url: str = "redis://localhost:6379"):
self.redis = redis.from_url(redis_url)
self.key = "drivers:locations"
def update_location(self, driver_id: str, lat: float, lon: float) -> None:
"""
Store or update a driver's location.
GEOADD is O(log n) per element.
"""
self.redis.geoadd(self.key, (lon, lat, driver_id))
def find_nearby(self, lat: float, lon: float,
radius_km: float, limit: int = 20) -> list:
"""
Find drivers within radius, sorted by distance.
GEORADIUS is O(log n + m) where m is results count.
"""
results = self.redis.georadius(
self.key,
longitude=lon,
latitude=lat,
radius=radius_km,
unit='km',
withdist=True,
withcoord=True,
count=limit,
sort='ASC'
)
return [
{
'driver_id': r[0].decode(),
'distance_km': r[1],
'location': {'lon': r[2][0], 'lat': r[2][1]}
}
for r in results
]
def remove_driver(self, driver_id: str) -> None:
"""
Remove driver when they go offline.
"""
self.redis.zrem(self.key, driver_id)
# Usage
service = GeolocationService()
service.update_location("driver_123", 40.7128, -74.0060)
nearby = service.find_nearby(40.7580, -73.9855, radius_km=5)
For more complex queries (polygon searches, spatial joins), PostGIS provides SQL-based geospatial operations with R-tree indexing. Elasticsearch offers full-text search combined with geo queries. Choose based on your query patterns.
Handling Scale & Performance
At massive scale, a single Redis instance won’t suffice. Geographic sharding distributes load by region:
import hashlib
from typing import List, Tuple
class GeoShardRouter:
"""
Route requests to appropriate shard based on geography.
Uses consistent hashing for even distribution.
"""
def __init__(self, shards: List[str], virtual_nodes: int = 150):
self.shards = shards
self.ring = {}
# Create virtual nodes for better distribution
for shard in shards:
for i in range(virtual_nodes):
key = f"{shard}:{i}"
hash_val = self._hash(key)
self.ring[hash_val] = shard
self.sorted_keys = sorted(self.ring.keys())
def _hash(self, key: str) -> int:
return int(hashlib.md5(key.encode()).hexdigest(), 16)
def get_shard(self, lat: float, lon: float) -> str:
"""
Determine shard for a geographic point.
Uses geohash prefix for locality.
"""
# Use coarse geohash (precision 3 ~= 150km cells)
geo_key = encode_geohash(lat, lon, precision=3)
hash_val = self._hash(geo_key)
# Find next node on ring
for key in self.sorted_keys:
if key >= hash_val:
return self.ring[key]
return self.ring[self.sorted_keys[0]]
def get_shards_for_query(self, lat: float, lon: float,
radius_km: float) -> List[str]:
"""
For large radii, query may span multiple shards.
Returns all shards that could contain results.
"""
# Get geohash cells covering the search area
cells = geohash_proximity_search(lat, lon, radius_km, precision=3)
shards = set()
for cell in cells:
# Decode cell center and route
# In production, decode geohash to lat/lon
shard = self.get_shard(lat, lon) # Simplified
shards.add(shard)
return list(shards)
Additional scaling tactics:
- Cache hot zones: Airport pickup areas, downtown cores, and stadium surroundings see concentrated queries. Cache these results with short TTLs.
- Read replicas: Proximity queries vastly outnumber location updates. Deploy read replicas for query distribution.
- Rate limit updates: Drivers don’t need to update every second. Batch updates or enforce minimum intervals (4-10 seconds) to reduce write load.
Real-World Considerations
Edge cases destroy naive implementations. The antimeridian (180°/-180° longitude) breaks distance calculations that assume continuous coordinate space. Points near the poles cause geohash cells to become extremely narrow. Dense urban areas may return thousands of results requiring pagination.
GPS accuracy varies wildly. Urban canyons cause multipath interference. Indoor locations drift significantly. Your service should handle location uncertainty—perhaps expanding search radius or weighting by reported accuracy.
Privacy demands attention. Location data is sensitive. Implement data retention policies (delete locations after 30 days). Allow users to pause tracking. Consider differential privacy for aggregate analytics. Never expose exact coordinates to other users—show approximate distance instead.
Monitor aggressively. Track p99 query latency by region. Alert on sudden increases in result set sizes (possible data corruption). Monitor cache hit rates for hot zones. Log slow queries for optimization.
Conclusion & Further Reading
Designing a geolocation service requires understanding the fundamental trade-off: preprocessing location data into spatial indexes enables fast queries at the cost of update complexity. For most applications, Redis with geospatial commands provides the right balance of simplicity and performance. At extreme scale, geographic sharding with careful boundary handling becomes necessary.
For production implementations, study Uber’s H3 hexagonal hierarchical spatial index and Google’s S2 geometry library. Both solve edge cases that simpler approaches miss. For extensions, consider real-time tracking with WebSockets, geofencing for entry/exit notifications, and historical trajectory analysis.
Start simple with Redis GEORADIUS. Add complexity only when your scale demands it.