11.10 — Ride Hailing

Two people, four streets apart, press "request a ride" within the same second. The same driver is the closest available car for both of them. Exactly one of those riders is going to get that driver, and the system has about three seconds to decide which — while a million other drivers are each reporting a new position every four seconds.

Every study so far optimised the read path. Reads dominated by a hundred to one, caches absorbed them, and writes were an afterthought. This one inverts. There are 250,000 location writes a second and 5,000 ride requests a second, so the hard engineering is on the write side, and the interesting correctness problem is a race between two writers over one physical car.

It is also the first study where the data has a shape: "near me" is not a lookup by key, and the answer to how you index space decides everything downstream.

1. Requirements

Functional. Drivers report their location continuously. A rider requests a trip from A to B. The system matches a nearby driver within seconds. Both parties see each other move on a map. The trip runs through a lifecycle to completion and payment. Prices rise in areas where demand exceeds supply.

Non-functional, with numbers.

• A match within 5 seconds at p95.
• Driver location no more than 5 seconds stale.
• A driver is never assigned to two rides. This is the one place in the system that needs strict consistency, and naming it as the only such place is part of the answer.
• Regional availability, because a ride is inherently local — a rider in Lisbon does not care whether the São Paulo cluster is healthy.

Out of scope today: route calculation and arrival-time estimation, which we assume come from a maps service; fraud detection; and driver onboarding.

The clarifying questions, and what each answer changes

"How often do drivers report their location?" This one number is the whole write load. Every four seconds gives 250,000 writes a second; every second gives a million. It is also a product trade — a slower ping means a stale car on the rider's map, and a faster one means four times the infrastructure.

"Does a rider pick a driver, or does the system assign one?" If riders choose, you need to show a list and hold candidates while they decide, which is a much harder concurrency problem. Assignment by the system is both simpler and, in this market, what everyone actually built.

"Is the price quoted before the ride, and is it binding?" A quoted, held price means the platform absorbs the risk of the trip taking longer than expected. A metered price means the rider does. This is a product and legal decision that arrives disguised as a pricing feature.

"Can a driver serve more than one rider at a time?" If yes, matching stops being "find the nearest car" and becomes route optimisation, which is a different problem class entirely — the drill at the end works through exactly how different.

"What happens if the rider's phone dies mid-trip?" The answer tells you where trip state lives. If it lives on the phone, this question has no good answer, which is why it lives on the server.

2. Estimation

Location writes, the number that shapes everything. 1 million active drivers, each reporting every 4 seconds = 250,000 writes a second. What that forces: current location cannot be a durable database write. At 250,000 writes a second, any store that indexes to disk on every update is either impossible or ruinously expensive. Current location belongs in memory, with a durable trail written asynchronously for history. This is the decision the whole architecture hangs on, and it is forced by one multiplication.

Ride requests. 100 million rides a day ÷ 86,400 ≈ 1,200 a second average, ~5,000 at peak. What that forces: nothing much. Five thousand requests a second is small. The important observation is the ratio: location writes outnumber ride requests fifty to one, which tells you exactly where engineering effort should go and where it should not.

Memory for the live index. 1 million drivers × roughly 200 bytes of state (position, heading, timestamp, cell, availability) = 200 MB. What that forces: nothing at all, and that is worth noticing. The live index is tiny. It is the write rate that is hard, not the size, and confusing the two leads people to reach for storage systems that solve the wrong problem.

Durable location history. 250,000 pings a second × 50 bytes = 12.5 MB a second ≈ 1 TB a day. What that forces: an append-only stream into time-partitioned storage with aggressive retention. History matters for billing disputes and analytics; it is never consulted during matching, and separating those two uses is what keeps the hot path in memory.

Search cost per match. A dense city might hold 20,000 available drivers. With cells of roughly one square kilometre, the rider's cell plus its neighbours contains on the order of tens of candidates rather than 20,000. What that forces: the whole point of the spatial index. Scanning a million drivers per request at 5,000 requests a second is 5 billion distance calculations a second; reading nine cells is a handful of set reads.

3. API

POST /drivers/d_881/location
{ "lat": 51.5211, "lng": -0.1339, "heading": 74, "ts": 1754003722145 }
→ 204 No Content            # high frequency, fire-and-forget, no body

POST /rides
{ "pickup": {"lat":…, "lng":…}, "dropoff": {…}, "product": "standard",
  "quoteId": "q_01J9…" }
→ 202 Accepted
  { "rideId": "r_5512", "status": "matching", "quotedFare": 1840 }

GET /rides/r_5512
→ 200 OK
  { "rideId": "r_5512", "status": "assigned",
    "driver": { "id": "d_881", "name": "Ana", "vehicle": "…", "rating": 4.9 },
    "driverPosition": { "lat":…, "lng":…, "ts":… },
    "etaSeconds": 240 }

POST /rides/r_5512/accept          # the driver taps accept
→ 200 OK   { "rideId": "r_5512", "status": "assigned" }
→ 409 Conflict { "error": { "code": "already_assigned", … } }

POST /rides/r_5512/status
{ "transition": "arrived" | "started" | "completed", "idempotencyKey": "…" }

The 409 on accept is the entire matching-correctness story. Several drivers are offered the same ride at once, because offering them one at a time makes matching take thirty seconds instead of three. Exactly one accept succeeds. Every other driver is told immediately rather than being left waiting for a timeout — which matters, because a driver staring at a spinner that resolves into nothing is a driver who stops accepting offers.

Location is 204 with no body and no acknowledgement of substance. At 250,000 a second, anything the server has to say back is 250,000 responses a second of pure waste. The client fires and forgets, and if a ping is lost the next one arrives four seconds later.

Status transitions carry an idempotency key (10.4). A driver in a basement car park will retry "arrived" several times, and the second one must be a no-op rather than an error or a duplicate event.

4. Data model, and how to index space

driver_state                      -- in memory, region-partitioned, TTL 30 s
  driver_id  →  { cell, lat, lng, heading, ts, availability, current_ride }

cell_index                        -- in memory, the search structure
  cell_id    →  set of driver_id

rides                             -- durable, the source of truth
  ride_id       UUID PRIMARY KEY
  rider_id      UUID, driver_id UUID NULL
  state         SMALLINT NOT NULL     -- see the lifecycle in 6.4
  pickup, dropoff  GEOGRAPHY
  quoted_fare   INT, final_fare INT NULL
  requested_at, assigned_at, started_at, completed_at

location_history                  -- append-only stream → time-partitioned storage
  driver_id, ts, lat, lng, ride_id NULL

Access patterns:

Query	Frequency	Returns
Update one driver's position	250,000/s	—
Read candidates near a point	5,000/s	tens of drivers
Claim a ride for a driver	~15,000/s (3 offers per ride)	1 or 0 rows
Read one ride's state	high, while a trip is live	one row
Append a location point to history	250,000/s	—

The spatial index is the interesting part. "Find drivers near this point" is not a lookup by key and not a range scan on any single column, so it needs a structure built for the question.

Divide the world into cells. Each cell has an identifier, and the index maps a cell to the set of drivers currently inside it. Finding nearby drivers becomes "read my cell, and its neighbours" — a handful of set reads. A driver's ping either updates one field, if they are still in the same cell, or moves them between two sets, if they crossed a boundary. Both are constant-time, which is what makes 250,000 writes a second affordable.

Use a hierarchical scheme with a neighbour operation. The two widely used schemes divide the world into cells at many resolutions — one uses hexagons, another uses squares projected from a cube — and both give you two operations that matter: "which cell contains this point, at resolution r" and "which cells are adjacent to this one". Hexagons have one pleasant property worth knowing: all six neighbours are the same distance away, whereas a square has four edge neighbours and four corner neighbours at different distances, which makes ring expansion slightly uneven.

What you must not do is match on a string prefix alone. A simple scheme where nearby points share a text prefix looks like it solves this, and it fails at boundaries: two points ten metres apart on opposite sides of a cell edge can have completely different prefixes. Prefix matching finds one cell; you need the cell and its neighbours, which is why the neighbour operation is the thing you are actually shopping for.

5. Architecture

Figure 1 — A match in four steps. The cell index turns proximity into set reads. Ranking uses travel time along roads rather than straight-line distance. And the entire correctness of assignment rests on one conditional update rather than on any coordination service.

The write path deserves its own panel, because keeping the durable store off it is what makes the numbers work.

Figure 2 — Two destinations for one ping. The live index is volatile on purpose, because it rebuilds itself in four seconds from traffic that is arriving anyway. The durable trail is asynchronous, because nothing on the matching path ever reads it.

6. Deep dives

6.1 Handling 250,000 location writes a second

Each ping does two cheap things and one thing that is deliberately somewhere else.

Update the in-memory record. Position, heading, timestamp. One field write.

Move between cell sets, only if the driver crossed a boundary. Most pings do not cross a boundary — a car at 50 km/h covers 55 metres in four seconds, and cells are hundreds of metres across — so the common case is a single field update and the boundary case is two set operations.

Append the ping to a stream, asynchronously. This is the durable history, consumed later into cold storage (10.8.1). It is never read during matching, which is precisely why it can be asynchronous, batched and lossy at the edges.

The index is partitioned by geography, so drivers in one city are held by that city's shard. This is unusually good partitioning: every matching query is local to one region by the nature of the problem, so there are no cross-shard reads, and capacity follows a city's own demand curve.

Every record carries a time-to-live of about 30 seconds. A driver whose app crashes, whose phone dies, or who drives into a tunnel stops pinging, and their record expires rather than lingering as a phantom car that riders can be matched to and that will never arrive. The time-to-live is what turns "we stopped hearing from them" into "they are not available", with no explicit sign-out required.

6.2 The search, and the two mistakes people make with cells

Read the rider's cell and its neighbours. If that yields too few candidates, expand to the next ring outward. Stop when you have enough — not when you reach a fixed radius.

Terminating on candidate count rather than distance is what lets one algorithm serve both densities. A dense city centre finds twenty drivers in the first ring. A rural area expands four rings and finds three. A fixed radius would either scan thousands of drivers downtown or find nobody in the countryside, and it would have to be tuned per city forever.

Mistake one: matching on a prefix instead of using neighbours. A driver ten metres away, across a cell boundary, has a different cell identifier — and with a text-prefix scheme, possibly a completely different prefix. Only the neighbour operation finds them. This is the single most common wrong answer to "how do you find nearby drivers".

Mistake two: ranking by straight-line distance. A driver 200 metres away on the far side of a river with no bridge is useless. A driver two kilometres away on a clear main road arrives first. Ranking must use travel time along the road network, which means a call to the maps service per candidate — and that call is why the candidate list has to be capped, since ranking cost is linear in candidates and the maps service is the slowest thing in the loop.

Ranking is not only about proximity. Acceptance rate, rating, and how long a driver has been waiting all belong in the score. The last one is a genuine product requirement rather than a nicety: a system that always offers the nearest car will starve drivers who happen to sit in quiet areas, and drivers who never get offers stop working for you.

6.3 One driver, two riders: the conditional write is the lock

Several drivers are offered the same ride simultaneously, because sequential offers with a fifteen-second deadline each would take a minute to find a taker. Exactly one must win.

UPDATE rides
   SET driver_id = :driver, state = 'assigned', assigned_at = now()
 WHERE ride_id = :ride
   AND state = 'matching';

The number of rows affected is the verdict. One means this driver won. Zero means someone else already did, and the caller gets an immediate 409. Symmetrically, the driver's own availability is claimed in the same transaction:

UPDATE drivers
   SET current_ride = :ride
 WHERE driver_id = :driver
   AND current_ride IS NULL;

Both in one transaction, so a driver can never be assigned to a ride while another ride already holds them.

Why not a distributed lock service? Because it would add a network round trip, a lease, a fencing token to stop a stalled holder from acting late, and an entire new failure mode — and it would achieve mutual exclusion that a single-row conditional update already provides for free, with no extra component to operate (10.7.2). Reaching for coordination machinery when the data store's own atomicity is sufficient is the most common over-engineering in system design, and saying so explicitly is a strong signal.

The constraint this imposes, which is the honest cost: the assignment record must live in one consistent store. You cannot spread ride state across three services and keep this property, which is a good argument for one service owning the ride's whole lifecycle (10.8.3).

And the human detail that matters more than it looks: the losing drivers must be told instantly, and their acceptance rate must not be penalised for a race they could not have won. Otherwise the mechanism that makes matching fast quietly punishes the drivers who respond fastest, and they learn to stop responding fast.

6.4 The trip lifecycle

requested → matching → assigned → arriving → in_progress → completed → paid
                 ↓         ↓          ↓            ↓
            cancelled_by_rider | cancelled_by_driver | cancelled_by_system

Three properties make this the correctness backbone rather than a diagram.

Every transition is a conditional write guarded by the current state. WHERE state = 'assigned' on the transition to arriving means a stale retry from a driver's phone cannot move a completed trip backwards.

Every transition is idempotent. A driver in an underground car park will send "arrived" four times. The second one finds the state already arriving and returns success without doing anything.

Every transition emits an event through an outbox (10.8.4), so pricing, notifications (11.6) and analytics all react to a state change that definitely happened, rather than to a message that may have been published before a rollback.

This is the State pattern from 9.4.14 at system scale, and it is why a ride never ends up in an impossible condition — no driver arriving at a cancelled trip, no completed trip with no driver.

6.5 Pricing, and which way a failure must be biased

Surge is a supply-and-demand ratio computed per cell over a rolling window, published to a fast-read store, and — the important part — quoted at request time and held for the whole trip.

A price that changes between the quote and the confirmation is a trust failure, and in several jurisdictions a legal one. So the quote is a small record with an expiry: the rider is shown a number, that number is stored with the request, and the trip is billed against it even if the surge multiplier moves while they are in the car. The platform absorbs the difference, which is a real cost and the correct one to bear.

When the surge feed is stale or unavailable, fall back to the base price. Never to the last known high price. This is a small rule with a large principle behind it: a pricing failure must be biased toward the customer, because the alternative is charging people extra because of your own outage, which is the kind of thing that ends up in a newspaper rather than in a post-mortem.

6.6 What the rider sees, and why it is not the same as what is true

The rider watches a car move on a map. Those positions come from the driver's pings, which arrive every four seconds with occasional gaps, and the map interpolates between them so the car glides instead of jumping.

Two rules keep that honest. Interpolate for display, never for billing — a fare computed from interpolated positions is a fare computed from a guess. And when the pings stop, say so: after a gap of more than a few intervals, the interface should stop pretending the car is moving and show that the connection was lost, because a smoothly gliding car that is not actually there is worse than an honest "we have lost contact with the driver".

7. Decision Ledger

Decision	Alternatives	Why this	What it costs
Current location in memory, partitioned by region	a database with spatial indexing	250,000 writes a second with sub-millisecond reads; geography gives natural locality	volatile — must be rebuildable within one ping interval
Hierarchical cells with a neighbour operation	a flat grid; text-prefix matching	adaptive resolution, and adjacency is a primitive rather than a hack	a scheme and a resolution policy to understand
Terminate the search on candidate count	a fixed search radius	one algorithm serves a dense city and a rural area	latency varies with density, so cap the expansion
Rank by road travel time	straight-line distance	a river with no bridge makes distance meaningless	one maps call per candidate, so candidates must be capped
Parallel offers with first-accept-wins	offer to one driver at a time	matching in seconds rather than tens of seconds	drivers see offers that vanish — mitigate with an instant 409 and no penalty
A conditional update as the lock	a distributed lock service	one round trip, no leases, no fencing, no new component	the assignment must live in one consistent store
Location history written asynchronously	make every ping durable	keeps the hot path in memory	history lags and is never usable for real-time decisions
Quote held for the trip	live metered pricing	trust, and legal compliance in several markets	the platform absorbs surge movement during the ride

8. Scale and failure

Regional isolation is the top-level structure. A ride is local, so each region runs an independent stack. A failure in one city cannot reach another, cross-region traffic is essentially zero, and capacity follows local demand curves. This is the bulkhead idea (10.9) applied at the largest granularity available, and it is possible only because the problem itself is geographically partitioned — which is a gift worth taking.

At 10×, add region shards, use finer cell resolutions in dense areas, and move the matcher into the region shard so a match involves no cross-service hop. The location write path scales horizontally by region almost trivially, which is the payoff for choosing geography as the partition key.

What breaks	Blast radius	How you find out	What keeps it running	Recovery
Live location store lost	that region's matching, for seconds	index size drops to zero; match failures	the index rebuilds in one ping interval from traffic already arriving	nothing to restore; it refills itself
Driver app loses connectivity mid-trip	one trip's map display	ping gap per driver	trip state is server-side; the app reconciles on reconnect	interpolate for display, never for billing
Maps service slow	ranking, therefore match latency	ranking-stage duration	cap candidates; cache travel times coarsely at peak	degrade to a coarser ranking, deliberately
Matching service down in a region	that region only	match success rate	honest "no cars available" rather than a hanging request	the state machine guarantees no half-assigned rides
Surge feed stale	pricing	feed age	fall back to base price, never to a stale high price	refresh; the bias must always favour the customer
Two accepts race	none — by design	409 rate, which is a normal number here	the conditional update settles it	none needed; the loser is returned to the pool
Location history consumer lagging	billing disputes and analytics	consumer lag	matching is unaffected, because it never reads history	reprocess from the stream

The first row is the one worth explaining. Losing the entire live location index sounds catastrophic and costs about four seconds, because every driver is going to ping again within one interval and the index is rebuilt from those pings. That property is what makes it safe to keep this data in memory with no durability at all — and it is a good example of a design where the recovery mechanism is the normal traffic, which is much stronger than a recovery mechanism you have to remember to test.

What the interviewer will push on

"How do you find the nearest drivers?" They are checking whether you know that this is not a key lookup. The answer is a cell index mapping cell to driver set, searched as "my cell plus its neighbours" with the ring widening until enough candidates are found. Then volunteer the two mistakes: matching on a text prefix misses drivers ten metres away across a boundary, and ranking by straight-line distance sends a car that is close as the crow flies and thirty minutes away by road.

"Two riders, one best driver, same second. How do you guarantee one assignment?" One conditional update whose affected-row count is the verdict, with the driver's availability claimed in the same transaction. The tell is what you say next: that a distributed lock would add a round trip, a lease, a fencing requirement and a new failure mode to achieve exclusion the database already provides. Candidates who reach for coordination machinery here are usually reaching for it everywhere.

"Why is the location index allowed to be in memory with no durability?" Because it rebuilds itself in one ping interval from traffic that is arriving regardless, and because nothing in matching consults history. The follow-up is the time-to-live: a driver who stops pinging expires rather than lingering as a phantom car, so "we lost contact" and "not available" become the same state without anyone having to sign out.

"A driver's phone dies mid-trip. What happens?" Trip state lives on the server, so nothing is lost; the app reconciles when it reconnects. Then the detail that separates a considered answer: positions are interpolated for display only, never for billing, and after a gap the interface must stop pretending the car is moving. A smoothly gliding car that is not there is worse than an honest loss of contact.

"Surge is 3.2× when the rider requests and 1.1× when they arrive. What do they pay?" The quoted price, held. Then the general rule: a pricing failure must be biased toward the customer, which is why a stale surge feed falls back to the base price rather than to the last known high one. The wrong answer is that the system charges whatever is current, which is technically simpler and is how you end up explaining yourself publicly.

"Matching latency is 45 seconds at peak. Where do you look?" The three causes are in the drill below, and the shape of a good answer is that they are separable: contention over a small candidate set (many drivers losing races), ring expansion widening repeatedly under scarcity so the maps service is called far more often, and an offer deadline calibrated for drivers who are parked rather than driving. Naming that under scarcity matching stops being a search problem and becomes an assignment problem is the senior observation.

Volunteer this, because nobody asks: this is the only study in this Part where the write path is the hard part, and the reason is worth stating — 250,000 location writes against 5,000 ride requests is a fifty-to-one inversion of every other system here. That single ratio is why the design puts the live index in memory, why history is asynchronous, why geography is the partition key, and why the only strictly consistent operation in the entire system is one conditional update on one row. Getting the ratio out in the first two minutes is what makes the rest of the design look inevitable rather than invented.

Next: 11.11 — from finding things near a point to finding things that start with a prefix, in under a hundred milliseconds, while the user is still typing.

Recall

• The inversion: 250,000 location writes a second against 5,000 ride requests a second. The write path is the hard part, which is unique in this Part, and that ratio forces everything else.
• Current location lives in memory, partitioned by region, with a 30-second time-to-live so a silent driver expires instead of becoming a phantom car. It is 200 MB — the size is trivial, the write rate is not.
• Durable history is appended to a stream asynchronously (~1 TB a day) and is never read during matching, which is exactly why it can be asynchronous.
• Spatial index: cell → set of drivers, using a hierarchical scheme whose neighbour operation is the thing you need. Search = own cell + neighbours, widening until enough candidates — not until a fixed radius.
• Two classic mistakes: text-prefix matching misses a driver ten metres away across a boundary; straight-line distance sends a car that is close but across a river.
• Assignment: parallel offers, then UPDATE … WHERE state = 'matching' with the affected-row count as the verdict. The conditional write is the lock — no lease, no fencing token, no new component. Losers get an instant 409 and no penalty.
• The trip lifecycle is guarded, idempotent conditional writes emitting events through an outbox, so a ride can never reach an impossible state.
• Surge is quoted and held. A stale feed falls back to the base price, never the last high one: pricing failures are biased toward the customer.
• Losing the whole live index costs one ping interval, because the recovery mechanism is the normal traffic.

Self-test: Which side is the scaling challenge and by what factor? Why cells with a neighbour operation rather than prefix matching? How is double-assignment prevented without a lock service, and what does that constrain? Why is it safe for the location index to be volatile? Which way must a pricing failure be biased, and why?

Quiz Bank

FoundationalHow do you find the nearest available drivers efficiently?

Not by computing distance to every driver. With a million drivers and 5,000 requests a second, that is five billion distance calculations a second, which is absurd — and it would still be wrong, for reasons the ranking step covers.

Use a cell-based spatial index. Divide the world into cells using a hierarchical scheme, and maintain a map from cell identifier to the set of drivers currently inside it. A driver's ping updates one field if they stayed in their cell, or moves them between two sets if they crossed a boundary — constant time either way, which is what makes 250,000 writes a second affordable.

Search reads the rider's cell plus its immediate neighbours. The neighbour inclusion is not an optimisation, it is the correctness requirement: a driver ten metres away may be on the other side of a cell edge. This is exactly why matching on a shared text prefix is a wrong answer — at a boundary, two adjacent cells can have entirely different prefixes, so prefix matching silently ignores the closest driver.

If the first ring yields too few candidates, expand outward. The loop terminates on candidate count, not on a fixed radius, and that is what lets one algorithm serve both a dense city centre (enough candidates in the first ring) and a rural area (four rings out and still counting) without per-city tuning.

Then rank, and here is the correction that matters: rank by travel time along roads, not by straight-line distance. A driver 200 metres away across a river with no bridge is useless; one two kilometres away on a clear main road arrives first. That means a maps-service call per candidate, which is the slowest step in the loop, which is why the candidate list must be capped before ranking rather than after.

Ranking is not purely about arrival time. Acceptance rate, rating, and how long a driver has been idle all belong in the score — the last one because a system that always picks the nearest car starves drivers waiting in quiet areas, and drivers who never receive offers stop working for you.

The scale property worth stating: because the index is partitioned by geography and every query is local to one region by the nature of the problem, this structure scales horizontally by adding regions with essentially zero cross-shard traffic.

InterviewTwo riders request simultaneously and the same driver is best for both. How do you guarantee no double-assignment?

Make the assignment a single conditional write and let the affected-row count be the verdict.

UPDATE rides SET driver_id = :d, state = 'assigned'
 WHERE ride_id = :r AND state = 'matching';

One row affected means this caller won. Zero means somebody else got there first, and the caller receives an immediate 409. The driver's own availability is claimed in the same transaction with UPDATE drivers SET current_ride = :r WHERE driver_id = :d AND current_ride IS NULL, so a driver cannot be assigned to a ride while another ride already holds them (10.4).

Why not a distributed lock service? Because it adds a network round trip, a lease that must be renewed, a fencing token to stop a stalled holder from acting on a lock it has already lost, and a completely new failure mode — all to achieve mutual exclusion that a single-row conditional update already provides for free, with no additional component to run, monitor and reason about (10.7.2). Reaching for coordination machinery when the data store's own atomicity is sufficient is the most common over-engineering in system design, and naming it as such is a strong signal.

The constraint this imposes, stated as a cost rather than hidden: the assignment record has to live in one consistent store. You cannot spread the ride's state across three services and keep this property, which is a solid argument for a single service owning the whole ride lifecycle (10.8.3).

And the part that is about people rather than rows. Losing drivers must be told instantly, so their app returns them to the pool rather than showing a spinner that resolves into nothing. Their acceptance rate must not be penalised for a race they could not have won. Otherwise the mechanism that makes matching fast — offering to several drivers at once — quietly punishes exactly the drivers who respond fastest, and they learn to respond slowly.

InterviewWhy is it acceptable for the live location index to be in memory with no durability at all?

Because the recovery mechanism is the normal traffic. Every driver reports their position every four seconds. If the entire index is lost, then four seconds later every active driver has reported again and the index is complete. There is no restore procedure, no replay, and no data to recover — the system rebuilds itself from load it was going to receive anyway.

That property only holds because of a second decision: matching never reads location history. If the matcher needed a driver's trail, or their position five minutes ago, the live index would have to be durable and the whole write-path argument would collapse. Keeping history in a separate asynchronous path is what makes the live path disposable.

The time-to-live does the other half of the work. Each record expires after about 30 seconds. A driver whose app crashes, whose battery dies, or who drives into a long tunnel simply stops appearing — no sign-out message required, no cleanup job, no phantom cars that riders get matched to and that never arrive. "We stopped hearing from them" and "they are not available" become the same state, which removes an entire class of stale-data bug.

What is genuinely lost when the index goes: matching in that region fails for a few seconds, and riders see "no cars available", which is honest. No ride is left half-assigned, because ride state lives in the durable store and every transition is guarded.

The general lesson worth extracting: data that regenerates itself faster than you could restore it does not need durability. Recognising which data has that property — and refusing to spend durability on it — is a large part of why this system can absorb 250,000 writes a second on ordinary hardware.

StaffNew Year's Eve. Demand is 8× normal in dense areas, matching latency is 45 seconds, and drivers report offers that expire before they can tap. Diagnose and respond.

Three interacting failures, and they have to be separated before anything is changed.

One: contention over a tiny candidate set. At eight times the demand with unchanged supply, many concurrent requests find the same few available drivers in the same dense cells. Every driver receives several simultaneous offers and loses all but one of the conditional-update races — which is precisely the reported symptom of offers vanishing — while each lost race is a wasted matching cycle that inflates latency for everybody.

The fix: soft reservation. When an offer is dispatched, hold that candidate provisionally with a short expiry, so a second matching pass skips them. Combine it with batch matching: instead of racing greedily per request, collect riders and drivers over a short window and solve the assignment across the whole set at once. Batch matching is measurably better under scarcity, and it is what mature systems switch to at peak.

Two: ring expansion storms. With supply scarce, the adaptive expansion loop widens again and again, each iteration reading more cells and — the expensive part — asking the maps service for a travel time per additional candidate. Latency grows faster than linearly with scarcity, because scarcity causes both more expansion and more candidates per expansion.

The fix: cap the expansion, cap the number of candidates ranked, and cache travel times coarsely during peak. A travel time that is thirty seconds stale is acceptable; a forty-five-second match is not. This is a deliberate accuracy-for-latency trade, and it should be a pre-built, pre-tested degradation mode rather than something invented during the incident (10.9).

Three: the offer deadline is calibrated for the wrong conditions. A fifteen-second deadline assumes a driver glancing at a parked phone. On New Year's Eve, drivers are moving through heavy traffic. The instinct is to shorten it, which makes things worse. Instead reduce the number of parallel offers, so fewer races are wasted, and lengthen the deadline slightly — relying on soft reservations so the longer hold does not block other riders.

Beyond the incident, the systemic responses.

Supply-side levers beat any code change at eight times demand. Surge pricing is exactly the mechanism for signalling scarcity and pulling drivers into the market, and its feedback loop needs to be fast at peak — short windows, computed per cell — while still being quoted and held per rider.

Demand shaping. Honest wait-time estimates and a "request later" option reduce futile requests, which reduces contention directly and costs nothing to build.

Capacity, planned in advance. New Year's Eve is forecastable. Regional capacity, maps-service capacity and batch-matching parameters should be pre-scaled and pre-tested, because scaling during the event is a race you lose.

The framing that makes this a staff-level answer: under scarcity, matching stops being a search problem and becomes an assignment problem. Greedy per-request matching is optimal when supply is plentiful and pathological when it is not, so the system needs both modes and an automatic signal to switch — driven by the measured supply-to-demand ratio, decided in advance, rather than by somebody's judgement at two in the morning.

Flashcards

FlashThe scaling inversion

250,000 location writes a second against 5,000 ride requests a second — fifty to one. The write path is the hard part, unlike every other study in this Part, and that ratio forces the whole design.

FlashThe spatial index

cell → set of drivers, hierarchical scheme, and the operation you actually need is neighbours. Search = own cell + neighbours, widening until enough candidates. Prefix matching misses drivers across a boundary.

FlashRanking

Travel time along roads, never straight-line distance — a river with no bridge makes distance meaningless. Plus rating, acceptance rate and idle time, the last of which stops quiet-area drivers from being starved.

FlashNo double assignment

UPDATE … WHERE state = 'matching', with the affected-row count as the verdict, plus the driver claim in the same transaction. The conditional write is the lock. Losers get an instant 409 and no acceptance-rate penalty.

FlashWhy the location index can be volatile

It rebuilds in one ping interval from traffic that is arriving anyway, and matching never reads history. A 30-second time-to-live makes a silent driver expire instead of becoming a phantom car.

FlashPricing bias

Quote at request time and hold it for the trip. A stale surge feed falls back to the base price, never the last known high one — pricing failures must be biased toward the customer.

Scenario Drill

DrillAdd scheduled rides ('pick me up at 6 AM tomorrow') and pooled rides (two riders sharing one vehicle). Which is harder, and why?

Scheduled rides look hard and are mostly plumbing. The mechanism is a durable timer (11.18): store the request with a target time, wake matching at the target minus a lead time, and from there it enters the normal flow. The lead time is derived from that pickup area's historical match latency plus travel time, so it is a number you compute rather than guess.

The genuine difficulties are product, not architecture. Matching too early wastes a driver's time and invites them to cancel. Matching too late risks no supply at all. And the promise made to the rider — "a car will be there at six" — is stronger than the system can actually guarantee, so the design needs an escalation ladder (widen the search, raise the incentive, tell the rider early if it is going badly) and an honest failure path that gives them time to make other arrangements. Add idempotency so a scheduler retry cannot trigger the ride twice (10.4), plus cancellation handling, and the feature is essentially done.

Pooling is genuinely harder, and it changes the problem class. Matching stops being "find the nearest driver" and becomes online route optimisation with constraints. Given a vehicle already carrying rider A, with a committed route and a promised drop-off window, the question is whether inserting rider B's pickup and drop-off keeps both promises within acceptable detours — and then, across every vehicle for which the answer is yes, which insertion costs the system least. That is a dynamic vehicle-routing problem, computationally hard in general, and solved in practice by insertion heuristics that score detour cost across the candidates the cell index returns, evaluated under a strict time budget.

Four consequences that ripple outward.

The state machine multiplies. A trip is no longer one rider's linear progression. The vehicle now has an itinerary of ordered stops, each belonging to a different rider with its own state, so in_progress has to express "carrying A, en route to collect B".

Pricing becomes coupled. Rider B's fare depends on A's route, and A's experience — the detour — depends on B. The quote-and-hold guarantee from section 6.5 now has to cover a detour that has not happened yet, which means the platform absorbs that uncertainty as well.

Promises become interdependent. A delay for A cascades into B's arrival time, so each rider needs a time guarantee with slack built in, and the system must sometimes decline a profitable match in order to protect a promise it already made. That is a policy decision that has to be made explicitly, because the greedy answer is always to take the match.

Cancellations destabilise. If A cancels after B was matched on the assumption of a shared route, B's price and route both change, and the system must either re-optimise on the spot or absorb the loss. Neither is free, and choosing which is a business decision.

The comparison to state plainly: scheduling adds a timer and a set of product promises. Pooling adds a combinatorial optimisation to the hot path and turns independent trips into a coupled system, where every match constrains every future match. One is an integration; the other is a different system wearing the same API.