System Design: Location Services — How Uber Matches Drivers in Real-Time

Published data: 25 April 2026

This question appears in
almost every senior eng
interview at Uber, Lyft,
DoorDash, and Google
Maps. Geohash + Redis
GEO is the canonical
answer — know it cold.

The question: Design Uber’s ride-matching system. Find the nearest available driver within 5 km, match in under 500 ms, handle 10 million drivers updating location every 5 seconds, serve globally.

The deceptively hard part isn’t finding nearby drivers — it’s doing it at scale: 2 million location writes per second, global distribution, and sub-500 ms end-to-end latency under bursty demand. This post walks every level of the solution, from a naive SQL query to the geohash + Redis architecture Uber actually uses.

Scale the numbers first:

The write storm — 2 million location writes per second — is the core challenge. Reads are comparatively light. Any solution that can’t absorb those writes at millisecond latency fails immediately.

The first instinct is a SQL query using the Haversine formula:

SELECT id, lat, lng,
  (6371 * acos(
    cos(radians(?)) * cos(radians(lat))
    * cos(radians(lng) - radians(?))
    + sin(radians(?)) * sin(radians(lat))
  )) AS distance
FROM drivers
WHERE available = 1
HAVING distance < 5
ORDER BY distance
LIMIT 10;

This works perfectly at hundreds of drivers. At 10 million active drivers with 2 million writes per second, it’s a disaster: full table scan on every request, HAVING filters applied after reading every row, trigonometric functions on every row, and the write rate alone saturates any relational database.

Instead of computing Haversine distance on every row, first narrow candidates with a cheap bounding box filter:

-- Pre-compute bounding box on application side
-- lat ± delta_lat, lng ± delta_lng (delta ≈ 0.045° per 5 km)
SELECT id, lat, lng
FROM drivers
WHERE available = 1
  AND lat BETWEEN ? AND ?
  AND lng BETWEEN ? AND ?
-- Then apply Haversine only on this small result set

Add a composite spatial index on (lat, lng) — B-tree or R-tree. PostgreSQL’s PostGIS uses exactly this approach. Better, but two problems remain: in dense areas the bounding box still returns thousands of candidates, and 2 million writes per second will saturate any relational write path via WAL overhead and index maintenance. We need something fundamentally different for the location data.

Geohash is elegant because
it turns a 2D spatial
problem into a 1D string
prefix problem — and
databases are very good
at prefix queries.

Geohash encodes any (lat, lng) coordinate as a short string by recursively bisecting the world into a grid. Each additional character doubles precision in both dimensions. The magic: nearby locations share the same prefix (most of the time), so a spatial query becomes a string prefix query: WHERE geohash LIKE 'u4pruy%'.

How encoding works:

1. Start with lat range [−90, 90] and lng range [−180, 180]
2. Interleave bits: even bits bisect longitude, odd bits bisect latitude
3. Group every 5 bits into one base32 character (alphabet: 0123456789bcdefghjkmnpqrstuvwxyz)
4. Longer hash = finer precision

Precision table:

Interactive Geohash Explorer — click any cell on the world grid to zoom into its sub-cells. Click “Place Driver” then click a cell to drop a driver and watch its geohash update as you change the precision slider.

The boundary problem: A driver near a cell border will fall in a different cell than a nearby rider. Solution: always query the 8 neighbouring cells in addition to the rider’s own cell. The grid above highlights these neighbours automatically.

Uber uses S2 geometry
(from Google) in production
— more accurate than
geohash at cell boundaries
— but geohash is perfect
for interviews and gets
you full marks.

Redis is the natural home for location data: in-memory, sub-millisecond reads/writes, built-in GEO data structure. Each geohash cell becomes a Redis sorted set key holding driver IDs. Redis GEO commands internally encode (lat, lng) as geohash and store in a sorted set.

# Driver updates location — atomic: remove old, add new
ZREM drivers:u4prue driver:42          # remove from old geohash
GEOADD drivers:city:london -0.1276 51.5074 driver:42

# Rider requests ride — query own cell + 8 neighbours
GEORADIUS drivers:city:london -0.1276 51.5074 5 km
  WITHCOORD WITHDIST ASC COUNT 20

# Check distance between two points
GEODIST drivers:city:london driver:42 driver:99 km

# Get geohash string for a driver (precision 6)
GEOHASH drivers:city:london driver:42
# → "gcpvhep"

# For the write storm: pipeline multiple updates
PIPELINE
  GEOADD drivers:city:london -0.128 51.507 driver:42
  GEOADD drivers:city:london -0.135 51.512 driver:99
  GEOADD drivers:city:london -0.121 51.503 driver:7
EXEC

Driver update flow:

1. Driver app detects GPS change > 50 m → sends update to Location Service via WebSocket
2. Location Service calls GEOADD city:geohash_key lng lat driver_id in Redis
3. Old geohash entry is automatically overwritten (sorted set member is unique by name)

Rider lookup flow:

1. Rider taps “Request” → Matching Service receives (lat, lng, radius=5km)
2. GEORADIUS returns up to 20 nearest available drivers with distances, sorted by proximity
3. Matching Service ranks by ETA (calls Maps API for road distance on top 5 candidates)
4. Sends offer to best driver via WebSocket push

Geohash divides the world into uniform rectangular cells. Quad trees divide space adaptively: each node splits into 4 quadrants recursively until each leaf contains ≤ K points (e.g. K = 100). This gives dense coverage in cities (deep tree) and sparse coverage in rural areas (shallow tree), with constant lookup time proportional to tree depth rather than area.

Interactive Quad Tree Builder — click to place driver dots, then click “Build Quad Tree” to watch it subdivide. Capacity K controls when a cell splits.

Quad tree vs geohash:

Click any component in the diagram below to see its role in detail.

2 million location writes per second is non-trivial. Four optimizations, ordered by impact:

Optimization 1 — Client-side movement filter (saves ~60%)

val MIN_DISTANCE_METERS = 50.0
var lastSentLocation: Location? = null

fun onGpsUpdate(newLoc: Location) {
  if (lastSentLocation == null ||
      newLoc.distanceTo(lastSentLocation!!) > MIN_DISTANCE_METERS) {
    sendLocationUpdate(newLoc)   // only send if moved > 50 m
    lastSentLocation = newLoc
  }
  // otherwise discard silently — cheapest server call is none at all
}

The “50 metres moved” filter
on the driver app saves
~60% of location updates
— the cheapest optimisation
is the one that prevents
the write from happening
at all.

Optimization 2 — Redis pipelining (batches multiple writes in one round-trip)

def flush_location_batch(updates):
  pipe = redis.pipeline(transaction=False)
  for driver_id, lat, lng in updates:
    city_key = "drivers:" + get_city(lat, lng)
    pipe.geoadd(city_key, [lng, lat, driver_id])
  pipe.execute()  # one network round-trip for all updates

Optimization 3 — Shard Redis by city / geohash prefix

# Redis Cluster: consistent hashing across shards
shard-0: drivers:london, drivers:paris, drivers:berlin
shard-1: drivers:nyc,    drivers:boston,  drivers:dc
shard-2: drivers:sf,     drivers:la,      drivers:seattle
shard-3: drivers:tokyo,  drivers:osaka,   drivers:seoul
# → each shard handles ~500k writes/sec — well within Redis limits

Optimization 4 — Dead zone suppression

Drivers in slow traffic or at stop lights barely move. Track the last-sent geohash and skip writes entirely if the driver is still in the same precision-6 cell (~1.2 km × 0.6 km). For Uber this suppresses an additional 20–30% of writes during rush-hour gridlock.

Surge pricing is a direct consequence of geospatial aggregation: divide the city into geohash zones, count active riders vs available drivers per zone in real time, and compute a multiplier when supply is short.

def compute_surge(geohash_prefix: str) -> float:
  zone_key = "zone:" + geohash_prefix
  riders   = redis.get(zone_key + ":riders")    # active ride requests
  drivers  = redis.zcard("drivers:" + geohash_prefix)  # available drivers

  if drivers == 0: return 3.0     # no drivers → max surge
  ratio = riders / drivers

  if   ratio < 1.0: return 1.0    # normal
  elif ratio < 2.0: return 1.5    # mild surge
  elif ratio < 3.5: return 2.0    # surge
  else:             return 3.0    # high surge

Live Surge Map — click “Simulate Rush Hour” to see demand spike in city centre. Each zone shows rider/driver ratio and surge multiplier.

Watch the complete matching pipeline in action: five drivers move around the city in real time. Click “Request Ride” then click anywhere on the grid to drop a ride request — the system highlights the geohash cells, finds the nearest driver, and animates the match.

Hit these points in order when answering in an interview:

1. Quantify the write storm first — 10M drivers × 1/5s = 2M writes/sec. This disqualifies SQL immediately.
2. Explain why geohash — turns 2D spatial into 1D string prefix; databases love prefix queries.
3. Name the boundary problem — and explain the 9-cell (own + 8 neighbours) solution.
4. Redis GEO — GEOADD, GEORADIUS, GEOHASH. In-memory, sub-ms, ~500 MB for 10M drivers.
5. Write optimisations in order — client-side 50 m filter → pipelining → shard by city.
6. ETA vs distance — sort by straight-line first, call Maps API only on top 5 candidates.
7. Mention S2 — Uber uses Google’s S2 library in production; geohash is interview-correct but S2 handles polar distortion better.

Next in the series: #12 — Design a Distributed Message Queue — Kafka internals, partitioning, consumer groups, and at-least-once vs exactly-once delivery.