The QuadTree Under Write Pressure

In one line: this is the chapter's central engineering problem. The Yelp chapter built a quadtree for points that never move; this chapter asks it to hold three million points that move every four seconds.

The location manager

Riders and drivers connect to the location manager service. It shows nearby drivers when a rider opens the app and receives driver location updates every ~4 seconds. The service forwards driver locations to the quadtree map service to determine the driver's current map segment. It also stores each driver's latest location and, during trips, records the route taken.

One service, four jobs, on very different schedules

Worth separating, because they have almost nothing in common operationally:

Job	Rate	Consumer
Ingest driver updates	750,000/s	Everything downstream
Serve nearby-driver browsing	Every app open	Riders
Store latest position	750,000/s, overwriting	Matching
Record route traces	Per in-progress trip, appending	Billing, fraud, analytics

The third and fourth are the pair to notice. Latest position is a mutable key-value write; a route trace is an immutable append. Same input stream, opposite storage shapes — which is precisely the polyglot split Lesson 10 makes, and precisely the workload Lesson 3 found the estimate had omitted.

The second is the odd one out: the only read in a service otherwise dedicated to absorbing writes. That mixture — a firehose of writes and a stream of browse queries against the same data — is what makes this component hard.

Why the Yelp quadtree does not survive

The most significant difference we have now is that our quadtree wasn't designed with regular upgrades in consideration.

The data structures must handle location updates from active drivers approximately every 4 seconds. Each location update may require modifying the quadtree. To process an update, the system determines the driver's current region based on the previous position. If the driver crosses region boundaries, the system removes the entry from the previous region and inserts it into the new region. If the updated region exceeds the configured driver threshold, it is subdivided further.

Every property that made the Yelp quadtree cheap is reversed here

Put the two chapters side by side:

	Yelp	Uber
Points	Static — a cafe stays put	Moving — every 4 seconds
Insert rate	5 per day	750,000 per second
Boundary crossings	Never	Constantly
Splits	Rare, and expensive was fine	Continuous, and expensive is fatal
Merges	Not needed	Required — cells empty as drivers leave

The Yelp chapter's conclusion was that "an operation's cost only matters multiplied by its frequency" — splits were expensive and completely acceptable at five writes a day.

Multiply the same cost by 750,000 per second and the design collapses.

And boundary crossings are not an edge case here — they are the normal state. A driver moving at 50 km/h covers 55 metres between updates, so in a dense city where leaves are small, a large fraction of updates cross a cell boundary. Each crossing is a remove plus an insert, and each insert risks a split.

Worse, the reverse operation now matters. Yelp never needed a merge, because places do not leave. Here drivers stream out of a region as constantly as they stream in, so cells empty and — without merging — the tree accumulates depth for density that has moved on.

A data structure's cost profile is a function of its workload, not of the structure. The quadtree is right for both chapters; what changes is everything about how you maintain it.

The fix: decouple the two questions

To overcome the above problem, we can use a hash table to store each driver's latest position and update our quadtree every 10–15 seconds. We can update the driver's location in the quadtree every 15 seconds instead of every 4 seconds, and we use a hash table that updates every 4 seconds and reflects the driver's latest location.

This works because the two structures answer different questions

The trick looks like a caching hack. It is better than that — it is a recognition that "where is driver X?" and "which drivers are near point P?" are different queries deserving different structures.

	Hash table	QuadTree
Question	Where is driver X?	Which drivers are near P?
Key	`driverID`	Spatial region
Write cost	O(1) overwrite	Remove, insert, maybe split
Update rate	Every 4 s	Every 10–15 s
Freshness	Exact	Up to 15 s stale

A hash table keyed by driver ID absorbs a positional update in constant time with no structural change — it is just overwriting a value. It is the perfect shape for a firehose of updates to known keys.

A quadtree cannot do that, because its whole value is organizing points by position, and changing a point's position is therefore a structural change.

So: put the firehose where it is cheap, and let the expensive structure lag.

The arithmetic of the relief:

QuadTree writes at 4 s  = 750,000/second
QuadTree writes at 15 s = 200,000/second     <- 3.75x reduction

Still enormous, and it is why Lesson 11 adds Redis in front. But a 3.75× reduction on the most expensive operation in the system is a large win for one parameter change.

When one structure is cheap to write and another is cheap to query, use both and accept lag between them. That is the same instinct as that building block's base-versus-transitory edge weights and that building block's semantic cache: materialize what is stable, compute or defer what is volatile.

Naming what the 15-second lag actually costs

The design says the lag is fine. It is worth being specific about why, and where it is not.

A driver at 50 km/h travels about 208 metres in 15 seconds. On a motorway, closer to 400. So the indexed position can be a few hundred metres from the truth.

That is acceptable for finding candidates — a driver 300 metres from where the index thought is still a fine match, and the exact position comes from the hash table once a specific driver is selected.

It is not acceptable for two things the design does not separate:

Showing cars on the rider's map. A car that jumps 200 metres every 15 seconds looks broken. This is why real apps interpolate client-side — the visual smoothness is a rendering concern, fed by the 4-second stream rather than the index.

Matching in a fast-moving situation. A driver who has just entered a motorway may be several hundred metres past the rider by the time they are offered the trip. Real systems weight by heading and speed, not just position — which the hash table's old-and-new coordinates from Lesson 5 make possible.

The honest framing: the index's job is recall, not precision. It must not miss a nearby driver; being slightly wrong about exactly where they are is harmless because a second, exact lookup follows.

What the design still owes: merges, hot cells, and the browse query

Three problems the two-tier scheme does not solve.

Merging. The design describes splitting and never merging. Drivers leave regions constantly — a stadium empties, rush hour ends — so cells that split during a peak stay split. Without merges the tree deepens permanently. The Yelp chapter had the same gap and answered it with a periodic rebuild; here the churn is far higher, so a rebuild needs to be far more frequent, or the tree needs real merge logic.

Hot cells. An airport arrivals lane or a stadium after a concert concentrates thousands of drivers into one small area. The threshold forces repeated splits until cells are metres across, and the tree becomes extremely deep in exactly the place with the most traffic. Some systems cap depth and accept larger leaves rather than fragmenting indefinitely.

Concurrent reads during restructuring. Same problem that building block raised — a rider's browse query traverses the tree while a split is in flight. At five splits a day it was a corner case; at this churn it is the normal state, and copy-on-write stops being an optimization and becomes mandatory.

Raising the merge gap unprompted is a strong move, because it is the one that follows directly from "the points move" and it is the one the design most clearly did not consider.

Sending fewer pings without losing accuracy

The write volume is set by a number the design chooses: how often each driver reports position. Treating that as fixed is the missed opportunity.

Accuracy is not a function of ping frequency; it is a function of how much the position changes between pings. A parked driver's location is perfectly accurate after one report, and reporting it again every five seconds adds cost and no information.

So let the client vary its interval on speed, heading, proximity to open requests, and driver status. A driver idling at home is nearly free to track; one moving quickly through a busy area gets the frequency that actually matters. The server can also interpolate between reports for a driver travelling predictably, which lets the interval stretch further without the matching service seeing a staler position.

This is the cheapest available reduction in the system's dominant load, and it costs only client-side logic.

Key takeaway

Every property that made the Yelp quadtree cheap reverses here: points move, inserts run at 750,000 per second, boundary crossings are the normal case rather than an edge case, and merges become necessary because drivers leave regions as fast as they arrive. The fix is to recognize that "where is driver X?" and "which drivers are near P?" are different questions: a hash table absorbs the firehose in O(1) with no structural change, while the quadtree lags by 10–15 seconds — a 3.75x reduction in the most expensive operation. The 15-second lag costs a few hundred metres of positional error, which is fine because the index's job is recall, not precision — an exact lookup follows. Still unsolved: merges, hot cells at airports and stadiums, and concurrent reads during splits, which now make copy-on-write mandatory rather than optional.

Interview signal by level

Level	What a strong answer sounds like
L4	"We use a quadtree like the Yelp design to find nearby drivers, and update it as drivers move."
L5	Sees the write problem: "the difference from Yelp is that drivers move, so every update may cross a cell boundary and trigger a remove, insert, and possibly a split. We put a hash table in front for the latest position and update the tree every 10 to 15 seconds instead."
Staff+	Names why two structures: "'where is driver X' and 'which drivers are near P' are different queries — a hash table absorbs 750,000 writes per second in O(1) with no structural change, and the quadtree lags, which cuts its write rate 3.75-fold. The 15-second lag costs a couple of hundred metres, which is fine because the index provides recall and the hash table provides precision. I'd flag three gaps: there's no merge operation even though drivers leave regions constantly, so the tree only deepens; hot cells at airports and stadiums fragment indefinitely unless you cap depth; and at this churn rate copy-on-write for concurrent readers stops being optional."

Next: matching a rider to a driver.