Back to Notes

Design Uber / Ride-Sharing (Geospatial + Real-Time Matching)

1. Problem & Real-World Context

Design a ride-sharing system: riders request trips, get matched to a nearby available driver in near-real-time, track the driver's position live, and get dynamic pricing under supply/demand pressure. The defining challenge is geospatial indexing at scale — "find the nearest available drivers to this point" is not a query a normal database index answers efficiently, and constantly-moving drivers make this a live, high-write-rate problem, not a static one.

Personal relevance: the real-time driver-tracking core of this problem — WebSocket connections streaming live position updates at scale — is functionally the same shape as a geospatial tracking engine built at HCLTech (250+ concurrent connections, 4–5 second update intervals, sub-second latency). That system is a legitimate war-story anchor for the "real-time location tracking" section of this design specifically — see the STAR script for the full story.

2. Requirements

Functional: rider requests a ride and is matched to a nearby available driver; real-time location updates (driver position streams to both the server and the matched rider); ETA calculation; surge pricing based on live supply/demand imbalance.

Non-functional: low-latency matching (sub-second to ~1s); frequent location updates (every 4–5 seconds is a realistic real-world interval, not continuous streaming — bandwidth/battery cost on the driver's device matters); high availability; consistent driver state (a driver shouldn't be matched to two riders simultaneously).

3. Capacity Estimation

  • At, say, 1M concurrent active drivers, each sending a location ping every 5 seconds → ~200K location updates/sec sustained — this write volume is the dominant cost driver in the whole system, well above the matching-request rate itself (ride requests are comparatively rare events per driver).
  • Geo-index size: 1M drivers' current positions need to live in a structure supporting fast "who's near this point" queries — small enough in raw bytes (lat/lng + driver ID, tens of bytes each) to fit comfortably in memory (Redis), but the indexing structure over those positions (not the raw storage) is what makes nearest-neighbor queries fast — that's the actual design problem, not storage volume.

4. High-Level Architecture

flowchart LR
    D[Driver App] -->|WebSocket,<br/>location every 4-5s| WS[WebSocket Server]
    WS --> GEO[(Geo-indexed<br/>Location Store - Redis)]
    R[Rider App] --> MS[Matching Service]
    MS --> GEO
    MS --> DS[Driver State Service<br/>available/busy]
    MS --> Route[Routing/ETA Service]
    MS --> Pricing[Surge Pricing Service]
    Route -->|assigned| R
    Route -->|assigned| D

Walking a location update: driver's app pushes its current lat/lng over a persistent WebSocket connection (same stateful-connection reasoning as [[WhatsApp Chat]] — a fresh HTTP request per update would add needless connection-setup overhead at this frequency) → the WebSocket server writes the position into a geo-indexed store → this store is what the matching service queries.

Walking a ride request: rider requests a ride → matching service queries the geo-index for available drivers near the rider's location → filters by driver availability state → picks the best candidate (nearest, or by a more sophisticated scoring function) → routing service computes ETA → both apps are notified of the match.

5. Geospatial Indexing — the Core Problem

A plain database index (B-tree on lat, another on lng) can't efficiently answer "who is within 2km of this point" — that's a 2D range query, and independently indexing two dimensions doesn't compose into an efficient 2D range search. Three real approaches:

Geohash

Encodes a lat/lng pair into a single base32 string where nearby locations share a common prefix — turning a 2D proximity problem into a 1D string-prefix problem, which a normal index handles well.

def geohash_encode(lat: float, lng: float, precision: int = 8) -> str:
    lat_range, lng_range = (-90.0, 90.0), (-180.0, 180.0)
    geohash = []
    bits = 0
    bit_count = 0
    even_bit = True   # alternates between encoding lng and lat bits
    base32 = "0123456789bcdefghjkmnpqrstuvwxyz"

    while len(geohash) < precision:
        if even_bit:
            mid = (lng_range[0] + lng_range[1]) / 2
            if lng >= mid:
                bits = (bits << 1) | 1
                lng_range = (mid, lng_range[1])
            else:
                bits = bits << 1
                lng_range = (lng_range[0], mid)
        else:
            mid = (lat_range[0] + lat_range[1]) / 2
            if lat >= mid:
                bits = (bits << 1) | 1
                lat_range = (mid, lat_range[1])
            else:
                bits = bits << 1
                lat_range = (lat_range[0], mid)
        even_bit = not even_bit
        bit_count += 1
        if bit_count == 5:
            geohash.append(base32[bits])
            bits = 0
            bit_count = 0
    return "".join(geohash)

The boundary problem: two points extremely close together but straddling a grid cell boundary can end up with completely different prefixes despite being physically adjacent — a naive "search by shared prefix" misses genuinely-nearby points on the wrong side of a cell edge. Real implementations search the target cell and its 8 neighboring cells, not just an exact prefix match, to compensate.

QuadTree

Recursively subdivides the map into quadrants, splitting further only where driver density is high — adapts resolution to actual density rather than using a uniform grid everywhere, which is more memory-efficient in sparse areas and more precise in dense ones. Good for range queries; more complex to shard across machines than a flat hash-based scheme.

H3 (Uber's actual production choice)

A hexagonal grid system (versus square cells) — hexagons have a genuine geometric advantage over squares/geohash's implicit rectangular cells: every neighboring hexagon is equidistant from the center (a square's diagonal neighbors are farther than its edge neighbors), which makes "find all cells within N rings of this one" a cleaner, more uniform operation for proximity search. Worth naming specifically — citing H3 by name signals awareness of the real production system this problem is modeled on, not just textbook Geohash/QuadTree.

6. Location Store: Redis Geospatial Commands

In practice, Redis exposes geo-indexing natively (built on a sorted set with geohash-encoded scores), making the location store a direct fit rather than something built from scratch on top of generic KV storage:

import redis
r = redis.Redis()

def update_driver_location(driver_id: str, lat: float, lng: float) -> None:
    r.geoadd("driver_locations", (lng, lat, driver_id))   # note: Redis takes (lng, lat) order

def find_nearby_drivers(lat: float, lng: float, radius_km: float = 3) -> list[str]:
    return r.geosearch(
        "driver_locations", longitude=lng, latitude=lat,
        radius=radius_km, unit="km", sort="ASC"            # sorted by distance, nearest first
    )

This is the same underlying data structure and single-threaded-atomicity discussion as [[Caching & Redis]] — the geospatial commands are a purpose-built layer over a sorted set, not a separate system.

7. Matching Algorithm

Naive: pick the single nearest available driver. In practice, matching balances several factors, not distance alone:

def match_driver(rider_lat: float, rider_lng: float) -> str | None:
    candidates = find_nearby_drivers(rider_lat, rider_lng, radius_km=3)
    available = [d for d in candidates if driver_state.is_available(d)]
    if not available:
        return None   # expand search radius and retry, or queue the request

    # Real systems score on more than raw distance: driver rating, vehicle type match,
    # how long the driver has been idle (fairness), estimated pickup ETA (not straight-line distance)
    best = min(available, key=lambda d: estimated_pickup_eta(d, rider_lat, rider_lng))
    if driver_state.try_reserve(best):    # atomic compare-and-set — see race condition below
        return best
    return match_driver(rider_lat, rider_lng)   # reservation lost the race, retry against remaining pool

The race condition this must handle: two riders requesting near-simultaneously could both select the same nearest driver before either reservation completes. try_reserve must be an atomic compare-and-set (driver state flips from available to reserved only if it was still available at the moment of the check) — the same check-then-act race as [[Parking Lot]]'s spot allocation, resolved the same way (an atomic claim, not a separate check followed by a separate write).

8. ETA & Routing

Computing the actual driving-distance ETA (not straight-line distance) requires a routing graph over the real road network — classic shortest-path algorithms (Dijkstra, or A* with a distance-to-destination heuristic for faster convergence) run against this graph, typically via a dedicated routing service/maps API rather than being reimplemented from scratch. This is intentionally a narrower, well-understood sub-problem within the larger design — worth naming the algorithm by name and moving on, not over-investing interview time here relative to the matching/geo-indexing core.

9. Surge Pricing

A live supply/demand signal — the ratio of ride requests to available drivers within a geographic cell (naturally computed per H3/geohash cell, reusing the same spatial partitioning as matching) — feeds a pricing multiplier applied to the base fare in that cell. This is a read of the same geo-indexed data already being maintained for matching, not a separate data pipeline — worth noting the reuse explicitly, since it's a real efficiency the design gets "for free" from choosing a good spatial index.

10. Deep Dives / Follow-ups

  • Expanding search radius: if no available drivers are found within the initial radius, retry with a progressively larger radius rather than failing immediately — a real usability requirement in low-supply areas.
  • Driver-side reconnection: if a driver's WebSocket drops mid-ride (tunnel, dead zone), the location store simply goes briefly stale for that driver — reconnection resumes updates; this is the same reconnect-and-catch-up pattern as [[WhatsApp Chat]]'s connection handling, applied to a moving-position stream instead of messages.
  • Fairness: pure nearest-driver matching can starve drivers who happen to be positioned less centrally — real systems weight in idle time to distribute rides more fairly across the driver pool, not purely by proximity.

11. Interview Drill Questions

  1. Why can't you just use a normal B-tree index on latitude and longitude columns separately? — A range query for "within 2km" needs both dimensions considered jointly; independently indexed lat/lng don't compose into an efficient 2D proximity search — this is exactly the problem Geohash/QuadTree/H3 solve by collapsing 2D proximity into a structure (a 1D string prefix, a tree, or a cell ID) that a normal index or direct lookup handles well.
  2. Why does Uber use a hexagonal grid (H3) instead of Geohash's implicit rectangular cells? — Hexagons have uniform neighbor distance (every adjacent hex is equidistant from center), while a square's diagonal neighbors are farther than its edge neighbors — this asymmetry makes proximity search and "expand outward by N rings" cleaner and more uniform with hexagons.
  3. Two riders request a ride at the same moment and both match to the same nearest driver. How do you prevent double-booking? — Driver reservation must be an atomic compare-and-set (available → reserved only if still available at that instant) — the same check-then-act race and fix as [[Parking Lot]]'s spot allocation; whichever request loses the race retries against the remaining candidate pool.
  4. How would you compute surge pricing without building a separate analytics pipeline? — Reuse the same geo-indexed driver/request data already maintained for matching — the request-to-available-driver ratio within a spatial cell (the same cell granularity used for matching) is directly computable from data the system already tracks, not a new data source.
  5. A driver's app loses connectivity for 30 seconds mid-trip. What does the rider see? — The driver's last known position simply stops updating in the geo-index during the gap — the rider's app shows a stale (last-known) position rather than an error, and updates resume once the WebSocket reconnects; this is a deliberate "degrade gracefully to stale data" choice rather than treating a brief disconnect as a hard failure.

Cross-links

[[Caching & Redis]] · [[WhatsApp Chat]] · [[Parking Lot]] · [[Consistent Hashing]] · [[Communication Protocols]]