Designing Uber
The location firehose, geospatial indexing with geohash, quadtrees, S2 and H3, batched matching, the trip state machine, surge pricing, ETA and payments.
On this page
Ride hailing is a matching problem wrapped in a geospatial index wrapped in a state machine. A million drivers report their position every few seconds, a rider asks who is nearby, and something has to decide — in under a second, with incomplete information about traffic and about whether the driver will even accept — which one to send. The database question that opens this design is deceptively small: how do you index a point on a sphere so that "near me" is a fast lookup?
The map
Read this first when short on time. Every branch is a section below.
What it must do, and at what size
It must track where every online driver is, show a rider the drivers near them with an honest wait estimate, match a request to exactly one driver, follow the trip through its states, and take payment. It must not, in this design, handle scheduled rides, multi-stop trips or shared pooling — pooling in particular changes the matching objective from "nearest driver" to "best route through several riders", which is a different problem.
Drivers 5M registered, ~1M online simultaneously at peak
Pings every 4 s per online driver -> 250,000 writes/s
Ping record driver id, lat, lng, heading, accuracy, ts ~= 50 B
250k/s x 50 B = 12.5 MB/s -> bandwidth is not the problem
Trips 25M/day -> ~290/s average, ~900/s peak
Nearby query once per rider app open, plus refreshes -> tens of thousands/s
Current state 1M drivers x 50 B = 50 MB -> the live index fits in memory
History 250k/s x 50 B x 86,400 ~= 1 TB/day to the logThe numbers say something useful immediately: the present is tiny — fifty megabytes holds every driver's current position, so the live index belongs in memory — while the past is a terabyte a day and belongs in a log that nothing on the critical path reads. Separating those two is the first design decision, and it removes the temptation to put a database write on the ping path.
flowchart TD D["driver app, ping every 4 s"] --> LI["location ingest"] LI --> IX[["in-memory geo index"]] LI --> LG[["location log"]] R["rider requests a ride"] --> DS["dispatch service"] DS --> IX DS --> ET["ETA service"] DS --> SU["surge service"] DS --> TR[["trip store"]] TR --> EV[["trip events"]] EV --> PY["payments saga"]
The location firehose
A quarter of a million writes a second, each fifty bytes, each overwriting the previous value for that driver. Treating that as ordinary database traffic is the single most common mistake in this design.
The current position is one record per driver, updated in place, held in memory and keyed by the geospatial index below. There is no history in it and no durability requirement: if the process restarts, drivers repopulate it within four seconds by pinging again. That property — self-healing within one ping interval — is what makes an in-memory store acceptable for something this important.
The history goes to an append-only log, partitioned by city, and is read by trip reconstruction, traffic estimation, fraud detection and billing disputes. None of those is latency-sensitive, so the log can lag and buffer freely.
Three client-side reductions keep the rate manageable and the battery alive: ping less often when the vehicle is stationary or the driver is not available, batch several points into one message when the network is slow, and compress by sending deltas rather than absolute positions. Losing individual points is acceptable — the next ping supersedes it — which is worth stating explicitly, because it licenses aggressive dropping under load.
Location points are one of the most sensitive data types a system can hold. Retention should be bounded and stated, access should be audited, and the analytics path should work on aggregates or coarsened cells wherever it can. This is a design requirement, not a policy afterthought.
Indexing the map
Now the central question: given a point, find the drivers within two kilometres, fast, tens of thousands of times a second.
The obvious approach fails for an instructive reason. A query with lat BETWEEN ... AND lng BETWEEN ... has two range predicates, and a B-tree index can order by only one dimension — so the database narrows by latitude and then scans every driver in that band, which in a dense city is most of the fleet. Two-dimensional data needs an index that understands both dimensions at once.
The trick behind every solution is to turn two dimensions into one such that points close in space are usually close in the resulting order. Interleave the bits of latitude and longitude and you get a single number whose prefix identifies a cell: the longer the prefix, the smaller the cell. Now "nearby" is a prefix match, which an ordinary index handles perfectly.
| System | Cell shape | Strengths | Weaknesses |
|---|---|---|---|
| Geohash | Rectangles from interleaved bits | Trivially simple, string prefixes, works in any database | Cells distort badly towards the poles, and two adjacent points can have completely different prefixes across a boundary |
| Quadtree | Recursive quadrants, subdivided where dense | Adapts to density: one cell per few hundred drivers regardless of city | A mutable tree that must be rebalanced, harder to shard |
| S2 | Cube projected on the sphere, ordered by a Hilbert curve | Very little distortion, 64-bit cell ids, excellent locality | Cells are still quadrilaterals, so neighbour distances are uneven |
| H3 | Hexagons | All six neighbours are equidistant, which makes radius search and smoothing natural | Hexagons cannot tile perfectly hierarchically, so nesting is approximate |
The boundary problem is common to all of them and worth understanding because it dictates the query. Two drivers a metre apart can fall in different cells, so searching one cell misses half the neighbourhood. Every implementation therefore searches the target cell and its surrounding ring, then filters by true distance afterwards. Hexagons are attractive precisely here: a hexagon has six neighbours all at the same centre-to-centre distance, while a square has four edge neighbours and four diagonal ones at a different distance, which makes any radius or smoothing calculation messier.
The query then becomes: compute the rider's cell at a resolution sized to hold a useful number of drivers, read that cell and its ring, and if the result is too small, drop a resolution level and repeat. Density varies enormously — a cell that holds forty drivers in a city centre holds none in a suburb — so adaptive widening is not an optimisation but the normal path.
- Uber built H3 for exactly this and open sourced it; the hexagonal grid is now used well beyond ride hailing for any per-area aggregation.
- S2 came out of Google and underpins geospatial indexing in Maps and in several databases.
- Redis, Postgres and Elasticsearch all ship geospatial types built on one of these ideas, which is usually the right place to start.
Matching
Finding nearby drivers is a query. Deciding which one to send is the product, and the difference between a mediocre and a good service is almost entirely here.
Greedy matching assigns each request to the nearest available driver as it arrives. It is simple and locally sensible, and it is globally poor: two requests arriving a second apart can both be given to drivers who would have been better assigned the other way, and a driver two hundred metres away gets skipped because a request made a moment earlier claimed them.
Batched matching waits a few seconds, collects the requests and available drivers in a city, and solves the assignment as one optimisation — minimising total expected wait across the batch rather than for each rider in turn. The counter-intuitive result is that making every rider wait a couple of seconds longer to be matched reduces the time they actually wait for a car, because the assignment is better. It also reduces cancellations, which are far more expensive than a slightly longer match time.
sequenceDiagram autonumber participant R as Rider participant D as Dispatch participant I as Geo index participant V as Driver R->>D: request a ride, pickup point D->>I: cell and ring at this resolution I-->>D: 28 available drivers Note over D: hold for the batch window, score by ETA and acceptance D->>V: offer, locked for 15 seconds V-->>D: accept D-->>R: driver assigned, ETA 4 minutes Note over D,V: a decline or timeout releases the lock and rematches
The scoring function is not distance. It is estimated time to pickup, which differs from distance whenever traffic, one-way systems or a river intervene — a driver four hundred metres away on the wrong side of a motorway is not the closest driver in any useful sense. Real systems add the predicted probability that a given driver accepts, and the effect on the overall supply picture of moving that driver, which is why dispatch is closer to an economics problem than a geometry one.
The offer lock is the correctness mechanism. When a driver is offered a trip, they are held for a short window with a lease; if they accept, the lease becomes an assignment, and if they decline or the lease expires, they return to the pool and the rider is rematched. Without the lease, two dispatch nodes handling two requests in the same second can offer the same driver twice — which produces the one failure the product cannot tolerate.
The trip state machine
Once matched, a trip is a small, strongly-consistent state machine — the one part of this system that cannot be eventually consistent, because two conflicting transitions produce real-world consequences.
stateDiagram-v2 [*] --> Requested Requested --> Offered: driver selected Offered --> Requested: declined or timed out Offered --> Accepted: driver accepts Accepted --> Arrived: driver at pickup Arrived --> InTrip: rider on board InTrip --> Completed: dropped off Requested --> Cancelled: rider cancels Accepted --> Cancelled: either side cancels Completed --> [*] Cancelled --> [*]
Three rules make it safe. One active trip per driver, enforced by a conditional write on the driver's record rather than by application logic, so that concurrent dispatch attempts cannot both succeed. Transitions are idempotent, keyed by a client-generated id, because a driver's phone will retry "arrived" over a bad connection. And every transition emits an event, so pricing, receipts, analytics and support tooling read the event stream rather than querying the trip store — the trip row stays the single small source of truth.
Surge
Surge pricing is a control loop: when demand in an area exceeds supply, the price rises, which suppresses some demand and attracts drivers from nearby areas until the two rebalance.
The signal is computed per cell over a short sliding window — open requests divided by available drivers — and then, importantly, smoothed. A raw ratio flaps: it crosses a threshold, the multiplier changes, riders and drivers react, and it crosses back. Three mechanisms keep it stable: exponential smoothing over the window, hysteresis so that going up requires a higher threshold than coming down, and a cap on how far and how fast the multiplier may move.
Cells also create hard boundaries where none exist in reality: standing on one side of a street should not change the price. Blending a cell's value with its neighbours' — trivial with hexagons, since all six are equidistant — produces a smooth surface instead of a mosaic.
The product rule that constrains the engineering: a quoted price is honoured. The multiplier is resolved when the rider is shown a price, stored on the request, and used for the fare even if surge has moved by the time the trip completes. That means surge is an input to the quote rather than to the billing, which is a much easier thing to build correctly.
ETA and routing
Every part of this system asks the same question: how long will it take to get from A to B? Matching uses it to score drivers, the rider app shows it, and pricing depends on it.
The road network is a graph where nodes are junctions and edges are road segments weighted by current travel time. Shortest-path search over a city graph is too slow to run tens of thousands of times a second naively, so the graph is preprocessed: techniques such as contraction hierarchies add shortcut edges that let a query skip over long stretches of unimportant road, turning a search that would visit millions of nodes into one that visits thousands.
The weights come from the fleet itself. Every driver pinging every four seconds is a traffic sensor, so segment speeds are estimated from the same firehose that feeds dispatch — which is the most elegant feedback loop in the design, and also a reason the product gets better with density rather than worse.
Finally, the graph gives a travel-time estimate and reality gives a different number, so a model corrects it using the time of day, the weather, historical error on that segment, and the parts a road graph does not model at all: finding the pickup point, parking, and the walk to the car. The pickup estimate is the one riders judge the product on, and it is mostly not a routing problem.
Payments, and failure in general
Payment spans the trip, so it cannot be a transaction. It is a saga: authorise a hold when the trip starts, capture when it completes, and compensate when something fails in between.
sequenceDiagram autonumber participant T as Trip service participant P as Payments participant G as Provider participant L as Ledger T->>P: authorise estimated fare, idempotency key P->>G: hold funds G-->>P: approved Note over T,P: the trip runs, the final fare differs from the estimate T->>P: capture the actual fare P->>G: capture G-->>P: settled P->>L: append the entries, driver and platform
The failures are all interesting. An authorisation declined before the trip is easy: refuse the request. A capture that fails after the trip is not, because the ride has already happened — the compensation is not a rollback but a debt recorded against the account, to be collected later. And the ledger is append-only: a correction is a new entry, never an edit, which is the property that makes disputes resolvable months later.
More broadly, this system's failure philosophy is that an in-flight trip is sacred and everything else may degrade. If the surge service is down, quote a flat rate. If the ETA service is down, use straight-line distance and a fudge factor. If the geo index is stale, match on positions a few seconds old. But a trip in progress must keep tracking, must complete, and must bill correctly, because there are two people in a car depending on it.
Geography helps: cities are almost entirely independent, so the system shards by city rather than by user, and a regional failure affects one place rather than everywhere. There is no query in this design that needs a global transaction, which is unusually convenient and worth exploiting deliberately.
What breaks first
- Location write rate. A quarter of a million writes a second growing linearly with drivers. Relieved by pinging less when stationary and by sharding the index by city, and it never touches a durable store on the hot path.
- Matching latency in dense cities. The batch window plus the assignment solve, in a city with thousands of concurrent requests. The lever is a shorter window with a smaller batch, trading match quality for speed.
- The road graph. Preprocessed graphs are memory-hungry and slow to rebuild when traffic shifts. Cities are independent, so the graph shards naturally, but a metropolitan area is indivisible.
- The payment provider. An external dependency with its own rate limits, and the one part of the system that cannot be scaled by adding hardware. Queue and retry with idempotency keys.
Recap
- The present is tiny and the past is enormous: fifty megabytes holds every driver's current position, while history is a terabyte a day. Keep the live index in memory and the history in a log nothing latency-sensitive reads.
- A location ping is disposable — the next one supersedes it — which licenses dropping points under load and makes an in-memory index acceptable, since it self-heals within one ping interval.
- Latitude and longitude range queries cannot be served efficiently by a B-tree, because an index orders by one dimension and the query constrains two.
- Every geospatial index interleaves the bits of the two coordinates so that a cell becomes a prefix and "nearby" becomes a range scan.
- Geohash is simplest, quadtrees adapt to density, S2 minimises distortion on the sphere, and H3's hexagons give six equidistant neighbours, which makes radius search and smoothing natural.
- Every grid has a boundary problem, so a query reads the target cell plus its ring and filters by true distance, widening the resolution when density is low.
- Greedy matching is locally sensible and globally poor; batching a few seconds of requests and solving the assignment together shortens actual waits and cuts cancellations.
- Score by estimated time to pickup rather than distance, and include the probability that the driver accepts.
- An offer holds the driver under a short lease; expiry releases them. Without it, two dispatchers can offer the same driver twice.
- The trip is a small strongly-consistent state machine with one active trip per driver enforced by a conditional write, idempotent transitions, and an event per change that everything else reads.
- Surge is a smoothed demand-over-supply ratio per cell with hysteresis and caps to stop flapping, blended across neighbours to avoid hard price boundaries, and quoted prices are honoured.
- ETA comes from a preprocessed road graph whose edge weights are estimated from the fleet's own pings, corrected by a model for the parts a graph does not capture, such as finding the pickup point.
- Payment is a saga: authorise at the start, capture at the end, compensate as a recorded debt when capture fails after the ride. Idempotency keys everywhere and an append-only ledger.
- Cities are independent, so shard by city; a regional failure is local and no operation needs a global transaction.
- Everything may degrade except an in-flight trip: flat pricing, straight-line ETAs and stale positions are all acceptable, and losing a trip in progress is not.
Questions
Try answering each one out loud before opening it. Lead with the one-line answer, then the reasoning, then one detail from a real system.
A million drivers ping every four seconds. Where do those writes go?
Into an in-memory index holding one record per driver, overwritten in place, plus an append-only log for history — never into a durable database on the request path.
- Current state for a million drivers is about 50 MB, so the live index fits comfortably in memory.
- The index needs no durability because drivers repopulate it within one ping interval after a restart.
- History is about a terabyte a day and is read only by analytics, traffic estimation and dispute resolution.
Recognising that a location ping is disposable is what licenses both the in-memory store and aggressive dropping under load.
Why can't you find nearby drivers with a query on latitude and longitude?
Because it is two range predicates and a B-tree index can only order by one dimension, so the database narrows on latitude and then scans every driver in that band — in a dense city, most of the fleet.
- Composite indexes do not help: the second column is only useful once the first is an equality match.
- Two-dimensional data needs an index that understands both dimensions simultaneously.
- The universal trick is to map two dimensions to one so that spatial locality becomes ordering locality.
That mapping is what geohash, S2 and H3 all are, differing mainly in cell shape and distortion.
Explain how a geospatial cell id is constructed.
Interleave the bits of latitude and longitude into a single value, so that a prefix of that value identifies a rectangular region — longer prefix, smaller cell — and points near each other usually share a prefix.
- Truncating the id zooms out, which is how a search widens when a cell holds too few drivers.
- Because it is just a sortable number or string, an ordinary index can serve prefix queries.
- The mapping is imperfect: two nearby points can still straddle a boundary and get very different ids.
S2 improves the locality by ordering cells along a Hilbert curve rather than by naive interleaving.
Compare geohash, quadtrees, S2 and H3.
Geohash is the simplest and works anywhere but distorts towards the poles; quadtrees subdivide where data is dense; S2 projects a cube onto the sphere and orders cells along a Hilbert curve for low distortion; H3 uses hexagons so that all six neighbours are equidistant.
- Fixed grids are easy to shard and cache, while quadtrees adapt better to wildly uneven density.
- Hexagons make radius search and smoothing natural, at the cost of not nesting perfectly between resolutions.
- All four need a neighbour search, because none of them solves the boundary problem.
Uber built and open sourced H3 for this workload, and it is now used well beyond ride hailing for per-area aggregation.
What is the boundary problem and how do you handle it?
Two points a metre apart can fall into different cells, so searching a single cell misses part of the neighbourhood; the fix is to search the target cell plus its surrounding ring and then filter by true distance.
- The filter is necessary anyway, since a cell is a rectangle or hexagon and the query is a circle.
- Hexagons help because all six neighbours are the same distance away, which makes the ring uniform.
- If the result set is too small, drop a resolution level and repeat, because density varies enormously between a city centre and a suburb.
Adaptive widening is the normal path rather than an edge case, which is worth designing for from the start.
Why is batched matching better than assigning the nearest driver immediately?
Because solving several requests together finds a globally better assignment: waiting a few seconds to match reduces the time riders actually wait for a car, and cuts cancellations, which cost far more than a slightly slower match.
- Greedy assignment can give a driver to one rider when a slightly later request would have been a much better fit.
- The batch is solved as an assignment problem minimising total expected wait.
- The trade is a couple of seconds of matching latency, which riders do not perceive the way they perceive the car's arrival.
It is a good example of optimising the metric the user feels rather than the one that is easy to measure.
Why score drivers by time rather than distance?
Because traffic, one-way systems and physical barriers make the nearest driver by straight-line distance frequently not the fastest to arrive — a car four hundred metres away across a motorway is not close in any useful sense.
- The score comes from the routing graph, whose edge weights reflect current speeds.
- Real dispatch also weighs the probability that a given driver accepts the offer.
- It may also consider the effect on supply elsewhere, which makes dispatch partly an economic decision.
This is why the ETA service is a dependency of matching rather than only a display feature.
How do you guarantee one driver is never assigned two rides?
Hold the driver under a short lease when the offer is made, and make the assignment a conditional write on the driver's record so that two concurrent dispatch attempts cannot both succeed.
- The lease expires by itself, so an unresponsive driver does not stall the rider's request.
- Enforcing uniqueness in application logic rather than at the store is what allows the race in the first place.
- A version number on the record fences a stale dispatcher that believes it still holds the lease.
This is the one part of the system that genuinely needs strong consistency, and it is small enough to afford it.
Why must trip state transitions be idempotent?
Because they are driven by a phone on a mobile network that will retry — a driver tapping "arrived" in a tunnel may send the transition three times — and applying it twice must not produce two events or two charges.
- A client-generated id per transition makes the retry recognisable.
- The trip row stays the single source of truth while every transition emits an event for everything downstream.
- Support tooling and analytics read the events, so the trip store never becomes a query surface.
It is the same pattern as the messaging article's client id, applied to a workflow rather than to a message.
How is surge computed, and how do you stop it flapping?
As a demand-over-supply ratio per cell over a short sliding window, smoothed exponentially, with hysteresis so that raising the multiplier needs a higher threshold than lowering it, and a cap on how fast it can move.
- Without hysteresis the multiplier oscillates as riders and drivers react to it — the control loop chases itself.
- Blending a cell's value with its neighbours' avoids a price cliff at an arbitrary boundary in the middle of a street.
- A quoted price is stored on the request and honoured, so surge affects the quote rather than the final bill.
Treating it as a control loop rather than a formula is what makes the stability mechanisms obvious.
How are ETAs computed quickly enough to use in matching?
The road graph is preprocessed with shortcut edges — contraction hierarchies and similar techniques — so a query visits thousands of nodes rather than millions, and edge weights come from live speeds estimated from the fleet's own location pings.
- A naive shortest-path search over a city graph is far too slow to run tens of thousands of times a second.
- Every driver pinging every four seconds is a traffic sensor, so the system's own data improves its estimates.
- A model corrects the graph's answer for the parts it does not model: pickup, parking and the walk to the car.
The pickup estimate is what riders judge the product on, and most of its error is not a routing error.
Why is payment a saga rather than a transaction?
Because it spans a period of real-world time and two systems: authorise a hold when the trip starts, capture the actual fare when it ends, and compensate if something fails in between — there is no transaction that can span a car journey.
- A capture that fails after the ride cannot be rolled back, because the ride happened, so the compensation is a recorded debt.
- Every call carries an idempotency key, since charging twice is the one unacceptable outcome.
- The ledger is append-only: corrections are new entries, which is what makes months-old disputes resolvable.
Authorise-then-capture is the standard shape for any payment whose final amount is not known at the start.
The surge and ETA services both fail. What should the system do?
Keep operating in a degraded mode: quote a flat rate without surge, estimate arrival from straight-line distance with a correction factor, and continue matching on positions that may be a few seconds stale.
- An in-flight trip must keep tracking and must complete correctly, because two people are in a car depending on it.
- Every non-essential dependency should have a defined fallback, decided in advance rather than during the incident.
- Degrading price accuracy is far cheaper than refusing rides.
Naming what is sacred and what may degrade is the part of the design that determines behaviour under failure.
How would you shard this system?
By city or metropolitan area, because trips, drivers, supply and pricing are almost entirely local, so no operation needs data from two shards and a regional failure affects one place.
- Sharding by user id would spread one city's drivers across every shard, making the nearby query a scatter-gather.
- The road graph shards along the same lines, though a metropolitan area cannot be split further.
- Cross-city concerns — the account, the payment method, the ledger — are a separate, much smaller global service.
Geography giving a natural shard key is a luxury most systems do not have, and it is worth exploiting explicitly.
How would the design change to support pooled rides?
The matching objective changes from "nearest available driver" to "best insertion into an existing route", so dispatch has to evaluate detours against the time cost imposed on riders already on board.
- A driver is no longer simply available or busy — they have a route with spare capacity and constraints.
- Batching becomes more valuable, since the algorithm needs several requests to find good pairings.
- ETA quality matters far more, because a bad detour estimate degrades every rider in the vehicle.
It is the same geospatial and state machinery with a much harder optimisation on top, which is why it was a later product.
What are the privacy obligations in a system like this?
Location traces are among the most sensitive data a system can hold, so retention must be bounded and stated, access audited, and analytics run on coarsened cells or aggregates wherever the use case allows.
- The history log is the sensitive artefact, not the live index, because a trace over time reveals far more than a position.
- Coarsening to a larger cell often preserves the analytical value while removing individual identifiability.
- This belongs in the design from the start, since retention decisions are hard to retrofit once pipelines depend on the data.
It is one of the few places where a design constraint comes from obligation rather than from load.