What Is a Geo-Proximity Service?
A geo-proximity service finds entities (businesses, drivers, users) near a given location. Core operations: store a location, find all entities within radius R of a point, find the K nearest entities. Used by: Yelp (nearby restaurants), Uber (nearby drivers), DoorDash (nearby restaurants), Airbnb (nearby listings).
Data Model
Entity table: entity_id, entity_type, name, latitude, longitude, is_active. Indexes: spatial index on (latitude, longitude) or geohash column. For drivers (frequently updating location): a separate driver_locations table or Redis GEO (in-memory, low latency for reads/writes).
Geohashing
Geohash encodes a (lat, lng) pair into a short string. The encoding divides the world into a grid recursively: split into 4 quadrants, encode each split as a bit. Longer strings = smaller cells = higher precision. At precision 6 (e.g., “9q5c2n”): cell is about 1.2km x 0.6km. At precision 8: 38m x 19m.
For radius search: find the geohash of the center point. Get all neighboring cells (the 8 surrounding geohashes). Query all entities whose geohash starts with any of the 9 prefixes. This gives an approximate radius search with no false negatives but some false positives (cells overlap with the radius — filter those out with Haversine distance).
Store geohash as a VARCHAR with an index. For a 5km radius, use precision 5 cells (~5km x 5km). Adjust precision to match your typical query radius.
Alternative: H3 Hexagonal Grid (Uber)
H3 is Uber open-source hexagonal grid system. Hexagons tile more uniformly than squares (equal distance to all 6 neighbors vs rectangular grids). H3 resolution 9 cells are ~0.1km^2. Each cell has a 64-bit integer ID. Spatial queries: index on H3 cell ID. For radius search, enumerate all cells within the radius using H3 disk/ring functions and query each. H3 is used by Uber for surge pricing zones, demand mapping, and driver dispatch.
Redis GEO Commands
Redis provides native geo commands using a geohash-based sorted set internally:
- GEOADD key lng lat member: add/update a location. O(log N).
- GEODIST key m1 m2 unit: distance between two members. O(log N).
- GEORADIUS key lng lat radius unit [ASC] [COUNT N]: all members within radius, sorted by distance. O(N+log M).
- GEORADIUSBYMEMBER key member radius unit: radius search centered on an existing member.
Best for: frequently updating locations (drivers, delivery couriers). At 1M active drivers updating every 4 seconds: 250K GEOADD/second — requires Redis Cluster. Reads (GEORADIUS for nearest drivers) are O(N) for returned results and extremely fast from RAM.
PostGIS for Persistent Geo Data
PostgreSQL with PostGIS extension provides full geospatial support: ST_DWithin(location, target, meters) uses a spatial index (R-tree via GIST) for fast radius queries. Better than Redis for: persistent data (businesses, venues), complex spatial queries (polygon containment, route intersection), join with other tables. Typical query: SELECT * FROM venues WHERE ST_DWithin(location, ST_MakePoint(lng, lat)::geography, 5000) ORDER BY location ST_MakePoint(lng, lat) LIMIT 20.
System Architecture
For a Yelp-like service: business locations in PostGIS (infrequent writes, complex queries). For a driver-tracking service: driver locations in Redis GEO (frequent writes, simple radius queries). Serve geo queries through a dedicated Location Service — do not expose the database directly. Cache popular searches (nearby restaurants in a geohash cell) in Redis with a 30-second TTL. Use CDN for static location data (venue metadata) once fetched.
Dealing with Edge Cases
Anti-meridian (longitude wrapping at 180/-180): geohash handles this, but custom lat/lng queries need special handling. Poles: high latitudes cause distortion in Mercator projections — use sphere-based distance (Haversine). Precision selection: match geohash precision to your typical query radius. If users commonly search within 1km, use precision 6 (cells are ~1.2km). Too coarse = too many false positives; too fine = might miss entities in neighboring cells.
Asked at: Uber Interview Guide
Asked at: Lyft Interview Guide
Asked at: DoorDash Interview Guide
Asked at: Airbnb Interview Guide
Asked at: Snap Interview Guide