Ride Sharing
Matching riders to nearby drivers — geospatial indexing, a flood of location updates, and making sure one driver gets one ride
The interesting parts are proximity search over constantly-moving points, and making sure two riders are never matched to the same driver.
1. Clarify and Scope
| Question | Assumption taken here |
|---|---|
| Core feature? | Request a ride, match to a nearby driver |
| Matching rule? | Nearest available driver, within 5 km |
| Location updates? | Every 4 seconds from active drivers |
| Pricing, payments, routing? | Out of scope — separate systems |
2. Put Numbers On It
1 million active drivers at peak
Location update every 4 seconds
1,000,000 ÷ 4 = 250,000 writes/sec ← the dominant load
RIDE REQUESTS
10 million rides/day
÷ 100,000 sec ≈ 100 requests/sec
× 3 peak ≈ 300 requests/sec ← trivial by comparison
Ratio: ~800 location writes per ride requestThis is a write-heavy system, which is unusual
250,000 writes per second against 300 reads per second. Almost every design instinct — cache the reads, add replicas — is pointed the wrong way here.
Two consequences follow immediately:
Driver locations do not belong in a durable database. Writing 250,000 rows per second to disk is enormous, and the data is worthless four seconds later. Keep it in memory.
Do not store location history on this path. If history is needed for analytics, stream it separately to a warehouse — do not make the matching path pay for it.
3. Define the Interface
FROM DRIVERS rate
update_location(driver_id, lat, lng) → ack 250,000/sec
set_available(driver_id, bool) → ack rare
accept(driver_id, ride_id) → { ok } | { taken }
FROM RIDERS
request_ride(rider_id, pickup, drop) → { ride_id } 300/sec
ride_updates(ride_id) → pushed, not polledThe rate column is part of the interface, not a footnote
update_location runs 800 times more often than request_ride. Writing them into the same list makes it obvious they cannot share a storage system, and that any work added to update_location is multiplied by 250,000.
An interface that hides its rates lets you design the cheap operation carefully and the expensive one by accident.
`accept` can return `taken` — the interface admits the race
Several drivers are offered the same ride. Only one can have it. Rather than pretend that never happens, the reply has a second outcome, and the driver's app is built to expect it.
An interface with only a success case forces the race to be resolved by luck or by locking. Naming the failure makes it something the design can handle — which is what section 5 does.
4. The Proximity Problem
"Find drivers within 5 km" cannot use an ordinary index. An index on latitude finds a horizontal band; an index on longitude finds a vertical one. Intersecting them scans far too much.
The answer is to turn two dimensions into one, using geohashing.
Driver at 51.5074, -0.1278 → geohash "gcpvj0"
Nearby drivers share a prefix:
gcpvj0 → same ~1 km cell
gcpvj → same ~5 km cell ← the radius this design promises
gcpv → same ~40 km cellA proximity query becomes a prefix match, which any sorted index handles.
Always search the neighbouring cells
Two points 10 metres apart can fall either side of a cell boundary and share no prefix.
Searching only the containing cell silently misses the nearest drivers. The bug is invisible in testing and appears as "the app said nobody was available" for users standing near a boundary.
Query the target cell plus all eight neighbours, then filter by true distance.
5. The Matching Race
Two riders request at the same moment, and the same driver is nearest to both.
Read-then-write is a race, and here it books one car twice
Rider A: find nearest → driver 7 is free
Rider B: find nearest → driver 7 is free
Rider A: assign driver 7
Rider B: assign driver 7 ← same driver, two ridesThe check and the claim must be one atomic operation — a conditional update that only succeeds if the driver is still free:
UPDATE drivers SET status='matched', ride_id=?
WHERE id=? AND status='available'If it affects zero rows, someone else won; move to the next candidate. This is the same read-then-write race as in the rate limiter, and it has the same fix.
The claim also needs a timeout. A driver who is offered a ride and does not respond must be released automatically, or they are stuck unavailable forever.
6. Reducing the Write Load
250,000 writes per second is achievable but not free. Two easy reductions:
| Technique | Saving |
|---|---|
| Skip unchanged locations — a parked driver need not report | Often 20–40% |
| Adaptive frequency — update less often when stationary or off-duty | Large |
| Batch on the client — send every 8 seconds instead of 4 | Halves it, at the cost of staleness |
Only active drivers need to be in the index
A driver who is off-duty or already on a ride is not matchable, so their location does not belong in the matching index at all.
Removing them shrinks both the write load and the search space. It sounds obvious and is frequently missed — the naive design tracks every driver all the time.
7. What Was Traded Away
| Decision | Gained | Cost |
|---|---|---|
| Locations in memory only | 250k writes/sec is affordable | Locations lost if the store restarts |
| Geohash prefix search | Proximity via an ordinary index | Must search 9 cells; edge effects |
| Atomic claim with conditional update | One driver, one ride | Some requests must retry with another driver |
| Only active drivers indexed | Smaller, faster index | Extra state transitions to manage |
| No location history on the hot path | Write path stays lean | History needs a separate stream |
Follow-on Questions
Related Reading
- Partitioning and Consistent Hashing — geohashing and quadtrees in detail
- Rate Limiter — the same atomic check-and-set problem
- Caching — in-memory stores and what happens when they restart
- Consistency and CAP — why matching must be strongly consistent