You open Uber, Ola or Rapido, tap "Book", and within seconds a driver 600 metres away accepts. You then watch a little car icon crawl towards you on the map. Behind that experience is a system that tracks millions of moving drivers, answers "who is near this point?" thousands of times a second, and makes sure no driver is ever given two rides at once.
This chapter designs a ride-sharing service. Unlike the Design a News Feed and Design a Video Streaming Service chapters, which were read-heavy, this system is write-heavy: the dominant traffic is drivers sending their location every few seconds. The new idea at its core is the geospatial index, and we will build a working one with geohashes.
A ride-sharing service continuously tracks the locations of available drivers, finds suitable nearby drivers when a rider requests a trip, assigns exactly one driver, and coordinates the trip in real time until payment.
Step 1: Clarify Requirements
Functional Requirements
Drivers go online/offline and send their location periodically while online.
A rider sees an estimated fare and ETA and requests a ride from pickup to drop.
The system matches the rider with a nearby available driver, who can accept or decline.
Rider and driver see each other's live location during the trip.
At the end, the fare is computed and payment is collected.
Out of scope: ride pooling, scheduled rides, ratings, driver onboarding, promotions.
Non-Functional Requirements
Low-latency matching: find candidate drivers in well under a second.
Strong consistency for assignment: a driver must never be assigned two trips; a trip must never get two drivers. (Location data, on the other hand, can be slightly stale.)
High availability: an outage strands people on the road.
Scale: hundreds of thousands of location updates per second.
Notice the mixed consistency needs. As the Consistency Models chapter showed, we can choose different guarantees for different data: eventual for locations, strong for trip and driver state.
Step 2: Back-of-the-Envelope Estimation
Assumptions
-----------
Trips per day : 10 million
Drivers online at peak : 2 million (≈1 million on average)
Location update interval : every 4 seconds
Size of one location update : ~100 bytes (driver id, lat, lon, heading, speed, time)
Peak factor for trip requests : 3
Trip requests
10M / 86,400 ≈ 116 trips/s (peak ≈ 350/s)
Location updates (peak)
2M drivers / 4 s = 500,000 updates/s
× 100 bytes = 50 MB/s ingest
Live driver index in memory
2M × ~200 bytes (with index overhead) ≈ 400 MB → fits in RAM easily
Location history (for trip replay, analytics, disputes)
1M avg drivers / 4 s × 86,400 s × 100 B ≈ 2.16 TB/day
Key insights:
Trip requests are a small number (hundreds per second). Matching logic can afford to be careful.
Location updates are the firehose: 500,000 writes per second. They must go to an in-memory store, not a relational database row update.
The live index is small (hundreds of MB). The problem is write rate, not size. Partitioning by city or region spreads the writes.
Step 3: The Core Problem — "Find Drivers Near Me"
A naïve query is:
SELECT driver_id FROM drivers
WHERE status = 'AVAILABLE'
AND lat BETWEEN 12.96 AND 12.98
AND lon BETWEEN 77.58 AND 77.61;
A B-tree index (as used in relational databases) helps on one column, but this is a two-dimensional range. The database finds all drivers in a latitude strip across the whole world, then filters by longitude. And the rows change every 4 seconds for every driver. We need an index designed for 2-D space that is cheap to update.
Geohash: Turning 2-D into 1-D
A geohash encodes a latitude/longitude point as a short string by repeatedly halving the world, alternating longitude and latitude, and writing the resulting bits in base-32. Points with a long common prefix are close together.
How it works, step by step:
Longitude range is [-180, 180]. Is the point's longitude in the upper half? Write 1, else 0. Halve the range.
Do the same for latitude in [-90, 90].
Alternate (lon, lat, lon, lat...). Every 5 bits become one base-32 character (alphabet
0123456789bcdefghjkmnpqrstuvwxyz, which skips a, i, l, o).
Each extra character makes the cell 32 times smaller. Approximate cell sizes (at the equator; cells get narrower towards the poles):
Geohash length | Cell size (width × height) | Typical use |
|---|---|---|
4 | ≈ 39 km × 19.5 km | City-level partitioning |
5 | ≈ 4.9 km × 4.9 km | Wider search when few drivers |
6 | ≈ 1.2 km × 0.6 km | Nearby-driver search in a city |
7 | ≈ 153 m × 153 m | Pickup-point precision |
8 | ≈ 38 m × 19 m | Very fine location |
Now "drivers near me" becomes: compute my geohash at length 6, and look up drivers whose cell is my cell or one of its 8 neighbours. Why neighbours? Because a driver 50 metres away might sit just across a cell border, with a completely different geohash. This edge effect is the most common geohash mistake.
north ↑
┌────────┬────────┬────────┐
│ tdr1v6 │ tdr1vd │ tdr1vf │
├────────┼────────┼────────┤
│ tdr1v3 │ tdr1v9 │ tdr1vc │ rider (MG Road, Bengaluru) is in the
├────────┼────────┼────────┤ centre cell tdr1v9; search all nine
│ tdr1v2 │ tdr1v8 │ tdr1vb │
└────────┴────────┴────────┘
west ← → east
Alternatives
Approach | Idea | Strengths | Weaknesses |
|---|---|---|---|
Geohash | Fixed grid, string prefix | Simple; works in any key-value store; prefix = area | Edge effects; cells distort near poles; fixed size regardless of density |
Quadtree | Split a square into 4 when it holds too many points | Adapts to density (small cells downtown, big cells in villages) | In-memory tree; rebalancing as drivers move is more work |
Google S2 | Projects the sphere onto a cube, cells along a Hilbert curve | Good coverage of arbitrary regions, hierarchical | More complex |
Uber H3 | Hierarchical hexagonal grid (open-sourced by Uber) | All 6 neighbours of a hexagon are the same distance away; great for surge zones and analytics | Hexagons do not nest perfectly into parents |
Redis GEO |
| Ready-made, in memory, fast | One key per area must be partitioned to spread write load |
In Redis, use GEOSEARCH (available since Redis 6.2); the older GEORADIUS command is deprecated.
Step 4: A Working Driver Index in Python
The program below implements geohash encoding and decoding from scratch, finds the 9 cells around a point, keeps an index from cell to drivers, and returns the nearest available drivers by true great-circle distance (the haversine formula). It first checks itself against a well-known geohash test value.
import math
from collections import defaultdict
BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"
def encode(lat, lon, precision=6):
lat_rng, lon_rng = [-90.0, 90.0], [-180.0, 180.0]
bits, bit_count, even, out = 0, 0, True, []
while len(out) < precision:
rng, val = (lon_rng, lon) if even else (lat_rng, lat)
mid = (rng[0] + rng[1]) / 2
if val >= mid:
bits = bits * 2 + 1
rng[0] = mid
else:
bits = bits * 2
rng[1] = mid
even = not even
bit_count += 1
if bit_count == 5:
out.append(BASE32[bits])
bits, bit_count = 0, 0
return "".join(out)
def bounds(gh):
lat_rng, lon_rng, even = [-90.0, 90.0], [-180.0, 180.0], True
for ch in gh:
v = BASE32.index(ch)
for shift in range(4, -1, -1):
rng = lon_rng if even else lat_rng
mid = (rng[0] + rng[1]) / 2
if (v >> shift) & 1:
rng[0] = mid
else:
rng[1] = mid
even = not even
return lat_rng, lon_rng
def neighbours(gh):
"""The cell itself plus its 8 surrounding cells (ignores poles/date line)."""
(la0, la1), (lo0, lo1) = bounds(gh)
dlat, dlon = la1 - la0, lo1 - lo0
clat, clon = (la0 + la1) / 2, (lo0 + lo1) / 2
return {encode(clat + i * dlat, clon + j * dlon, len(gh))
for i in (-1, 0, 1) for j in (-1, 0, 1)}
def haversine_km(lat1, lon1, lat2, lon2):
r = 6371.0
p1, p2 = math.radians(lat1), math.radians(lat2)
dp, dl = p2 - p1, math.radians(lon2 - lon1)
a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
return 2 * r * math.asin(math.sqrt(a))
class DriverIndex:
def __init__(self, precision=6):
self.p = precision
self.cells = defaultdict(set) # geohash -> driver ids
self.where = {} # driver id -> (lat, lon, geohash)
def update(self, driver, lat, lon):
gh = encode(lat, lon, self.p)
if driver in self.where:
self.cells[self.where[driver][2]].discard(driver) # moved cell
self.cells[gh].add(driver)
self.where[driver] = (lat, lon, gh)
def remove(self, driver): # driver went offline or got a trip
lat, lon, gh = self.where.pop(driver)
self.cells[gh].discard(driver)
def nearest(self, lat, lon, k=3, max_km=3.0):
candidates = set()
for cell in neighbours(encode(lat, lon, self.p)):
candidates |= self.cells[cell]
scored = sorted((haversine_km(lat, lon, *self.where[d][:2]), d)
for d in candidates)
return [(d, round(km, 2)) for km, d in scored if km <= max_km][:k]
print("check:", encode(57.64911, 10.40744, 11)) # known value: u4pruydqqvj
rider = (12.9716, 77.5946) # Bengaluru, MG Road area
print("rider cell:", encode(*rider), "neighbours:", sorted(neighbours(encode(*rider))))
idx = DriverIndex()
drivers = {"D1": (12.9750, 77.5990), "D2": (12.9690, 77.5900),
"D3": (12.9352, 77.6245), "D4": (12.9720, 77.6010),
"D5": (13.0350, 77.5970)}
for d, (la, lo) in drivers.items():
idx.update(d, la, lo)
print(f"{d} at {la},{lo} -> cell {idx.where[d][2]}")
print("nearest:", idx.nearest(*rider))
idx.remove("D2") # D2 accepted another trip
idx.update("D4", 12.9718, 77.5950) # D4 drove closer
print("after updates:", idx.nearest(*rider))
Output:
check: u4pruydqqvj
rider cell: tdr1v9 neighbours: ['tdr1v2', 'tdr1v3', 'tdr1v6', 'tdr1v8', 'tdr1v9', 'tdr1vb', 'tdr1vc', 'tdr1vd', 'tdr1vf']
D1 at 12.975,77.599 -> cell tdr1vf
D2 at 12.969,77.59 -> cell tdr1v8
D3 at 12.9352,77.6245 -> cell tdr1w6
D4 at 12.972,77.601 -> cell tdr1vc
D5 at 13.035,77.597 -> cell tdr4ju
nearest: [('D2', 0.58), ('D1', 0.61), ('D4', 0.69)]
after updates: [('D4', 0.05), ('D1', 0.61)]
What to notice:
The self-check prints
u4pruydqqvj, the standard example value for (57.64911, 10.40744), so the encoder is correct.D3 (about 5 km away, in cell
tdr1w6) and D5 (about 7 km away) are never even examined: the cell lookup filters them out before any distance calculation. That is the whole point of the index.D2 is in a neighbour cell (
tdr1v8), not the rider's cell, yet it is the closest driver. Searching only the rider's own cell would have missed it.Updating a driver is O(1): remove from the old cell set, add to the new one. That is what lets us absorb 500,000 updates per second when sharded.
The 9-cell area is only guaranteed to cover about 0.6 km in every direction at length 6. If too few drivers are found, the search widens to length 5 (≈ 4.9 km cells).
Step 5: High-Level Architecture
Rider app Driver app
│ HTTPS (requests) │ location every 4 s
│ WebSocket (live updates) │ WebSocket / persistent connection
▼ ▼
┌──────────────────────── API Gateway / Load balancer ─────────────────────────┐
└───┬───────────────┬──────────────────┬───────────────────────┬──────────────┘
▼ ▼ ▼ ▼
┌────────┐ ┌─────────────┐ ┌───────────────┐ ┌───────────────┐
│ Pricing│ │ Trip service│◀─▶│ Matching / │◀─────▶│ Location svc │
│ & ETA │ │ (state │ │ Dispatch svc │ query │ (geo index in │
└───┬────┘ │ machine) │ └───────┬───────┘ │ memory, │
│ └──────┬──────┘ │ offer │ sharded by │
▼ ▼ ▼ │ region/cell) │
Maps/routing Trips DB Notification / └──────┬────────┘
(road graph) (strongly Connection gateway │ stream
consistent) (push to driver/rider) ▼
│ Kafka-like log ──▶ history store,
▼ analytics, surge
Payment service
The Location Service
Driver apps keep a persistent connection (WebSocket, as in Design a Chat Application) and send a location every few seconds. Connection gateways are stateful, so a load balancer routes each driver to one gateway.
Each update overwrites the driver's entry in the in-memory geo index (our
DriverIndex, or Redis GEO). Only the latest position matters for matching, so no durable write is needed on this path.Updates are also appended to a log (see Message Queues & Pub/Sub) that feeds trip-route storage, ETA models, and surge pricing, all asynchronously.
Sharding: partition by geography (city, or geohash prefix). A rider in Bengaluru never needs drivers in Delhi, so a query hits one shard. Very busy cities are split further by finer cells; sparse regions share a shard. This is Database Sharding & Partitioning with a geographic key.
If a location shard crashes, nothing important is lost: drivers resend their position within 4 seconds, and the index rebuilds itself. This "soft state" is why an in-memory store is acceptable here.
The Matching Flow
The rider requests a ride. The trip service creates a trip with state
REQUESTEDand an idempotency key from the app, so a double tap does not create two trips.The dispatch service asks the location service for, say, the 10 nearest available drivers, then ranks them by ETA on the road network (not straight-line distance; a driver across a river may be 500 m away but 15 minutes by road).
Dispatch atomically reserves the best driver: a compare-and-set that changes the driver from
AVAILABLEtoOFFEREDonly if they are still available (for example a conditional update in the database, or a RedisSET driver_lock:{id} trip_id NX PX 15000). If the set fails, someone else got that driver; try the next one.The offer is pushed to the driver's app with a timeout (say 15 seconds).
On accept, the trip moves to
ACCEPTEDand the driver toON_TRIPin one transaction. On decline or timeout, the reservation is released and dispatch offers the next driver.
Step 3 is the critical one for correctness. Two riders in the same area may both see driver D4 as "nearest" at the same instant. Without an atomic reservation, D4 could receive two offers and accept both. Location can be eventually consistent; assignment cannot.
The Trip State Machine
REQUESTED ──match──▶ DRIVER_OFFERED ──accept──▶ ACCEPTED ──arrive──▶ DRIVER_ARRIVED
│ │ decline/timeout │ start
│ └──▶ back to REQUESTED (next driver) ▼
│ no driver / rider cancels IN_PROGRESS
▼ │ end
CANCELLED ◀── rider or driver cancels (cancellation fee rules) ── COMPLETED ──▶ PAID
Every transition is validated on the server ("you cannot start a trip that was never accepted") and stored in the strongly consistent trips database, which is sharded by trip_id (or by city). Each transition also emits an event, which the notification service pushes to both apps.
Step 6: Deep Dives
ETA and Routing
ETA comes from a routing engine that runs shortest-path searches on a road graph whose edge weights are travel times, updated from live traffic (the drivers' own location stream is a great traffic sensor). Plain Dijkstra is too slow for continent-sized graphs, so production engines precompute shortcuts (techniques such as contraction hierarchies) to answer queries in milliseconds. Machine learning models then correct the raw estimate using historical trip data.
Surge (Dynamic) Pricing
Divide the city into cells (H3 hexagons are popular for this). A stream processor counts open requests and available drivers per cell every minute or so. When demand far exceeds supply in a cell, a multiplier rises, which both encourages more drivers to come and reduces requests. The fare shown to the rider is locked when they confirm, so a multiplier change a second later does not change their price.
Payments
Payment runs after COMPLETED and talks to an external payment gateway. Use an idempotency key per trip so retries never charge twice, record every attempt, and handle failures asynchronously (retry, then mark the trip "payment pending"). The payment service is isolated from dispatch, so a slow gateway never blocks matching.
Handling Failures and Scale
Driver app loses network: stop offering them rides after missing a few heartbeats (for example 3 updates). Their entry expires from the index via a TTL.
Dispatch server crashes mid-match: reservations have a TTL, so a stuck
OFFEREDdriver becomes available again automatically, and the trip is retried.Hot area (stadium after a match): split that region's shard into finer cells; rate-limit repeated rider requests (see Rate Limiting).
Region failure: trips DB replicated across zones; location data simply rebuilds from fresh driver updates.
Comparison: Which Store for Which Data?
Data | Write rate | Consistency needed | Store |
|---|---|---|---|
Live driver location | Very high (≈500K/s) | Eventual; latest value only | In-memory geo index, sharded by region |
Location history | Very high, append-only | Eventual | Log → wide-column store / object storage |
Driver status (available/offered/on trip) | Moderate | Strong (no double assignment) | Atomic compare-and-set store |
Trips | Low (hundreds/s) | Strong, transactional | Sharded relational DB |
Payments | Low | Strong, auditable | Relational DB + idempotency keys |
Common Mistakes
Storing every location update in a relational table. 500,000 row updates per second with secondary indexes will melt the database. Keep live locations in memory.
Searching only the rider's own geohash cell. Always include the 8 neighbours (or widen the radius), or you miss drivers just across a border.
Ranking by straight-line distance. Rivers, one-way streets and flyovers matter; rank final candidates by road ETA.
No atomic reservation. Without compare-and-set, two riders can get the same driver.
Applying one consistency level everywhere. Strong consistency for locations wastes resources; eventual consistency for assignment causes real-world chaos.
Forgetting idempotency. Network retries on "request ride" and "charge card" must not create duplicate trips or charges.
Interview Questions
1. Why is a regular B-tree index on latitude and longitude not enough for "find nearby drivers"?
A B-tree orders by one key (or a composite with one leading column), so a 2-D range query scans a whole strip of the leading dimension and filters the other. With locations changing every few seconds, maintaining these indexes is also expensive. Geospatial indexes (geohash, quadtree, S2, H3) map nearby points to nearby keys so the search touches only a few cells.
2. Two points are 30 metres apart but have very different geohashes. How is that possible, and how do you handle it?
They lie on opposite sides of a cell boundary (possibly a high-level boundary, such as the equator or prime meridian, where even the first character differs). Prefix closeness implies nearness, but nearness does not imply a shared prefix. Handle it by always searching the query cell plus its 8 neighbours, then filtering by real distance.
3. How do you prevent the same driver from being assigned to two riders?
Reserve the driver atomically before sending the offer: a compare-and-set from AVAILABLE to OFFERED (for example a conditional database update or Redis SET with NX and an expiry). Only the request that wins the set may offer the trip; others move to the next candidate. The expiry frees the driver if the offer times out or the dispatcher crashes.
4. 3 million drivers send location every 5 seconds with 120-byte messages. What is the update rate and bandwidth?
3,000,000 / 5 = 600,000 updates per second. 600,000 × 120 bytes = 72 MB/s, or about 576 Mbps of ingress. Spread across regional shards and gateways, this is very manageable in memory.
5. Why is it acceptable for the live location index to be in memory without durable writes?
It is soft state: only the latest position matters, and every online driver resends it every few seconds. If a node dies, the index rebuilds within one update interval. Durable history is written separately and asynchronously through a log.
6. Quadtree or geohash for a city with a very dense centre and sparse outskirts?
A quadtree adapts cell size to density (it splits a cell when it holds too many drivers), so dense downtown gets small cells and outskirts get large ones, keeping each search small. A geohash uses fixed-size cells, so you compensate by choosing the precision dynamically (finer in dense areas, or widening the search when too few drivers are found). Both work; the quadtree trades simplicity for adaptivity.
Summary
Ride-sharing is write-heavy: hundreds of thousands of location updates per second versus a few hundred trip requests.
Live locations live in a sharded in-memory geospatial index; it is soft state that rebuilds from driver updates.
Geohash turns 2-D positions into 1-D prefix strings; always search the cell plus its 8 neighbours and filter by real distance. Quadtrees, S2 and H3 are alternatives.
Matching: find nearby available drivers → rank by road ETA → atomically reserve one → offer with a timeout → accept or try the next.
Use different consistency per data type: eventual for location, strong for driver assignment, trips and payments.
A server-validated trip state machine, idempotency keys and TTL-based reservations keep the system correct under retries and crashes.
Let locations be fast and approximate, but make assignments exact: one driver, one trip, every time.