Design an Uber-style ride service

01Functional requirements

A ride service first finds possible drivers, then asks one of them to accept. Finding a driver on the map does not reserve that driver. We will keep fast, approximate location search separate from the final assignment decision.

1. FR1: Driver availability. Let an authenticated driver report available, assigned, or offline status subject to server-side trip ownership. An assigned driver cannot become available merely by sending a new client flag.

2. FR2: Driver location reports. Accept driver locations from verified sessions, using increasing sequence numbers to reject reports that arrive out of order. Use those reports to find possible drivers and update the active-trip map.

3. FR3: Fare and arrival quote. Return a versioned basic fare quote and estimated pickup time for a pickup, destination, and service class. The server saves the quoted price; the browser references that quote rather than supplying its own charge amount.

4. FR4: Trip requests. Create one recoverable trip process for each rider request identity. After reconnecting or retrying, the rider can retrieve that same trip’s matching, assigned or ended state.

5. FR5: Driver offers. Find eligible nearby candidates and send expiring offers. If the bounded matching attempt finds no accepting eligible driver, return an explicit unmatched outcome rather than leaving the rider waiting indefinitely.

6. FR6: Driver acceptance. Accept an offer only if the trip is still matching, the driver is still available and the offer has not expired. Only the server currently permitted to write assignment records may make that decision. A replaced server cannot commit a late assignment.

7. FR7: Cancellation. When cancellation policy allows it, let the trip handler save the cancellation and any driver release together in the trip database. A cancellation that wins before acceptance must prevent a stale offer from reviving the trip.

8. FR8: Trip status. Keep the rider and assigned driver informed with versioned lifecycle status and necessary live location updates. Notifications may be retried; both participants can read current trip state.

Out of scope

• Ride pooling and a production route or dynamic-pricing model. Basic fare and arrival estimates remain in scope.
• Using the approximate nearby-driver map as an assignment authority; only the coordinated write path can claim a driver.

Example. Mina requests T1 while another rider requests T2. Both searches may discover D1. Discovery makes D1 a candidate for both; it grants neither trip ownership of D1.

02Nonfunctional requirements

These are independently chosen exercise assumptions to validate, not measured production guarantees.

1. NFR1: Initial-offer latency. Publish an initial offer within five seconds for at least 95% of admitted matching requests in the stated exercise workload, measured from durable trip creation. Record requests with no eligible driver separately and count their matching outcomes; this is not a promise that a driver accepts.

2. NFR2: Candidate-location freshness. At least 95% of candidate positions inspected during matching should have a valid report younger than ten seconds. Measure age before removing stale candidates, then reject reports outside the cutoff before offering; map animation rate is not the measurement.

3. NFR3: Telemetry capacity. Plan for 200,000 driver reports/second under the stated assumptions. Size this frequent location-report path separately from the smaller set of transactions that claim drivers and trips.

4. NFR4: Trip-request capacity. Plan for about 230 trip requests/second at the assumed peak. Include offer waves, acceptance contention, and notification work in the capacity test.

5. NFR5: One driver per trip. Allow zero active trips with more than one assigned driver. The assignment transaction checks the current trip state, valid offer and current assignment owner before committing.

6. NFR6: One active trip per driver. Allow zero drivers with more than one active trip. Claim the driver and trip together; two independent best-effort record updates do not establish this guarantee.

7. NFR7: Transition recovery. After a trip-state change reports success, a process crash must not lose that saved state or the work to notify its participants. The trip handler saves both together under the agreed database durability settings. A lost reply or notification recovers the same trip, operation and version. If the service cannot establish which server may currently write, temporarily reject assignment.

03Back-of-the-envelope Estimates

The app sends far more location reports than trip requests. Giving both the same write path would make the correctness-critical assignment work compete with much larger map traffic.

1. Location reports. One million online drivers sending every five seconds create 1,000,000 ÷5 =200,000 reports/second. At 100 bytes each, raw ingress is 20 MB/second. Give this path its own capacity budget.
2. Position retention. Saving every report would add about 20 MB ×86,400 =1.73 TB/day before indexes and copies. Saving only one latest 100-byte report per driver is about 100 MB raw. Keep history only for a defined audit or analytics purpose.
3. Trip requests. Two million trips/day average 2,000,000 ÷86,400 ≈23/second. A chosen tenfold peak is 230/second. If matching tries three rounds and inspects five drivers per round, peak work is 230 ×3 ×5 =3,450 candidate evaluations/second. Limit those rounds; more location reports do not justify unlimited matching.
4. Trip records. At 5 KB for each trip and its lifecycle events, two million trips add 10 GB/day raw. Routes, maps and verbose logs need separate byte estimates.
5. Connected apps. Assume two million simultaneous rider/driver connections and 20 KB of server state per connection. That is 40 GB across the gateway fleet before actual encryption, buffers and runtime costs. Measure those costs and test reconnect bursts.
6. Busy regions. A stadium exit can overwhelm one region while the global average remains low. Measure local report rate, matching attempts and competing assignment transactions, keeping spare capacity for a failed server.

04API Design and Retry Contracts

Mina’s app first asks for a quote. The server saves its price, route inputs and expiry as Q17. Mina then references that quote when starting her trip; T1 is the saved trip ID returned to her.

POST /trips
Idempotency-Key: mina-trip-17
Content-Type: application/json

{"quoteId":"Q17"}

{"tripId":"T1","state":"matching","version":1}

1. Quote the trip. POST /quotes takes pickup, destination and service class. It returns quoteId, estimated fare, currency, expiry and estimated pickup seconds. The server sets the price; a browser-provided amount is not a fare decision.
2. Create one matching process. POST /trips takes the quote ID and rider idempotency key. Save the key’s result with T1, then return 202 and matching. A retry with that key retrieves T1 instead of starting another trip. The 202 does not mean a driver has accepted.
3. Accept a specific offer. POST /offers/{offerId}/accept identifies the saved trip/driver invitation. The server returns its committed assignment or 409 if the offer expired, the trip ended or someone else won. The driver identity comes from authentication.
4. Report driver state. POST /drivers/me/locations and PATCH /drivers/me/availability verify the driver’s current session and increasing report sequence. The server rejects attempts to declare an already assigned driver available without a valid trip transition.
5. Cancel or recover. POST /trips/T1/cancel takes a stable command key and expected trip version. GET /trips/T1 returns current versioned state only to authorized participants, including an explicit unmatched result when matching ends without a driver. Both apps use it after a lost reply or notification.

05Data Model and Access Paths

The trip database makes the final assignment decision. The map only helps matching code find drivers to ask. For the example, T1 is Mina’s trip, T2 is another rider’s trip, and D1/D2 identify two drivers.

• A trip row records whether that trip is matching, assigned, in progress, completed, cancelled or unmatched. An offer row records which driver was invited and until when; sending it does not reserve the driver.
• A driver row records whether the driver already has an active trip. The acceptance transaction changes this row and the trip row together, so neither can claim an assignment without the other.
• An owner-permission record says which regional assignment process may write. Its number is stored as ownerEpoch. For example, a failover controller can replace permission 12 with 13. The database write path rejects an assignment carrying 12 once 13 is current. This checked permission number is an epoch; it is not a timestamp or a number a driver may choose.
• An outbox row records “send this committed trip transition” in the same database transaction as the transition. A relay program reads it later and retries delivery if a gateway or phone was unavailable.
• The latest-location row stores one verified session’s increasing report number and accepted coordinates. It supplies approximate discovery, not proof of assignment or physical presence.

Payment after completion has its own saved operation and provider reference. A trip’s assignment ID alone does not prove what a payment provider did.

06Baseline: Start with a regional matching authority

Start with one regional app, a spatial index and a transactional trip database. First follow Mina’s request to an offer:

1. The quote handler saves Q17. The trip handler validates it and saves T1 as matching with Mina’s creation-key result.
2. Matching code asks the spatial index for nearby apparently available drivers. It rejects old reports and wrong service classes; the index entry is only a candidate to inspect.
3. It uses straight-line distance to narrow the list, then compares road arrival estimates for a small finalist set. A river or one-way road can make the nearer coordinate slower by road.
4. It saves an offer row linking T1 and D1 with a server-time expiry, then the app’s connection code sends that invitation. Do not hold database locks while waiting for the driver’s phone.

When D1 accepts, the acceptance handler performs this short transaction:

1. Lock or conditionally claim the trip and driver records in a consistent order, reducing circular waits between competing transactions.
2. Check that the caller is D1, the offer belongs to T1/D1 and is unexpired, T1 is still matching and D1 is still available. Check the current regional write-permission number too.
3. Set T1.driverId=D1 and T1’s state to assigned. Set D1.activeTripId=T1 and D1’s state to assigned. Enforce unique active assignment so another transaction cannot claim either one simultaneously.
4. Save the accepted offer/result and pending notification work in that same commit. Return success only after the required records are durable.

A lock only inside one matching process is insufficient because another process can accept concurrently. The database must protect the paired decision. A conditional update is useful only if the whole trip/driver decision remains coordinated.

Sequential offers are simple but wait on declines. Small parallel waves improve the chance of a quick acceptance but create legitimate losing acceptances; they still use this transaction. Bound rounds and total matching time. If no driver accepts, the matching code commits an unmatched result. That terminal transition uses the same current-trip check, so a late offer cannot revive it.

07Evolution: Scale matching without weakening ownership

First test a larger regional server or database for the measured resource limit. Neither extra CPU nor extra location workers lets two writers assign one driver independently.

Move connections away from matching work

1. Run connection gateways to authenticate apps and keep their live channels. They deliver saved offers and status messages; matching workers focus on candidate selection and assignment attempts.
2. The relay reads a committed outbox row and sends its trip ID/version through the gateway. If the send succeeded but progress recording failed, it may send again. The app recognizes the same offer ID or trip version instead of treating it as a new assignment.
3. On reconnect, the app supplies the last trip version it applied and reads current T1 state. A missed notification must not erase the database’s assignment.

Divide location work without dividing ownership incorrectly

1. Location-ingest code accepts only a newer report number for the current driver session. Partition reports by region/cell and retain the latest position separately from optional history.
2. Background cell updates may temporarily list D1 twice or omit D1’s new cell. Matching code removes repeated IDs and checks latest accepted coordinates and age before offering.
3. Keep the trip and driver claim within one regional assignment authority. If proposed storage puts them on independent shards, co-locate the decision or show a real cross-store coordination protocol. Two unrelated “set assigned” calls are not the transaction above.
4. During a region handoff, the failover controller installs a new write-permission number. The database checks that number on every accepted assignment write. An old matcher carrying 12 cannot commit after 13 is current, even if its phone connections still work. If current permission cannot be established, pause assignments rather than allow two owners.

Supply/demand aggregates may improve pricing, but a good fare or arrival estimate does not claim a driver. Quote publication, discovery and exclusive assignment retain different records and responsibilities.

08Failure and Recovery Scenarios

Test each race against the saved trip and driver rows:

1. D1 accepts T1 and T2. Both searches may have found D1. If T1’s transaction claims D1 first, T2’s transaction reads assigned state and returns conflict, then searches elsewhere.
2. D2 also accepts T1. T1’s transaction allows one winning driver. A legal ordering is T1→D2 and T2→D1; D1 owning both trips or T1 owning both drivers is forbidden.
3. Success is saved but the reply is lost. Repeating the same accepted offer recovers its saved assignment instead of making another one. Read current trip state too if it has since been cancelled or completed. The outbox relay separately retries the missed notification.
4. Cancellation wins the race. A cancellation handler checks the same trip state and expected version. If it commits before acceptance, the old offer loses because T1 is no longer matching. An allowed assigned-trip cancellation releases the driver in the coordinated transition. Ending an in-progress ride follows its own fare/payment policy.
5. An old regional process remains alive. It still carries permission 12 after the controller installed 13. The database rejects 12, even if the old process’s map looks fresh. Changing routing alone would not stop that stale process from writing through another path.
6. The phone shows an expired offer. The server checks expiry, not the phone’s displayed screen or clock. If the current writer or required state cannot be verified, return a temporary failure instead of assigning from the map.

Authenticate each status read before returning precise pickup or location data. Notifications help people notice the result; only the saved coordinated transition decides it.

09Trade-offs and Validation

Use separate measurements for discovery, assignment and delivery:

• Discovery: report age, time before positions reach the index, repeated or missing candidates and busiest-region load.
• Assignment: time to first offer and final assignment, rejected-offer reasons, transaction waits, stuck matching attempts and any duplicate claim.
• Delivery: gateway memory, reconnect bursts, notification delay and the version recovered after a missed message.
• Privacy and abuse: trip-creation limits, location-query limits, access to exact coordinates and retention. A rider needs the assigned driver’s necessary status, not a history of every driver.
• Payment recovery: if completion charging is uncertain, reconcile the same saved payment operation rather than submit another charge ID.

Close by tracing Mina’s quote, saved T1, nearby candidates, expiring offer, paired acceptance transaction and reconnect read. The fast map proposes a driver; the main database checks and changes the two ownership records. Scaling the map must not remove that final check.