- Book: System Design Pocket Guide: Interviews — 15 Real System Designs, Step by Step
- My project: Hermes IDE | GitHub — an IDE for developers who ship with Claude Code and other AI coding tools
- Me: xgabriel.com | GitHub
A driver in San Francisco taps "online." Their phone starts emitting GPS updates every few seconds. As a back-of-envelope estimate: a few hundred thousand active drivers on a Saturday night, one update every ~4 seconds, lands you on the order of a hundred thousand location updates per second. The proximity query a rider triggers when they tap the request button needs to come back well inside a sub-200ms latency budget.
This is the part of the Uber design question interviewers actually care about, and the part candidates rush past on the way to "we use Kafka." The interesting work is the proximity index. Given a rider at a lat/lng, return the 20 nearest available drivers in a low-millisecond query, while the underlying data is overwritten many times per minute.
The original Uber answer was geohash. The current answer, since the open-sourcing of H3 in 2018, is hexagonal tiling. The reason H3 won the rewrite generalizes to any "find nearest" workload: food delivery, scooter rental, last-mile logistics, even cellular handoff.
The pieces of a dispatch system
Six components do most of the work.
- Driver location firehose. Phones POST GPS updates every 3–5 seconds. A gateway authenticates, validates, publishes to Kafka partitioned by region.
- Hot location store. A consumer reads the stream and updates a low-latency store keyed by driver ID. The source of truth for "where is driver 7124 right now."
- Proximity index. A second view organized by spatial cell. Given a lat/lng, return the driver IDs in the surrounding cells.
- Dispatch service. Queries the proximity index, scores candidates (ETA, surge, acceptance rate, vehicle type), and offers the ride.
- Match orchestrator. Holds the request open while the offered driver decides, falls back to the next candidate on rejection.
- Surge engine. Computes per-cell multipliers from supply/demand ratios in the same H3 cells the proximity index uses.
The proximity index makes or breaks the latency budget, and the choice of spatial index is the most consequential decision in the design.
Geohash: the obvious answer that almost worked
Geohash divides the world into a recursive grid of rectangles. Each cell gets a string identifier; 9q8yyk is roughly 150m × 150m in San Francisco. Cells with a common prefix are spatially close; truncating the prefix gives the larger enclosing cell.
It's simple. Compute geohash on driver location, store driver IDs in a Redis set keyed by the hash, and proximity becomes "give me drivers in this geohash and the 8 surrounding ones."
Three problems show up in production.
Cell shapes distort with latitude. A 150m × 150m cell at the equator becomes roughly 150m × 77m in Stockholm (cos(59°) ≈ 0.515). The "8 neighbors" trick gives a different physical search radius depending on where on the planet the rider is.
Neighbor distances aren't uniform. A square cell has two neighbor distances: edge-adjacent (side length) and corner-adjacent (side × √2). Some of the 8 neighbors are 41% farther than others. ML models trained on cell features pick up directional bias.
Boundary discontinuities are ugly. A driver one meter inside a cell and one meter on the other side of the boundary share no common prefix beyond the parent. To find both as "nearby," you query the parent, which covers an area 32× the size you wanted.
Each is fixable in isolation. Together, they produce a dispatch path full of special cases and a surge model that gives different multipliers to riders standing 50 feet apart.
H3: hexagons, on purpose
H3 tiles the world with hexagons at 16 resolutions, from continents down to roughly 1 square meter. Every hexagonal cell has the same property: all six neighbors are equidistant from the center. One neighbor distance, not two.
That single fact compounds through the rest of the system.
Proximity searches expand uniformly. The gridDisk(cell, k) function returns every cell within k rings, a roughly circular search area regardless of direction. Geohash's "9 surrounding cells" is rectangular and biased; gridDisk is symmetric.
Cell areas are nearly equal across the globe. Per the H3 area tables on h3geo.org, variance at resolution 9 is on the order of 1–2%, where geohash cells vary by 50%+ between equator and high latitude.
ML features and surge multipliers stop carrying directional bias. A heatmap on H3 cells reflects actual demand density. A heatmap on geohash cells has a north-south stretch baked in.
The catch: hexagons don't tile recursively. A resolution-9 hex doesn't contain an integer number of resolution-10 hexes. H3 handles this with pentagon-based apertures, but some operations need approximate algorithms. For dispatch this barely matters; you're asking "what's near point P," not "what's exactly inside cell X."
A 50-line nearest-driver lookup
This is the proximity index in its smallest honest form. H3 indexes the location to a cell ID. Redis stores driver IDs in a hash keyed by cell. Lookup expands rings around the rider's cell until enough candidates accumulate.
import math
import time
import h3 # requires h3 >= 4.0
import redis
r = redis.Redis(decode_responses=True)
RES = 9 # ~174m hex edge; one block-ish in dense urban
TTL_S = 30
def haversine_m(lat1: float, lng1: float, lat2: float, lng2: float) -> float:
R = 6_371_000.0
p1, p2 = math.radians(lat1), math.radians(lat2)
dp = math.radians(lat2 - lat1)
dl = math.radians(lng2 - lng1)
a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
return 2 * R * math.asin(math.sqrt(a))
def update_driver(driver_id: str, lat: float, lng: float) -> None:
cell = h3.latlng_to_cell(lat, lng, RES)
# Read prev cell synchronously; the rest is pipelined.
prev = r.get(f"driver:cell:{driver_id}")
pipe = r.pipeline()
if prev and prev != cell:
pipe.srem(f"cell:drivers:{prev}", driver_id)
pipe.sadd(f"cell:drivers:{cell}", driver_id)
pipe.expire(f"cell:drivers:{cell}", TTL_S)
pipe.set(f"driver:cell:{driver_id}", cell, ex=TTL_S)
pipe.hset(
f"driver:loc:{driver_id}",
mapping={"lat": lat, "lng": lng, "ts": time.time()},
)
pipe.expire(f"driver:loc:{driver_id}", TTL_S)
pipe.execute()
def nearest_drivers(
lat: float, lng: float, want: int = 20, max_rings: int = 5
) -> list[str]:
center = h3.latlng_to_cell(lat, lng, RES)
found: list[str] = []
for k in range(max_rings + 1):
cells = h3.grid_disk(center, k)
if k > 0:
# Only the new outer ring; inner cells were checked.
inner = set(h3.grid_disk(center, k - 1))
cells = [c for c in cells if c not in inner]
for cell in cells:
ids = r.smembers(f"cell:drivers:{cell}")
found.extend(ids)
if len(found) >= want:
break
# Score by exact distance for the final ranking.
scored = []
for did in found:
loc = r.hgetall(f"driver:loc:{did}")
if not loc:
continue
d = haversine_m(lat, lng, float(loc["lat"]), float(loc["lng"]))
scored.append((d, did))
scored.sort()
return [did for _, did in scored[:want]]
Two design choices to call out. The driver's cell membership is tracked with a reverse pointer (driver:cell:{id}) so updates can clean up the previous cell. Without that, drivers leak into stale cells and corrupt the index. Every key in the sketch carries a 30-second TTL, refreshed on each update, so a driver who goes silent expires from the cell set, the reverse pointer, and the location hash automatically rather than requiring an explicit "offline" event the phone might never send.
For the dispatch service, the proximity query feeds into a scoring function that adds ETA (using a routing service), surge, vehicle type filters, and driver acceptance probability. The H3-based candidate set is the input, not the answer.
Why hex tiles win the surge calculation
Surge pricing is the second place H3 pays off. Surge is a per-cell ratio of open requests to available drivers. Compute it on geohash and multipliers stretch with latitude. A Stockholm geohash cell is roughly twice as tall (north-south) as wide (east-west), so the supply-demand ratio is averaged over a non-circular region. Riders standing along the cell's east-west axis see surge averaged over a ~75m span; riders along the north-south axis see surge averaged over ~150m. They pay different prices for indistinguishable trips.
Compute on H3 and the cell is roughly circular. Surge averages over an equal-radius neighborhood in every direction. Prices change as you walk a block, not as you walk a block in a particular direction.
Uber's H3 announcement frames this as "uniform aggregation": the surge engine, the demand-forecasting model, and the dispatch index share one spatial primitive with uniform geometric properties everywhere.
What an interviewer wants you to say
If this comes up in a system-design interview, three points carry most of the weight.
- Decouple the firehose from the proximity index. The location stream goes to Kafka for durability and downstream analytics. A consumer service updates the hot index. Don't let the dispatch path query the firehose directly.
- The proximity index is a separate data model from the driver-state store. One is keyed by driver ID (state lookups). The other is keyed by spatial cell (proximity queries). Both are written by the same consumer, ideally atomically, and both have short TTLs so dead drivers fall out automatically.
-
Pick H3 over geohash with reasoning. Uniform neighbor distances. Near-equal cell areas globally.
gridDiskgives circular search regions. Surge and ML features inherit those properties. Don't just say "Uber uses it," say why the geometry matters.
The last point separates a candidate who memorized the answer from one who can defend it. Hexagons are the unique tiling with a single neighbor distance, and every dispatch primitive that depends on neighbor distance gets simpler because of it.
Where this generalizes
Any "find the closest N entities in space" workload reuses this architecture. Food delivery swaps drivers for couriers. Scooter rental swaps moving entities for stationary ones. Cellular handoff swaps drivers for cell towers. Drone routing uses H3 at higher resolutions for collision avoidance.
The primitives (index, expand, score) stay the same. What changes is the cell resolution and the scoring function. H3 is a coordinate system that happens to have the right properties for proximity work, and dispatch is one application of it among many.
If this was useful
This dispatch design is one of the 15 worked-through systems in the System Design Pocket Guide: Interviews, laid out the way you'd actually walk through it on a whiteboard, with the spatial-index decision argued out instead of asserted. If you're interviewing or running interviews and want a reference of how to defend these choices in 45 minutes, the book is built for that.
Top comments (0)