Design a Ride-Sharing Service

The single-server version put the front door, the position store, and the trip store all in one box. The first move is to pull them apart into a shape that can grow. Two roles are obviously different. One role is receiving traffic — accepting a flood of driver pings and a stream of rider queries and requests. The other role is holding driver positions and answering "who's nearby." Splitting them lets each scale on its own. A driver's ping and a rider's "who's nearby" arrive at very different rates and for very different reasons — so where does each land, and what holds the positions the rider query reads?

The location stream is an inlet, not a connection design, and it is worth saying why once and moving on. The driver's app streams a ping every few seconds over a long-lived connection. Everything about that connection — how it is kept open across a mobile network, how millions of them are balanced across gateway nodes, how a gateway restart hands them off without dropping pings — is the persistent-connection problem the chat board owns. Re-deriving it here would rebuild another board's signature, so the gateway takes a ping as an inlet and the connection layer underneath is out of scope.

That leaves the real shape decision, which is about where state is allowed to live. The gateway must hold nothing, because it sits on the firehose: a million pings a second flow through it, and anything it had to remember per driver would pin that state to the one tier you most need to keep thin and replaceable. Push all the position-holding back to the geo workers, and the gateway becomes a pure forwarder you scale flat. The workers hold the state and do the finding — which is why the two hard problems that follow, the firehose write and the nearby read, both land on the workers and nowhere else.

A stateless Location gateway in front, a tier of geo workers holding positions behind it. Put a thin, stateless Location gateway in front, and a tier of geo workers holding positions behind it. The pings arrive over a connection the driver's app holds open — that connection itself is not what we are designing here; it is an inlet, so a ping shows up at the front door and we take it from there. The gateway accepts a ping and hands it onward, accepts a rider query and routes it, and holds no driver state of its own, so it scales by simply adding more stateless instances. Behind it, the geo workers hold driver positions, split across many of them, and answer the rider's "who's nearby." A ping is forwarded to a worker, which records the driver's latest position; a nearby query is forwarded to the workers, which look for drivers close to the rider.

And right now, established here as the baseline the next use cases attack, the way a worker answers "who's nearby" is a full scan: it looks at all the positions it holds and keeps the ones near the rider. That works, and it is honest to draw it, but it is the naive baseline on two axes at once. The positions are still being written the expensive durable way inherited from the single-server design, and the read is still a scan. The next two use cases fix exactly those two things, in that order — first the firehose write, then the nearby read.

The pipeline has a shape now, but the geo workers are still storing positions the way the single server did: durably, on disk. The firehose from the brief is now pointed straight at them, and this is where it either sinks the design or forces the idea the whole system is built on. A quarter of a million location writes arrive every second in one region, and each one is a driver's new position that will be stale in four seconds. Where does that write land?

Follow the obvious answer first, because it is what most people reach for. Keep a drivers table — now maybe sharded across several databases so no single one takes the whole rate — and UPDATE the driver's row on every ping. The attraction is real: it is the design you already have, it is simple, and the position is safely on disk if anything crashes. But size it. Each UPDATE is a durable write, about ten milliseconds of work to put the new position on disk in a crash-proof way. You are doing that a quarter of a million times a second in one region, and every single write is durably saving a number that a fresh ping overwrites four seconds later. You are paying the full cost of durability — the slowest, most expensive property a store can offer — for the one piece of data in this whole system that has no durability requirement at all. Sharding the table spreads the pain across more disks, but it does not remove it; you are still writing to disk on the firehose.

The second attempt improves the medium but keeps the mistake: put the positions in a fast store like Redis instead of a relational table — memory-speed writes, much higher throughput. That is genuinely faster. But if you configure it to persist every write for durability, you are back to paying for durability the data does not need, now on a different box. The store being fast is not the point; the point is whether the write is durable at all, and a persisted position write is still a durable write on the firehose. Only when you see that the firehose itself makes durability unnecessary does the cheap answer — memory, no persistence — become the safe one.

Live location in memory across the geo workers — non-durable, no database. Live driver location never touches a database — it lives in memory across the geo workers, and it is not durable. Each geo worker holds its slice of driver positions in RAM. A ping updates a value in memory, which takes microseconds instead of ten milliseconds, and nothing is written to disk. The design deliberately accepts that these positions are not crash-proof — and the reason it can accept that is the firehose itself. A position is only ever a few seconds from being replaced: if a worker loses a position, because the process restarted or a whole worker died, the driver's next ping, at most four seconds away, writes it again. The data heals itself. There is nothing to recover because the source keeps re-sending. Uber states this exact choice in its own words: database storage would be useless because of how fleeting the location data is.

That is the aha, and it inverts the naive instinct. The firehose is not a scaling problem you throw a bigger database at — the firehose is the reason you can drop durability entirely: data that rewrites itself every four seconds does not need to survive a crash, so it does not need a disk, so it does not need a database. But durability did not vanish; it moved. A trip is not fleeting. "This rider took this ride with this driver, and it cost this much" has to survive crashes, be queried later, and be exactly right. So the design splits the two datasets by their real needs: live positions get freshness without durability, held in memory on the geo workers; trips get durability, in a separate store built for it — the Trip store, a relational store sharded a fixed number of ways. Durability is spent on the one dataset that needs it and denied to the one that does not. That split — freshness here, durability there — is the signature of this whole design.

The positions are in memory now, fast to write. But the read is still the naive full scan from the first use case: to answer "who's near this rider," a worker looks at every position it holds. The geo workers hold a region's million live positions between them; a rider opens the app at one point on the map and wants the cars within a couple of kilometers. How do you answer that without looking at every position? The firehose fixed the write; this use case fixes the read.

The instinct is to argue about granularity — "use a finer grid so cells are smaller and queries are more precise" — and seeing why that is a trap is the heart of this deep dive. All the serious encodings — geohash, S2, H3 — let you pick essentially any cell size you want. Uber's original S2 index used level-twelve cells at roughly three to six square kilometers, which sits right between two H3 resolutions; H3's resolution knob alone spans about thirteen orders of magnitude in area across its sixteen resolutions, from hexagons of millions of square kilometers down to under a square meter. Granularity is a knob every option has. It was never the thing that separated them.

Walk the candidates by geometry instead. Geohash encodes a latitude-longitude pair into a string, and its cells are rectangles whose ground area changes sharply with latitude — a grid whose cells quietly change size as you move around the globe is awkward to reason about. S2, Google's library and Uber's original choice, is better: it projects the sphere off the six faces of a cube and recursively splits each face into four, so it is literally a quadtree on the sphere. Its cells are squares — and squares are where the subtle problem lives, because a square has two neighbor distances, edge and corner, so any analysis over a neighborhood keeps correcting for which kind of neighbor it is looking at. H3 tiles the map with hexagons, which have one neighbor distance, and that is the whole reason Uber built it. The migration from S2 to H3 was not about smaller cells; it was about swapping a shape with two neighbor distances for a shape with one.

A hexagonal spatial index (H3), cell resolution tuned to driver density. Bucket driver positions into hexagonal cells, and to answer a nearby query, scan the rider's cell and its ring of neighbors. The idea behind every answer is the same: stop treating positions as an unordered pile and start bucketing them by where they are, so a query that used to scan the whole region now scans a handful of cells. The pick between the encodings is not about granularity — all of them let you choose essentially any cell size — it is about geometry, the shape of the cells. A square cell has two different distances to its neighbors: the four cells across an edge are one step away, but the four across a corner are farther, about one and a half steps. A hexagon has one neighbor distance — all six neighbors are the same distance from the center — so "the neighboring cells" is one clean ring with nothing to correct for. In Uber's own words, hexagons have only one distance between a centerpoint and its neighbors, and that property greatly simplifies analysis and smoothing over gradients. That, not smaller cells, is why Uber moved from squares to hexagons.

The positions themselves are spread across the whole worker fleet, so a nearby query fans out: each worker scans the rider's cell and its neighbors among the positions it holds and sends back its shortlist, and the gateway merges the handful of shortlists into one answer. The read that was a full scan of the region becomes a scan of a small, fixed neighborhood. The one genuine knob left is the cell resolution, tuned to the driver density you actually see. And one myth to kill on the way past: Uber's live driver index was never geohash. It was S2, and then H3. Geohash shows up here only in supporting roles — the internal encoding inside Redis's geospatial type, and an offline aggregation key in Lyft's ETA model. Saying "Uber uses geohash for its live index" is wrong, historically and today.

The board reads well now: positions land in memory at firehose speed, and a rider's nearby query is a bounded scan. Time to try to break it. Two things the happy path glossed are about to bite, and they are really one thing. A ride request has to reach the exact worker holding the target driver's live state — and two riders must never both be told they got the same driver. And a worker holding a slice of the fleet will, at some point, die. Both come down to one question: who owns a given driver's state, and how is that ownership decided and moved — without a lock across the whole cluster?

The instinct is a distributed lock: before creating a trip, take a cluster-wide lock on that driver's id so no one else can grab them, and release it when the trip is created or the offer is declined. It sounds right and it is a trap. A lock negotiated across a cluster on every dispatch is slow — it is a round trip to a lock service on the critical path of every ride — and it adds a new thing that can fail and stall every dispatch behind it. Worse, it is solving a problem the design can avoid entirely rather than manage.

The real answer makes the double-booking question local by deciding ownership up front, so there is nothing to coordinate. Route every request for a driver to that driver's one owning worker by hashing the driver id, and the worker serializes them in its own process — the first books, the second is declined. No lock service, no round trip, no new failure mode on the critical path. The guarantee falls out of the routing: one owner per driver means one place makes the decision, in order.

A consistent-hash ring — one owning worker per driver, decided by hash(driverId). Put the geo workers on a consistent-hash ring, and make the double-booking question local by deciding ownership up front. Hash each driver's id onto the ring, and the ring assigns that driver to exactly one owning worker. Now every request that touches a given driver — a position update, a dispatch offer — is routed to that one owner by hashing the driver id, with no directory consult, because the hash is the address. And because all requests for a driver land on the same single worker, "don't double-book" stops being a distributed problem: that one worker handles its drivers' requests one at a time, in its own process. Two ride requests for the same driver both route to the same owner, which handles them in order — the first finds the driver free and books them, the second finds the driver taken and is declined and offered the next candidate. It is a local decision inside one process — no cluster-wide lock, because there is nothing to coordinate across the cluster.

The same ring is the failure story, and it is why the index can be non-durable. A consistent-hash ring is built to lose a node gracefully: when a worker dies, the ring hands its slice of drivers to the neighbor around the ring — in Uber's words, when node one in the hash ring goes down, work proceeds as usual, and all of those objects between nodes one and two get picked up by node two. The dead worker's in-memory positions are gone, but that is exactly the loss the signature dive already made safe: every driver on that slice pings again within four seconds, and the ping lands on the new owner, which records the position. The slice re-populates itself in about one ping cycle. This closes the loop opened two use cases back — the geo workers can afford to hold positions in memory with no durability precisely because the ring plus the firehose rebuild a lost worker's state automatically.

Step back and look at what is built. It is correct and complete for an ordinary busy city: the firehose lands in memory, nearby is a bounded query, and one driver goes to one trip while surviving a worker's death. Now the premise arrives already broken, the way a real incident does — and it is honest to say up front that this one is not a failure of anything built so far. The location pipeline is fine. The index is fine. The dispatch routing is fine. The system falls over anyway, and understanding why is the point. It is New Year's Eve. Across a city, far more people want a ride than there are drivers to give one, all at once. On a real night like this, Uber saw a 26-minute window where its surge-pricing algorithm was down in New York; with that one signal missing, the share of ride requests that went unfulfilled rose to 25% and estimated waits spiked to about 8 minutes — against a 2.6-minute average during a comparable event where surge worked. Nothing in the location or dispatch tier had crashed. The thing that broke was the marketplace's balancing signal.

The instinct is to add capacity — spin up more geo workers, more dispatch instances, throw hardware at it. It is the reflex that worked when the firehose needed more workers, and here it does nothing, because the shortage is not compute. There are only so many drivers on the road. A thousand more dispatch instances cannot match a rider to a driver who does not exist. When demand far exceeds supply, the bottleneck is the supply of cars, and no server you add creates a car.

So the only responses that help are the ones that work on the side you control: reach further out for a driver, hold and admit requests as drivers free up, and tell riders the honest wait — while the marketplace's balancing signal does the actual rebalancing over time. The New Year's Eve outage is the clean proof: nothing in the location or dispatch tier crashed, and the marketplace still fell over, because the balancing signal — not any box on this board — is what keeps supply and demand in step.

Degrade gracefully — widen the radius, shed or queue, quote honest ETAs. Degrade gracefully on the dispatch path — never pretend the index can conjure supply. When a region floods and there are not enough nearby drivers, the dispatch service has real, honest moves, and none of them is "scale up." It can widen the search radius — reach further out for a driver, accepting a longer pickup, rather than returning nothing. It can shed or queue requests — hold new requests briefly and admit them as drivers free up, instead of failing every one under load. And it can quote honest, longer ETAs — tell the rider the real wait rather than a comfortable lie. Underneath all three, the marketplace's own balancing signal — surge pricing, which this board does not design — is what actually rebalances supply and demand over time by drawing more drivers out and damping some demand. The New Year's Eve incident is the proof of what happens when that signal is missing: unfulfilled requests and long waits, not because the machinery broke, but because the loop that keeps supply and demand in balance went quiet.

The reframe is the lesson to carry out, and it is bigger than this one board. A ride-sharing service is not a request-response system that either has capacity or does not. It is a control loop between supply and demand, and matching is worthless when there is no supply to match. You can build a flawless location firehose, a perfect spatial index, and lock-free dispatch — everything in the four use cases before this — and the system can still fall over under a flood, because the thing that fails is not any component but the balance between two sides of a market. The engineering answer to a flood is to degrade honestly on the side you control, and to respect that the real fix lives in the balancing signal, not in more servers. The hot-cell tension from the spatial-index dive is this same flood in miniature — one part of the map carrying far more load than the rest, answered by adapting to the skew rather than pretending one setting fits every load.