1. Requirements & Estimation
Week 1's framework, applied to a system whose traffic shape is genuinely unusual:
Functional:
- A rider requests a trip from location A to location B
- The system matches the rider to the nearest available driver
- Both parties see the other's live location until pickup
Non-functional:
- Scale: 5M daily active riders, ~2M trip requests/day
- 500,000 active drivers during peak hours
- Match latency: under 5 seconds
- Consistency: a driver must NEVER be matched to two riders
at once -- strong consistency required for this one step,
unlike most of this course's read-heavy systems
Estimation:
Trip requests: 2,000,000/day / 86,400s ≈ 23/sec average
peak (rush hour) ≈ 23 * 8 ≈ 180/sec
Location pings: each active driver pings every ~4 seconds
500,000 / 4 ≈ 125,000 writes/second
The location-ping number dwarfs the trip-request number by
nearly 700x -- this system's dominant traffic is location
updates, not the "actual" product action of requesting a ride.
That imbalance is the single most important number in this design: a design that treats trip-matching and location-ingestion as equally weighted traffic hasn't understood this system yet. The location-update pipeline needs its own scaling story, entirely separate from the low-volume, strongly-consistent trip-matching path — Section 2 splits them into different services precisely because of this.
2. High-Level Architecture
[Driver App] --location ping, ~4s--> [Location Ingest Service]
|
writes to [Geospatial Index]
(Section 3), NOT a normal DB
[Rider App] --request trip--> [Trip Service] --> [Matching Service]
|
queries [Geospatial Index]
for nearby available
drivers (Section 3)
|
acquires a lock on the
chosen driver (Section 4)
|
[Trip Service] confirms the match,
both apps switch to live tracking
over WebSocket (Week 20)
This follows Week 15's bounded-context decomposition directly: Location Ingest owns the high-volume write path and nothing else; Matching owns the correctness-critical read-then-lock sequence; Trip Service owns the trip's lifecycle state. Splitting location ingestion out as its own service is exactly the kind of independent-scaling justification Week 15 asked for — this specific path needs to handle 125,000 writes/second regardless of how much trip-matching traffic exists, and scaling it independently means the trip-matching path never has to pay for capacity it doesn't need.
3. Deep Dive: Geospatial Indexing with Geohashing
"Which drivers are within 2km of this rider?" is not a query a normal B-tree index answers efficiently — latitude and longitude are two independent dimensions, and indexing them separately doesn't let you efficiently query "near a point" in both at once. Geohashing solves this by encoding a 2D location into a single 1D string, in a way that preserves proximity.
The world is recursively divided into a grid. Each cell gets
a string code; longer codes = smaller, more precise cells.
"9q8yy" -- a ~1.2km x 0.6km cell in San Francisco
"9q8yyk" -- a smaller cell nested inside it
Key property: two locations physically near each other USUALLY
share a long common string prefix. "9q8yyk" and "9q8yym" are
both inside "9q8yy" -- nearby cells, nearby prefixes.
To find drivers near a rider:
1. Compute the rider's geohash, e.g. "9q8yyk"
2. Query for all drivers whose geohash starts with "9q8yy"
(the coarser, shared prefix) -- a simple prefix query,
not a 2D distance calculation against every driver
3. Optionally also check the 8 neighboring cells, to catch
nearby drivers who happen to fall just across a cell
boundary
This turns "find nearby drivers" into a prefix lookup — the same underlying idea as Week 19's trie, applied to geographic coordinates instead of search-query text. The geospatial index itself is typically an in-memory structure (Redis has built-in geospatial commands built on exactly this idea), because it needs to absorb 125,000 writes/second from Section 1's estimation and still answer nearby-driver queries in well under a second — a durable, disk-backed database would struggle to sustain that write rate at this latency.
A rider one meter from a driver, but on opposite sides of a cell boundary, would share almost no geohash prefix despite being nearly adjacent — this is a real edge case, not a rare corner case, and naming it (and the neighbor-cell check that fixes it) in an interview signals the geohash approach was actually understood, not just memorized as a black box.
4. Deep Dive: Matching Without Double-Booking
Section 3 finds candidate nearby drivers; this step has to pick one and guarantee no other request can pick the same driver in the same instant — a direct application of Week 23's distributed lock, with real consequences if it's implemented naively.
1. Matching Service gets candidate drivers from the geospatial
index (Section 3), sorted by distance
2. For the closest candidate, attempt to acquire a lock:
SET lock:driver-4821 "trip-99123" NX EX 10
(NX = only if not already locked; EX 10 = auto-expires in
10 seconds, per Week 23's crash-safety reasoning)
3. If lock acquired: confirm the match, update Trip Service's
database (the actual source of truth) with a fencing token
(Week 23) tied to this lock acquisition, THEN release the
lock
4. If lock NOT acquired (another request beat this one to it):
move to the next-closest candidate driver, retry from step 2
The lock's only job is to serialize concurrent attempts to match the same driver — it is deliberately short-lived (a few seconds) and released as soon as the match is durably confirmed in Trip Service's actual database, which is the real source of truth a driver's app checks. This mirrors Week 23's fencing-token lesson exactly: the lock reduces the window for a conflict, but the confirmed write to Trip Service (checked against the fencing token) is what actually prevents two trips from ever being simultaneously active for one driver, even in the rare case the lock itself is fooled by a slow request.
One more detail worth naming: if the closest driver's lock attempt fails, the system doesn't fail the whole request — it retries against the next-closest candidate (step 4). This graceful degradation matters at scale: during a high-demand period, a popular driver near many riders will frequently lose these lock races, and the matching flow needs to handle that as an expected, common case, not an error.
5. Hands-on Exercise
Add surge pricing to the dispatch system
The product wants surge pricing: when the ratio of active trip requests to available nearby drivers in a given area gets too high, prices for new requests in that area increase.
Requirements:
- Decide which existing component (Section 2) should compute the current supply/demand ratio for a given area, and explain what data it needs that it doesn't already have.
- Using Section 3's geohash cells as the unit of "area," describe how you'd track request count and available-driver count per cell in near real time.
- Decide whether surge price calculation needs Week 23-level strong consistency, or whether an eventually-consistent, slightly-stale count is acceptable — justify against the user-facing cost of being wrong in each direction (overcharging vs. undercharging).
- Explain what happens to a rider who sees a surge price, waits 90 seconds to decide, then confirms — should they pay the price shown at request time or the current price at confirmation time? State an assumption and justify it.
- Identify one abuse vector this feature introduces (think about how "demand" is measured) and propose a mitigation.
For requirement 5: if "demand" is measured by counting open ride requests in an area, a bad actor could open (and never confirm) many fake requests to artificially trigger surge pricing — think about whether counting confirmed vs. merely-requested trips changes that incentive.
6. Knowledge Check
Four quick questions. Expand each to check your answer.
Q1
Why does location ingestion need to be its own independently-scaled service, separate from trip matching?
Why does location ingestion need to be its own independently-scaled service, separate from trip matching?
Location pings (125,000/second) outnumber trip requests (180/second at peak) by nearly 700x, so the two have wildly different scaling needs. Coupling them into one service would force the low-volume, strongly-consistent trip-matching path to scale alongside the high-volume location stream, wasting capacity and complicating the correctness-critical path unnecessarily.
Q2
Why does geohashing turn a "find nearby drivers" query into a simple string-prefix lookup?
Why does geohashing turn a "find nearby drivers" query into a simple string-prefix lookup?
Geohashing encodes 2D coordinates into a string such that physically nearby locations usually share a long common prefix. Finding nearby drivers becomes a query for every geohash sharing the rider's coarser prefix, a straightforward prefix lookup, instead of computing a 2D distance calculation against every driver in the system.
Q3
Why does the matching step check neighboring geohash cells, not just the exact cell a rider falls in?
Why does the matching step check neighboring geohash cells, not just the exact cell a rider falls in?
Two points very close together physically can fall on opposite sides of a geohash cell boundary and share almost no common prefix, since the grid is a somewhat arbitrary partition. Without checking neighboring cells, a genuinely nearby driver just across a boundary would be missed entirely by a pure prefix match.
Q4
Why does the matching flow retry against the next-closest driver when a lock attempt fails, rather than treating it as a request failure?
Why does the matching flow retry against the next-closest driver when a lock attempt fails, rather than treating it as a request failure?
A failed lock attempt just means a different concurrent request won the race for that specific driver — it's an expected, common outcome during high-demand periods with many riders near one popular driver, not a system error. Retrying against the next-closest candidate lets the request still succeed quickly, rather than failing the rider's trip request over an ordinary contention event.