Design Uber

Instagram and Twitter were read-heavy problems solved with precomputation and caching. Uber is the opposite, and that is why it belongs at the end of the module.

Two properties make it different:

• It is write-heavy. Every driver reports their location every few seconds, continuously, whether or not anyone is looking.
• The query is geometric. Not "give me row 42" but "which drivers are near this point right now?" — and standard indexes cannot answer that efficiently.

Add a hard correctness requirement — one driver must never be assigned two rides — and you have a genuinely different design problem.

Phase 1: Clarify

In scope: drivers publish location; riders request a ride from A to B; the system matches a nearby driver; both track each other live during the trip.

Out of scope: payments, pricing and surge, ratings, pooling, food delivery.

Non-functional:

• Matching within a few seconds.
• Location updates must sustain very high write volume.
• Matching must be strongly consistent — this is a CP requirement, unlike the feeds. Double-booking a driver is a real-world failure no reconciliation fixes.
• Location data itself can be slightly stale; a two-second-old position is fine.

Note that the system contains both consistency choices, exactly as the CAP lesson described: AP for location, CP for matching.

Phase 2: Estimate

Assume 1M active drivers, each reporting every 4 seconds, and 1M rides per day.

Location writes: 1M ÷ 4 = 250,000 writes per second, sustained, all day.

Ride requests: 1M ÷ 86,400 ≈ 12 per second, perhaps 50/s at peak.

Storage: if every update were persisted at ~100 bytes, that is 250,000 × 100B × 86,400 ≈ 2 TB per day of data that is worthless within seconds.

State the conclusion:

"Location writes outnumber ride requests by 20,000 to 1, and the data is only useful for a few seconds. So current locations belong in memory, not a durable database — and we only persist trip paths, which are far smaller."

That is the insight the estimate exists to produce.

Phase 3: API and data model

POST /v1/drivers/location    { lat, lng }            -> 204
POST /v1/rides               { pickup, dropoff }     -> { rideId, status }
GET  /v1/rides/{id}                                  -> { status, driverLocation }

Location updates should be fire-and-forget over a persistent connection, not individual HTTPS requests. At 250,000 per second, a TLS handshake per update is unthinkable.

drivers        (id, name, vehicle, status)              -- durable
rides          (id, rider_id, driver_id, status, ...)   -- durable
trip_locations (ride_id, lat, lng, recorded_at)         -- durable, only during a trip
current_location (driver_id -> lat, lng, updated_at)    -- in memory

The core problem: finding nearby drivers

"All drivers within 3km of this point" is the query everything depends on. Consider why it is hard.

SELECT * FROM drivers
WHERE lat BETWEEN ? AND ? AND lng BETWEEN ? AND ?;

A standard B-tree index sorts on one dimension. It can narrow by latitude quickly, but then must scan every driver in that latitude band across the entire world to filter by longitude. Two-dimensional proximity does not decompose into independent one-dimensional lookups.

The fix is to convert two dimensions into one in a way that preserves locality.

Geohashing

Divide the world into a grid. Repeatedly subdivide each cell into four, recording which quadrant you land in. The resulting string identifies a rectangle, and the longer the string, the smaller the area.

The valuable property: nearby points share a prefix. So "drivers near me" becomes a prefix match — an ordinary string index answers a geometric question.

// Drivers in this cell and its 8 neighbours
const cell = geohash(lat, lng, 6);
const cells = [cell, ...neighbours(cell)];
const nearby = await redis.sunion(...cells.map(c => `drivers:${c}`));

Querying the eight neighbouring cells matters: a driver 100m away may sit just across a cell boundary, and checking only your own cell would miss them.

Architecture

The location service absorbs 250,000 writes per second and updates the in-memory index. It does not touch a durable database on the hot path.

The matching service queries the index for candidates, ranks them, and offers the ride.

The rides database is a normal relational store — only ~50 writes per second, and it needs transactions.

Separating these matters: they have completely different scaling characteristics, and coupling them would force the low-volume, high-correctness path onto infrastructure sized for the high-volume, low-correctness one.

Matching without double-booking

This is the part candidates skip, and where the interesting failure lives.

Two riders request rides simultaneously. Both queries return driver D as nearest. Without care, both are assigned.

The naive approach fails:

const driver = await findNearest(pickup);
if (driver.status === 'available') {          // <- race window here
  await assign(driver.id, rideId);
}

Between the check and the assignment, another request can do the same thing. This is the check-then-act race from the rate limiting lesson.

The fix is an atomic conditional update — let the database decide the winner:

UPDATE drivers SET status = 'assigned', ride_id = ?
WHERE id = ? AND status = 'available';
-- 1 row updated: you won. 0 rows: someone else got them, try the next candidate.

One statement, no window. The loser simply moves to the next candidate.

Add a timeout: if the driver does not accept within a few seconds, release them and offer the ride to the next. Otherwise a driver who put their phone down blocks a rider indefinitely.

Bottlenecks and failure

Location write volume. Shard the geo index by region — traffic is naturally geographic, so a city maps to a partition. This also keeps queries local.

Hot cells. An airport or stadium at closing time concentrates enormous driver density in one cell. This is the hot-key problem again: use finer cells in dense areas, which is precisely what quadtrees and H3 handle better than fixed-length geohashes.

Location service failure. Lose the in-memory index and matching stops. Replicate it, and accept that a few seconds of location data is expendable — drivers will report again shortly. That is a legitimate reason to keep it in memory rather than engineering durability you do not need.

Notification delivery. A driver whose connection drops must still receive the offer. Retry, then move on after a timeout.

Region isolation. A failure in one city should not affect another — a strong argument for regional sharding beyond just capacity.

Check your understanding

Common mistakes

Scanning every driver to find the nearest one. Distance computed across the whole fleet per request does not survive contact with a city, let alone a country. Location needs a spatial index so the search touches only the relevant cells.

Treating location updates as ordinary writes. Every vehicle reporting every few seconds is a firehose of writes whose value expires almost immediately. It does not belong in the same store, or on the same durability guarantees, as the trip record.

Letting two riders match the same driver. Matching is an allocation problem with real contention. A design without an explicit claim step — one winner, everyone else told no — has a double-booking bug in it by construction.

Forgetting the offer can be declined. A driver who ignores the request must not strand the rider. The matching loop needs timeouts and re-offers, and those are where most of the real complexity lives.

Assuming connectivity. Phones go through tunnels and dead zones mid-trip. State that only exists on a device with a live connection will be lost, and the design has to say what happens when it is.

Ignoring fairness. Always offering the closest driver concentrates work on whoever happens to be central and starves the rest. Any real dispatch system has a fairness constraint pulling against pure efficiency.

Practice

Key takeaways

• Uber inverts the previous case studies: it is write-heavy, with location updates outnumbering ride requests roughly 20,000 to 1.
• Because location data is worthless within seconds, current positions live in memory and only trip paths are persisted.
• Standard B-tree indexes cannot answer proximity queries, because two dimensions do not decompose into independent lookups.
• Geohashing converts 2D to 1D while preserving locality — nearby points share a prefix — so a string index answers a geometric question. Always query neighbouring cells too.
• Quadtrees and H3 adapt to uneven density where fixed geohash cells struggle; know the trade-off.
• The system deliberately mixes CAP choices: AP for location, CP for matching.
• Prevent double-booking with an atomic conditional update, not check-then-act — and time out unaccepted offers.

Further reading

• Antonin Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching" (SIGMOD 1984).
• Gustavo Niemeyer, "Geohash" (2008), and the Google S2 Geometry documentation — cell-based spatial indexing.
• Harold Kuhn, "The Hungarian Method for the Assignment Problem" (Naval Research Logistics Quarterly, 1955) — batched matching as an assignment problem.
• Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), chapter 11 — streams of position events.
• Pat Helland, "Life Beyond Distributed Transactions: An Apostate's Opinion" (CIDR 2007) — atomic claims on scarce resources.