STANDARDwalkthrough
QuadTree vs H3 Grid
Why not use a QuadTree? It is the textbook answer for spatial indexing.
Each update may trigger a QuadTree node split or merge as drivers cross cell boundaries, causing write amplification and lock contention on internal nodes. We chose the H3 hexagonal grid (not QuadTree) because cell assignment is a pure function of latitude and longitude with no tree structure to maintain.
“The constraint: with 500K drivers updating GPS every 3 seconds, that is 167K updates per second.”
Trade-off: we gave up QuadTree's automatic density adaptation in exchange for zero lock contention at 167K writes/sec. When a driver moves, we remove them from the old cell's Redis sorted set and add them to the new cell's set.
Both operations are in Redis. QuadTree adapts density automatically: dense downtown areas get smaller cells, sparse suburbs get larger ones.
H3 cells are fixed-size. We compensate by using resolution 9 globally (0.1 km^2 per cell), which is fine-grained enough for urban areas.
For sparse suburban queries, we expand the k-ring radius from 1 to 2 or 3 to widen the search area. Uber's production system confirmed this approach: the write path matters more than adaptive reads when drivers outnumber rider queries 14,000:1 (167K location writes vs 12 match queries per second).
Related concepts