Tap “Book” and within seconds a driver a few hundred metres away accepts. “Design Uber” (or Ola, or a food-delivery app's rider assignment) is a frequently reported question at Uber, Amazon, Swiggy and Zomato. It's the course's geospatial problem: how do you search “near me” across a million moving points, hundreds of thousands of times a second?
Step 1 · Requirements
- Functional: riders request a ride and see nearby cars; the system matches a driver; both see each other live on the map; fare estimate; trip history; payment.
- Non-functional: match within seconds; location updates handled at massive write rates; never assign one driver to two riders; highly available in every city.
- Out of scope (say it): route calculation internals (we use a maps/ETA service), driver onboarding, ratings.
Step 2 · Estimates
- Location writes: 1 million active drivers × one update every 4 s = 250,000 writes/s. Each is tiny (driver ID, lat, lng, time ≈ 50 bytes), so only ~12 MB/s, but the write rate is the challenge.
- Ride requests: 20 million trips a day ≈ 230/s average, several times more at rush hour or when it rains.
- Memory: latest positions for 1M drivers ≈ 50 MB. It fits in RAM easily; shard by city/region anyway for load and isolation.
Step 3 · API
Driver app → PUT /drivers/me/location { lat, lng, heading, ts } (every ~4 s, or over a WebSocket)
Rider app → POST /rides { pickup, dropoff } → { rideId, fareEstimate }
Driver app ← offer { rideId, pickup } → POST /rides/{id}/accept | decline
Both apps ← live updates over WebSocket: driver position, ETA, ride statusStep 4 · Design
Finding nearby drivers: cut the map into cells
Squares are drivers (dark ones get checked), the dot is the rider. Tap anywhere on the map:
🎮 Find drivers near a rider
Rider · cell (4, 3)
Drivers in the whole city: 20
In the rider's own cell: 1
In cell + 8 neighbours (checked): 5
- Driver 6 · 400 m → offer the ride
- Driver 14 · 405 m
- Driver 7 · 498 m
- Driver 16 · 986 m
Tap near a cell's edge. The closest driver is often in the next cell, which is why we search the rider's cell plus its 8 neighbours. Instead of measuring distance to all drivers in the city, we check only a handful.
A geohash is one way to name those cells: it turns a latitude and longitude into a short string, and nearby places share a prefix. Store drivers under their geohash and “who is near me?” becomes a few key lookups:
BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"
def geohash(lat: float, lng: float, length: int = 7) -> str:
"""Turn a location into a short string; nearby places share a prefix."""
lat_lo, lat_hi = -90.0, 90.0
lng_lo, lng_hi = -180.0, 180.0
code, bits, ch, even = [], 0, 0, True
while len(code) < length:
if even: # even bits split longitude, odd bits split latitude
mid = (lng_lo + lng_hi) / 2
if lng >= mid:
ch = (ch << 1) | 1
lng_lo = mid
else:
ch <<= 1
lng_hi = mid
else:
mid = (lat_lo + lat_hi) / 2
if lat >= mid:
ch = (ch << 1) | 1
lat_lo = mid
else:
ch <<= 1
lat_hi = mid
even = not even
bits += 1
if bits == 5: # every 5 bits = one base32 character
code.append(BASE32[ch])
bits, ch = 0, 0
return "".join(code)
print(geohash(57.64911, 10.40744, 11)) # u4pruydqqvj (a well-known test value)
print(geohash(12.9716, 77.5946, 6)) # tdr1v9 (Bengaluru city centre)
print(geohash(12.9750, 77.6050, 6)) # tdr1vf (~1 km away: same first 5 characters)| Index | How it works | Good | Watch out |
|---|---|---|---|
| Geohash | Fixed grid of rectangles named by strings | Simple; works as a database or Redis key | Cells are the same size in busy and empty areas |
| Quadtree | Split a square into 4 only where it's crowded | Adapts to density | Must be rebuilt/updated in memory as drivers move |
| H3 (Uber's open-source grid) | Hexagons at many resolutions | All 6 neighbours are equally far; great for pricing zones | Library dependency |
Matching and the trip lifecycle
- Get available drivers in the rider's cell + neighbours (widen the ring if too few).
- Rank by ETA from a maps service. A driver 300 m away across a river may be 15 minutes out.
- Reserve the best driver atomically (available → reserved) so no other request can take them.
- Send the offer; if declined or no answer in ~10 seconds, release and try the next driver.
- Trip states: requested → matched → driver arriving → in progress → completed (or cancelled). Each change is stored and pushed to both apps.
Step 5 · Scale and reliability
- Shard by geography: each city or region has its own location and matching servers; a rider in Pune never needs Delhi's drivers.
- Only the latest location matters: overwrite in memory; stream the full history to a log for analytics, fraud checks and fare disputes.
- Hot zones: airports and stadiums at event end: use smaller cells (higher geohash precision or H3 resolution) where it's dense.
- Surge pricing: per cell, compare open requests with available drivers; raise prices where demand outstrips supply to attract drivers.
- Payments: charge after the trip asynchronously with idempotency keys, so a retry never charges twice.
- Failures: if a location server restarts, drivers' next pings (within seconds) rebuild the index. The data heals itself.
🧠 PATH memory card
Remember the ride matching design for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
An old auto-rickshaw radio dispatcher with a wall map divided into squares and a pigeonhole for each. Every few minutes drivers radio in where they are, and their name card moves to that square's pigeonhole. When a call comes in, the dispatcher checks the caller's pigeonhole and the eight around it, picks the driver who can get there fastest, and radios the offer.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Ping, Bucket, Search neighbours, Offer”
- Ping→Driver location every few seconds (~250k writes/s for 1M drivers)
- Bucket→Geospatial index: geohash / quadtree / H3 cell → drivers
- Search neighbours→Rider's cell + 8 neighbours, widen if empty
- Offer→Rank by ETA, reserve atomically, timeout → next driver
- Pigeonholes in memory→Only the latest location matters; history goes to a log
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Rider at Bengaluru centre → geohashtdr1v9. Look up drivers intdr1v9and its 8 neighbours → 6 drivers. Maps service ETAs: 3, 4, 7, 9, 12, 15 min. Reserve driver A (available → reserved ✓), send the offer. A declines → release, reserve driver B → accepts → ride state matched, both apps get live positions over WebSocket. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 8 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Follow-up questions interviewers ask
- “Shared rides (pool)?” Matching becomes a routing problem: find a driver whose current route can pick up another rider with a small detour.
- “GPS is noisy?” Snap locations to roads (map matching) and smooth jumps before showing them.
- “Network drops mid-trip?” The app buffers locations and resends; the server trusts the trip state machine, not single messages.
Where to go next
Uber must never give one driver to two riders. The final part is the ultimate “don't sell the same thing twice” problem, with millions of fans clicking at the same second: design BookMyShow. Grid search feels like BFS? It is: review BFS vs DFS.
Key takeaways
- ✓Drivers stream locations; keep only the latest per driver, in memory.
- ✓Index locations by map cells: geohash, quadtree or H3.
- ✓Search the rider's cell plus neighbours; rank candidates by ETA.
- ✓Reserve a driver atomically before offering; time out and move on.
- ✓Shard by geography; stream location history to cheap storage; charge asynchronously and idempotently.
Frequently asked questions
How does Uber find nearby drivers?
Every active driver's app sends its location every few seconds. The location service stores the latest position in memory, indexed by a grid of map cells (geohash, a quadtree, or Uber's hexagonal H3 grid). To find drivers near a rider, the service looks up the rider's cell and the neighbouring cells, then ranks only those drivers by distance or estimated arrival time.
What is a geohash?
A geohash turns a latitude and longitude into a short string by repeatedly splitting the world in half, alternating longitude and latitude, and recording which half the point falls in. Each extra character makes the cell smaller. Places close together usually share a prefix, so 'all drivers in cell tdr1v' becomes a simple key lookup.
What is the difference between a geohash and a quadtree?
A geohash uses a fixed grid: every cell at a given length is the same size, which makes it simple to compute and store as a key. A quadtree splits a square into four only where there are many points, so busy city centres get small cells and empty areas stay as big cells. Quadtrees adapt to density but must be kept up to date in memory as drivers move.
How does Uber match a rider to a driver?
The matching service gets nearby available drivers from the location service, ranks them by estimated time to pickup (not just straight-line distance), and offers the trip to the best one. If that driver declines or doesn't respond within a few seconds, it offers to the next. A lock on the driver's status prevents two riders being matched to the same driver at once.
How much location data does a ride-hailing app handle?
A lot. With 1 million active drivers each sending a location every 4 seconds, the system receives about 250,000 location updates per second. Only the latest position matters for matching, so it's kept in memory and overwritten; the full history is streamed to cheaper storage for analytics and trip records.
🧠 Quick check: Uber design
1. Why not compute the distance from a rider to every driver in the city?
2. The rider is right at the edge of a grid cell. What must the search include?
3. 1 million drivers send their location every 4 seconds. About how many updates per second?
4. Two riders' requests try to grab the same driver at the same moment. What prevents a double match?
Checking your access…