# Design Uber / Lyft (ride hailing)

> Match drivers to riders in real time at city scale. Geohashing, dispatch algorithms, surge pricing, and the realtime location pipeline.

Canonical: https://ironclad.academy/system-design/articles/design-uber | Difficulty: advanced | Topics: Interview, Geo, Realtime, Matching, Streaming
Asked at: Uber, Lyft, Amazon, Meta

## Key takeaways
- At ~450k global location writes per second, live positions belong in a sharded in-memory index — Redis sorted sets per H3 cell, or a Ringpop-style consistent-hash ring — because a relational database saturates its write-ahead log long before global peak.
- The atomic Redis SET NX EX command does the entire double-booking prevention in a single operation; splitting into SETNX plus EXPIRE creates a crash window that permanently locks a driver slot.
- Dispatch ranks candidates by contraction-hierarchy ETA, not raw distance — a driver 1.2 km away across a bridge may arrive later than one 1.8 km away on clear roads.
- Bipartite matching over 1-2 second request windows minimizes collective rider wait time across a cell; greedy nearest-first optimizes each request in isolation and produces worse aggregate outcomes.
- Surge pricing is a per-H3-cell control loop capped at 4x, recomputed every 30-60 seconds, with ML applied proactively so the multiplier leads imbalance rather than trailing it.

> **In one line:** Index millions of moving drivers in a geospatial data structure, dispatch the best one atomically, and stream live locations to both sides — a real-time matching problem that lives or dies on spatial indexing, atomic claims, and sub-second latency.

**The problem.** Riders open an app, see nearby drivers, and expect a match in seconds. Behind that: millions of drivers emitting location updates every few seconds, a dispatch system that must pick a driver, claim it atomically so no two riders get the same driver, and communicate the match to both parties — all within a latency budget riders never consciously experience.

**Requirements that drive the design.**
- Rider requests ride; dispatch finds and claims a driver; both sides see real-time location during the trip.
- p99 dispatch < 500ms; driver offer timeout ~15s; ride completion triggers fare calc + payment.
- Surge pricing per geo cell; adaptive to supply/demand in near-real-time.
- 99.99% availability — a dispatch failure is a stranded customer.

**Scale (back-of-the-envelope).**
- ~161M MAU globally (Q3 2024); ~28–31M trips/day ≈ ~360 avg / ~1,500 peak trips/sec.
- ~5–6M active drivers globally; assume ~2M online at peak.
- Each driver emits location every ~4–5s → ~400k–500k location writes/sec at peak.
- Location record: ~100 bytes → ~40–50 MB/s ingest; trivial for a Redis cluster.

**The architecture in one diagram.**

```mermaid
flowchart LR
    DRV[Driver app] -.location 4-5s.-> LP[Location<br/>Pipeline]
    RID[Rider app] -->|request ride| GW[API Gateway]
    GW --> DISP[Dispatch Service]
    LP --> GEO[(Geo Index<br/>Redis / H3 cells)]
    DISP --> GEO
    DISP --> ETA[ETA Service]
    DISP --> SURGE[Surge Service]
    DISP -.atomic claim.-> GEO
    DISP --> DRV2[Driver notification<br/>WebSocket / Push]
    DRV2 --> TRIP[Trip Service]
    TRIP --> PAY[Payments]
    TRIP --> KAFKA[Kafka → Analytics]
    style DISP fill:#ff6b1a,color:#0a0a0f
    style GEO fill:#15803d,color:#fff
    style LP fill:#0e7490,color:#fff
    style TRIP fill:#a855f7,color:#fff
```

**Key design decisions.**

| Decision | Choice | Why |
| --- | --- | --- |
| Spatial index | H3 hex cells (res 9, ~0.1 km²) in Redis sorted sets | Uniform neighbor distance; O(1) cell lookup; TTL auto-expires stale cells |
| Location store | Redis (in-memory), **not** Postgres | 400k+ writes/sec; sub-ms geo queries; Postgres is reserved for durable state |
| Driver claim | Redis `SET driver:{id}:offer ride:{id} NX EX <ttl>` | Single atomic command sets key only if absent and sets TTL; prevents double-booking without distributed locks |
| Dispatch order | ETA ranking via contraction-hierarchy router, not raw distance | A driver 1.2km away over a bridge may arrive later than one 1.8km away |
| Matching algorithm | Batched bipartite matching (Hungarian) every ~1–2s | Minimizes total expected wait across all pending requests in a cell |
| Surge pricing | Demand/supply ratio per H3 cell, recalculated every 30–60s | Local imbalance (not global) drives price; proactive ML for known events |
| Trip state | State machine in Trip Service, events to Kafka | Single source of truth; downstream fans out to payments, analytics, push |

**If you have 60 seconds, say this.** "The hard part is the geo-index and atomic dispatch. I store live driver positions in Redis keyed by H3 cell (res 9, ~0.1 km²) with a TTL so stale entries age out automatically. A ride request hits the Dispatch Service, which queries the nearest cells, ranks candidates by predicted ETA (contraction-hierarchy routing, not raw distance), then atomically claims the best driver with a Redis `SET key value NX EX <ttl>` — a single atomic command that conditionally sets and expires, preventing double-booking. I batch recent requests across a cell and run bipartite matching to minimize collective wait time. Surge is a per-cell demand/supply ratio fed by a streaming pipeline, recomputed every 30–60s. The trip lifecycle is a state machine; every transition goes to Kafka so payments, analytics, and push are decoupled."



## The problem

Uber launched in San Francisco in 2010 with a dead-simple premise: tap a button and a car arrives. By 2024, the platform was handling roughly 28–31 million trips a day across 70+ countries, with around 161 million monthly active users. Lyft runs the same model in North America. At small scale this is a weekend project — a database table of drivers, a query that finds the nearest one, done. At real scale it is one of the harder distributed systems problems in consumer software.

The core challenge is **matching under movement**. Millions of drivers are continuously moving, each emitting a GPS ping every few seconds. A ride request arrives and the system must find the right driver — not just the closest one, but the one who will actually arrive soonest given current traffic — within a latency budget riders don't consciously notice. Then it must *claim* that driver atomically so two simultaneous requests don't both get assigned to the same car. And it must do all of this while ingesting roughly 400k–500k location updates per second.

That write throughput is what kills the obvious approaches. A single relational database saturates. A naive full-table scan of driver coordinates is O(N) on every request. The solution is a spatial index in memory — a geohash or hexagonal grid — that turns "find drivers near this point" from a scan into a handful of key lookups. The rest of the architecture fans out from that core insight: location in Redis, dispatch as a dedicated service with an atomic claim step, surge pricing as a streaming control loop, and a Kafka-backed trip lifecycle.

The two tensions that run through the whole design are **write throughput versus query speed** (you have to keep the geo index fresh without making every read wait for a write) and **atomic coordination at sub-second latency** (claim one driver across potentially hundreds of competing requests without a slow distributed lock). Every major design decision in this article is an answer to one of those two problems.

## Functional requirements

- Riders open the app, see nearby drivers, request a ride.
- Drivers receive ride requests, accept/decline.
- Once matched, both see live location of the other.
- Trip ends, fare calculated, payment processed.
- Surge pricing in busy areas.

## Non-functional

- p99 dispatch < 500ms.
- 99.99% availability — ride hailing failures = stranded customers.
- ~161M MAU globally (Q3 2024); ~28–31M rides/day.
- Realtime location updates from millions of moving drivers.

## Capacity

| Dimension | Estimate | How we got there |
| --- | --- | --- |
| Monthly active users | ~161M globally | Uber Q3 2024: 161M MAPCs, 13% YoY growth |
| Active drivers (global, incl. couriers) | ~5–6M total; ~2M online at peak | Uber published figures; peak assumes ~35–40% of fleet online simultaneously |
| Location update rate (peak) | ~450k writes/sec | `2M drivers ÷ 4.5s avg ping interval` |
| Rides per day | ~28–31M/day | Q1 2024 ~28M/day, Q3 2024 ~31M/day |
| Dispatch rate — average | ~360 rides/sec | `31M ÷ 86,400s` |
| Dispatch rate — peak | ~1,500 rides/sec | ~4× average; evening rush in dense markets |
| Dispatch latency budget | must beat ~10–30s patience | Rider patience ~10s; driver offer window ~15–30s |

**Takeaway:** the location-write throughput (~450k/sec) is the dimensioning constraint — it rules out any single relational database and mandates an in-memory geo index.

## Building up to the design

Uber is the most geometric question in the catalog. The hard part isn't the API — it's "given a moving cloud of drivers, find one quickly and don't double-book." The naive version is doable in a hackathon weekend; production-Uber takes years. Walking the path makes each layer earn its keep.

### V1: One table, brute-force scan

```sql
CREATE TABLE drivers (id INT, lat FLOAT, lng FLOAT, online BOOL);
```

Driver app pings `UPDATE drivers SET lat=?, lng=? WHERE id=?` every few seconds.

On a ride request:
```sql
SELECT id FROM drivers WHERE online
ORDER BY (lat-?)^2 + (lng-?)^2 LIMIT 5;
```

This works at neighborhood scale — every problem reduces to SQL and you have a demo in a weekend. But that ORDER BY is an O(N) full sort on every dispatch. At 100k drivers online, every ride request scans the entire table. And once you're doing 450k location updates per second, a single Postgres write-ahead log becomes the bottleneck long before the query plan does.

### V2: Geohash index

Encode `(lat, lng)` into a string prefix where shared prefixes mean spatial closeness. Index on the geohash.

```
nearby_drivers(lat, lng) → all drivers with same 6-char geohash prefix → ~1.2km × 0.6km cell
```

Candidate lookup drops from O(N) to a single index range scan — a huge win. But cities aren't uniform. A 6-char geohash in midtown Manhattan might hold 1,000 drivers; one in rural Wyoming has zero. More importantly, writing every location update to Postgres still saturates the disk. A geo index tells the database *where* to look, not *how fast* to write.

### V3: Move location state to Redis

Store live driver positions in Redis. Either `GEOADD` (Redis's native geo index, supporting `GEORADIUS` queries in ~1ms) or sharded hash maps keyed by geohash bucket. Persist to the durable DB only on meaningful state transitions — came online, went offline, started a trip.

400k+ location writes per second land comfortably in Redis. Proximity queries drop under 1ms. Postgres is no longer in the hot path at all. What's left: dispatch is still naive. "Pick the closest 5, try driver #1, time out, try #2" is slow and produces bad UX. Worse, two riders requesting at the same instant can both receive an offer to the same driver.

### V4: Dispatch service with atomic claim

A dedicated Dispatch Service does four things in sequence:
1. Query the geo index for candidate drivers within the relevant cells.
2. Rank them by predicted ETA — not raw distance, because traffic matters.
3. Atomically claim the top candidate with `SET driver:X:offered ride:Y NX EX <ttl>` — a single Redis command that sets the key only if it doesn't exist and expires it automatically. Exactly one caller wins; the other immediately moves to its next candidate.
4. Send the offer. On accept, transition to trip. On decline or timeout, retry down the ranked list.

This eliminates double-booking and keeps dispatch latency under 500ms for the non-driver-wait portion. What it can't fix is when rider demand simply exceeds driver supply — and that's when drivers learn there's money sitting in the app.

### V5: Surge + supply/demand balance

A streaming pipeline (Kafka feeding an aggregator) measures the demand/supply ratio per geo cell every 30–60 seconds. When a cell goes imbalanced, a surge multiplier raises prices — showing riders "1.4× surge" and showing nearby off-duty drivers a "hot zone" indicator. In practice, ML models predict imbalance before it fully develops and apply surge proactively rather than reactively.

### V6: Production Uber

V3 + V4 + V5 plus a trip lifecycle service, payments, a full ETA service with map data and live traffic, push/WebSocket notification channels, and Kafka-fed analytics across all of it.

```mermaid
flowchart LR
    V1[V1: SQL scan<br/>100 drivers] --> V2[V2: + geohash<br/>fast proximity]
    V2 --> V3[V3: + Redis live state<br/>400k+ writes/sec]
    V3 --> V4[V4: + dispatch service<br/>no double-book]
    V4 --> V5[V5: + surge pricing<br/>balance]
    V5 --> V6[V6: + trip + payments + ETA]
    style V1 fill:#0e7490,color:#fff
    style V3 fill:#15803d,color:#fff
    style V4 fill:#ff6b1a,color:#0a0a0f
    style V6 fill:#a855f7,color:#fff
```

The rest of the article zooms in on V3–V6 — what it actually takes to run this.

## High-level architecture

```mermaid
flowchart TD
    DRV[Driver app] -.location pings.-> LP[Location Pipeline]
    RID[Rider app] -->|"request ride"| API[API Gateway]
    API --> DISPATCH[Dispatch Service]

    LP --> GEODB[(Geo Index<br/>H3 cells / Redis)]
    DISPATCH --> GEODB
    DISPATCH --> ETA[ETA Service]
    DISPATCH --> SURGE[Surge Service]

    DISPATCH --> DRV2[Driver app<br/>via Push / WebSocket]
    DRV2 --> ACCEPT[Driver accepts]
    ACCEPT --> TRIP[Trip Service]
    TRIP --> RID2[Rider notified]

    TRIP --> PAY[Payments]
    TRIP --> KAFKA[Kafka events]
    KAFKA --> ANA[Analytics]

    style DISPATCH fill:#ff6b1a,color:#0a0a0f
    style GEODB fill:#15803d,color:#fff
    style LP fill:#0e7490,color:#fff
```

## Storing locations efficiently

With ~2M drivers online at peak, each pinging every 4–5 seconds, you're looking at ~450k writes per second. That write rate will saturate any single relational database — and a naive `ORDER BY distance` on raw lat/lng still requires a full scan even with a btree index on the coordinate columns. You need a **spatial index**.

### Geohash

Encode a (lat, lng) into a string where common prefixes mean geographic proximity.

```
(37.775, -122.418)  →  "9q8yyk"
(37.776, -122.419)  →  "9q8yyk"   ← same prefix
(34.052, -118.243)  →  "9q5ctr"   ← different prefix (LA vs SF)
```

Each character of the geohash adds precision by halving the bounding box in alternating longitude/latitude. A 6-character geohash covers a rectangular cell roughly 1.2 km wide × 0.6 km tall — a reasonable first-pass radius for "show me drivers near here." For denser cities, query the cell plus its 8 neighbors to avoid edge effects when a driver is near a cell boundary.

```mermaid
flowchart TD
    G[Earth: lng -180..180, lat -90..90] --> L[First bit: lng < 0 or ≥ 0]
    L --> LL[West half]
    L --> LR[East half]
    LR --> LR1[Second bit: lat < 0 or ≥ 0]
    LR1 --> LR2[Each base-32 character adds 5 bits<br/>→ shrinks bounding box area ~32× per char]
    style LR2 fill:#ff6b1a,color:#0a0a0f
```

### Hexagonal grid: Uber's H3

Uber actually uses **H3**, a hexagonal grid library they open-sourced. Hexagons tile the sphere with uniform neighbor distance — every hexagon's center is equidistant from all 6 neighboring hexagon centers, a property squares don't have. H3 has 16 resolution levels (0–15), ranging from continent-size cells (~4M km²) down to ~1 m².

For ride dispatch, **resolution 9** is a common choice: each cell is ~0.1 km² with an average edge length of ~174m. That's roughly 2–3 city blocks — small enough to be sparse (a few drivers per cell in most areas) but large enough that a 7-cell query (cell + 6 neighbors) covers a useful radius. Be honest about the geometry, because interviewers push on it: for a rider at the cell center the flower's boundary sits ~350m away in the nearest (vertex) direction and reaches ~460m at its far points; for a rider standing near a cell edge the *guaranteed* capture radius drops to roughly one edge length (~174m). So "~475m" is the flower's best-case reach, not a promise. If you need a hard ~500m guarantee regardless of where the rider stands, query k-ring 2. At finer resolutions you'd expand the ring; at coarser resolutions the candidate list gets too large to rank cheaply.

Each driver's last location is stored in `(h3_cell_at_resolution_9, driver_id)`. Lookup "drivers in this cell + 6 neighbors" fetches 7 Redis keys — each a sorted set — and merges the results.

### The location pipeline

Drivers don't write directly to Redis. Their location pings go through a pipeline that handles batching, deduplication, and the TTL writes.

```mermaid
flowchart LR
    APP[Driver app<br/>4-5s ping] --> INGEST[Location Ingest<br/>service]
    INGEST --> KAFKA[(Kafka<br/>location topic)]
    KAFKA --> WORKER[Location Worker<br/>fan-out]
    WORKER --> GEO[(Geo Index<br/>Redis sorted sets)]
    WORKER --> HIST[(Location History<br/>Cassandra)]
    GEO -.TTL 30s.-> GEO
    style INGEST fill:#0e7490,color:#fff
    style KAFKA fill:#a855f7,color:#fff
    style GEO fill:#15803d,color:#fff
    style HIST fill:#ffaa00,color:#0a0a0f
```

Location events land in Kafka first. Workers consume them and write to two places: the Redis geo index (current position, with a 30-second cell-level TTL so inactive cells automatically age out) and a Cassandra table for historical location data (used for trip replay, compliance, and driver earnings disputes). The Kafka buffer also smooths out spikes — if there's a momentary surge in driver pings, the workers drain the queue rather than hammering Redis directly.

### Where do we store this?

A **Redis** sorted set per cell, keyed by `cell_id`, with a cell-level TTL (the EXPIRE applies to the entire key, so all drivers in a cell expire together — stale cells age out automatically):

```
ZADD geo:cell:8a283082 <ts> driver_42
EXPIRE geo:cell:8a283082 30
# Note: ZADD + EXPIRE are two separate commands — a crash between them leaves
# the key without a TTL (same race as SETNX+EXPIRE). In production, wrap both
# in a Lua script (EVAL) or use a pipeline with error handling.
```

The TTL is cell-level, so it only garbage-collects cells that go entirely quiet. In a busy downtown cell the key's `EXPIRE` gets refreshed on every write, so an offline driver who stops pinging never ages out on his own — his member lingers as a ghost that dispatch would happily offer rides to. That's what the `<ts>` score is for: prune stale members on read with `ZREMRANGEBYSCORE geo:cell:X 0 <now-30s>` to drop anyone whose last ping is older than the ping interval, and `ZREM` the member explicitly when a driver goes offline or gets claimed. Member-level freshness is the score's job; the TTL just cleans up dead cells.

Or specialized: Uber historically used **Ringpop** (now deprecated) — an in-memory consistent-hash ring library that sharded the geo index across a cluster of nodes, with each node owning a set of cells. The pattern is sound regardless of the specific library: shard cell ownership across a cluster, keep the index in memory, rely on a membership protocol (SWIM / gossip) for node discovery.

## Dispatch algorithm

```mermaid
sequenceDiagram
    participant Rider
    participant Dispatch
    participant Geo
    participant Driver
    Rider->>Dispatch: request ride at (lat, lng)
    Dispatch->>Geo: drivers within 5 km?
    Geo-->>Dispatch: list of ~20 candidates
    Dispatch->>Dispatch: filter (vehicle type, rating, ETA)
    Dispatch->>Dispatch: rank by ETA + rider/driver score
    loop for top candidates
      Dispatch->>Driver: ping (accept window ~15s)
      alt accept
        Driver-->>Dispatch: ✓
        Dispatch-->>Rider: matched!
      else decline / timeout
        Driver-->>Dispatch: ✗
      end
    end
```

The "5 km" in that diagram is the *effective* search area, not a single query. Dispatch starts with the 7-cell k-ring around the rider (~350–460m of reach); if that returns too few candidates — routine in low-supply areas and off-peak — it expands the ring (k-ring 2, then 3, …) or drops to a coarser H3 resolution, growing the search until it has enough drivers to rank, up to a market-dependent cap of a few kilometers. In a dense downtown cell the first 7-cell lookup is usually enough; in the suburbs the ring keeps widening. That progressive expansion is how a tight cell-plus-neighbors query becomes a multi-kilometer search when supply is thin.

Real systems don't just hand the request to the closest driver. They **batch** several recent ride requests together with nearby drivers and solve a small **bipartite assignment problem**: riders on one side, drivers on the other, edge weights equal to predicted ETA. The Hungarian algorithm (O(n³)) finds the minimum-weight perfect matching. Uber accumulates requests in ~1–2 second windows, so the graph is small — tens of riders × tens of drivers per cell — and the solve finishes well under 100ms. The payoff is that collective wait time across all riders drops versus greedy nearest-first dispatch.

Two other adjustments matter: drivers who decline too often are penalized with fewer offers (so gaming the system by waiting for shorter trips is costly), and dispatch ranks by **ETA rather than euclidean distance** — a driver across a bridge is closer in kilometers but farther in minutes. ETA comes from the routing engine described below.

## ETA service

For both dispatch ("which driver gets there fastest?") and rider UX ("ETA is 4 minutes"), you need realtime traffic-aware routing.

```mermaid
flowchart LR
    REQ[ETA request] --> ROUTER[Routing engine]
    ROUTER --> GRAPH[(Road graph<br/>OSM-derived)]
    ROUTER --> TRAFFIC[(Traffic data<br/>realtime)]
    ROUTER --> ML[ML predictor<br/>this segment historically takes X]
    ROUTER --> ETA[ETA in seconds]
    style ROUTER fill:#ff6b1a,color:#0a0a0f
    style ML fill:#a855f7,color:#fff
```

Backbone: **contraction hierarchies (CH)** on a road graph. CH preprocesses the graph by iteratively "contracting" low-importance nodes and adding shortcut edges, creating a hierarchy (local roads → arterials → highways). A bidirectional Dijkstra search over this hierarchy visits only a few hundred nodes for a cross-city query, giving sub-millisecond exact shortest paths versus seconds for vanilla Dijkstra. ML is layered on top to learn "this segment at 5pm on a Friday normally takes 30% longer than the static weight."

## Surge pricing

Surge is **dynamic pricing in response to local imbalance** — too many requests, too few drivers. The goals are to encourage more drivers to log on and to push rate-sensitive riders toward waiting or walking. A simple algorithm:

```
demand = ride requests in last 3 min in cell C
supply = available drivers in cell C
imbalance = demand / supply

multiplier = clip(0.7 + 3.0 × log(imbalance), 1.0, 4.0)
```

Calculated per H3 cell, recomputed every 30–60 seconds. The key insight is that it's *local* imbalance that drives price — a shortage in downtown has no bearing on the airport, and vice versa. In practice, ML models predict imbalance ahead of time and apply surge proactively, so the multiplier doesn't lag badly behind a sudden concert let-out.

```mermaid
flowchart LR
    EVENTS[Location + ride events] --> KAFKA[(Kafka stream)]
    KAFKA --> AGG[Surge aggregator<br/>30-60s windows]
    AGG --> CELL{Imbalance by<br/>H3 cell}
    CELL -->|demand > supply| MULT[Compute multiplier<br/>clip 1.0 - 4.0]
    MULT --> CACHE[(Surge cache<br/>Redis)]
    CACHE --> RIDER[Rider app<br/>shows surge]
    CACHE --> DRIVER[Driver app<br/>shows hot zone]
    style AGG fill:#ff6b1a,color:#0a0a0f
    style CACHE fill:#15803d,color:#fff
    style KAFKA fill:#a855f7,color:#fff
```

## The trip lifecycle

```mermaid
stateDiagram-v2
    [*] --> Requested
    Requested --> Matched: driver accepts
    Matched --> EnRoute: driver heading to pickup
    EnRoute --> InTrip: rider in car
    InTrip --> Completed: dropoff confirmed
    Completed --> Paid: payment processed
    Paid --> [*]

    Requested --> Cancelled: rider cancels
    Matched --> Cancelled: driver cancels (penalty)
    EnRoute --> Cancelled
```

Each state transition is an event. The Trip Service is the source of truth; events go to Kafka for downstream consumers — analytics, payments, notifications. Nothing downstream holds authoritative state; they're just projections off the event stream.

## Storage choices

| Data | Store |
| --- | --- |
| User accounts | Postgres |
| Driver locations (current) | Redis / in-memory |
| Driver locations (history) | Cassandra |
| Trips (active) | Postgres / DynamoDB |
| Trips (archive) | Cassandra / S3 |
| Geo index | Redis sorted sets / custom in-memory |
| Payments | Postgres (strong consistency, money) |
| Events / analytics | Kafka → S3 → BigQuery |

## Hot path: ride request

Latency budget for "open app → driver dispatched":

| Step | ms |
| --- | --- |
| API gateway + auth | 30 |
| Geo lookup (drivers nearby) | 50 |
| ETA & ranking | 100 |
| Driver ping + ~15s response window | up to 15,000 |
| Dispatch confirm | 50 |
| Notify rider | 50 |

The driver acceptance window dominates everything else. All the machinery above — geo lookup, ETA ranking, atomic claim — completes in under 200ms. The Dispatch Service retries with the next candidate if a driver declines or times out, which means total wall-clock time before "no drivers available" can be 30–60 seconds in bad supply conditions. Uber has varied the acceptance window over the years (driver community reports and third-party sources cite windows in the roughly 10–20 second range, varying by market and period), trading rider wait time against driver quality of life.

## Mobile considerations

The driver app is always-on, always-streaming. Battery and data are precious.

- **Adaptive ping rate**: 4s when moving, 10s when stationary.
- **WebSocket** for bidirectional communication (push ride requests, receive trip events) — or HTTP long-poll on poor networks.
- **Foreground service** on Android, background location on iOS, with explicit user consent.

## Failure modes

### Driver app loses connection mid-trip

The app caches recent state and reconciles when the connection returns. The server keeps the trip state authoritative.

### Two riders match the same driver simultaneously

The atomic claim in Redis prevents this on the happy path:

```
SET driver:{id}:offer ride:{Y} NX EX <offer_window_seconds>
```

`SET … NX EX` is a single atomic command (available since Redis 2.6.12): it sets the key only if it does not already exist **and** sets its TTL in one operation. The older pattern of `SETNX` followed by a separate `EXPIRE` has a race — if the process crashes between the two calls, the key has no TTL and locks that driver slot forever. With `SET NX EX`, if two dispatch workers race, exactly one wins; the other gets a nil response and immediately tries its next candidate. On accept, the Dispatch Service does a final compare-and-set to transition the driver to `IN_TRIP` before telling the rider. No distributed lock is needed — the single Redis Cluster slot for that key serializes the SET.

```mermaid
sequenceDiagram
    participant W1 as Dispatch Worker 1
    participant W2 as Dispatch Worker 2
    participant R as Redis
    participant RID1 as Rider 1
    participant RID2 as Rider 2
    W1->>R: "SET driver:42:offer ride:A NX EX 15"
    W2->>R: "SET driver:42:offer ride:B NX EX 15"
    R-->>W1: OK (wins)
    R-->>W2: nil (loses)
    W1->>RID1: Driver 42 is on the way
    W2->>R: "SET driver:99:offer ride:B NX EX 15"
    W2->>RID2: Driver 99 is on the way
```

### A geo-index shard dies

The geo index is volatile by design, and that's the point. If a Redis shard holding a batch of hot cells crashes, those drivers' positions vanish and dispatch in that area degrades — the affected cells look empty, so requests there fall back to ring expansion or briefly wait. But the index self-heals within one ping interval (~4–5s): every online driver re-reports its location on the next ping, and the workers repopulate the cells straight from the live Kafka stream. There's nothing to replay and no backup to restore — the freshest possible state is at most one ping away. That self-repair is exactly why holding live positions in memory with zero durability is an acceptable trade: the data continuously reconstructs itself.

### A region's data center fails

Cross-region replication keeps account and completed-trip state recoverable, and failover routes new requests to a healthy region. In-flight trips are the hard part. A trip whose authoritative state lived in the failed region is served from a replica that may be seconds behind, so a claim or a state transition that hadn't replicated yet can be lost — a driver who just accepted might see the trip snap back to `Requested`, or a just-completed trip might reappear as active until the payment event reconciles it. The workable stance is to make trip transitions idempotent and let the Kafka event log re-drive them on the healthy side, accepting a few seconds of visible inconsistency rather than blocking every trip on synchronous cross-region writes.

## Things to discuss in an interview

- **Spatial index**: geohash or H3 cells; in-memory index keyed by cell.
- **Dispatch as an optimization problem**: not just nearest, but ETA + rider score + driver decline rate.
- **Surge as a control loop**: demand/supply → multiplier; updated per cell every 30–60 seconds.
- **Event-driven trip lifecycle**: state machine with Kafka events.
- **Realtime location pipeline**: batched, with TTL, in-memory.

## Things you should now be able to answer

- Why is geohashing better than naive lat/lng comparison?
- Why does Uber use hexagonal cells (H3) instead of square cells?
- How do you ensure a driver isn't double-matched?
- What's the difference between greedy and batched matching?
- Why is surge pricing computed per cell, not globally?

## The decision in practice

Two things carry this design, and the rest is plumbing. Get the **spatial index** right — H3 cells in memory, cell-plus-k-ring lookup, member-level freshness — and get the **atomic claim** right — a single `SET NX EX`, no distributed lock — and you have a dispatch path that never double-books and answers in well under a second. Rank by **ETA rather than raw distance** and you've covered the third thing interviewers actually probe.

Above that baseline is where you separate a strong answer from a passing one: batched bipartite matching instead of greedy nearest-first, and surge as a per-cell control loop with proactive ML. Below it — the trip state machine, payments, push channels, the Kafka fan-out — is commodity event-driven plumbing you should describe quickly and move past. Spend your minutes on the geo index and the claim. That's where this system lives or dies.

## Further reading

- "Engineering Real-time Indexing at Uber" — eng.uber.com
- H3 hexagonal indexing library — open source, github.com/uber/h3
- "Marketplace 101: matching & routing" — Lyft Engineering

## Frequently asked questions
Q: Why does Uber use H3 hexagonal cells instead of square geohash cells for the geo index?
A: Hexagons tile the sphere with uniform neighbor distance — every hexagon center is equidistant from all six neighboring centers, a property squares lack. Uber uses H3 resolution 9 cells (~0.1 km², ~174m edge length), where querying a cell plus its six neighbors covers roughly 350m from the cell center in the nearest direction, out to ~460m at the flower's far points, with far less boundary distortion than square geohash cells. For a hard ~500m radius you query k-ring 2.

Q: How does Uber prevent two riders from being matched to the same driver simultaneously?
A: The Dispatch Service issues a Redis SET driver:{id}:offer ride:{Y} NX EX command — a single atomic operation that sets the key only if absent and applies a TTL in one step. Exactly one dispatch worker wins; the other receives nil and immediately tries its next candidate. The older SETNX followed by a separate EXPIRE has a race condition: if the process crashes between those two calls, the key has no TTL and locks the driver slot permanently.

Q: What write throughput must Uber's location pipeline handle, and why does that rule out a relational database?
A: With roughly 2 million drivers online at peak each pinging every 4-5 seconds, the system ingests approximately 450,000 location writes per second. That rate saturates any single relational database's write-ahead log, so live driver positions are stored in Redis (in-memory), with Postgres reserved only for durable state like accounts and completed trips.

Q: What is batched bipartite matching in Uber's dispatch, and how does it improve on greedy nearest-first?
A: Rather than assigning each request to the closest available driver immediately, the Dispatch Service accumulates ride requests over 1-2 second windows, then solves a bipartite assignment problem — riders on one side, drivers on the other, edge weights equal to predicted ETA — using the Hungarian algorithm (O(n³)). Because the per-cell graph is small (tens of riders times tens of drivers), the solve finishes well under 100ms, and the result minimizes collective wait time across all riders rather than just optimizing each request greedily.

Q: How is surge pricing calculated and why is it per cell rather than global?
A: A streaming aggregator reads location and ride events from Kafka, computes demand/supply ratio per H3 cell every 30-60 seconds, and applies the formula: multiplier = clip(0.7 + 3.0 x log(imbalance), 1.0, 4.0). The cap of 4x is reached at an imbalance of roughly 3 (3 requests per available driver), a realistic peak scenario. It is local by design — a shortage downtown has no bearing on the airport — and ML models predict imbalance ahead of time so the multiplier does not lag behind sudden demand spikes like a concert letting out.