Designing Uber

1.1What it has to do

The core of Uber, the part that moves people, comes down to a short list:

1. Show nearby cars on the rider's map as soon as the app opens.
2. Match a request to a driver, and get the driver to accept it.
3. Estimate times: how long until the car arrives, and how long the trip will take.
4. Price the trip, including raising prices where demand outruns supply (surge).
5. Track the trip live for both rider and driver, from pickup to drop-off.
6. Charge the rider and pay the driver once the trip ends.

And the qualities it needs while doing that:

• Fresh: the system's idea of where each car is should be seconds old, not minutes.
• Fast: a match within a couple of seconds of tapping Request.
• Correct where it matters: one driver can't be assigned to two riders at once, and a trip that has started must never be forgotten.
• Available: a failing data centre mustn't strand riders mid-trip.

This list differs from WhatsApp's in one important way. WhatsApp's hard problem was delivering messages to the right place; Uber's is a question about space: which of the moving things are close to this point, and in what sense of close. Most of this case study is about answering that question quickly.

1.2How big is it?

Uber's own filings give the scale. In the quarter that ended in June 2026, the platform handled about 3.9 billion trips and had 208 million people using it each month. A record 10.2 million drivers and couriers earned money on it that quarter. Across 2025, Uber completed about 13.6 billion trips, more than 40 million a day. (These "trips" include food and package deliveries, not only rides.) It operates in over 70 countries and more than 15,000 cities.

The number that shapes the design most, though, is how often each car reports where it is. Every driver's phone works out its position from GPS satellites and sends it to Uber's servers every few seconds. Uber described this in 2015 as every four seconds, and its partner API still delivers driver locations at a four-second interval by default.

2.1The obvious design

The most obvious design is a database table with one row per driver: driver ID, latitude, longitude, and whether they're free. Each location update overwrites the driver's row. When Priya requests a ride, the server asks for the free drivers ordered by distance from Priya and takes the closest.

Both halves break at Uber's scale. The writes are the first problem: a quarter of a million updates a second to a database on disk, each one written durably even though it will be useless four seconds later. The reads are the second: "order by distance from Priya" means computing the distance from Priya to every free driver and sorting. An ordinary database index can't help, because an index sorts by one value, and distance from Priya isn't a value stored in any row; it depends on where Priya is.

So we need two things: a place to keep the latest positions that can absorb constant overwrites, and a way to find the drivers near a point without looking at all of them. The first is the easy part. Since only the latest position matters and it's replaced every few seconds anyway, it can live in memory. The rest of this section's trouble, finding nearby drivers without scanning everyone, takes the whole of the next section.

3.1Chop the map into cells

Here's an idea you'd probably come up with yourself. Divide the city into a grid of squares, say 500 metres on a side, and keep a list of the drivers currently inside each square. When Ravi's update arrives, compute which square he's in (divide his coordinates by 500 and round down) and move him into that square's list if he's crossed a line. When Priya requests, look only in her square and the eight squares around it.

This program tries it with a million drivers scattered over a 40 km by 40 km city, comparing it with checking every driver:

import math, random, time
random.seed(1)
 
# 1,000,000 drivers scattered over a 40 km x 40 km city
N, SIZE = 1_000_000, 40_000.0
drivers = [(random.uniform(0, SIZE), random.uniform(0, SIZE)) for _ in range(N)]
rider = (21_345.0, 18_210.0)
 
def dist(a, b):
    return math.hypot(a[0] - b[0], a[1] - b[1])
 
# 1. brute force: look at every driver
t = time.perf_counter()
best = min(drivers, key=lambda d: dist(d, rider))
brute_ms = (time.perf_counter() - t) * 1000
 
# 2. grid index: 500 m cells, look only in the rider's cell and its neighbours
CELL = 500.0
grid = {}
for d in drivers:
    grid.setdefault((int(d[0] // CELL), int(d[1] // CELL)), []).append(d)
 
t = time.perf_counter()
cx, cy = int(rider[0] // CELL), int(rider[1] // CELL)
nearby = [d for dx in (-1, 0, 1) for dy in (-1, 0, 1)
          for d in grid.get((cx + dx, cy + dy), [])]
best_grid = min(nearby, key=lambda d: dist(d, rider))
grid_ms = (time.perf_counter() - t) * 1000
 
print(f"brute force: {N:,} drivers checked, {brute_ms:.1f} ms")
print(f"grid index:  {len(nearby):,} drivers checked, {grid_ms:.3f} ms")
print(f"same driver found: {best == best_grid}, {dist(best, rider):.0f} m away")

brute force: 1,000,000 drivers checked, 81.7 ms
grid index:  1,456 drivers checked, 0.327 ms
same driver found: True, 24 m away

The grid found the same driver after looking at 1,456 drivers instead of a million, about 250 times faster (the exact times vary from run to run). The program has a deliberate shortcut: it assumes the nearest driver is within one cell of Priya, which is true here because the city is evenly packed with drivers. With sparse drivers, the search has to widen ring by ring until it finds someone.

That last caveat is the grid's real weakness, because real cities are not evenly packed. At 6 pm a 500-metre square in central Mumbai might hold hundreds of cars while one on the outskirts holds none. A single cell size is too coarse downtown, where every cell holds too many cars, and too fine in the suburbs, where Priya's search has to step through many empty cells. The fixes are smarter ways to cut space into cells, and there are four well-known ones.

3.2Geohash: a cell you can write as a string

A geohash turns a location into a short string, by repeatedly halving the world. The first step asks "is the point east or west of the middle longitude?" and records a 1 or a 0. The next asks "north or south of the middle latitude?", and so on, alternating, halving the remaining box each time. Every five of those bits become one character from a 32-character alphabet. Each extra character makes the box 32 times smaller.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"
 
def geohash(lat, lon, length=7):
    lat_lo, lat_hi, lon_lo, lon_hi = -90.0, 90.0, -180.0, 180.0
    bits, even, out = 0, True, ""
    for i in range(length * 5):
        if even:                      # even bits split longitude
            mid = (lon_lo + lon_hi) / 2
            bit = lon >= mid
            lon_lo, lon_hi = (mid, lon_hi) if bit else (lon_lo, mid)
        else:                         # odd bits split latitude
            mid = (lat_lo + lat_hi) / 2
            bit = lat >= mid
            lat_lo, lat_hi = (mid, lat_hi) if bit else (lat_lo, mid)
        bits = bits * 2 + bit
        even = not even
        if i % 5 == 4:
            out += BASE32[bits]
            bits = 0
    return out
 
places = {
    "Pune station":   (18.5286, 73.8743),
    "Koregaon Park":  (18.5362, 73.8940),
    "Mumbai CST":     (18.9398, 72.8355),
}
for name, (lat, lon) in places.items():
    print(f"{name:14} {geohash(lat, lon)}")

Pune station   tek93j1
Koregaon Park  tek93qr
Mumbai CST     te7g9rv

Pune station and Koregaon Park, about two kilometres apart, share the first five characters, tek93. Mumbai, 120 km away, shares only te. That's the property that makes geohashes useful: nearby places usually share a long prefix, so "drivers near Priya" becomes "drivers whose geohash starts with tek93", a prefix search that any ordinary sorted index, in Redis, Postgres or Cassandra, can answer.

The word "usually" in that paragraph is the catch. The halving traces a zig-zag path through space called a Z-order curve, and where the curve jumps, two points a few metres apart on either side of a cell boundary can have completely different prefixes. A geohash search therefore always has to check the eight neighbouring cells too, just like the grid. Geohash cells also get narrower towards the poles, so a "cell" isn't the same size everywhere.

3.3Quadtrees and S2: cells that adapt

A quadtree fixes the density problem directly. Start with one square covering the city. Whenever a square holds more than some limit of drivers, split it into four equal squares, and keep splitting until every square is below the limit. Busy downtown streets end up covered by many small squares, and empty suburbs by a few big ones.

Google's S2 library takes the hierarchy of squares and makes it global and fixed. It projects the Earth onto the six faces of a cube and divides each face into a quadtree of cells, 31 levels deep. Each cell gets a 64-bit ID, numbered along a Hilbert curve, a path that winds through every cell without the big jumps of the Z-order curve. Cells that are close on the curve are close on the ground, so a range of IDs covers a compact area, which suits a sorted index well. According to write-ups of a 2015 Uber talk, Uber's dispatch system used S2 cells at level 12, each a few square kilometres, to organise its driver index at the time.

3.4H3: hexagons

In 2018 Uber open-sourced its own grid system, H3, and it isn't made of squares at all. H3 covers the Earth with hexagons.

The reason is the neighbours. Look at a square cell: four neighbours share an edge with it, and four more touch it only at a corner, about 1.4 times further away. Any calculation that spreads out from a cell, such as "demand in this area and the areas around it", has to treat those two kinds of neighbour differently. A hexagon has six neighbours, all sharing an edge and all at the same distance. Uber's 2018 post puts it plainly: hexagons have only one distance between a cell's centre and its neighbours', where squares have two.

H3 offers 16 resolutions, from cells the size of continents down to cells under a square metre. Each finer resolution has cells about a seventh the area of the one above:

A city-scale question uses resolutions around 7 to 9: a resolution-8 hexagon is roughly a neighbourhood, half a kilometre across. Which resolution Uber uses for each job isn't published.

"Find drivers near Priya" in H3 becomes: find Priya's cell, then ask for every cell within k steps of it. That operation is called gridDisk (it was named kRing in earlier versions). With k = 1 it returns Priya's cell and its 6 neighbours, 7 cells. In general it returns 3k² + 3k + 1 cells, so 19 for k = 2, and the search widens ring by ring until enough drivers turn up.

Hexagons have one drawback, and it's built into geometry: you can't divide a hexagon exactly into seven smaller hexagons. H3's children cover their parent only approximately, slightly rotated, where S2's four children tile their parent square exactly.

3.5Inside an H3 cell ID

An H3 cell is identified by a single 64-bit integer, which is what makes it cheap to store, hash and compare. The bits are laid out like this:

So an ID is literally a path: start from one of the 122 base cells and take one of seven turns at each resolution. Finding a cell's parent means setting the resolution field one lower and blanking the last used digit, a couple of bit operations. That's also what makes compaction possible: when all seven children of a parent are in a set, replace them with the parent. Uber's 2018 post gives the example of California: 10,633 cells at resolution 6, or 901 cells once compacted into a mix of resolutions.

4.1Too much for one machine

We now know how to find nearby drivers in a grid. The next question is where that grid lives. Holding the latest position of a few million drivers takes only a few hundred megabytes, which fits on one machine easily. The problem is the traffic: a quarter of a million updates a second, plus every rider's search, plus the fact that one machine is one machine, and when it fails, nobody can get a ride anywhere.

So the index is split across many machines, and the natural way to split it is by cell. Each machine owns some set of cells and holds the drivers currently inside them. Ravi's location update goes to whichever machine owns his current cell. Priya's search goes to the machines that own the cells in her gridDisk, usually just one or two, since nearby cells tend to be on the same machine.

One property of this workload makes failures far less painful than usual. Because every driver resends their position every four seconds, a node that crashes and restarts empty is fully repopulated within a few seconds, without any backup or replica. The data heals itself. That's a big part of why it can live in memory at all.

4.2Who owns which cells: Ringpop

Something has to decide which node owns each cell, and keep every node and gateway in agreement as nodes join, crash and restart. Uber built and open-sourced a library for this in 2015 called Ringpop, and the motivating case was exactly this driver-location service.

Ringpop combines two ideas from chapters 29 and 30. The first is a consistent hash ring: each node is placed at several points on a circle of hash values, and each key, here a cell ID, belongs to the first node clockwise from the key's hash. When a node leaves, only its keys move, to its neighbours on the ring; everyone else's stay put. Ringpop keeps the ring in a red-black tree, so finding a key's owner takes a logarithmic number of steps.

The second is SWIM gossip for membership: nodes ping each other at random, ask others to ping a node that doesn't answer, mark it suspect and then faulty, and spread those changes by piggybacking them on their pings. So there's no central coordinator; every node keeps its own copy of the membership list and the copies converge.

When a request arrives at a node that doesn't own the key, that node forwards it to the owner. Uber called this "handle or forward". Any node can take any request, which keeps clients simple.

5.1Nearest isn't quickest

Dispatch now has a list of candidate drivers near Priya. The next mistake to avoid is picking the closest one in a straight line. Pune has a river running through it, and the nearest car in a straight line might be across a bridge that's twenty minutes away at rush hour, while a car twice as far away is on Priya's side of the river and three minutes from her.

So matching is done on estimated time of arrival (ETA), computed along the actual road network, not on straight-line distance. Uber's own description of its marketplace says it directly: closest doesn't always mean quickest, because of traffic, overpasses, rivers and other geography. The straight-line search from section 3 still has a job, though. It cheaply narrows millions of drivers down to a few dozen, and only those few dozen get the expensive road-based ETA calculation, which section 6 covers.

5.2One rider at a time, or a batch?

The second mistake is subtler. Suppose two riders request within a second of each other, and two free drivers are nearby.

This short program does both: greedy in order of request, and a search over every possible pairing for the lowest total wait.

from itertools import permutations
 
# minutes for each driver to reach each rider
eta = {
    ("Ravi", "Priya"): 2, ("Ravi", "Sam"): 3,
    ("Meena", "Priya"): 4, ("Meena", "Sam"): 9,
}
riders, drivers = ["Priya", "Sam"], ["Ravi", "Meena"]
 
# Greedy: each rider, in order of request, takes the nearest free driver
free, greedy = set(drivers), {}
for r in riders:
    d = min(free, key=lambda d: eta[(d, r)])
    greedy[r] = d
    free.remove(d)
 
# Batched: try every assignment, keep the lowest total wait
best = min(permutations(drivers),
           key=lambda ds: sum(eta[(d, r)] for d, r in zip(ds, riders)))
batched = dict(zip(riders, best))
 
for name, plan in [("greedy", greedy), ("batched", batched)]:
    waits = {r: eta[(d, r)] for r, d in plan.items()}
    print(f"{name:8} {plan}  waits {waits}  total {sum(waits.values())} min")

greedy   {'Priya': 'Ravi', 'Sam': 'Meena'}  waits {'Priya': 2, 'Sam': 9}  total 11 min
batched  {'Priya': 'Meena', 'Sam': 'Ravi'}  waits {'Priya': 4, 'Sam': 3}  total 7 min

Pairing riders with drivers to minimise the total cost is a classic problem called bipartite matching, or the assignment problem. Trying every pairing, as the program does, works for two riders and two drivers, but the number of pairings grows factorially, so real solvers use algorithms such as the Hungarian algorithm, which solves it in polynomial time, or min-cost flow. Uber hasn't published which solver it uses.

5.3One driver, one trip

The batch gives Ravi to Sam. Dispatch sends Ravi an offer, Ravi's phone shows it with a countdown, and Ravi taps Accept. If Ravi ignores it, the offer expires and Sam goes back into the next batch.

Here, for the first time, correctness matters more than speed. Two dispatch processes, perhaps handling neighbouring areas, must never offer Ravi to two riders at once, and once Ravi accepts, the trip must exist and be remembered whatever fails. Think of each driver and trip as a small state machine, where only certain moves are allowed, and each move must happen at most once:

The state names here are illustrative; Uber's internal ones aren't public. What is public is how its thinking changed. Uber's original trip platform was built, in its engineers' words, on the premise of trading consistency for availability and latency, using Node.js, Ringpop, Cassandra and Redis. In 2021 Uber described rebuilding it in Java on Google Cloud Spanner, a database that offers transactions across shards, and modelling each driver, rider and trip as a hierarchical state machine. The rebuilt platform served over a million concurrent users in over 10,000 cities.

6.1The road network as a graph

Matching needs an ETA for each candidate driver, and the app shows ETAs all the time: for the car to arrive, for the trip, for the price estimate. To compute one, Uber models the road network as a graph: every intersection is a node, every stretch of road between two intersections is an edge, and each edge's weight is how long it takes to drive. Turn restrictions and the cost of turning are modelled too. An ETA is then the length of the shortest path between two nodes.

The textbook algorithm for shortest paths is Dijkstra's algorithm, which explores outward from the start in order of distance until it reaches the destination. On a city graph with millions of edges, that exploration touches a large part of the city for every query. A* speeds it up by preferring nodes in the direction of the destination, and Uber's 2015 post on its routing engine measured a city-scale A* query with live traffic at about 120 milliseconds. That sounds fast, but it's far too slow when every request needs dozens of ETAs and the whole platform asks for hundreds of thousands a second.

The standard trick for fast routing is to precompute. Contraction hierarchies rank the nodes by importance and add "shortcut" edges that skip over unimportant nodes, so a query can climb quickly onto major roads and come back down near the destination, answering in milliseconds. The catch is the precomputation: Uber's post notes that building the contracted graph for all the roads of the world takes about 12 hours, which makes folding in live traffic, which changes by the minute, very hard.

DeepETA is worth a moment, because it's a neat design pattern. The routing engine computes an ETA as a sum of segment travel times. Then a neural network, which Uber says replaced one of the largest gradient-boosted tree ensembles in the world, predicts how wrong that sum will be, given the time of day, the type of request and other features. Learning only the correction keeps the model's job small and lets the routing engine keep doing what it's good at. Uber's ETAs feed fares, pickup estimates, matching and delivery planning, which is why DeepETA is described as its highest-traffic model.

7.1Supply and demand on a map

It's raining, a concert has just ended, and two hundred people near the stadium open the app at once. There are thirty drivers nearby. If prices stay normal, most of those people get no car and the drivers stay put. Raising the price in that area does two things at once: some riders decide to wait or walk, and drivers from nearby areas head towards the stadium. That's surge pricing, and it's computed per area.

Uber's 2018 H3 post says it plainly: surge is calculated by measuring supply and demand in hexagons in each city. A later post on Uber's real-time analytics system, Gairos, describes the calculation as querying the number of requests and the number of available drivers for a hexagon, with over a million events a second flowing into that system. This is where hexagons earn their keep: smoothing a surge value across a hexagon and its six equidistant neighbours avoids sharp price cliffs at cell edges, and treats every direction the same.

Uber's 2021 paper on its real-time data infrastructure describes surge's choices directly: the pipeline favours fresh data and availability over consistency, and events that arrive late for their window are dropped. It runs in several regions at once, and if one region fails, the surge calculation fails over to another. A price computed from slightly incomplete counts a few seconds ago is far better than no price at all.

8.1Pushing updates to phones

While Ravi drives to Sam, Sam's app shows the car moving and the ETA counting down, and Ravi's app shows directions. The simple way to build this is for each app to ask the server every few seconds for updates. Uber did exactly that at first, and by its own account, at one point 80% of the requests to its API gateway were these polling calls, most of them answering "nothing new".

Uber's fix, described in 2020, was a push platform called RAMEN: each app keeps one long-lived connection open, and the server pushes updates down it when something changes, with a heartbeat every four seconds to keep the connection alive and detect failures. It handled over 1.5 million concurrent connections and over 250,000 messages a second. In 2022 Uber moved it to bidirectional gRPC streams, because with the earlier one-way design the server couldn't tell for up to 30 seconds whether a message had arrived.

That's the same decision WhatsApp made in its section 2, for the same reason: when the server knows first that something has changed, it should tell the phone, not wait to be asked.

8.2Where trips are stored

A trip, once accepted, is a record that must never be lost: it's the basis of the fare, the driver's pay, receipts, disputes and safety investigations. In 2014 Uber outgrew a single Postgres database and built Schemaless, a layer on top of many MySQL databases. Its data model was an append-only map from (row ID, column name, version) to an immutable JSON value. A trip's row had columns such as BASE for the trip itself, STATUS, NOTES and FARE ADJUSTMENTS, and every change wrote a new version instead of updating in place. The data was split across 4,096 fixed shards, each a primary MySQL database with two replicas.

That design later evolved into Docstore, which added Raft-based replication within each partition and strict consistency per partition, at a scale of tens of millions of queries a second. And as section 5.3 described, the trip-handling platform itself moved onto Spanner in 2021 for transactions across shards.

9.1The phone remembers the trip

Sam is halfway to the airport when the data centre handling Pune goes dark. The trip is in progress, Ravi is driving, and the servers that knew about the trip are unreachable.

Uber's 2016 description of its stack says that each city is assigned to the closest data centre and backed up in another, and that if one data centre fails, trips fail over to another. The interesting part is what makes that possible for trips already in progress. According to write-ups of a 2015 Uber talk, the dispatch system periodically sent each driver's phone an encrypted digest of the trip's state. If the data centre failed, the phone's next request would land in the backup data centre, which wouldn't recognise the trip, ask the phone for its digest, and rebuild the trip's state from it. The phone, which is present for the whole trip anyway, acts as a backup of its own trip.

On the app side, Uber described in 2020 a small state machine in its mobile client with four states, primary, failover, backup and recovery, that decides which network path to use and moves back only after test requests succeed.

10.1Every box, and why it's there

10.2From top to bottom

11.1Failures this design has to survive

11.2The tradeoffs, in one table