Phase 5 · Chapter 5

System Design: Uber

Geospatial queries, real-time location at scale, and the matching problem

What this chapter does to you: Uber's hard problem is not payments, not user accounts, not even surge pricing. It is this: millions of drivers broadcasting their GPS coordinates every 4 seconds, millions of riders asking "find me the nearest available driver" in real time, on a dataset that is completely different every 4 seconds. After this chapter, you will understand geohashing — why it works, how to implement it, and why it is the right data structure for this problem. You will also understand the matching problem, the trip state machine, and why Uber's architecture is fundamentally different from every other system we've designed so far.

Step 1: Clarify Requirements

Functional requirements:

• Rider requests a trip from location A to B
• System finds the nearest available driver
• Driver accepts or rejects the request
• Trip begins — both parties track each other in real time
• Trip ends — fare calculated, payment processed
• Driver/rider ratings after each trip
• Surge pricing — price multiplier when demand exceeds supply in an area

Non-functional requirements:

• 5 million drivers worldwide, ~1 million active at peak
• 20 million riders worldwide, ~5 million active at peak
• Driver location updates every 4 seconds
• Matching latency: nearest driver found in < 500ms
• Trip request → driver response: < 30 seconds
• High availability: a rider unable to book is direct revenue loss
• Consistency: a driver must not be matched to two riders simultaneously

The core constraint you identified: "Driver location updates every 4 seconds" × "1 million active drivers" = 250,000 location writes/second. This is the dominant write pattern.

"Find nearest available driver" × "5 million active riders" querying simultaneously = you need a spatial index that handles 250,000 writes/second AND answers "nearest neighbor" queries in < 500ms simultaneously.

No standard SQL database has this property out of the box.

Step 2: Estimate Scale

Location updates:

• 1M active drivers × 1 update/4 seconds = 250,000 writes/second
• Each update: driver_id (8B) + lat (8B) + lng (8B) + timestamp (8B) = 32 bytes
• 250,000 × 32 bytes = 8MB/second of location data ingested continuously

Ride requests:

• 20M trips/day = ~230 requests/second
• Peak: ~600 requests/second
• Each request triggers a "find nearest driver" spatial query

Trip state:

• At any moment: ~200,000 active trips
• Each trip has two users tracking each other in real time
• 400,000 active location streams during peak

Storage:

• Location data: only current position matters for matching — not historical
• Trip history: 20M trips/day × ~500 bytes = 10GB/day
• After a trip completes, location history can be archived or discarded

What this tells you:

• Location data is ephemeral — you need current position, not history
• 250,000 writes/second rules out Postgres as the primary location store
• Spatial queries ("nearest driver") require a specialized data structure
• Redis with geospatial support is the right tool — you'll see why

Part 3: The Geospatial Problem — Why SQL Fails

The Naive Approach

Store driver locations in Postgres:

CREATE TABLE driver_locations (
  driver_id  BIGINT PRIMARY KEY,
  latitude   DOUBLE PRECISION,
  longitude  DOUBLE PRECISION,
  updated_at TIMESTAMP
);

Query for nearest driver:

SELECT driver_id,
  SQRT(
    POWER(latitude - $1, 2) + POWER(longitude - $2, 2)
  ) AS distance
FROM driver_locations
WHERE available = true
ORDER BY distance ASC
LIMIT 10;

Why this fails:

• No index on (latitude, longitude) can help this query — you're computing a derived value (distance) and sorting by it
• Full table scan of 1M rows on every request
• At 600 requests/second: 600M row-scans/second from one Postgres

Even with PostGIS (Postgres's geospatial extension), the write rate of 250,000 updates/second makes a single Postgres instance impossible.

The fundamental problem: 2D spatial queries don't map naturally to 1D indexes (B-trees). A B-tree can efficiently answer "latitude between 12.9 and 13.1" but combining with "longitude between 77.5 and 77.7" still requires scanning all rows in the latitude range and filtering by longitude.

You need a data structure designed for 2D spatial queries.

Part 4: Geohashing — The Core Data Structure

The Idea

The Earth is 2D. Databases index 1D. What if you could turn a 2D coordinate into a 1D string in a way that preserves spatial proximity?

That's geohashing.

How Geohashing Works

Step 1: Divide the world in half, recursively.

Take the entire world. Divide it into two halves: left (longitude < 0) and right (longitude >= 0). If your point is in the right half: encode 1. Left half: encode 0.

Take your half. Divide it into top and bottom by latitude. Top half: encode 1. Bottom: encode 0.

Repeat. Alternate between longitude and latitude splits.

After 30 splits, you have a 30-bit binary string that precisely identifies a tiny region of Earth. Convert that binary string to base32 (using the alphabet 0123456789bcdefghjkmnpqrstuvwxyz): you get a short alphanumeric string.

Latitude: 12.9716° N
Longitude: 77.5946° E  (Bengaluru, Karnataka)

Binary encoding process:
  Longitude: 77.5946 → right half (>=0) → 1
  Latitude:  12.9716 → top half   (>=0) → 1
  Longitude: 77.5946 → right of 0-180   → 1
  Latitude:  12.9716 → bottom of 45-90  → 0
  ... (continue for desired precision)

Geohash: "tdr1w"  (5-character precision)

The precision table:

Characters | Cell size          | Use case
───────────┼────────────────────┼──────────────────────────
1          | 5,000 km × 5,000km | Country-level
2          | 1,250 km × 625 km  | Region
3          | 156 km  × 156 km   | City
4          | 39 km   × 20 km    | District
5          | 4.9 km  × 4.9 km   | Neighborhood ← Uber uses this
6          | 1.2 km  × 0.6 km   | Street block
7          | 152 m   × 152 m    | Building

A 5-character geohash covers a ~5km × 5km area. Every driver within that area has the same 5-character geohash prefix.

The Key Property: Prefix = Proximity

Two locations with the same geohash prefix are geographically close.

Bengaluru city center:  tdr1w
1km north:              tdr1w  (same 5-char prefix)
5km east:               tdr1x  (differs in last char only)
Different city:         s0000  (completely different prefix)

This means: "find all drivers near me" becomes "find all drivers whose geohash starts with the same prefix as mine."

That's a string prefix query. Extremely fast with any standard index.

Geohashing in Redis

Redis has native geospatial commands built on top of sorted sets. Internally, Redis encodes lat/lng as a geohash and uses it as the sorted set score.

// Driver updates their location:
await redis.geoadd('drivers:available', longitude, latitude, driverId)
// Stores: ZADD drivers:available [geohash_score] driverId

// Rider requests a trip — find nearest 10 drivers within 5km:
const nearbyDrivers = await redis.georadius(
  'drivers:available',
  riderLongitude,
  riderLatitude,
  5,          // radius
  'km',       // unit
  'ASC',      // nearest first
  'COUNT', 10 // return at most 10
)

GEORADIUS computes the geohash of the center point, finds all members within the radius using the sorted set's spatial index, and returns them sorted by actual distance.

The write pattern:

// Every 4 seconds from each driver app:
async function updateDriverLocation(driverId, lat, lng) {
  if (driverAvailable) {
    await redis.geoadd('drivers:available', lng, lat, driverId)
  } else {
    await redis.zrem('drivers:available', driverId)  // remove if unavailable
  }
}

GEOADD = ZADD underneath = O(log N). At 250,000 updates/second on a sorted set of 1M drivers: fast. Redis handles this.

The Edge Case: Geohash Boundary Problem

A driver is just across the boundary of your geohash cell.

Your geohash: tdr1w (5km × 5km box)
Driver is 100m away but just outside the box → different geohash prefix

Your prefix search misses them.

The fix: search neighboring cells too.

Every geohash cell has exactly 8 neighbors (N, NE, E, SE, S, SW, W, NW). Search your cell + all 8 neighbors = 9 cells total. No driver near a boundary is missed.

const neighbors = geohash.neighbors('tdr1w')
// → ['tdr1x', 'tdr1r', 'tdr3b', 'tdr1q', 'tdr1m', 'tdr3n', 'tdr3j', 'tdr1t']

const allCells = ['tdr1w', ...neighbors]
const drivers = await Promise.all(
  allCells.map(cell =>
    redis.georadius(`drivers:${cell}`, lng, lat, 1, 'km', 'ASC', 'COUNT', 5)
  )
)
// Merge, deduplicate, sort by actual distance

Part 5: The Matching Problem

Finding nearby drivers is just step one. The real problem is matching.

The State Machine

A driver has states:

A ride request has states:

These are not just status fields. Each transition has business logic, timeout handling, and payment implications.

The Matching Algorithm

async function matchRider(riderId, riderLocation) {
  const searchRadii = [1, 2, 5, 10]  // km — expand search if no drivers found

  for (const radius of searchRadii) {
    const nearbyDrivers = await redis.georadius(
      'drivers:available',
      riderLocation.lng,
      riderLocation.lat,
      radius,
      'km',
      'ASC',
      'COUNT', 10
    )

    if (nearbyDrivers.length === 0) continue  // expand radius

    // Try each nearby driver in order of proximity
    for (const driverId of nearbyDrivers) {
      const matched = await tryMatchDriver(driverId, riderId)
      if (matched) return { driverId, status: 'MATCHED' }
    }
  }

  return { status: 'NO_DRIVER_FOUND' }
}

The Race Condition in Matching

Two riders are 100m apart. Same driver is nearest to both. Both requests arrive simultaneously. Both call GEORADIUS, both get the same driverID as nearest. Both try to match that driver.

If both succeed: one driver, two trips. Revenue loss, user fury.

Solution: atomic driver reservation using Redis

async function tryMatchDriver(driverId, riderId) {
  // Atomic: remove driver from available pool AND mark as matched
  // SET driverId:matched riderId NX EX 30
  // NX = only if not already matched
  // EX 30 = auto-expire if driver doesn't accept within 30 seconds

  const reserved = await redis.set(
    `driver:${driverId}:matched`,
    riderId,
    'NX',   // only set if not exists — atomic reservation
    'EX', 30
  )

  if (!reserved) return false  // another rider got there first

  // Remove from available pool
  await redis.zrem('drivers:available', driverId)

  // Send trip request to driver via WebSocket (Chapter 4!)
  await notifyDriver(driverId, riderId)

  return true
}

SET NX is atomic — exactly one caller gets true. This is the same distributed lock pattern from Chapter 2 (Rate Limiting) and Chapter 4 (Queue dedup). The pattern is universal: whenever two concurrent actors must exclusively claim a resource, use Redis SET NX.

Driver Acceptance Timeout

Driver has 30 seconds to accept. If they don't:

// After sending match request to driver:
await matchTimeoutQueue.add('handleTimeout', { driverId, riderId }, {
  delay: 30000,     // 30 seconds
  jobId: `timeout:${driverId}:${riderId}`  // deduplicated
})

// If driver accepts before timeout:
async function driverAccepted(driverId, riderId) {
  // Cancel the timeout job
  const job = await matchTimeoutQueue.getJob(`timeout:${driverId}:${riderId}`)
  await job?.remove()

  // Begin trip
  await beginTrip(driverId, riderId)
}

// If timeout fires:
async function handleMatchTimeout({ driverId, riderId }) {
  // Release driver reservation
  await redis.del(`driver:${driverId}:matched`)
  await redis.geoadd('drivers:available', driverLng, driverLat, driverId)

  // Find next nearest driver for the rider
  await matchRider(riderId, riderLocation)
}

This is the BullMQ delayed job pattern from Chapter 4 of Phase 4. The timeout is a job with a delay. If the happy path (driver accepts) fires first, the timeout job is cancelled. If not, the job fires and retries matching.

Part 6: Real-Time Trip Tracking — Both Sides

Once a trip begins, rider and driver track each other in real time.

The Problem

Driver's phone sends GPS updates every 4 seconds. Rider's app needs to show the driver's position moving on the map.

This is a publish-subscribe problem:

• Driver publishes location
• Rider subscribes to that driver's location

Using Redis Pub/Sub:

// Driver app sends update:
async function driverLocationUpdate(driverId, lat, lng) {
  await redis.publish(
    `trip:${tripId}:driver_location`,
    JSON.stringify({ lat, lng, timestamp: Date.now() })
  )
}

// Rider's connection server subscribes:
async function subscribeToTrip(tripId, riderSocket) {
  const subscriber = redis.duplicate()  // separate connection for subscriptions
  await subscriber.subscribe(`trip:${tripId}:driver_location`)

  subscriber.on('message', (channel, message) => {
    riderSocket.send(message)  // forward to rider's WebSocket
  })
}

Redis Pub/Sub: publisher sends to a channel, all subscribers receive instantly. No persistence (unlike queues) — if rider disconnects and reconnects, they don't get the missed updates. That's fine: the driver is still moving, the next update arrives in 4 seconds.

The ETA calculation:

Every location update triggers an ETA recalculation:

async function recalculateETA(driverLat, driverLng, destinationLat, destLng) {
  // Not Euclidean distance — actual road distance via routing engine
  const eta = await routingEngine.getETA(
    { lat: driverLat, lng: driverLng },
    { lat: destinationLat, lng: destLng }
  )
  return eta  // seconds until arrival
}

ETA uses a routing engine (Google Maps API, OpenStreetMap + OSRM, or Uber's own H3 + routing layer). This is a separate system — not part of what we're designing. The key architectural point: ETA calculation is CPU-intensive and latency-sensitive. It runs on dedicated routing servers, not your main app servers.

Part 7: Surge Pricing — Supply and Demand in Real Time

Surge pricing increases fares when demand exceeds supply in a geographic area.

The calculation:

async function getSurgeMultiplier(geohash) {
  const [availableDrivers, pendingRequests] = await Promise.all([
    redis.georadius('drivers:available', cellCenterLng, cellCenterLat, 5, 'km', 'COUNT', 1000),
    redis.get(`requests:pending:${geohash}`)  // riders waiting in this cell
  ])

  const ratio = pendingRequests / Math.max(availableDrivers, 1)

  if (ratio < 0.5) return 1.0    // plenty of drivers
  if (ratio < 1.0) return 1.2    // mild surge
  if (ratio < 2.0) return 1.5    // moderate surge
  if (ratio < 3.0) return 2.0    // high surge
  return 2.5                      // extreme surge cap
}

Why geohash cells again:

Surge pricing is geographic — it applies to a zone, not the whole city. Geohash cells are the natural unit of geographic aggregation. The same data structure that finds drivers also defines surge zones.

The feedback loop:

Higher surge price → more drivers head to the area (they see surge zones in their app) → supply increases → surge drops. This is market dynamics implemented as a feedback loop on your location + demand data.

Part 8: The Data Model

Driver Locations (Redis — ephemeral)

Key: drivers:available
Type: Sorted Set (Redis GEO)
Internal score: geohash-encoded integer
Members: driver IDs

GEOADD drivers:available 77.5946 12.9716 "driver:123"
GEORADIUS drivers:available 77.59 12.97 5 km ASC COUNT 10

Not in Postgres. Location is transient — drivers move, updates overwrite previous position. The source of truth for current location is Redis, not a database.

Trips (Postgres — durable)

CREATE TABLE trips (
  id              BIGINT PRIMARY KEY,   -- Snowflake ID
  rider_id        BIGINT NOT NULL,
  driver_id       BIGINT NOT NULL,
  status          VARCHAR(20) NOT NULL, -- requested/accepted/in_progress/completed/cancelled
  pickup_lat      DOUBLE PRECISION,
  pickup_lng      DOUBLE PRECISION,
  dropoff_lat     DOUBLE PRECISION,
  dropoff_lng     DOUBLE PRECISION,
  requested_at    TIMESTAMP NOT NULL,
  accepted_at     TIMESTAMP,
  started_at      TIMESTAMP,
  completed_at    TIMESTAMP,
  fare_amount     DECIMAL(10,2),
  surge_multiplier DECIMAL(4,2) DEFAULT 1.0,
  distance_km     DOUBLE PRECISION,
  duration_seconds INT
);

CREATE INDEX idx_trips_rider ON trips(rider_id, requested_at DESC);
CREATE INDEX idx_trips_driver ON trips(driver_id, requested_at DESC);
CREATE INDEX idx_trips_status ON trips(status) WHERE status IN ('requested','accepted','in_progress');

The partial index on active statuses: WHERE status IN ('requested','accepted','in_progress'). Only a fraction of trips are active at any moment. Queries for active trips (dashboards, monitoring) hit only those rows.

Driver State (Redis — with Postgres backup)

// Driver availability state — Redis for speed
HSET driver:123:state
  available    "true"
  lat          "12.9716"
  lng          "77.5946"
  updated_at   "1705312800000"
  current_trip "null"

// TTL: 60 seconds — if driver app crashes, they auto-disappear from available pool
EXPIRE driver:123:state 60

Why Redis with TTL for driver state? A crashed driver app stops sending heartbeats. After 60 seconds, the key expires. Driver disappears from the available pool. No manual "driver went offline" handling needed. Same pattern as WhatsApp presence.

Part 9: Scaling Location Updates

250,000 location updates/second. How do you scale this?

The Write Path

Driver app → WebSocket → Connection Server → Location Service → Redis GEOADD

All 250,000 updates go to the Location Service. This is stateless — it just does Redis GEOADD. Horizontally scalable: add more Location Service instances.

The Redis bottleneck:

Redis single-threaded. 100,000 ops/second maximum per instance. 250,000 GEOADD commands/second → 2.5 Redis instances needed minimum.

Solution: Redis Cluster + geographic sharding

Shard by city or geographic region:

function getLocationShard(lat, lng) {
  // Shard by coarse geohash (1-character = continent/region)
  const coarseHash = geohash.encode(lat, lng, 1)
  return `drivers:available:${coarseHash}`
}

// Driver in Bengaluru:
// coarseHash = "t"
// → GEOADD drivers:available:t 77.5946 12.9716 "driver:123"

// Driver in Mumbai:
// coarseHash = "t" (same region for India)
// → or use 2-char hash for finer sharding

Each shard is a separate Redis key, potentially on a different Redis node. City-level sharding is natural: a rider in Bengaluru never needs to query drivers in Mumbai. Queries are always local.

The matching query is already naturally sharded:

async function findNearbyDrivers(lat, lng, radius) {
  const shard = getLocationShard(lat, lng)
  return redis.georadius(shard, lng, lat, radius, 'km', 'ASC', 'COUNT', 10)
}

One Redis node per city/region. Location writes and reads are local. No cross-shard queries needed for matching.

Part 10: The Complete Architecture

The critical data flows:

Part 11: What This System Has That Others Don't

Look at what Uber required that none of our previous designs needed:

Every tool is something you've already learned. The novelty is the geohash — the insight that 2D coordinates can be encoded as 1D strings that preserve proximity. Once you have that, everything else falls into place.

Part 12: The Vocabulary Map

Part 13: Practice Problems

Problem 1 (Geohash Math): A rider is at latitude 12.9716, longitude 77.5946 (Bengaluru). A driver is 4.8km away — just inside your 5km search radius. Another driver is 5.2km away — just outside.

You search only the rider's geohash cell (5-char precision, ~5km × 5km).

Draw the cell boundary. Which driver might be missed? Now search the 8 neighboring cells too. Does the 5.2km driver definitely appear now? What is the worst-case distance of a driver you'd miss even after searching 9 cells?

Problem 2 (Race Condition): Two riders R1 and R2 are 200m apart. Driver D1 is equidistant between them. Both riders request a trip at exactly the same millisecond.

Both Matching Service instances call:

1. GEORADIUS drivers:available → both get D1 as nearest
2. SET driver:D1:matched R1 NX EX 30
3. SET driver:D1:matched R2 NX EX 30

Walk through what Redis returns for each SET NX call. What happens to the rider who "lost" the reservation? Design the exact retry behavior — what does the Matching Service do for R2 after failing to reserve D1?

Problem 3 (Scale — Location Updates): You're launching Uber in India. 500,000 active drivers in peak hours. You decide to shard location data by state (29 states + 7 UTs).

Maharashtra (Mumbai) has 80,000 active drivers. UP + Delhi combined have 120,000 active drivers.

Calculate:

• Location updates/second per shard for Maharashtra
• Is a single Redis instance sufficient for Maharashtra's shard?
• What happens during a cricket match final in Mumbai when driver density spikes 3× in one neighborhood?
• How would you handle this hotspot without re-sharding?

Problem 4 (Trip State Machine): A trip is IN_PROGRESS. The driver's app crashes. The driver reboots their phone, restarts the app.

What state is the trip in? How does the driver's app know it crashed mid-trip and not mid-idle? How do you resume the trip without creating a duplicate? What happens to the rider's tracking during the crash window?

Design the exact recovery flow using tools from this chapter and previous chapters (connection state from Chapter 4, idempotency from Chapter 4 Phase 4).

Problem 5 (Connect Everything — Full System Trace): It is 6pm on a Friday. Rider opens Uber in Bengaluru. The city is in 2.1× surge.

Trace the complete system from "app opens" to "trip begins":

1. App opens → how does it show nearby drivers on the map? (What Redis command? What WebSocket event? What data is streamed?)

2. Rider requests trip → exact sequence of Redis + Postgres + WebSocket operations

3. Surge price shown → how was 2.1× calculated? What data? Which geohash cell?

4. Driver found → SET NX reservation → driver notified via WebSocket

5. Driver accepts → trip begins → tracking starts

For each step: which chapter's concept applies? Which component is the bottleneck at 2× normal load? What fails first if Redis goes down mid-trip?

Where We Are in Phase 5

Phase 5 — System Design Case Studies
  ✅ Chapter 1: URL Shortener   (caching, ID generation, read-heavy)
  ✅ Chapter 2: Twitter Feed    (fan-out, write amplification, social graph)
  ✅ Chapter 3: YouTube         (media pipeline, CDN, adaptive streaming)
  ✅ Chapter 4: WhatsApp        (WebSocket, E2EE, effectively-once delivery)
  ✅ Chapter 5: Uber            (geohash, real-time location, matching)
  ⬜ Chapter 6: Google Docs     (real-time collaboration, OT vs CRDT)
  ⬜ Chapter 7: Notifications   (fan-out at scale, multi-channel delivery)

Five systems. Five different bottlenecks. One method.

Every problem started with: clarify requirements → estimate scale → identify the dominant constraint → design around it.

The dominant constraint was different every time:

• URL Shortener: read volume (100:1 read:write)
• Twitter: write amplification (fan-out to millions)
• YouTube: media bandwidth and transcoding compute
• WhatsApp: connection state and effectively-once delivery
• Uber: spatial queries on a dataset that changes completely every 4 seconds

Next: Chapter 6 — Google Docs. Two people typing in the same sentence at the same time is a consistency problem (Phase 3) that no lock can solve gracefully. Then Chapter 7 closes the course with a notification system that combines fan-out, queues, Kafka, and deduplication.

Now is also a good time to go back to Problem 5 of the CAP chapter (Phase 3, Chapter 1): classify each system you just designed with PACELC.

End of Phase 5, Chapter 5. Estimated reading time: 85-100 minutes. Practice problems: 60-90 minutes. Do not proceed to Chapter 6 until you can answer Problem 5 completely — the full system trace from app open to trip start. That problem synthesises every chapter so far into one coherent flow. If you can trace it clearly, with the right vocabulary at every layer, you are ready for most system design interviews.