Step 2 of 14 · 1 min

The location stream

Start with napkin math (lesson 1.3), for a larger Gaadi, across several cities:

200,000 drivers online at peak
1 location update every 4 seconds
→ 50,000 updates a second

What do those updates need?

• The latest position of each driver has to be quick to query by area. That's needed for matching.
• The position of drivers on a trip has to reach the rider's app, so they can watch the car approach.
• The history of each trip's route is needed afterwards, for the fare and for disputes, but not in real time, and not every 4 seconds for drivers who aren't on a trip.

So the stream splits by purpose:

• Latest positions live in memory, not in the database: in Redis, or in a dedicated in-memory location service, partitioned by city (more on that below). Each update overwrites the driver's previous position. Nothing is written to disk on every update. If the location store loses a node, drivers' positions are back within 4 seconds, when they next report. This is data that's useful for seconds and worthless after a minute, so it's treated that way.
• Updates are also appended to a log (Kafka, lesson 4.1), which feeds route history for trips, analytics, and anything else that wants them later. Writes to a log are cheap appends.
• The database stores trips, not positions: a trip's start, end, route summary and fare, written once per trip, not every 4 seconds.

That removed 10,000 writes a second from Gaadi's database the week it shipped.

Step 3 of 14 · 3 min

Finding things near a point

The harder question: "which available drivers are within 2 km of this rider?"

A normal B-tree index (lesson 1.4) sorts by one column at a time. An index on latitude finds drivers in a horizontal band across the whole city; an index on longitude, a vertical band. Neither finds a small circle around a point. What's needed is a way to turn two-dimensional closeness into something an index can look up quickly.

The answer, in every version, is to divide the map into cells, give each cell an ID, and index drivers by the cell they're in. To find drivers near a rider, look in the rider's cell and the cells around it.

Geohash

A geohash turns a latitude and longitude into a short string by repeatedly halving the world: is the point in the west or east half? The north or south half of that? And so on, alternating. Each answer is a bit, and the bits are written in a compact base-32 alphabet.

The useful property: points close together usually share a long prefix. Two points in the same neighbourhood of Pune might both start with tek3p. Longer strings mean smaller cells: roughly, 5 characters is a cell a few kilometres across; 6 characters is about 1.2 km by 0.6 km; 7 characters, about 150 m.

So "drivers near this rider" becomes:

1. Compute the rider's geohash at a suitable precision, say 6 characters.
2. Look up drivers whose geohash starts with that cell's ID, and with each of the 8 neighbouring cells' IDs.
3. Calculate real distances for just those drivers, and pick the closest.

Why the neighbours? Because cells have edges. A rider standing near the edge of their cell might be 20 metres from a driver in the next cell, whose geohash shares a much shorter prefix. Searching the 3 × 3 block of cells around the rider covers that.

Redis has this built in: GEOADD stores a member at a position (internally, a geohash in a sorted set), and GEOSEARCH finds members within a radius. Gaadi's first fix used exactly that, one key per city.

Grids, quadtrees and hexagons

Geohash is one of several ways to divide the map, each with trade-offs:

• A fixed grid (say, 500 m squares) is the simplest: compute the cell by rounding coordinates. It's fine within one city.
• A quadtree splits busy areas into smaller cells and leaves quiet areas as big cells, so each cell holds a similar number of drivers. Good when density varies a lot, like a dense city centre and empty outskirts.
• Google's S2 divides the Earth's surface into cells along a space-filling curve, so cells that are close in ID are close on the map. Used widely in Google's own systems.
• Uber's H3 uses hexagons. Every neighbour of a hexagon is the same distance from its centre (squares have 4 close neighbours and 4 diagonal ones further away), which makes "everything within k rings of this cell" a clean, even approximation of a circle. It's popular for analysing demand and pricing by area.

For "find drivers near a point," any of these works well. The main choice is cell size: too big, and each search checks too many drivers; too small, and a search needs many cells to cover a useful radius. Many systems keep a couple of sizes and widen the search ring by ring until enough drivers are found.

Step 4 of 14 · 2 min

Matching without double-booking

Finding nearby drivers gives a list of candidates. Now one of them has to be assigned, and this is where Gaadi's double-booking came from.

Two riders, a few hundred metres apart, requested cars at the same moment. Both searches returned driver 8812 as the closest available. Both matching processes then did "check that she's available, then assign her," and since both checked before either assigned, both succeeded. Lesson 5.3 called this out as the classic "check, then act" mistake, and lesson 1.4 showed the fix: make the check and the claim a single atomic step.

Gaadi's driver state lives in the location service, partitioned so that each driver belongs to exactly one place. Claiming a driver is a conditional update there:

claim driver 8812 for ride R51 IF her state is "available"

Only one claim can succeed; the other matching process sees "already taken" and moves on to its next candidate. In Redis, this can be a small Lua script (lesson 6.3) that checks and sets the driver's state together; in a database, it's UPDATE … WHERE state = 'available' and checking how many rows changed.

Asking the driver

Even after a successful claim, the driver has to accept. The claim reserves her with a short expiry (say, 15 seconds). Her app shows the request. If she accepts, the ride is confirmed. If she declines or doesn't respond in time, the reservation expires, she becomes available again, and matching tries the next candidate. The expiry is important: without it, a driver whose phone lost signal would be stuck "reserved" forever (lesson 6.5's lease idea, at a small scale).

Better matches by waiting a moment

Matching each rider the instant they ask ("greedy" matching) is simple, but can be poor overall. If two riders request at almost the same time, giving the closest driver to whoever asked first can leave the second with a driver much further away, when swapping would have been better for both.

Large ride-hailing companies often batch matching: collect requests and available drivers in an area for a second or two, then solve the assignment for the whole batch at once, minimizing total pickup time. The batch window is a trade-off between waiting a moment and getting better matches. Gaadi used greedy matching at first, and moved to two-second batches in its busiest cities.

Step 5 of 14 · 1 min

Partitioning by city

Lesson 5.1's partitioning question has an unusually clean answer here: almost nothing crosses city lines. A rider in Pune is matched with drivers in Pune; their trip happens in Pune. So Gaadi partitioned its location service, matching and live trip state by city, with each city's data in its nearest region (lesson 5.5).

Large cities get split further, into zones, each with its own partition of the location service. A search near a zone boundary asks both zones, just like the neighbouring-cells trick, one level up.

Step 6 of 14 · 1 min

Hot spots

Most of the time, drivers and riders are spread across a city. Then a match ends at a stadium. Fifty thousand people come out of the same few streets at once, and thousands request rides in the same few cells within minutes.

That's lesson 4.5's hot-key problem, in geography: a few cells receive a burst of searches and claims, and the drivers near them receive a flood of requests. What helps:

• Small cells and zone partitions, so the hot area is a small share of one partition rather than a whole city's worth of load on one node.
• A queue for demand, like a virtual taxi rank: riders in the hot area join a queue and are matched in order as drivers arrive, instead of every rider hammering the same few drivers with simultaneous claims.
• Surge pricing, which is a market mechanism rather than an engineering one: higher prices in a cell with many more requests than drivers both reduce demand and attract drivers from nearby. It's computed per cell (often hexagons) from recent supply and demand, using exactly the cell structures above.

Step 7 of 14 · 1 min

ETAs follow roads

"The nearest driver" by straight-line distance is often not the fastest to arrive: across a river, the other side of a highway, or stuck in traffic. Real ETAs come from a road graph: intersections as nodes, road segments as edges, each with a current travel time based on live traffic (estimated from the same driver location stream). Finding the fastest route is a shortest-path problem on that graph.

Computing a full route for every candidate driver on every request would be too slow, so systems use a quick estimate to narrow candidates (straight-line distance, or precomputed travel times between cells), then compute real routes for the best few. Routing engines precompute shortcuts across the graph so a city-scale route takes milliseconds rather than seconds.

Step 8 of 14 · 1 min

Trips: the part that must not be lost

Locations can be lossy. Trips can't. A trip moves through a series of states: requested, driver assigned, driver arrived, in progress, completed, paid. Each transition is written durably (in the city's database partition) as it happens, and the money side goes through a payment flow like lesson 7.3's.

Phones lose connection all the time in the middle of trips: in underground car parks, in tunnels, on the edge of town. So the driver's app records the route locally and uploads it when it can, and the server never assumes "no update" means the trip ended. A trip is completed only by an explicit event, retried until acknowledged (with an idempotency key, lesson 1.5).

Step 9 of 14 · 1 min

From the real world: keeping a city in memory

This lesson put Gaadi's driver state in memory, partitioned by place. Uber described the same choice in 2015, when it open-sourced Ringpop, the library its dispatch services used to divide work between servers.

The problem: dispatch needs very fast reads and writes of the current state of every driver and rider in an area, many times a second. A database round trip for every location update and every match is too slow, and locking across servers to avoid double-booking is worse. So each dispatch server owns some areas of the map and keeps everything about them in its own memory.

Ringpop combines two ideas from this course:

• Consistent hashing (lesson 5.2) decides which server owns each area. Any server can receive a request; it looks at the ring and forwards the request to the owner.
• SWIM gossip decides who's in the ring. Servers ping each other in a randomized pattern and spread news of failures; when a server stops answering, the others notice within a few rounds and its areas move to neighbours on the ring. Drivers in those areas send their state again within seconds, so nothing durable is lost.

Because one process owns an area, matching in that area needs no distributed locks: the owner just decides, in memory. That's the same "single writer per partition" idea as lesson 4.1's log partitions. The trade-off is that a server failure briefly loses in-memory state for its areas, which is acceptable for driver positions (they're re-sent every few seconds) and not for trips (which this lesson stored durably).

Step 10 of 14 · 1 min

Going deeper: matching in batches

"Give each rider the nearest available driver" is a greedy rule: it makes the best choice for each request as it arrives. It's simple and fast. It's also measurably worse than it could be, because a choice that's best for one rider can be bad for the next.

Rider 1 asks first and gets driver A, two minutes away. One second later, rider 2 asks, and the only free driver left is B, twelve minutes away. Total waiting: 14 minutes. If both requests had been considered together, rider 1 could have taken B (3 minutes) and rider 2 taken A (4 minutes): 7 minutes total, and nobody waits 12.

Batched matching collects requests and free drivers for a short window, a second or two, then solves the assignment for the whole batch at once: choose pairs to minimize total pickup time (or a score that also weighs rider waiting time, driver idle time and fairness). That's the classic assignment problem, solved exactly by the Hungarian algorithm or as a min-cost flow, or approximately for very large batches. Ride-hailing companies have published research on batched dispatch (DiDi's 2018 paper on large-scale order dispatch is a well-known one), and food delivery companies use the same idea for assigning couriers.

The design questions it raises are good interview material:

• How long is the window? Longer windows find better matches but add waiting before anyone is matched. One to two seconds is usually invisible to riders.
• Where does it run? Per city, or per area within a city (the partitions above), so each batch is small enough to solve quickly.
• What about requests near area boundaries? Include nearby drivers from neighbouring areas as candidates, with an owner for each driver so two areas can't both assign the same one.

Step 11 of 14 · 1 min

What Gaadi built

• Locations in memory, partitioned by city and zone, overwritten on each update and expired if a driver goes quiet. Also appended to a log for history and analytics.
• A cell-based index (geohash in Redis at first, later H3 hexagons) to find drivers near a point by searching the rider's cell and its neighbours.
• Atomic claims on a driver's state, with a short reservation while the driver decides.
• Batched matching in the busiest cities.
• Demand queues and surge pricing per cell for events.
• Road-based ETAs for the shortlisted drivers.
• Durable trip state with explicit, idempotent transitions.

Double-booked drivers dropped to zero, and the median time from request to driver assigned went from 9 seconds to under 2.

Step 12 of 14 · 1 min

If you're here for an interview

"Design Uber" (or Ola, or Lyft) is a very common question. Strong answers:

• Estimate the location stream and keep latest positions in memory, not in the main database.
• Explain a spatial index: geohash, quadtree, S2 or H3. Search the rider's cell and its neighbours, then compute real distances.
• Make the claim atomic, so a driver can't be given to two riders, and use a reservation with an expiry while the driver accepts.
• Partition by city or region, and talk about hot spots at events.
• Mention ETAs on the road graph, and durable trip states.

Step 13 of 14 · 2 min

Try these yourself

Step 14 of 14 · 1 min

Further reading

• Uber Engineering, "H3: Uber's Hexagonal Hierarchical Spatial Index" (2018).
• Redis documentation on geospatial commands (GEOADD, GEOSEARCH).
• The S2 Geometry library's documentation, for how S2 cells work.
• Any introduction to Dijkstra's algorithm and contraction hierarchies, for how routing engines compute ETAs quickly.
• Uber Engineering, "Introducing Ringpop" (2015) and the Ringpop documentation; Abhinandan Das, Indranil Gupta and Ashish Motivala, "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol," DSN 2002.
• Zhe Xu et al., "Large-Scale Order Dispatch in On-Demand Ride-Hailing Platforms: A Learning and Planning Approach," KDD 2018.