Design a driver location heatmap

Source: https://www.hack2hire.com/question-bank/questions/system-design/69d2e1c707421ca06eb8e4c0
Company: Uber, Amazon
Difficulty: Hard

Problem statement

Show near-real-time density of available drivers and rider demand on a city map, updated every few seconds from millions of location pings.

Requirements

We are building a near-real-time heatmap service: it turns millions of driver location pings and rider demand events into per-cell counts of available drivers and open demand on a city map, refreshed every few seconds for ops dashboards and pricing, with history kept for analysis and export.

Clarify early: who reads it (internal ops and pricing, not riders), how fresh "live" must be (5–10 s), what counts as a driver (online and not on a trip), what demand means (app opens with a destination plus ride requests), cell size, and how far back history goes.

Functional requirements

• Ingest driver pings (driver ID, lat/lng, status, device timestamp) from the driver app every ~4 s.
• Ingest demand events (session opened, request created, request unfulfilled) from the rider app.
• Live view: for a city or viewport, return per-cell counts of available drivers, demand, and the supply/demand ratio for the current minute and the last 30 minutes.
• Push refreshed cells to open dashboards every 5 s instead of having them poll.
• Historical view: the same counts per cell for any past window (hour, day, month) at minute or hour grain.
• Export: a bulk job that writes a city and date range to files for data science.

Non-functional requirements

• Freshness: a ping shows up on the live map within 10 s at p99; the UI shows how stale it is when that slips.
• Availability over precision: a count that is off by a few percent is fine; a blank map is not.
• Ingest absorbs 2× peak bursts (concert end, rain) without dropping pings; it degrades freshness first.
• Location data is sensitive: raw tracks are restricted and expire; the heatmap only ever exposes aggregates.
• Live reads at p99 under 100 ms; historical queries over a day of one city under 2 s.

Back-of-the-envelope estimation

• 5M drivers online at global peak, one ping per 4 s → 1.25M pings/s. At ~150 B per ping that is ~190 MB/s, ~16 TB/day raw.
• Demand events: ~200k/s at peak, small next to pings.
• H3 resolution 8 cells (~0.7 km²): a large city covers ~3,000 cells, and only ~1,500 have activity in a given minute. 1,000 active cities × 1,500 cells = 1.5M live cells per minute.
• One cell-minute row (city, cell, minute, drivers, demand, requests) ≈ 40 B → 1.5M × 1,440 × 40 B ≈ 86 GB/day of minute rollups, about 200× smaller than raw.
• Live window: 30 minutes × 1.5M cells × 40 B ≈ 1.8 GB. That fits in memory across a small Redis cluster.
• Live readers: ~20k dashboards each pulling ~500 cells every 5 s → 4k reads/s, trivial next to ingest.

API design

Writes are fire-and-forget over a binary protocol; reads are small aggregate queries.

Driver ingest (mobile → edge gateway, gRPC or HTTP/2 batched):

POST /v1/locations:batch
{ driver_id, session_id, pings: [ { seq: 81234, ts_device: 1760275200123,
  lat: 37.7749, lng: -122.4194, accuracy_m: 8, speed_mps: 6.1,
  status: "available" } ] }
→ 202 { ack_seq: 81234 }

The client keeps a monotonic seq per session and resends anything not acked, so retries are safe. The gateway stamps ts_server and reads driver_id from the auth token, never from the body.

Recent heatmap read:

GET /v1/heatmap/live?city=sf&res=8&window=1m&cells=8828308281fffff,...
→ { as_of: "2026-10-12T18:04:00Z", watermark_lag_s: 4,
    cells: [ { h3: "8828308281fffff", drivers: 14, demand: 22, ratio: 0.64 } ] }

The client can pass bbox instead of cells; the server converts it to a cell set. window is 1m, 5m, or 30m.

Historical query:

GET /v1/heatmap/history?city=sf&res=7&from=2026-10-01&to=2026-10-08&grain=1h&cells=...
→ { rows: [ { h3, bucket_start, drivers_avg, drivers_max, demand_sum } ], next_cursor }

Export: POST /v1/exports {city, from, to, res, grain, format: "parquet"} → 202 {export_id}; GET /v1/exports/{id} → {status, files: [signed_url]}.

Live stream: WebSocket subscribe {city, cells | bbox, res}. The server pushes {as_of, watermark_lag_s, changed: [{h3, drivers, demand}]} every 5 s, only for cells that changed. On reconnect the client calls the live read once to get a full snapshot, then resumes the stream.

Auth and trust: drivers authenticate with their app token; readers use internal SSO with a per-city role. Only aggregates leave the read API, and cells with fewer than 3 drivers are shown as "1–2" for historical exports, so individual drivers can't be traced.

Data model

Split what must be durable from what can be rebuilt.

Invariants:

• A driver counts at most once per cell-minute, in the cell of their last valid ping in that minute.
• Counts at a coarser resolution equal the sum of their children; we compute res 8 and roll up to res 7 and 6 by H3 parent, never re-bucket from points.
• Every live and historical row carries the watermark it was computed with, so readers can tell final from provisional.

Why these stores: Redis serves the "current minute for 500 cells" read in one HMGET per minute key. ClickHouse handles "a week of hourly counts for a city" as a columnar scan over a sorted key. Postgres holds the few rows that need transactions. Kafka is the replay log that lets everything else be rebuilt.

High-level design

Putting every ping into one database fails first on writes: 1.25M row upserts/s with per-driver index updates swamps any single primary, and the read side would then need GROUP BY over billions of rows every 5 s. So we aggregate in a stream and store only cell-level results.

flowchart LR
  D[Driver app] --> GW[Ingest gateway]
  R[Rider app] --> DE[Demand service]
  GW --> K[(Kafka pings)]
  DE --> KD[(Kafka demand)]
  K --> F[Flink aggregator]
  KD --> F
  F --> RC[(Redis live cells)]
  F --> KR[(Kafka cell minutes)]
  KR --> CH[(ClickHouse)]
  K --> S3[(S3 raw archive)]
  RC --> API[Heatmap API]
  CH --> API
  API --> WS[WebSocket fanout]
  WS --> UI[Ops dashboard]
  API --> UI
  EX[Export workers] --> CH
  EX --> S3E[(S3 exports)]

1. Ingest and recent rollup. The gateway authenticates, validates ranges, stamps server time, and writes batches to Kafka keyed by driver. Flink keeps each driver's last state, maps each valid ping to an H3 res 8 cell, and on each 10 s tick emits per-cell counts for the current minute. It writes those to Redis with HSET hm:sf:202610121804 and a 35-minute TTL.
2. Recent read, push, and recovery. The API reads the current minute key (and up to 29 earlier ones for a 30-minute window), sums them, and returns cells with as_of and lag. A fanout tier subscribes to a per-city Redis pub/sub channel that Flink publishes changed cells on, and forwards deltas only to sockets whose viewport covers those cells. A reconnecting client fetches a snapshot, then takes deltas.
3. Historical materialization. When the event-time watermark passes a minute plus the lateness allowance (2 min), Flink emits the final cell-minute row to a Kafka topic. ClickHouse consumes it into cell_minute; a materialized view rolls up into cell_hour. History queries hit hour rows for ranges over a day and minute rows otherwise.
4. Export. The API writes an exports row; a worker runs a ClickHouse INSERT INTO FUNCTION s3(...) split by day, then marks it done with signed URLs.

When the stream lags, the live map keeps serving the last complete minute and shows its age; history waits for the watermark and is never wrong, only late.

Deep dives

From GPS points to H3 minute buckets. A driver should count once per cell per minute, not once per ping, otherwise a parked driver who pings 15 times looks like 15 drivers. Flink keys by driver_id and keeps {last_cell, last_status, last_event_ts}. For each minute it marks the driver present in the cell of their last valid available ping in that minute. Per-cell counts are a running map in a second keyed operator (city, minute) that receives +1/−1 deltas when a driver's minute cell changes, which keeps state at ~1.5M counters instead of 5M driver sets. H3 hexagons beat a square geohash grid because every neighbor is the same distance away, so smoothing and "drivers within 2 rings" are uniform. Resolution 8 is the store grain; 9 (0.1 km²) is too sparse to read and 4× the rows. Demand events go through the same path keyed by rider session, so a rider who opens the app three times in a minute is one unit of demand.

Handling duplicate, late, and invalid updates.

The watermark is per Kafka partition with bounded out-of-orderness of 10 s, and idle partitions are marked idle so one quiet partition does not stall the city.

Hot-cell skew, partitioning, and recent-cache rebuild. Ingest is keyed by driver, which spreads evenly. The skew shows up in the aggregation step: an airport cell at 5 pm can get 3,000 drivers' deltas per tick. Two-phase aggregation fixes it: each driver-keyed task pre-sums deltas per (city, minute, cell) for 1 s before sending, so the cell operator gets one message per task per second. Cell counters are keyed by (city, minute) and the largest cities (NYC, São Paulo) are split by H3 res 4 parent so no single task owns a whole metro. Redis keys are per city-minute; for a 30-minute read that is 30 HMGETs pipelined to one shard, about 3 ms. If Redis is lost, Flink restarts from its last checkpoint (every 30 s) and replays Kafka from 35 minutes back with the Redis sink in rebuild mode, writing all buckets. That refills the live window in about 2 minutes at 10× catch-up speed. Meanwhile the API falls back to the newest ClickHouse minute rows, flagged as stale.

Historical rollups, ClickHouse reads, and export jobs. cell_minute uses ReplacingMergeTree(version) keyed (city, res, cell, minute), so a correction from the nightly late-data job replaces the original row on merge; queries use FINAL only for the last day. Res 7 and 6 are materialized views that group by h3ToParent. A one-week, hourly, city-wide query reads ~3,000 cells × 168 hours ≈ 500k rows, well under 1 s. Exports run as a queue of day-sized tasks with at most 4 concurrent per requester, so a year-long export cannot starve dashboards; they run on a replica set apart from the one serving the API.

Freshness, backfill, and the 20–60 minute gap. Every response carries watermark_lag_s; above 30 s the UI greys the map and shows "data as of 18:03". Backfill after a bug fix replays from S3 into a separate Flink job writing into a shadow ClickHouse table, then swaps partitions, so readers never see a half-rebuilt day. The awkward window is 20–60 minutes back: past Redis's useful range for cheap sums, before late data is final in ClickHouse. Extending the Redis TTL to 65 minutes costs ~2 GB more memory and covers it; a separate middle tier only earns its cost if product wants second-level grain for hours, which it does not.

Trade-offs

• Aggregating in the stream gives cheap reads and small storage, but you lose any query not planned upfront; the 30-day raw archive is the escape hatch, at the cost of storing locations twice.
• Counting a driver once per cell-minute removes ping-rate bias but loses sub-minute movement; drivers crossing cells mid-minute count only in their last cell.
• Fixed 2-minute lateness gives timely history but needs a nightly correction pass; waiting longer would delay every chart.
• Pushing deltas over WebSockets cuts read load and latency, but adds a stateful fanout tier and a snapshot-plus-resume protocol.
• Redis for the live window is fast and simple but volatile, so recovery depends on Kafka retention and replay speed.
• H3 res 8 as the single stored grain keeps storage simple, but street-level views (res 9+) would need a new pipeline or raw data.
• Suppressing tiny counts protects driver privacy but makes rural areas look emptier than they are.

Interviewer expectations

Mid-level (L4)

• Separates ingest from reads with a queue and does not write every ping to a database.
• Buckets locations into a grid (geohash or H3) and counts per cell per time window.
• Uses a cache for the live map and a separate store for history, with plausible API shapes.

Senior (L5)

• Does the math (1.25M pings/s, ~1.5M live cells) and picks stream aggregation because of it.
• Counts distinct drivers per cell-minute, handles duplicates, late, and invalid pings with event time and watermarks.
• Addresses hot cells with pre-aggregation, and explains how the live cache is rebuilt from Kafka after a failure.
• Uses push for the live view and shows freshness to the user.

Staff (L6+)

• Frames the design around durable versus rebuildable data, and plans replay and backfill without reader-visible gaps.
• Reasons about cost: what is stored twice, retention per tier, and when a middle tier is worth it.
• Raises privacy (aggregate-only output, small-count suppression, restricted raw tracks) and multi-region ingest.
• Defines SLOs for freshness and correctness and what degrades first under load.