Engineering Atlas › System Design Interviews

Storing and querying locations

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

When the pattern shows up in interviews

"Design Uber/Lyft", "Design Yelp or Google Places", "Design Tinder" (people near me), "Design DoorDash tracking", "Find My Friends", and geofencing ("notify me when I arrive"). Interviewers want to hear how you avoid scanning all points, how you handle density differences between a city centre and the countryside, how often locations update, and what happens at cell boundaries.

Geohash: cells as string prefixes

Geohash interleaves bits from repeatedly halving longitude and latitude ranges, then encodes every 5 bits as a base-32 character. Each extra character shrinks the cell; at 6 characters a cell is roughly 1.2 km by 0.6 km (Wikipedia). Points that share a prefix are in the same cell, so any store that supports prefix or range scans (a B-tree, a sorted set, a wide-column store) becomes a spatial index. The weakness is the seam: two points a metre apart on opposite sides of a cell boundary can have completely different prefixes, so queries always include the 8 neighbouring cells.

Quadtrees and R-trees: adaptive structures

A quadtree starts with the whole map as one node and splits a node into four children when it holds more than some threshold of points. Dense downtown areas end up with tiny cells, deserts with huge ones, so each leaf holds a similar number of points. It is usually built in memory and rebuilt or updated incrementally. An R-tree groups nearby objects into bounding rectangles in a balanced tree (Guttman, SIGMOD 1984) and is what PostGIS uses (through a GiST index) to answer ST_DWithin queries. Both shine for static or slowly changing data.

S2 and H3: global cell systems

Google's S2 projects the sphere onto a cube and orders cells along a Hilbert curve, which preserves locality better than geohash's Z-order. A 64-bit cell ID holds 3 face bits, then 2 bits per level down to 30 levels, where leaf cells are about 1 cm across (S2 docs); a "region coverer" returns a small set of cells covering any circle or polygon. Uber's H3 tiles the globe with hexagons at 16 resolutions, from about 1.4 km edges at resolution 7 to 200 m at resolution 9; every neighbour of a hexagon is the same distance away, which makes it convenient for "ring of cells around me" queries and for aggregating demand and supply into cells for pricing. A sphere cannot be tiled with hexagons alone, so each resolution also has exactly 12 pentagons, with five neighbours, that ring code must tolerate (H3 docs). Older tutorials use the version 3 API: geoToH3 is now latLngToCell and kRing is now gridDisk (H3 docs).

Moving objects

Drivers send a location every few seconds. Writing each update into a disk-based spatial index would churn it, so keep a separate in-memory structure: a map from cell ID to the set of driver IDs in that cell, plus a map from driver to its last position and cell. On each update, if the cell changed, move the driver between sets. Entries carry a last-seen time and drop out when stale. Redis's GEOADD and GEOSEARCH implement exactly this on top of a sorted set; GEORADIUS, still common in older answers, has been deprecated since Redis 6.2 (Redis docs). Partition by city or by coarse cell so one shard handles one region.

Tracking and fan-out

When a trip starts, the rider subscribes to the driver's updates. The driver's app sends positions over a persistent connection to a gateway; the location service publishes them on a channel keyed by trip ID; the rider's gateway pushes them down a WebSocket. Clients interpolate between updates to animate smoothly, so a 4-second update interval looks continuous.

Down the stack

Layer 1The contract

A radius query returns every indexed object whose last reported position is within the radius, sorted by distance, as of a staleness bound equal to the update interval plus pipeline delay. Positions older than a TTL are excluded. A nearest-k query returns the k closest, which may require widening the search ring when nearby cells are empty. Tracking delivers updates in order per object with best-effort latency; a dropped update is superseded by the next, so it needs no retry.

Layer 2The mechanism

Geohash encoding alternates bits: bit 0 halves longitude, bit 1 halves latitude, and so on; 5 bits map to one character of 0123456789bcdefghjkmnpqrstuvwxyz. Redis stores members of a geo set in a sorted set whose score is a 52-bit interleaved geohash integer, which a double holds exactly; because it uses the Web Mercator bounds, latitudes beyond about 85.05 degrees are rejected (Redis docs). GEOSEARCH ... BYRADIUS estimates the geohash precision whose cell size fits the radius, computes the centre cell and its 8 neighbours, issues a score range lookup for each in the sorted set's skip list, then computes exact distance for each candidate and discards those outside the circle. PostGIS builds a GiST index of bounding boxes; ST_DWithin(geog, point, 2000) expands the point into a box for the index scan, then rechecks exact distance on the candidates, measured in metres on the spheroid by default (PostGIS docs). A quadtree node holds either up to N points or four children, and a query descends only into children whose bounds intersect the search circle.

Layer 3The machine

A location update is small: an ID, two float64 coordinates (16 bytes), a timestamp and maybe heading and speed, under 100 bytes on the wire after framing. A million active drivers reporting every 4 seconds is 250,000 updates per second, which is a lot of requests but only tens of MB per second of payload and around 100 MB of state in memory. The cost is in connections and syscalls, not bytes, so gateways batch writes and keep long-lived TCP or WebSocket connections, each costing kilobytes of kernel and user-space buffers. Exact distance uses the haversine formula, a handful of trigonometric calls costing on the order of tens to a hundred nanoseconds, so filtering a few thousand candidates is cheap; scanning millions is not. Haversine assumes a spherical Earth, so it can be off by up to 0.5%, fine for "drivers near me" but not for surveying (the same Redis page). Phone GPS is typically accurate to about 4.9 m under open sky and worse near buildings, bridges and trees (GPS.gov), so precision beyond that is noise; snapping to roads happens server-side.

Why it's built this way

  1. Databases index well in one dimension, so 2D positions are mapped onto a 1D curve (geohash, S2) or a tree of rectangles.
  2. Curves have seams, so queries cover neighbouring cells and then filter by exact distance.
  3. Density varies by orders of magnitude between places, so adaptive structures or multiple resolutions keep cells balanced.
  4. Moving objects write constantly and only the latest position matters, so they live in memory with TTLs rather than in a durable spatial index.
  5. One region's traffic is independent of another's, so shard by geography and keep fan-out local to the trip.

Diagram

flowchart LR
    D["Driver app (every 4 s)"] --> GW["Connection gateway"]
    GW --> LS["Location service (city shard)"]
    LS --> GRID[("In-memory grid: cell -> driver IDs")]
    LS --> PS["Pub/sub channel per trip"]
    PS --> RG["Rider gateway"]
    RG --> R["Rider app (WebSocket)"]
    M["Matching service"] -->|"cells covering 2 km"| GRID
    GRID -->|"candidates"| M
    M --> F["Exact distance filter + ETA ranking"]

Worked example

A ride-hailing company serves one large metro with up to 60,000 online drivers at peak. Each sends a position every 4 seconds: 15,000 updates per second for the city. The location service keeps a map of geohash-6 cells (about 1.2 by 0.6 km) to driver sets, and a driver map of last position, cell and timestamp. State is about 60,000 times 100 bytes, roughly 6 MB, so one process could hold it; the team runs three replicas fed from the same update stream for availability.

Riders request about 400 trips per second at peak. For each, matching looks up the rider's cell and its 8 neighbours, which covers at least 0.6 km in every direction and typically returns 50 to 200 drivers downtown. It drops entries older than 15 seconds, computes haversine distance, keeps the closest 20, and calls the routing service for road ETAs on those only. If fewer than 5 candidates appear, it widens to the next ring of cells. Suburbs work the same way with more rings, which is why some designs choose a coarser precision or an adaptive quadtree in sparse areas.

Once matched, the driver's updates are also published to trip:{id} and pushed to the rider's WebSocket.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Geohash in a KV or sorted setWorks on any ordered store, simpleSeams, uneven cell sizes by latitudeMost interview answers, Redis GEO
Quadtree (in memory)Adapts to densityRebuild cost, harder to shardStatic points with very uneven density
PostGIS R-tree (GiST)Exact queries, polygons, SQL joinsSingle-node writes, heavy for high update ratesPlaces, geofences, admin queries
S2 cellsHilbert locality, good region coveringMore complex libraryLarge-scale geo systems, polygons
H3 hexagonsUniform neighbours, great for aggregationHexagons do not nest perfectlySupply and demand heatmaps, pricing

Pitfalls in production

Leadership lens

Check yourself

  1. Why can't a composite B-tree index on (lat, lon) answer a radius query efficiently?

    Show answer

    It orders by latitude first, so a latitude band scan returns every longitude in that band worldwide, and the longitude condition filters afterwards.

  2. Why does a geohash radius query look at neighbouring cells?

    Show answer

    Points close together can sit on opposite sides of a cell boundary and share no prefix, so the centre cell alone misses them.

  3. Why are moving drivers kept in memory instead of in PostGIS?

    Show answer

    Each driver writes every few seconds and only the latest position matters, so a durable spatial index would churn while an in-memory cell map handles the rate cheaply.

  4. What makes H3 hexagons attractive for pricing heatmaps?

    Show answer

    All six neighbours are equidistant from the centre, so rings and smoothing behave uniformly, unlike squares with diagonal neighbours.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →