Design a ride-hailing backend

01Problem and scope

A ride-hailing backend discovers nearby drivers, issues offers, commits one exclusive assignment, and maintains the trip lifecycle for both participants. Location suggests drivers who may be suitable; assignment records which driver has actually won the ride. For example, driver D17 appearing near a pickup point does not reserve that driver for ride R501. Acceptance must verify current offer, driver and ride state atomically before either client receives a successful assignment.

On one server, keep driver coordinates, a driver availability field, and ride records. Find nearby available drivers, then transactionally record an assignment. A transaction groups state changes so they either commit together or do not happen. This baseline exposes the key distinction: location search suggests candidates; assignment changes ownership.

Require at most one active assigned ride per driver and at most one winning driver per ride. Phones may disconnect, GPS may be stale and offers may arrive late, so discovery and notification are advisory. Scope the initial assignment protocol to one operating region where the driver, ride and offer records can be changed in the same database transaction (a shared transaction domain); pooling, cross-region matching, surge pricing and a full financial ledger are extensions.

The architecture separates three workloads: frequent position updates, candidate discovery and low-volume but correctness-critical assignment transitions. The design must preserve both assignment invariants while each workload scales independently. Its lifecycle continues through tracking and completion; a location or socket failure must not erase that durable state.

02Functional requirements

1. Publish driver state: Let drivers update position and driver availability; show riders fresh-enough nearby candidates.
2. Create a ride once: Network retries preserve one logical rider request.
3. Offer and accept: Send eligible drivers expiring offers; let them accept or decline. Only one driver may win a ride, and one driver cannot simultaneously win another active ride.
4. Track and recover: After assignment, both authorized parties can track the trip and recover the committed assignment after reconnecting.
5. Advance or cancel: Drivers advance allowed trip states; riders cancel under product rules. Cancellation must leave consistent driver/ride state and an event for any later billing policy.

Explicit trip lifecycle

requested → offering → assigned → in-progress → completed, with allowed cancellation transitions. A disconnected phone is neither a cancellation command nor a reason to end a trip or decide its fare. Discovery freshness and more tightly authorized active-trip tracking are different paths.

Workload and matching boundary

Define maximum ages for position observations and driver availability. Assume one million registered drivers and 500K daily active drivers; daily active does not mean simultaneously connected. The calculations deliberately assume 500K concurrent drivers at peak.

Initially, match within one operating region and one assignment transaction domain. Cross-region pooling or matching across an ownership boundary requires an explicit reservation/coordination protocol first.

Extensions

Routing, pooling, surge pricing and a full billing ledger are extensions. A separate service may supply routes and estimated times of arrival (ETAs) for ranking; neither a full routing engine nor a financial ledger is needed to prove exclusive assignment.

03Non-functional requirements

1. Position workload: Driver updates every three seconds at peak.
2. Discovery latency: Nearby-map p95 below 300 ms; first offer within two seconds under ordinary demand.
3. Assignment latency: Accepted assignment commits and becomes visible to both parties within one second p95, excluding driver decision time.
4. Availability: 99.95% trip API availability; reject unsafe assignments during an authority partition.
5. Durability: A successful assignment survives one database-node failure under the configured replica commit policy.
6. Position freshness: Reject discovery positions older than an illustrative ten seconds and recheck current driver availability before assignment. Return observation age: GPS error and network delay make map dots approximate.
7. Privacy and retention: Keep only necessary high-frequency location history under a stated policy. Operational trip records and billing events have different retention; restrict locations to authorized participants or suitably coarse nearby displays.

Assignment and trip invariants

Availability, freshness and privacy are separate guarantees. A reachable location service may hold stale points, and fresh points may still be unauthorized.

04Capacity estimates

Worked estimates

Size position ingestion and subscriber delivery separately from ride creation. A subscription is one viewer’s interest in updates for a driver; five viewers per driver therefore create more delivery relationships than driver records. The table’s ride-start rate sizes a different path: matching and durable assignment.

Capacity implications and limits

A minimal packed layout containing old/new coordinates and a three-byte driver ID totals 35 MB for one million drivers. Practical IDs, timestamps, sequences, state, and hash overhead require more. Do not broadcast three-second input as if a new measured position arrived every second; interpolation is a separate display choice.

With a threefold traffic headroom assumption, provision and test about 500,000 location updates/s, not merely the 11.6 average ride starts/s. Suppose a stored latest-position record is 128 bytes: 500K concurrent drivers consume about 64 MB logical latest state, but indexes, subscriptions and runtime maps can be much larger. Persisting every three-second sample for a day creates 14.4 billion samples, or about 1.84 TB/day at that envelope before replicas. This explains why latest state and historical telemetry need different stores/retention.

At 11.6 rides/s, a batch of three offers produces about 34.8 offer messages/s on average; a local station surge can be orders of magnitude above this. Match capacity is constrained by local available supply and ETA calls, not global averages. If each candidate ETA call takes 20 ms CPU and twenty candidates are evaluated per request, the matcher spends 400 ms CPU/request unless it batches, approximates or narrows candidates.

For push tracking, a slow client need not receive every intermediate coordinate. Coalescing to the latest sequence reduces queue memory while preserving the freshest display; it is unsuitable for durable trip state transitions, which must remain replayable.

05APIs and contracts

Request and response example

POST /rides  Idempotency-Key:k8
{pickup:{lat,lon},destination:{lat,lon}}
→ {rideId:R501,state:offering,version:2}

POST /offers/O81/accept {expectedVersion:3}
→ {rideId:R501,driverId:D17,state:assigned,assignmentId:A77}

The server derives rider/driver identity from authentication. A ride creation retry with k8 and the same payload returns R501; conflicting payload reuse returns 409. Acceptance errors distinguish expired offer, unavailable driver, already-assigned ride and invalid actor. A duplicate successful acceptance returns A77, rather than saying “driver unavailable” after the first call already succeeded.

Position updates carry a session/boot generation and monotonic sequence. A sequence alone may restart at zero after an app reinstall, so establish an authenticated new session generation without allowing an old session to overwrite it. Include observation time and server receipt time; the server rejects implausibly old or invalid updates according to policy.

Reconnect APIs retrieve active trip and last durable event version for the authenticated participant. WebSocket events contain trip ID, event ID and version; gaps trigger status recovery. Cancellation/start/complete endpoints use expected versions and operation identities. A client cannot directly submit an arbitrary final fare; downstream billing consumes authorized lifecycle and pricing inputs under its own contract.

06Data model and access patterns

Three kinds of state describe a driver’s involvement: Position says where the driver was observed, availability says whether the driver can accept work, and Trip records the rider’s request and lifecycle. The matching service reads across these records, but only the assignment transaction may turn an available driver and an offered ride into a committed pair.

Authenticate the actor from credentials, not submitted driver ID. Maintain previous/current points for membership transitions; reject older sequences. Index trips by participant for reconnects. Offers have IDs, versions, and deadlines. Store durable change events beside trip updates so notifications can be retried.

Add regionOwner and an ownership epoch, the version number identifying the current regional writer, to driver availability and offer records. All active assignments for one driver are decided by that driver's current region authority. The baseline region contains both R501 and the driver availability record for D17 in one relational transaction domain. A region-routing directory directs acceptance there; the nearby spatial cell is not automatically the transaction owner.

An ownership epoch distinguishes successive regional writers. Fencing means enforcing that only the current writer may commit changes, so a paused or disconnected previous writer cannot resume and assign the same driver independently. Routing requests to the new owner alone would not stop the old writer.

Keep a unique active assignment per driver and a unique assigned driver per ride, enforced by schema constraints plus the guarded transaction. The assignment row A77 links both IDs and carries lifecycle/version. Store offer O81 with its target driver, ride, expiry and active status. Outbox e77 commits with the assignment so a crash cannot lose notification work.

The outbox is a stored notification-work record committed in the same transaction as A77. A delivery worker can retry sending it after a crash without recreating the assignment; receiving the notification and owning the ride are therefore separate events.

Latest position is keyed by driver/session/sequence; cell membership is a derived index. Trips are indexed by rider and driver for reconnect. Driver sessions map to connection gateways with expiring leases. These are different access patterns: losing a gateway session should not delete a durable trip, and losing a spatial cache should not make an assigned driver available again.

Commands that change driver availability use the same authority and expected version as acceptance. A client cannot mark itself AVAILABLE while an active assignment exists, and a location heartbeat cannot reset that state. Cancellation/completion release the active-assignment constraint and reciprocal driver/ride references in the same transaction. If cancellation first reads a tentative assigned driver to determine lock order, it locks that driver and ride, then revalidates the relationship and retries if it changed; do not assume an earlier read remained true while locks were acquired.

07Basic working design

One regional application and database

Start with one application, one database and a table of latest driver positions. The rider creates R501 once with k8. The application queries nearby available drivers, sends expiring offers through a simple connection gateway, and waits for acceptance. D17's O81 acceptance executes one short database transaction over the driver, ride and offer records.

Assignment transaction and lock order

The transaction locks D17, then R501 and O81 in a consistent order; it verifies the offer belongs to D17, is unexpired, the ride is still offering and the driver is available. It creates A77, updates both sides to assigned, records a replay result and outbox event, then commits. Only after the required durable commit does it tell D17 that the assignment committed.

Discovery is approximate

The nearby list may be stale: D17 might have moved or accepted another offer after it was assembled. That is harmless if final acceptance rechecks authority. If D18 accepts the same ride a moment later, the ride state rejects that driver. If D17 retries after losing the success response, the stored operation/offer result returns A77.

Baseline correctness and growth limits

This baseline is complete enough to test exclusivity. Its remaining limits are how many location writes and matches it can handle, and which regional failures it can survive.

08Find the baseline flaws

09Improve the design, step by step

A quadtree groups dense areas by repeatedly splitting them into four rectangles. Rebuilding/splitting that structure on every small movement wastes work. Store every fresh point by driver ID; update cell membership promptly on boundary crossings, coalescing movement inside a cell. Fixed or hierarchical cells are alternatives to a custom quadtree. H3 introduction.

Consider a spatial index that trails incoming locations by 10–15 seconds. At an assumed maximum 20 meters/second, fifteen seconds permits 300 meters of motion. Expanding candidate coverage by that bound can help only if speed, lag, and measurement error are truly bounded. Fresh filtering removes stale candidates but cannot recover omitted arrivals. Use different thresholds for splitting and merging, called hysteresis: for example, split above 550 records and merge below 450 around a target of 500. Small fluctuations near the target then avoid repeatedly splitting and merging the same region.

1. Change 1 — separate latest positions from trip authority. Trigger: location writes overwhelm assignment storage. A partitioned latest-position service accepts sequence-checked updates, while the spatial index changes primarily on cell crossings. This reduces database pressure and tree churn. Costs are index lag and two-store reads; final assignment still checks current driver availability. A single spatial database is simpler at smaller scale.

2. Change 2 — region routing and replicated assignment authority. Trigger: one region's durable writes/availability exceed one process. Route each driver and ride to a defined owner, replicate committed assignment state and fence old writers on failover. Independent regions scale in parallel, but cross-boundary matching now needs a protocol. Before transferring a driver, stop new offers and finish or cancel active ones. Transfer the saved state and ownership version, preventing the old owner from writing; a changed location alone must not create a second owner.

3. Change 3 — bounded matcher/offer workers. Trigger: station bursts and slow ETA work delay all requests. A durable request queue supports bounded candidate batches, offer deadlines and retries. It smooths spikes but adds queue latency and cancellation races. Workers verify current ride state before issuing the next batch; a canceled request must not keep generating offers. Synchronous matching remains simpler for a tiny workload.

4. Change 4 — dedicated connection routing and coalesced tracking. Trigger: 2.5M subscriptions and slow phones. A gateway directory maps users to sockets; durable trip events go through outbox delivery, while ephemeral position updates coalesce to latest sequence. This reduces backlog and lets reconnect recover state. The cost is subscription lifecycle and duplicate delivery; an unbounded per-client queue is rejected because old coordinates are less useful than fresh ones.

10Detailed architecture

High-volume location path

The final architecture has three paths. Driver location updates enter the position service, which writes the latest sequence/point and maintains regional spatial membership. Rider discovery and matcher queries use that spatial index, then fetch fresh points and current driver availability to build plausible candidates. The spatial index suggests drivers; it does not grant a ride.

Authoritative assignment path

Ride creation and offer acceptance route to the regional assignment service. Its replicated relational database stores rides, driver availability, offers, assignment IDs, saved retry results and outbox records. A current region/driver directory selects this owner. All competing accepts for D17 and R501 must reach this same transaction domain. If a product later requires arbitrary cross-region matching, the design needs a protocol that coordinates both regions. A distributed transaction can preserve atomic assignment; a reservation workflow instead needs explicit pending states and recovery rules before either side treats the assignment as final.

Matching and authorized notifications

The matcher consumes durable requests, calls a bounded ETA/routing service for shortlisted candidates and writes expiring offers through the authority. A delivery worker reads committed outbox events, looks up participant gateways and sends notifications. Mobile push may wake an offline app; reconnect fetches authoritative trip state. Position subscriptions flow through the same or separate gateways but use latest-only buffering.

Durable replicas versus session leases

The graph separates database replicas from connection/session leases. Replicas preserve assignment state; session leases only find connected phones. A lost session can delay delivery without changing who owns the ride. Driver availability is revalidated at acceptance even if the map still shows a driver as free.

Concrete relational implementation

PostgreSQL can implement the regional assignment domain with row locks, unique active-assignment constraints, scoped request-result rows and an outbox transaction. Its failover deployment must preserve acknowledged commits and fence the previous writer; ordinary asynchronous replicas do not establish that guarantee. A spatial cell service and latest-position cache may remain disposable. This chapter’s stated durability covers one database-node failure; surviving an availability-zone or whole-region loss additionally requires the corresponding replica placement, election and recovery design.

11Write path and acknowledgement

Ride acceptance must protect both sides of the assignment in one authority. The example identifies ride R501, driver D17, offer O81, assignment A77 and outbox event e77; these records survive a lost response.

1. The rider submits k8; the ride store creates R501 once in offering state.
2. The matcher obtains nearby IDs from the spatial index, reads fresh points, and filters unavailable/expired drivers.
3. It ranks by pickup suitability/ETA with product/rating constraints, then sends expiring offers to an illustrative batch of three drivers.
4. D17 accepts O81. In one transaction, lock/check R501 is unassigned and D17 is available at version 9; set R501→assigned(D17) and D17→assigned(R501), then record e77.
5. After commit, e77 informs the rider and D17; other offers are canceled idempotently.
6. If no valid offer is accepted before expiry, the matcher tries another bounded batch.

The two records must share a transaction domain or use an explicitly designed reservation protocol; two unrelated successful writes do not prove exclusive assignment.

The accepted O81 request is identified by driver, offer and operation key. After acquiring the relevant locks and before deciding a new result, the authority rechecks whether O81 or the scoped operation key already produced A77; this handles a response lost after commit. It then validates offer deadline, current driver owner epoch, ride version and driver availability under locks. Source versions and operation IDs are recorded with the transition.

When A77 commits, every subsequent current read sees D17 assigned to R501 or a later valid state. The outbox event e77 carries that assignment/version. Losing a notification does not release D17. Other offers are canceled as recoverable work, and their acceptance checks also see that the ride is no longer offering.

If the driver declines or the offer expires, the matcher can issue another bounded batch only after checking R501 remains eligible. Rider cancellation and acceptance serialize through the ride row. A cancellation that wins before assignment prevents acceptance; one that follows assignment executes the product's assigned-trip cancellation transition and releases D17 atomically. A timeout is an unknown result to query, not permission to create a parallel ride.

12Read and delivery path

Discovery queries approximate nearby supply, while an active trip read recovers an authoritative assignment and controls precise tracking access. These paths have different freshness, privacy and buffering requirements.

Coalesce slow-client queues to the latest coordinate; use WebSockets/long polling and mobile wakeup notifications as appropriate. Replicate location/notification state, but rebuild ephemeral subscriptions from clients if needed. Restrict location audiences and retention; inspect implausible jumps/replays. Measure position age, match/offer latency, double-assignment invariants, cancellation rate, queue lag, and recovery time.

For discovery, the rider's request covers nearby cells and asks for candidate IDs. The service loads the latest point for each candidate driver, removes expired/assigned drivers and returns approximate/coarsened display positions under policy. It may poll every five seconds or subscribe to cells, but must update subscriptions when the rider moves; subscribing only to the initially visible IDs misses newly entering drivers.

For R501 after assignment, the gateway authorizes the rider and D17 as participants by current trip state. Each new coordinate carries session/sequence, and a slow recipient's buffer keeps the most recent point rather than a minute of obsolete ones. A reconnect reads current A77/trip version and then resumes events after the last applied sequence where retained, fetching a snapshot if needed.

The trip status response comes from authority when the caller needs their just-committed acceptance. Arbitrary lagging replicas must not make D17 appear free immediately after the assignment committed. Historical trip reads can use a different consistency/latency path. Completion/billing notifications are durable events, whereas missing an intermediate map coordinate is acceptable.

13Correctness deep dive

Protect both driver and ride

D17 accepts R501 and R502 concurrently. The first transaction changes D17 from available to assigned. The second then sees the changed state and cannot assign that driver. If D18 also accepts R501, the ride-state check rejects that competing assignment. Explicit locks/conditional updates implement these checks; retries handle transactional conflicts. PostgreSQL locking.

Lost response does not undo assignment

A crash after commit but before notification does not undo the trip. Reconnect with the trip ID and read durable state; replay e77 if necessary. A timeout is not permission to create another assignment. Expire stale driver availability after location-server loss, but preserve active trip history. Billing consumes authenticated lifecycle events and reconciles uncertain completion instead of trusting connectivity.

transaction accept(driver D17, offer O81, operation K):
  authenticate driver; derive replay key=(driverId,K)
  lock driver D17; lock ride O81.ride; lock offer O81
  require authenticatedDriver == O81.driver
  if replay[driverId,K] exists:
      require saved payload matches this offer/operation
      return saved result
  if O81 already accepted by this driver: return its saved assignment
  require O81.active and freshAuthorityTime() < O81.deadline
  require driver.ownerEpoch == request.ownerEpoch
  require driver.state == AVAILABLE
  require ride.state == OFFERING and ride.driver is null
  insert assignment A77 with unique active driver and ride
  set driver=(ASSIGNED,R501); set ride=(ASSIGNED,D17)
  mark O81 accepted; insert replay[K] and outbox e77
  commit under replica policy; return A77

Two rides contend for one driver

Recover a committed assignment

Crash after commit: the database retains both sides, offer result and e77. Replaying K returns A77. Crash before commit: all changes roll back; another valid offer may win. Notification delivery never decides the winner.

Transaction-domain and fencing assumptions

Replay and expiry checks after lock waits

14Failure and recovery

During a station surge, cap match attempts, offer batches and ETA calls. A large request queue can turn a two-second first-offer goal into an invisible ten-minute wait; expose waiting/capacity outcomes and expire stale demand. Do not send unlimited simultaneous offers to every driver, which creates distracting races and poor acceptance behavior.

Reconnect storms pressure authentication, gateway directories and current-trip reads. Randomize client reconnect delays, combine repeated position requests where possible, and reserve capacity for assignment/status recovery. Missing position updates make location stale, not trip completed. A late start/complete event from an old driver session must pass current actor, assignment and transition checks before changing durable state.

The system cannot guarantee that a displayed driver will still be available when a rider submits a request. It guarantees that only a valid committed acceptance creates an assignment, and that a lost delivery does not create another winner.

15Operations, security, and cost

Location and assignment signals

Monitor received position age, observation lag, dropped old sequences, candidate-to-offer ratio, first-offer latency, acceptance commit latency, cancellation/expiry outcomes and notification lag. Continuously check that active assignment tables contain no duplicate driver or ride ownership and that reciprocal references agree. This is more direct than watching HTTP 200 rates.

Identity and location-disclosure controls

Authenticate location updates and reject implausible jumps or replayed sessions with a policy that accounts for noisy GPS; do not silently treat spoof-resistant location as solved. Only assigned participants may receive precise active-trip tracking. Audit administrative location access and apply retention limits to raw telemetry. Nearby display can use coarse or delayed points where product requirements permit.

Position-history and subscriber costs

At 500K concurrent drivers and three-second updates, storing every 128-byte sample creates roughly 1.84 TB/day logical; seven days and three replicas exceed 38 TB before indexes. Keeping only latest state plus a selected telemetry/history stream can sharply reduce hot storage, but the retained history must still meet debugging and product needs. Subscription fanout and mobile network egress are separate costs.

Lifecycle rollout and race tests

Roll out a new assignment state with readers first, then writers. Test D17 accepting two rides, D17/D18 accepting one ride, cancellation at the commit boundary, primary loss after acknowledgment and region transfer with a paused old owner. Replay a realistic city-density trace to measure spatial lag and offer quality, rather than distributing fake drivers uniformly over the globe.

16Decision ledger and limitations

Partitioning by cell improves location lookup, but assignment ownership should not churn on every boundary crossing. One driver moving ten meters should not trigger a distributed transaction migration. Separate spatial membership from durable regional authority and define transfers deliberately.

A 10–15-second spatial-index delay is not automatically harmless. At 20 m/s, fifteen seconds permits 300 meters of motion; expanding coverage helps only with defensible speed, lag and measurement-error bounds. Otherwise accept and measure reduced discovery recall or improve the index path. Fresh filtering corrects wrong candidates but not missing arrivals. These distinctions matter more than choosing a fashionable spatial index name.

17Interview closing

“I separate high-volume location discovery from durable ride assignment. Drivers publish sequence-checked points into a latest-position service and spatial index. A matcher uses those approximate candidates, fresh points and bounded ETA work to issue expiring offers. Acceptance routes to one regional authority and atomically checks both the ride and driver before assigning them. Two rides cannot win one driver, and two drivers cannot win one ride, because the same transaction guards both records and records the replay result and outbox event.

“Committed trip state survives lost sockets; reconnect retrieves it. Position delivery can coalesce intermediate updates, but trip transitions remain durable. The tradeoffs are spatial freshness, regional ownership boundaries and limited offer batching. I would next measure the fraction of eligible nearby drivers found by discovery in each city, first-offer latency and assignment behavior under concurrent accepts and primary failure.”

If the interviewer adds pooling, the exclusivity invariant changes from one active ride to a capacity/route-compatible assignment set, requiring a new guarded optimization and reservation model. If they add cross-region matching, introduce an explicit driver reservation/transfer protocol or a distributed transaction system. Neither change is solved by retaining the old claim and drawing more matcher boxes.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.