Design Uber / Ride Sharing

A rider opens the app, drops a pin and taps request. Within about three seconds the app should show a named driver, a car and a pickup time. From then until drop-off, both phones show each other moving on a map, and when the trip ends the fare is final and charged once.

Behind that flow sit four separate systems that interviews tend to blur together: a location index that absorbs a constant stream of GPS points, a dispatcher that picks and locks a driver, a live tracking channel that pushes positions to riders, and a pricing and ETA layer that decides what the trip costs and how long it takes. Each has a different consistency need, and treating them as one service is the most common mistake candidates make.

Assume 18 million trips a day across about 700 cities, 2.5 million drivers online at the global peak, and a largest city with 120,000 drivers online on a Friday night. About a third of online drivers are on a trip at any moment.

The system is built as cells. A cell is a full copy of the real-time stack serving a group of nearby cities: its own socket gateways, location index, dispatcher, trip store and pub/sub. A routing layer maps each city to one cell, and a large city may get a cell to itself. Shared global services, such as accounts, payments and maps data, sit outside the cells and are called asynchronously wherever possible.

Two paths run through each cell. The location path is high volume and lossy by design: a driver's phone sends a point over its socket, ingest snaps it to a road, updates the in-memory hex index and appends the point to Kafka for history. Nothing on this path waits for a disk. The trip path is low volume and strict: creating a trip, offering it, accepting it and finishing it are durable state transitions with versioning.

They meet at the dispatcher. It reads candidates from the index, asks the ETA service for real drive times, and then claims a driver through an atomic compare-and-set on the driver state store. Every trip state change is published on a per-trip channel, which the socket gateway forwards to whichever phones are subscribed.

The question the index answers thousands of times a second is: which available drivers are within a few minutes of this point? A database query on latitude and longitude ranges is too slow once each driver writes every few seconds. You want a scheme that turns a position into a short key, so that "nearby" becomes "these few keys".

We index drivers at resolution 9, where a hexagon is about 0.1 km², roughly 175 metres across. For each cell the index holds a small set of driver IDs with their last point. A driver update does three things: compute the new cell from the snapped point, remove the driver from the old cell if it changed, and overwrite its entry in a per-driver hash with a TTL of 30 seconds. A driver who stops reporting therefore disappears from search without any cleanup job.

To search, take the pickup's cell and expand rings with gridDisk(k). Ring 1 is 7 cells, ring 3 is 37, ring 6 is 127. Stop as soon as you have about 15 available candidates or hit a maximum radius around 3 km. In a dense core that usually happens at ring 2; on the edge of a city it takes more rings, and the dispatcher widens the radius rather than giving up.

Straight-line distance is only a first filter. A driver 400 metres away on the other side of a river or a highway can be 12 minutes out. The dispatcher sends the candidate list to the ETA service and ranks by real pickup time, which is the number the rider actually experiences.

Every trip and every driver has a small state machine, and every transition is a conditional write that names the version it expects. If the version has moved on, the write fails and the caller re-reads. This one rule handles nearly every race in the system: a rider cancelling while a driver accepts, two dispatchers working the same driver, a retry arriving after the first attempt succeeded.

A driver near a busy junction may be the best candidate for three requests at the same instant. If three dispatchers each send an offer, the driver gets three pings and two riders are disappointed. So before sending an offer, the dispatcher claims the driver:

Only the winner sends an offer. When the driver accepts, a second conditional write moves the driver to on_trip and the trip to accepted, both guarded by version. Because the two rows live in different stores, the trip service writes the trip first and the driver second, and a reconciler repairs any pair left half-done after a crash by checking offer expiry times.

In Redis the same claim is a short Lua script that compares status and version, then sets the new values. Either way, the lock is the state itself, so there is no separate lock service to fail or leak.

Offers expire after 10 seconds. Shorter windows cause drivers who are mid-turn or glancing at the road to miss offers they would have taken; longer windows mean a rider waits through several silent drivers. With a typical acceptance rate around 80% and three candidates ready, the expected wait to an accepted driver stays under 15 seconds even with one decline.

In dense areas we also run batched matching: collect all requests and available drivers in a zone over a 2-second window and solve the assignment as a small bipartite matching problem that minimises total pickup time. Greedy nearest-driver assignment often gives one rider a great match and the next a terrible one; batching smooths that out at the cost of a 1 to 2 second delay.

Once a trip is accepted, the rider watches the car approach. Polling would be the simplest design, but 1.1 million watchers polling every 2 seconds is another 550,000 HTTP requests per second, each paying for TLS, auth and routing to return a few bytes. Persistent sockets cost one connection per phone and a small frame per update.

Rider drops: the app reconnects with backoff, calls the trip endpoint, and resubscribes. Missed points are not replayed; only the latest position matters. Driver drops: the phone buffers points locally and uploads the batch on reconnect, so trip distance for the fare is still complete, while the rider sees a "connection lost" hint after 15 seconds without updates. Gateway node dies: its 60,000 phones reconnect to other nodes over the next few seconds. Jitter the reconnect delay on the client, or the surviving nodes take a thundering herd of TLS handshakes at once.

A stadium empties at 22:40. In five minutes, 9,000 people within 800 metres open the app. Three things go wrong together: demand outruns supply in a few hexagons, the shard holding those hexagons runs hot, and drivers already nearby are claimed instantly, leaving later requests with ETAs of 25 minutes.

Every 30 seconds, the pricing service counts open requests and available drivers per resolution-7 hexagon (about 5 km²) and smooths the ratio over the last few minutes. A multiplier comes from a capped curve of that ratio: 1.0 when supply covers demand, rising in steps of 0.1 up to a regulated maximum. Smoothing across neighbouring hexes stops prices jumping at a street corner.

The multiplier does two jobs at once. Some riders wait or choose a cheaper product, which trims demand. Drivers see a heat map and move towards the zone, which adds supply over 5 to 10 minutes. The quote a rider confirms is signed and honoured for a few minutes, so the price never changes after the rider says yes.

Ring searches from a thousand requests in one area all hit the same index shard. Three measures keep it healthy. First, coalesce searches: requests in the same resolution-9 hex within a 500 ms window share one candidate list. Second, give the shard read replicas, since a few hundred milliseconds of staleness is harmless for candidate search when the claim step re-checks status anyway. Third, for known venues and airports, run a virtual queue: riders join a line and drivers are matched in order at a pickup zone, which turns a geographic search into a FIFO.

ETA shows up three times in one trip: ranking candidate drivers, quoting the price, and the countdown on the rider's screen. Calling an external maps API for each would mean several million paid calls an hour with 100 ms or more of latency each. Ranking alone calls for a dozen ETAs per request. So the ETA service is in-house and layered from cheap to precise.

Layer 1 multiplies the haversine distance by a per-city detour factor, usually around 1.3 to 1.5, and divides by a typical speed for that hour. It is free and used only to prune obviously far candidates. Layer 2 is a table of median travel times between resolution-7 hexes for each 15-minute slot of the week, built offline from trip history. It answers in microseconds and is good enough for rough price quotes.

Layer 3 runs a real shortest-path query on the road graph. Plain Dijkstra on a city graph with a few million edges takes far too long, so the graph is preprocessed with contraction hierarchies: nodes are ranked by importance and shortcut edges are added that skip over unimportant ones. A query then searches upward from both ends and meets in the middle, touching only a few thousand nodes, in about a millisecond. Live traffic is applied by updating edge weights from recent probe speeds; customisable variants of the technique let you refresh weights every few minutes without redoing the full preprocessing.

Layer 4 is a gradient-boosted model that predicts the error of layer 3 from features such as time of day, weather, pickup type (airport, mall, side street) and the driver's recent speed. Every completed trip is a labelled example, so the model improves as the platform grows, which is a real advantage over a new competitor.