Design a ride-sharing backend: geospatial indexes, location updates at scale, driver matching, ETA, trip state machine, surge pricing, payments and failure modes.
What you'll learn: By the end of this lesson you will be able to (1) choose and explain a geospatial index (geohash, quadtree, S2, H3) for finding nearby drivers, (2) design high-rate location ingestion, (3) model a trip as a state machine with safe, idempotent transitions, and (4) explain matching, ETA, surge pricing and payment flow at a high level.
Picture a taxi dispatcher with a huge wall map covered in pins, one for each cab, moved every few seconds. A caller phones in. The dispatcher looks at the area around the caller, picks a nearby free cab, radios the driver, and waits for a yes. If the driver does not answer, the dispatcher tries the next one. Meanwhile pins keep moving, and two callers must never be promised the same cab.
A ride-sharing backend is that dispatcher at city scale. The interesting problems are all about the map: finding nearby things quickly when everything moves constantly, assigning each driver to at most one rider, and keeping a trip's state correct when phones lose signal.
Turn "near me" into a lookup. Searching every driver by distance does not scale. Instead, divide the world into cells, store each driver under the cell that contains them, and answer "who is near this point" by reading the point's cell and its neighbours. Everything else (matching, ETA, surge) builds on cell-based queries over a fast, in-memory view of driver positions that is allowed to be a few seconds stale.
Requirements and scope
Functional: riders request a ride from a pickup point to a destination, see nearby drivers and an estimated fare and arrival time, get matched with a driver, track the driver, complete the trip and pay. Drivers go online or offline, stream their location, accept or decline offers, and navigate.
Out of scope: maps and turn-by-turn navigation internals, ride pooling, driver onboarding and fraud systems, detailed tax and regulation handling.
Non-functional (assumptions):
The first offer goes to a driver within a few seconds of the request.
Location is "fresh enough": driver pins a few seconds old are acceptable.
Never assign one driver to two active trips, and never charge a rider twice for one trip (correctness over speed for these two).
Highly available in each city. Cities are largely independent, which helps scaling.
Back-of-envelope estimate
All numbers are illustrative assumptions.
Quantity
Assumption
Result
Online drivers at peak
1 million worldwide
Location update interval
every 4 seconds
250,000 updates per second
Update size
about 100 bytes
about 25 MB per second ingress
In-memory driver state
1 million x about 100 bytes
about 100 MB, which is small enough to fit on one machine
Trips per day
20 million
about 230 per second average, about 700 per second at 3x peak
Rider app polling or streaming
5 million active riders viewing nearby cars at peak, update every 5 s
about 1 million nearby-driver queries per second at peak
Trip events
about 10 state changes per trip
about 2,300 writes per second average, about 7,000 at 3x peak
Two insights. First, the driver location state is tiny: a few hundred megabytes at most, so it lives in memory, sharded by region mainly for throughput and failure isolation rather than size. Second, the load is dominated by location writes and nearby-driver reads, not by trips. Trips are low-rate and need strong correctness. Locations are high-rate and can be lossy.
API design
PUT /v1/drivers/{id}/location { "lat": 12.9716, "lng": 77.5946, "heading": 90, "ts": 1760000000 }
POST /v1/drivers/{id}/status { "state": "online" }
GET /v1/nearby?lat=..&lng=..&radius=1500
POST /v1/trips { "pickup": {...}, "dest": {...}, "idempotencyKey": "..." } -> 201 { "tripId": "t_1" }
GET /v1/trips/t_1
POST /v1/trips/t_1/offers/{offerId}/accept (driver)
POST /v1/trips/t_1/cancel
Location updates usually travel over a persistent connection or a lightweight protocol rather than a new HTTP request per update, to cut overhead. Trip creation takes an idempotency key because a mobile client on a weak network will retry (see API design).
Geospatial indexing: choosing the cell scheme
The central design decision is how to cut the Earth into cells. Four common options, stated carefully:
Geohash. Encodes latitude and longitude into a short base-32 string by repeatedly halving the range and interleaving bits. Nearby points usually share a prefix, and a longer prefix means a smaller cell. Weaknesses: two points either side of a cell boundary can have totally different hashes, so you must also query neighbouring cells, and cell size varies with latitude.
Quadtree. A tree that recursively splits a square region into four children only where needed, so dense areas split deeper than empty ones. It adapts to uneven density and is typically held in memory, but is harder to share across machines than a fixed grid.
S2. A library that maps the sphere onto a cube and divides each face hierarchically into cells with 64-bit IDs. Cells at one level are roughly similar in size, and IDs follow a space-filling curve, so a region is covered by a few ID ranges. Good for range queries in ordinary databases.
H3. A hierarchical grid of hexagons (plus a few pentagons), open-sourced by Uber. A hexagon's neighbours are all equidistant from its centre, which makes ring queries and smooth density analysis (like surge) cleaner. Coarser cells contain finer ones approximately, not exactly.
Scheme
Use when
Cost
Alternative
Geohash
Simple, string prefixes work in any store
Boundary problem, uneven cell size
S2 or H3 for better geometry
Quadtree
Very uneven density, in-memory index
Harder to distribute and persist
Fixed grid with finer cells in dense areas
S2
Range queries on a database, global coverage
Library dependency, cells are not hexagons
H3
H3
Neighbourhood and ring queries, analytics, surge cells
Approximate containment between levels
S2
None of these is "the correct" answer. The right interview move is to state the problem (nearby search with moving objects), pick one, and explain its boundary handling: always query the cell containing the point plus its neighbours, then filter by exact distance.
flowchart TD
S["Need nearby search over moving drivers"] --> A{"Density very uneven and index stays in memory?"}
A -->|yes| Q["Adaptive quadtree"]
A -->|no| B{"Need hexagon rings or smooth surge cells?"}
B -->|yes| H["H3"]
B -->|no| C{"Need range queries in an ordinary database?"}
C -->|yes| S2["S2 cell ID ranges"]
C -->|no| G["Geohash prefixes"]
Q --> N["Always query cell plus neighbours, then filter by distance"]
H --> N
S2 --> N
G --> N
How to read it: the answer depends on your store and your analytics needs, and every branch ends in the same boundary rule.
High-level design
The geo index is a sharded in-memory store: cell -> set of driver ids, plus driver -> latest location, cell, status. When a driver's update arrives, the ingest service moves them between cells if they crossed a boundary. Location updates are also written to a stream (for analytics, surge, replay and trip history) but the index is the serving copy. Trips go to a transactional database, because that is where correctness matters.
The durable records are few and small. The geo index is deliberately not among them.
erDiagram
RIDERS ||--o{ TRIPS : requests
DRIVERS ||--o{ TRIPS : drives
TRIPS ||--o{ TRIP_EVENTS : logs
TRIPS ||--o{ OFFERS : generates
TRIPS ||--o{ PAYMENTS : settles
DRIVERS {
string driver_id PK
string state
string current_trip_id
int version
}
TRIPS {
string trip_id PK
string rider_id FK
string driver_id FK
string state
string idempotency_key
}
OFFERS {
string offer_id PK
string trip_id FK
string driver_id FK
datetime expires_at
}
TRIP_EVENTS {
string trip_id FK
int seq
string event
}
PAYMENTS {
string payment_id PK
string trip_id FK
string status
}
How to read it: DRIVERS.state with its version is where the compare-and-set happens, and TRIP_EVENTS is the append-only history behind every state change.
Reference deployment topology
Cities are the natural unit of deployment: each city cell has its own ingest, geo index and matchers, while trips and payments sit in shared transactional stores.
How to read it: the bottom path (location gateway, ingest pods, Redis geo index) is lossy and high rate, the path through the trip service and its neighbours at the top is strict and low rate, and Kafka carries copies of location and trip events to analytics and surge (the dashed arrows) without slowing either. The driver-state record used for compare-and-set sits with the trip data in PostgreSQL trips, not in the Redis geo index.
Deep dive 1: location updates at scale
At 250,000 updates per second, the aim is to ingest cheaply and avoid hurting the database.
Do not write every point to the main database. Keep the latest position in memory, send raw points to a stream, and persist a thinned path only for active trips.
Shard by region (city or coarse cell prefix), so a nearby query touches one or two shards and a city's incident stays contained. Split hot cities further by cell.
Last write wins by timestamp. Updates arrive out of order, so ignore anything older than the stored value.
Expire stale drivers. Give each driver's record a TTL and treat missing heartbeats as offline. In Redis, individual members of a set or sorted set cannot carry their own TTL, so keep each driver under its own key with a TTL and have queries filter (or a sweeper prune) cell members by last-seen time.
Adaptive update rates. Update less often when stationary or when no rider is nearby, and more often during a trip.
Loss tolerance. Missing one point in a few is fine, so location can use cheap transport while trip events use reliable paths.
The main scaling issue is write throughput per shard and fan-out to riders watching cars. Throttle and coalesce rider updates, since nobody needs sub-second movement for cars two kilometres away.
Deep dive 2: matching, offers and trip state
Candidate search. Compute the pickup's cell, read it and neighbouring rings until you have enough candidates or hit a radius limit, filter to drivers who are online and available, and rank them. Straight-line distance is a fast first filter, but a driver across a river may be close in a straight line and far by road. So shortlist by distance, compute road ETA for the top few, and choose by ETA plus other factors (rating, vehicle type, acceptance history, waiting time).
Offer, not assignment. Send the offer to the chosen driver with a short timeout (for illustration, 10 to 15 seconds). If the driver declines or times out, offer to the next candidate. Batching riders and drivers over a short window to solve a global assignment can reduce total wait at the cost of a small delay. Sequential offers are simpler to reason about.
Never double-assign. The key correctness rule is that one driver can hold at most one active offer or trip. Implement it as an atomic compare-and-set on the driver's state: available -> offered(trip_id). If two matchers race for the same driver, only one succeeds and the other moves to its next candidate. The same applies at accept time: the transition offered(t1) -> on_trip(t1) succeeds only if the driver is still offered to that trip. Offers carry an expiry so a crashed matcher cannot lock a driver forever. The state used for this compare-and-set must live in a store with atomic conditional updates (or be reconstructable from the trip database), not only in the lossy in-memory location index.
sequenceDiagram
participant M1 as Matcher 1
participant M2 as Matcher 2
participant D as Driver state
participant DR as Driver app
participant T as Trip service
M1->>D: set offered t1 if available
D-->>M1: success
M2->>D: set offered t2 if available
D-->>M2: rejected
M2->>M2: try next candidate
M1->>DR: offer t1 with expiry
DR->>T: accept offer t1
T->>D: set on_trip t1 if offered t1
D-->>T: success
How to read it: the conditional write is the only arbiter. The loser never needs to know why it lost, it just moves on.
Trip state machine. Model the trip explicitly, with each transition triggered by one event and validated against the current state.
Persist each transition in the trip database with the previous state as a precondition (a conditional update), plus an append-only event log. Phones go offline mid-trip, so clients send transitions with idempotency keys and tolerate duplicates: applying trip started twice leaves the trip in InProgress. Because the client's view can lag, the server is authoritative, and the app re-syncs state on reconnect.
IMPORTANT
Use a database that supports atomic conditional updates for the trip and driver-state transitions. Eventually consistent writes without compare-and-set are how a driver ends up with two riders.
Deep dive 3: ETA, surge and payments
ETA. Estimating arrival time has two parts. First, routing over a road graph (intersections as nodes, road segments with travel times as edges). Plain shortest-path search is too slow at global scale, so routing engines use precomputed structures such as contraction hierarchies, or partition the graph by region. Second, adjusting for traffic: travel times come from historical averages by time of day plus live speeds derived from driver location streams, often corrected by a learned model. For the pre-match shortlist, straight-line distance over an average speed is acceptable, and the precise ETA is computed only for finalists. Cache ETAs by origin and destination cell pair for a few seconds.
Surge pricing (concept). When demand in an area exceeds the supply of available drivers, prices rise to rebalance: higher prices reduce marginal demand and attract drivers. Mechanically: aggregate requests and available drivers per cell over a sliding window, compute a demand to supply ratio, map it to a capped multiplier, smooth it over time and across neighbouring cells so prices do not flicker or jump at borders, and quote it to the rider before they confirm, locking it for that trip. Hexagonal cells make smoothing uniform. Surge policy has ethical and regulatory dimensions (caps during emergencies, transparency), which we flag but do not design.
Payments overview. Payments are an external, failure-prone dependency, so treat them with the care in distributed transactions.
At request time, validate the payment method and optionally authorise (place a hold on) an estimated amount.
At completion, compute the final fare from distance, time and surge, then capture the payment with the provider.
Send every provider call with an idempotency key derived from the trip ID and the operation (authorise, capture), so a retry does not charge twice.
If capture fails, move the trip to PaymentFailed, retry with backoff, and block the rider from new trips until resolved.
Record payment events through a transactional outbox so the trip database and the payment workflow cannot disagree after a crash.
Payouts to drivers are an asynchronous batch process built on the same event log, with reconciliation against provider reports.
Bottlenecks and scaling
Location ingress. Scale gateways horizontally, shard ingest by region, and use lightweight protocols. Coalesce updates for downstream consumers.
Geo index hot cells. An airport, stadium exit or city centre concentrates thousands of drivers and riders. Use finer cells in dense areas or a quadtree, cap per-cell query results, and spread hot cells across shards.
Nearby reads from rider apps. Update at a modest interval, cache per cell for a second or two, and send diffs rather than full lists.
Matching throughput. Run matchers per city, and keep their data local (the cell index) so a match decision is a few in-memory reads and one conditional write.
Trip database. About 7,000 writes per second at peak is manageable for a sharded transactional store, and far less per city. Shard by trip ID or city, and keep active trips in a small hot table, archiving completed ones.
Failure modes
Failure
Effect
Mitigation
Geo index shard lost
Nearby results empty in a region
Rebuild from the next few seconds of location updates, replicas for fast failover
Driver app loses connection mid-trip
Missing path points, stale status
Buffer on device and upload later, server keeps trip state, mark driver stale only for offers
Matcher crashes with an offer outstanding
Driver locked
Offers have expiry timestamps, another matcher restarts the search
Two matchers pick the same driver
Double booking risk
Atomic compare-and-set on driver state
Payment provider outage
Cannot capture
Complete the trip anyway, queue captures, retry with idempotency keys
Surge calculation stalls
Stale or missing prices
Fall back to the last good multiplier with a short validity, or to no surge, per policy
Routing or ETA service slow
Slow matching
Timeouts, fall back to distance-based estimates
Duplicate client retries
Duplicate trips
Idempotency keys on trip creation
City-level incident
One city down
Cells and services are partitioned by city, so the blast radius is limited
Trade-offs worth stating
Decision
Option A
Option B
How to choose
Spatial index
Fixed grid cells (geohash, S2, H3)
Adaptive quadtree
Fixed grids are easier to shard. Quadtree handles extreme density
Matching
Sequential offers
Batched global assignment
Sequential is simple. Batched can lower average wait at the cost of delay
Location durability
Lossy and in memory
Durable per point
Lossy for serving. Durable stream for analytics and active-trip paths
Ranking
Straight-line distance
Road ETA
Distance to shortlist, ETA to decide
Driver state
Eventually consistent
Atomic conditional updates
Atomic for assignment and trip state. Eventual for presence and pins
Interview cheat sheet
Step
What to say
Key numbers (illustrative)
Requirements
Request, match, track, pay. Never double-assign or double-charge
20M trips per day
Estimate
Location writes dominate. State is tiny
250k updates/s, about 100 MB state, about 700 trips/s peak
API
Location stream, nearby query, trip create with idempotency key
Offers with expiry
Data
In-memory geo index, trip DB with event log, location stream
Latest value only in memory
Design
Gateway, ingest, geo index, matching, ETA, pricing, payments
Shard by city or region
Deep dives
Cell scheme and boundaries, compare-and-set matching, trip state machine
Query cell plus neighbours
Failures
Index rebuild, matcher crash, payment outage, hot cells
Idempotent transitions
Trade-offs
Geohash vs S2 vs H3, sequential vs batch matching, distance vs ETA
Correctness where money and assignment are involved
In practice: operating the reference design
NOTE
A realistic scenario, not a case history. This is a composite example built from common production patterns. It does not describe any specific company, and every number in it is an illustrative assumption.
Assume a team of fifteen runs this on Kubernetes with one deployment cell per city or region, Redis for the geo index, Kafka for location and trip events, PostgreSQL for trips and the versioned driver-state record, an external payment provider, and Prometheus and Grafana for monitoring.
SLOs and dashboards
SLI
SLO (assumed)
Dashboard panels
First offer latency
95% of requests get a first offer within 5 s
Request to offer time, candidate count, offer accept rate
Nearby query
p99 under 200 ms
Query latency per city, cells scanned, cache hit ratio
The correctness SLI is a checker, not a latency: a scheduled query that looks for any driver attached to more than one active trip. Any hit is an incident.
Capacity-review cadence
Weekly: ingest lag by city, hot-cell query rates, matcher latency, offer expiry rate.
Monthly: driver count growth, update interval tuning against the 250,000 updates per second assumption, trip table size and archival.
Quarterly: replay a peak evening into staging, drill a geo-index shard loss, and test payment-provider failure handling.
Before events and holidays: stadium and airport cells need finer resolution and extra matcher capacity.
Runbook
Symptom
Likely cause
First check
Mitigation
No nearby drivers in a city
Geo index shard lost or ingest stalled
Shard health, ingest lag
Fail over to replica, let updates repopulate in seconds
Offers time out more often
Matcher slow or ETA service degraded
ETA latency and timeouts
Fall back to distance-based shortlist
Driver shows two trips
Conditional update bypassed
Invariant checker, recent code changes
Cancel the later trip, patch the write path, add a test
Fares flicker between values
Surge not smoothed or stale cell data
Surge input lag, smoothing window
Freeze to last good multiplier
Payments stuck in PaymentFailed
Provider outage or credential issue
Provider error codes, retry queue
Queue captures, retry with idempotency keys
One hot cell slows a shard
Airport or event crowd
Per-cell query rate
Use finer cells, cap results, spread the cell
Decision record: sequential offers with compare-and-set
Field
Entry
Context
Batched global assignment can lower average wait, but it is harder to reason about, and double assignment is the failure the business cannot tolerate.
Decision
Send sequential offers with short expiry. Enforce one active offer or trip per driver with a conditional update on a versioned driver record.
Consequences (good)
Simple to explain and test, easy to bound the blast radius, strong correctness.
Consequences (bad)
Higher wait in dense, contested areas, and each decline adds a round trip.
Revisit when
Measured rider wait in dense cells exceeds the target and a batched pilot shows a clear gain without breaking the invariant checker.
Cost view
Compute and memory for the location path dominate, followed by routing and map data, the event stream, and payment fees.
Cost driver
Lever
Location ingest
Adaptive update rates, batching on the device, lightweight transport
Geo index memory
Latest value only, TTL expiry, sharding by city
Routing and ETA
Cache by cell pair, distance shortlist before routing, precomputed graph structures
Event stream
Retention limits, thinned active-trip paths, compaction for state topics
Payments
Provider fee structure, retry discipline, reconciliation to catch leakage
Architect's notes
Measure location update value, not just volume. An update every 4 seconds may be wasteful when stationary. Adaptive rates are the cheapest scaling lever.
Ask where the correctness boundary is. Say out loud which data can be lossy (pins) and which cannot (assignments, charges), and give them different stores.
Cities are the organisational unit too. Give each city cell an owner and an on-call rota, or incidents become cross-team arguments.
The invariant checker is worth more than another dashboard. Run it continuously and alert on the first violation.
Defer batching and learned ETA. Ship sequential offers and a simple ETA first. Optimise when measurements justify it.
Rehearse the payment outage. Completing trips while captures queue is a product decision, so settle it with the business before an incident.
Common mistakes
Scanning all drivers by distance. It does not scale. Index by cell and query the cell plus neighbours.
Forgetting the cell boundary problem. Drivers just across an edge are missed. Always include adjacent cells, then filter by exact distance.
Writing every location to the main database. The write rate overwhelms it. Keep latest positions in memory and stream the rest.
Assigning without an atomic check. Races double-book drivers. Use compare-and-set on driver and trip state.
Letting offers live forever. A crashed matcher locks a driver. Give every offer an expiry.
Charging without idempotency keys. Retries double charge riders. Derive a key from the trip ID for every provider call.
Applying surge cell by cell without smoothing. Prices jump at borders and flicker over time. Smooth across space and time, and cap the multiplier.
Key takeaways
"Near me" is a cell lookup. Divide the map into cells and query a cell plus its neighbours.
Pick a cell scheme deliberately. Geohash is simple, quadtrees adapt to density, S2 gives range-friendly IDs, and H3 gives uniform neighbours.
Driver state is small and hot. It fits in memory. Throughput and failure isolation drive sharding.
Lossy for locations, strict for trips. Use different guarantees for different data.
Assign with compare-and-set. One driver, one active offer or trip, enforced atomically.
Model the trip as a state machine. Conditional, idempotent transitions survive retries and offline phones.
ETA is routing plus traffic. Shortlist by distance, then decide using road time.
Money flows need idempotency and an outbox. Retries must never charge twice.
Practice exercises
Exercise 1 — Starter (30 min): Using the illustrative numbers, compute location ingress per second if the update interval is 2 seconds instead of 4 and the driver count is 3 million. Then describe what changes if updates are batched every 10 seconds on the device.
Exercise 2 — Intermediate (2 hours): Implement, in pseudocode, the nearby-driver query: given a point and radius, compute the center cell and rings of neighbours, fetch drivers, filter by exact distance and availability, and stop early when enough candidates are found. Explain what resolution you choose for a dense city centre versus a suburb, and why.
Exercise 3 — Advanced (half day): Design the offer and accept protocol with concurrency in mind. Define the driver and trip records, the exact conditional updates, offer expiry handling, and what happens when the driver accepts after the offer expired, when two riders race for one driver, and when the matcher crashes after sending an offer. Write a test plan with fault injection for each case.
Related reading
Sharding - partitioning by region and handling hot cells.
Event streaming - the location and trip event streams behind analytics and surge.
Lesson 14 of 14 · Advanced System Design and Case Studies
Design a ride-sharing backend: geospatial indexes, location updates at scale, driver matching, ETA, trip state machine, surge pricing, payments and failure modes.
In the rest of this lesson
High-level design
Reference deployment topology
Deep dive 1: location updates at scale
Deep dive 2: matching, offers and trip state
Deep dive 3: ETA, surge and payments
Bottlenecks and scaling
Enrolling is free. It unlocks every lesson in Advanced System Design and Case Studies, tracks your progress across devices and keeps your quiz scores. The newsletter is optional.
Real architecture decisions, LLMOps patterns that survive production, and engineering leadership advice — from 12+ years of building at enterprise scale. Free. No spam. Unsubscribe anytime.
Get new articles by email
Free. We email a confirmation link first, and you can unsubscribe from any email.