Once a rider is matched to a driver, the interesting problem is not “who is my driver” - it is the little car crawling across the map toward the pin, and the number under it that says “4 min” and keeps updating. Both look trivial. Both hide the hard part. The car moving smoothly is the output of a fan-out system that takes one driver’s GPS ping and delivers it to the exact rider watching that trip, in under a second, five million times over. The “4 min” is the output of a routing engine that has to answer “how long from here to there, given the traffic right now” continuously for the entire duration of every trip, without recomputing a shortest path over a road graph on every single ping.

This post is about those two systems and how they interlock: live location sharing (a targeted, low-latency push fan-out) and the ETA service (traffic-aware route-time estimation that has to stay fresh as both the car and the traffic move). The scale target is 5M concurrent rides, each expecting sub-second location updates and an ETA that reflects live conditions. I will treat “who matched this driver to this rider” as already solved (it is a separate matching system) and focus entirely on the tracking-and-ETA plane, which is where the sub-second, continuous-recompute constraint actually bites.

Functional Requirements (FR)

In scope:

  • Live location streaming to the rider. During an active trip, the driver’s app streams GPS position every ~4s. The rider watching that trip sees the car move on the map with sub-second delay from ping to render.
  • Continuous ETA to pickup and to destination. The rider sees a live ETA (“driver arrives in 4 min”, then “in progress, 12 min to destination”) that updates as the car moves and as traffic changes, not a one-time estimate frozen at request time.
  • Traffic-aware routing. The ETA reflects live road speeds - a jam that forms mid-trip should push the ETA up within a minute or two, not stay stale until arrival.
  • Smooth client rendering. The car should glide along the road, not teleport between GPS points every 4s. The path shown should follow the actual road, not a straight line through buildings.
  • Share-my-trip. A rider can share a live link with a friend who is not in the app; the friend sees the same moving car and ETA in a browser, read-only.
  • Reconnect and catch-up. If the rider’s app backgrounds or drops network, on reconnect it gets the current position and ETA immediately, not a replay of every missed ping.

Explicitly out of scope (own the scope out loud):

  • Matching / dispatch. Who the driver is and how they got assigned is a separate system; a trip arrives here already having a driver, a rider, and a route.
  • The map tiles and rendering SDK. The client-side map (tiles, sprite animation) is a solved client concern. I design the data feeding it.
  • Turn-by-turn navigation for the driver. The driver’s nav is its own product surface. I compute ETAs; I am not designing the voice-guidance UX.
  • Building the road graph and traffic collection pipeline from scratch. I will design how the ETA service uses a road graph and a live-speed layer, and how that speed layer is fed, but not the map cartography ingestion.
  • Billing, ratings, support. Downstream systems handed the finished trip.

The one decision that shapes everything: this is a targeted-push fan-out problem bolted to a read-mostly routing problem, and both must stay fresh continuously. Live location is not a broadcast (one car goes to one rider, not to everyone) and not a request/response (the rider is not polling, the server is pushing). ETA is not a one-shot compute (it must track a moving car through changing traffic). Those two shapes - point-to-point push and continuous re-estimation - drive the architecture.

Non-Functional Requirements (NFR)

  • Scale: 5M concurrent active trips at peak. Each has one driver pushing GPS every ~4s (so ~1.25M location pings/sec inbound) and at least one rider (often two or three viewers with trip-share) watching. Call it ~7-10M concurrent viewer connections.
  • Latency: end-to-end ping-to-render p99 under ~1s. ETA recompute reflected to the rider within a few seconds of a position change and within ~1-2 min of a traffic change. The “car glides” smoothing happens client-side to hide the 4s ping gap.
  • Availability: 99.9%+ on the tracking path. A rider who cannot see their car gets anxious but the ride still happens, so this is important but not as sacred as the matching path. Location streaming can tolerate brief degradation - a dropped ping is superseded by the next one 4s later.
  • Consistency: best-effort and eventually consistent throughout. There is no money and no assignment here, so there is no need for strong consistency. The rider seeing a position that is 4s stale, or an ETA off by 20s, is fine. Freshness matters far more than agreement.
  • Durability: location pings are ephemeral - we keep only “where is the car now” plus a rolling trail for smoothing. The full trip route polyline is archived once, at trip end, for receipts and disputes. Losing an individual ping is a non-event.
  • Freshness: the rider’s view should be no more than one ping interval (~4s) behind reality, plus network. The ETA should incorporate traffic no older than ~1-2 min.

Back-of-the-Envelope Estimation (BoE)

Real numbers, with the arithmetic, because they pick the architecture.

Location ingest (driver -> backend):

5M concurrent trips, one driver each, ping every 4s
= 5,000,000 / 4
= 1,250,000 location pings/sec average
Peak (1.5x, evening rush overlap) ≈ ~1.9M pings/sec

Fan-out (backend -> viewers):

Each trip has ~1.5 viewers on average (rider always, plus trip-share sometimes):

5M trips * ~1.5 viewers = ~7.5M concurrent viewer connections
Each viewer receives one position update per driver ping (~every 4s)
= 7,500,000 / 4
≈ 1.9M outbound location messages/sec

So inbound and outbound message rates are the same order (~2M/sec each). The key asymmetry from a chat system: the fan-out is tiny and fixed per source (one driver to ~1.5 viewers), not a celebrity broadcast to millions. That makes the routing tractable - we never fan one message to a huge audience.

ETA computations:

Naively recomputing an ETA on every ping:

1.25M pings/sec, each triggering a route computation
= 1.25M ETA computes/sec

A full shortest-path over a city road graph is milliseconds of CPU; 1.25M/sec of that is enormous and, crucially, wasteful - the ETA does not change meaningfully between two pings 30m apart on the same road. So the real design does not recompute per ping; it recomputes on triggers (route deviation, elapsed time, traffic change). Estimate after throttling:

Recompute per trip at most every ~20-30s, or on deviation
≈ 5M trips / 25s ≈ 200K ETA computes/sec (steady)
plus event-driven recomputes on traffic changes (bounded, batched)

That is a 6x reduction just from not being naive, and it drops further because most recomputes are cheap incremental updates, not full path searches (deep-dive below).

Live location state (in memory):

Per active trip live record:
  trip_id        8 bytes
  driver pos     16 bytes (lat/lng)
  heading/speed  8 bytes
  route ref      8 bytes
  eta_pickup/dest 8 bytes
  recent trail   ~10 points * 12 bytes ≈ 120 bytes
  ≈ 170 bytes (round to ~256 with keys/overhead)
5M trips * 256 bytes ≈ 1.3 GB of live tracking state

Small. The entire live tracking picture fits in RAM across a handful of nodes. The hard part is not storing it, it is pushing it to the right connection ~2M times/sec and keeping the ETA fresh.

Bandwidth:

Ingress: 1.9M pings/sec * ~150 bytes (payload + framing) ≈ 285 MB/sec
Egress:  1.9M msgs/sec * ~120 bytes ≈ 230 MB/sec

Trip route archive (durable, at trip end only):

20M trips/day, each stores one final route polyline ≈ 3 KB
= 20M * 3 KB = 60 GB/day ≈ 22 TB/year, cheap object storage.

The takeaways: ~2M pings/sec in and ~2M targeted messages/sec out with a small fixed per-source fan-out, ~1.3 GB of live state that fits in memory, and an ETA workload that is only survivable if you refuse to recompute per ping. The connection/fan-out layer and the ETA recompute-trigger strategy, not storage, are the design drivers.

High-Level Design (HLD)

Two planes again, but different from the matching design. The streaming plane ingests driver pings and pushes them to the specific viewers of that trip. The ETA plane keeps a fresh route-time for every trip, fed by a live traffic layer, and injects updated ETAs into the same stream the position flows through. A connection registry ties a trip_id to the set of connections watching it.

   ┌──────────────┐   GPS ping /4s        ┌───────────────────────────┐
   │  Driver App   │──────────────────────▶│  Ingest Gateway            │
   │ (GPS stream)  │   persistent WSS/gRPC │ (terminates driver streams)│
   └──────────────┘                        └──────────┬────────────────┘
                                                      │ produce (key = trip_id)
                                            ┌─────────▼──────────┐
                                            │ Kafka: raw-locations│
                                            └─────────┬──────────┘
                                                      │ consume
                              ┌───────────────────────▼───────────────────────┐
                              │            Tracking Service                     │
                              │  ┌───────────────┐   ┌────────────────────┐     │
                              │  │ Live state     │   │ Map-matcher +       │     │
                              │  │ per trip (RAM) │   │ smoother (snap to    │    │
                              │  │ pos, trail, eta│   │ road, dedupe jitter) │    │
                              │  └───────┬───────┘   └─────────┬───────────┘     │
                              └──────────┼──────────────────────┼───────────────┘
                                         │ position + eta        │ "recompute?"
                          ┌──────────────▼──────────┐   ┌────────▼───────────────┐
                          │  Fan-out / Push layer     │   │   ETA Service           │
                          │  (Pub/Sub by trip_id ->   │   │  ┌──────────────────┐   │
                          │   viewer connections)     │   │  │ Road graph (CH)   │  │
                          └──────────┬────────────────┘   │  │ + live speed layer│  │
                                     │ push                │  └──────────────────┘   │
              ┌──────────────────────┼───────────┐        └────────┬───────────────┘
   ┌──────────▼────────┐  ┌──────────▼───────┐    │                 │ reads
   │  Rider App         │  │ Shared-link      │   │        ┌─────────▼──────────┐
   │ (watch car + ETA)  │  │ Browser (viewer) │   │        │ Traffic Aggregator  │
   └────────────────────┘  └──────────────────┘   │        │ (driver speeds ->   │
   ┌──────────▼────────────────────────┐          │        │  per-edge speeds,   │
   │  Connection Registry              │◀─────────┘        │  windowed stream)   │
   │ (trip_id -> {conn, edge node})    │                   └─────────┬──────────┘
   └───────────────────────────────────┘                             │ feeds
                                                        ┌────────────▼─────────┐
                                                        │  Route Archive        │
                                                        │  (object store, at end)│
                                                        └──────────────────────┘

Location ingest and fan-out flow:

  1. The driver app holds a persistent connection (WebSocket/gRPC) to an Ingest Gateway and pushes {trip_id, driver_id, lat, lng, heading, speed, ts} every ~4s.
  2. The gateway publishes to a Kafka topic keyed by trip_id (all of one trip’s pings stay ordered on one partition; a stale ping never overtakes a fresh one).
  3. The Tracking Service consumes the stream. For each ping it runs the map-matcher (snap the raw GPS to the road, discard jitter) and updates the trip’s in-memory live state (position, a short trail of recent points, current ETA).
  4. It hands the cleaned position (and any updated ETA) to the Fan-out layer, which looks up in the Connection Registry which viewer connections are watching this trip_id and pushes the update to exactly those connections, on whichever edge nodes hold them.
  5. The rider’s app receives the position and ETA and animates the car smoothly between the last point and the new one (client-side interpolation hides the 4s gap).

ETA flow:

  1. Every driver ping also doubles as a real-world speed sample for the road segment the car is on. The Traffic Aggregator consumes the location stream and maintains a live per-edge speed layer (how fast traffic is actually moving on each road segment right now).
  2. The ETA Service owns a road graph with precomputed shortcuts (contraction hierarchies) and reads the live speed layer as edge weights. Given (current position, destination) it returns a travel time.
  3. The Tracking Service does not call the ETA Service on every ping. It calls on triggers: the car deviated from its planned route, a fixed time elapsed (~20-30s), or the ETA Service signalled that traffic on this trip’s remaining route changed materially. The fresh ETA is written to live state and pushed to viewers on the next update.

Trip-share flow: a shared link resolves to a read-only viewer that subscribes to the same trip_id in the Connection Registry and receives the identical position+ETA stream. No app install, no auth beyond the link token.

The key insight: position and ETA travel to the rider over one targeted push stream, keyed by trip_id; the fan-out is small and fixed per source; and the expensive part (routing) is decoupled from the cheap part (pushing) so we never do a shortest-path computation on the hot per-ping path.

Component Deep Dive

The hard parts, naive-first then evolved: (1) delivering one driver’s ping to the right viewers at 2M/sec, (2) keeping the ETA fresh against live traffic without recomputing per ping, (3) map-matching and smoothing so the car follows the road, (4) reconnect and trip-share.

1. Targeted fan-out: one driver’s ping to the right viewers

Naive approach: the rider polls. The rider’s app does GET /trips/{id}/location every second.

Where it breaks:

  • Read amplification. 7.5M viewers polling every 1s = 7.5M reads/sec, most returning the same position because the underlying ping only changes every 4s. Three out of four polls are wasted.
  • Latency floor. Polling puts a 1s floor on freshness and adds request/response overhead (TLS, auth, headers) to every poll. It cannot be sub-second cheaply.
  • Thundering herd on reconnect. Every backgrounded app resuming at once hammers the endpoint.

First evolution: server push over a shared connection, but broadcast per region. Give each viewer a WebSocket and push positions. But if you broadcast every trip’s position to every connection on a node and let the client filter, you send each connection ~5M positions/sec. Absurd. The push has to be targeted: a viewer receives only the one trip it is watching.

The answer: a Connection Registry plus a pub/sub fan-out keyed by trip_id.

  • Persistent connections at stateless edge nodes. Every viewer (rider app, shared-link browser) holds a WebSocket to a Push Edge node. The node is stateless beyond the sockets it holds.
  • Connection Registry maps trip_id -> {connections, and which edge node holds each}. When a viewer subscribes to a trip, the registry records trip_id -> (conn_id, edge_node_id). This is a small, fast key-value structure (Redis or a sharded in-memory service). Because average fan-out is ~1.5, each trip_id maps to a tiny set.
  • Fan-out routes by trip_id. When the Tracking Service produces an updated position for a trip, the Fan-out layer looks up the trip’s viewers, groups them by edge node, and forwards the message to each relevant edge node, which writes it to the local sockets. One ping fans to ~1.5 sockets, typically on 1-2 nodes.
subscribe(trip_id, conn):
    registry.add(trip_id, {conn_id: conn.id, node: this_node})

on_position_update(trip_id, payload):
    viewers = registry.get(trip_id)          # ~1.5 entries
    for node, conns in group_by_node(viewers):
        edge[node].push(conns, payload)      # local socket writes

Why this scales where broadcast does not: the fan-out degree is bounded by the number of people watching one trip (a handful), never by the total system size. This is the opposite of a Twitter timeline. It means the total outbound message rate equals the inbound ping rate times a small constant (~1.5), and the routing is a cheap registry lookup, not a search.

The edge nodes are horizontally scaled by connection count (each holds, say, 100K-500K sockets). The registry is sharded by trip_id. The Tracking Service is sharded by trip_id (same key as Kafka partitioning) so a trip’s pings, state, and fan-out decisions all live together. When an edge node dies, its viewers reconnect (with catch-up, deep-dive 4) and re-register; no message is durably lost because the next ping is 4s away.

ApproachFreshnessMsgs/sec at scaleServer work per update
Client polling 1s≥1s floor7.5M reads/sec (75% wasted)read + serialize per poll
Broadcast + client filtersub-second5M * connections (absurd)push everything everywhere
Registry + targeted pushsub-second~1.9M targeted/secregistry lookup + ~1.5 writes

2. Keeping the ETA fresh without recomputing per ping

This is the real “hard part” of the assignment: the ETA must track a moving car through changing traffic, continuously, for millions of trips.

Naive approach: recompute a shortest path on every ping. Each ping, run Dijkstra from the driver’s current node to the destination over the road graph, weighted by current traffic.

Where it breaks:

  • Compute cost. Dijkstra over a metropolitan road graph is single-digit milliseconds. At 1.25M pings/sec that is thousands of CPU-cores of routing, continuously, for a number that barely moved. A ping 30m further down the same road yields essentially the same ETA.
  • Graph weight volatility. If you re-read live traffic on every query, tiny speed fluctuations make the ETA jitter up and down second to second, which looks broken to the rider.
  • No reuse. Every query throws away the previous route even though 99% of it is unchanged.

First evolution: cache the route, decrement the ETA locally. Compute the full route once at trip start, then on each ping just subtract elapsed time / advance along the cached route. Cheap, but it goes stale: it never learns that a jam formed on the road ahead, so the ETA silently lies until the car hits the jam.

The answer: precomputed routing (contraction hierarchies) + a live per-edge speed layer + trigger-based recompute, split into cheap and expensive updates.

Contraction hierarchies (CH) for fast routing. A plain Dijkstra is too slow to run often. CH preprocesses the static road graph by adding “shortcut” edges that let a query skip over unimportant nodes, turning a metro-scale shortest path from milliseconds into tens of microseconds. The graph topology is static (roads do not move), so CH preprocessing is done offline and reused; only the edge weights (travel times) change with traffic.

Live speed layer as edge weights. The Traffic Aggregator (deep-dive below) maintains, per road segment (edge), the current travel time derived from real driver speeds. The ETA query is a CH search over the graph using these live weights. Because weights change but topology does not, we use customizable CH (CCH) style updates: re-customize edge weights cheaply without re-running the full contraction.

Trigger-based recompute, not per-ping. The Tracking Service recomputes a trip’s ETA only when it matters:

should_recompute(trip, ping):
    if off_route(ping, trip.route):        return FULL      # driver deviated -> new path
    if now - trip.eta_computed_at > 25s:   return REFRESH   # periodic re-weight
    if traffic_changed(trip.remaining_edges): return REFRESH # jam formed ahead
    return NONE                            # just advance position along cached route
  • NONE (the common case): advance the car along the already-known route and linearly decrement the ETA. Pure arithmetic, no routing call. This handles the overwhelming majority of pings.
  • REFRESH (cheap): re-evaluate travel time along the same cached route using updated edge weights. No path search - just sum the current weights of the route’s remaining edges. Microseconds. Runs every ~25s or when the traffic layer flags a change on this route.
  • FULL (rare): the driver went off the planned route (wrong turn, driver’s own nav rerouted). Run a fresh CH query for a new path. This is the only case that pays for a real shortest-path search, and it is rare per trip.

Push traffic changes to affected trips, do not poll. When the Traffic Aggregator detects a material speed change on an edge, it publishes the edge id. The ETA Service keeps a reverse index edge -> trips whose remaining route uses this edge and flags exactly those trips for REFRESH. A jam on one road wakes only the trips heading into it, not all 5M.

Traffic Aggregator: edge E slowed 60kph -> 15kph  --publish-->
ETA Service: trips_using[E] = {t_9, t_44, ...}   -> flag REFRESH
             (cheap re-sum of remaining-edge weights, no path search)

The layering is the whole trick: topology is preprocessed once (CH), weights update continuously and cheaply (live speed layer), and full path searches happen only on the rare deviation. The per-ping path is arithmetic; the periodic path is a weight re-sum; the shortest-path search is the exception. That is how you keep 5M ETAs traffic-fresh without a datacenter of routing CPU.

3. Map-matching and smoothing: making the car follow the road

Naive approach: draw the car at the raw GPS coordinate. Take each ping’s lat/lng and place the sprite there.

Where it breaks:

  • GPS jitter. Consumer GPS is noisy: in an urban canyon it wanders 10-50m, so the car appears to jump onto rooftops, into the river, or hop between parallel roads.
  • Teleporting. Pings are 4s apart; drawing raw points makes the car jump in discrete hops instead of moving smoothly.
  • Straight-line paths. Connecting two GPS points with a straight line cuts through buildings and does not follow the curve of the road.

The fix: server-side map-matching plus client-side interpolation along the road geometry.

  • Map-matching (server). Snap each raw GPS point to the most likely road segment given the trip’s route and recent trail. A Hidden Markov Model style matcher considers candidate road positions near the raw point and picks the sequence most consistent with the road network and the previous positions - so a point that GPS placed in the river snaps back to the road the car is actually on. The output is a clean position on a road edge plus how far along that edge.
  • Dedupe and reject outliers. If a ping implies the car moved 2km in 4s (500kph), it is GPS garbage; drop it and keep the previous position. Keying Kafka by trip_id guarantees order, so we can trust “later ts wins” and discard stragglers.
  • Send road geometry, not just a point. The Tracking Service pushes the matched position and the polyline of the road segment between the previous and current position. The client animates the sprite along that polyline over the ~4s interval, so the car curves along the actual road at roughly the real speed. This client-side interpolation is what turns 4s-spaced points into smooth motion - the server does not need to send positions more often than the GPS produces them.
raw ping -> map_match(ping, route, trail) -> {edge_id, offset, snapped_latlng}
         -> if implied_speed > sane_max: drop
         -> push { pos: snapped_latlng,
                   segment_polyline: geometry(prev -> snapped),
                   eta_s, heading }
client: animate sprite along segment_polyline over interval  (glide, not teleport)

The division of labor: the server cleans and snaps (map-matching, outlier rejection) because it has the road graph and the trail; the client smooths motion (interpolation along the sent geometry) because that is a render concern and doing it client-side means we do not raise the ping rate. Raising GPS frequency to make motion smooth would multiply the ingest firehose for no real freshness gain; interpolation gets smoothness for free.

4. Reconnect, catch-up, and trip-share

Naive approach: on reconnect, replay the missed pings. When a rider’s app returns from background, send everything it missed.

Where it breaks:

  • Nobody wants history. The rider wants to know where the car is now, not to watch a time-lapse of the last 90s. Replaying missed pings wastes bandwidth and shows stale motion.
  • Reconnect storms. A network blip drops thousands of connections at once; if each triggers a heavy replay, the reconnect path melts.

The fix: snapshot-on-subscribe, then live tail.

  • Latest-state snapshot. The Tracking Service keeps each trip’s current position, trail, and ETA in memory (it already does, for fan-out). On (re)subscribe, the client immediately gets one snapshot message: current position, current ETA, the recent trail (so the map can draw the path so far). Then it joins the live stream. No replay of individual missed pings.
  • Idempotent, last-write-wins updates. Every message carries the ping ts. The client ignores anything older than what it has rendered, so an out-of-order straggler after reconnect cannot rewind the car.
  • Cheap re-registration. Reconnect is: open socket -> subscribe(trip_id) -> get snapshot -> tail. The Connection Registry entry is rebuilt on subscribe; the old entry (on the dead node) expires by TTL/heartbeat. No global coordination.

Trip-share is the same subscribe path with a twist: the shared link carries a scoped, expiring token that grants read-only viewer access to exactly one trip_id and auto-revokes at trip end. The browser viewer subscribes like any other viewer and receives the identical snapshot-then-tail stream. Because fan-out is already per-trip_id and viewer-count-agnostic, adding a shared viewer is just one more entry in the registry - the system does not care whether a viewer is the rider or a friend.

GET /share/{token}  -> resolve token -> trip_id (read-only, expires at trip end)
   -> open viewer socket -> subscribe(trip_id) -> snapshot -> live tail

API Design & Data Schema

The location path is streamed frames; control operations are REST; the viewer path is a subscribe stream.

Location ingest (driver -> backend), persistent stream

// driver -> server, one frame every ~4s
{ "type": "LOCATION", "trip_id": "t_51", "driver_id": "d_88",
  "lat": 19.0762, "lng": 72.8779, "heading": 210, "speed_kph": 34,
  "ts": 1752... }

Viewer stream (rider / shared browser <- backend)

// server -> viewer, on subscribe (snapshot)
{ "type": "SNAPSHOT", "trip_id": "t_51", "status": "driver_en_route",
  "pos": {"lat":19.0762,"lng":72.8779}, "trail": [ ...recent points... ],
  "eta_pickup_s": 240, "eta_dest_s": null, "ts": 1752... }

// server -> viewer, live update per driver ping
{ "type": "POSITION", "trip_id": "t_51",
  "pos": {"lat":19.0770,"lng":72.8785},
  "segment_polyline": "encoded_polyline...",   // for smooth client animation
  "eta_pickup_s": 220, "heading": 208, "ts": 1752... }

REST (control plane)

POST /api/v1/trips/{trip_id}/subscribe          (rider app; returns stream endpoint + token)
  -> { ws_url: "wss://edge-7...", sub_token: "st_..." }

POST /api/v1/trips/{trip_id}/share              (rider creates a share link)
  -> { url: "https://.../share/eyJ...", expires: "trip_end" }

GET  /share/{token}                             (public, read-only viewer bootstrap)
  -> { trip_id, ws_url, sub_token }             (scoped to one trip, expiring)

GET  /api/v1/trips/{trip_id}/eta                (fallback poll if stream unavailable)
  -> { eta_pickup_s: 220, eta_dest_s: 760, computed_at: 1752... }

Data stores - the right tool per plane

1. Live tracking state - in-memory, sharded by trip_id (NOT a durable DB). Position, recent trail, current ETA, route reference. ~1.3 GB total, rebuildable from a minute of the Kafka location topic. Deliberately non-durable because the data lives seconds.

In-memory per trip (or Redis hash per trip):
  trip:{id}:pos     -> {lat, lng, heading, ts}
  trip:{id}:trail   -> ring buffer of last ~10 matched points
  trip:{id}:eta     -> {pickup_s, dest_s, computed_at}
  trip:{id}:route   -> ref to current CH route (edge list)

2. Connection Registry - in-memory / Redis, sharded by trip_id. Maps a trip to its viewers and their edge nodes. Ephemeral; entries expire on heartbeat loss.

registry: trip_id -> Set<{conn_id, edge_node, role: rider|share, expires}>

3. Road graph + CH shortcuts - in-memory, read-mostly, replicated per region. The static topology plus precomputed contraction hierarchy shortcuts. Rebuilt offline when the map changes (rarely). Loaded into every ETA Service node.

4. Live speed layer - in-memory key-value, edge_id -> current_travel_time, per region. Updated continuously by the Traffic Aggregator; read by the ETA Service as edge weights. Plus a reverse index edge_id -> Set<trip_id> for targeted REFRESH.

5. Route archive - object storage, written once at trip end. The final route polyline and a downsampled position trail, for receipts and disputes. Immutable, cheap, ~22 TB/year.

Object store key: trips/{yyyy-mm}/{city}/{trip_id}.json
  { trip_id, route_polyline, sampled_trail, distance_km, duration_s }

6. Trip metadata - relational (sharded by city_id). The durable record of the trip (rider, driver, status, timestamps). Owned largely by the matching/trip system; the tracking plane reads it to bootstrap and writes only the final route reference.

Why in-memory/streaming for tracking but object store for the archive and SQL for metadata: the planes have opposite needs. Live positions are ephemeral, enormous in rate, and read once by ~1.5 viewers - a durable DB would be pure write amplification on data thrown away in seconds. The archive is written exactly once and read rarely - object storage is ideal. Trip metadata is a relational record with a state machine and relationships - that wants SQL. There is no strong-consistency requirement anywhere in the tracking plane, which is what lets the whole live path be in-memory and best-effort.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Fan-out connection count (breaks first). ~7.5M concurrent viewer sockets plus ~5M driver sockets is far beyond one node. Fix: horizontally scaled stateless edge nodes, each holding 100K-500K sockets, behind a connection-aware load balancer. Viewers and drivers are spread across nodes; the Connection Registry (sharded by trip_id) records which node holds each connection so fan-out routes correctly. Add nodes to add capacity linearly.

2. Targeting the fan-out. Sending each ping to the right ~1.5 sockets without scanning. Fix: pub/sub keyed by trip_id backed by the registry. One ping -> registry lookup -> push to a handful of sockets on 1-2 nodes. Fan-out degree is bounded by viewers-per-trip (small and fixed), never by system size, so total egress is inbound-times-a-constant.

3. Location ingest firehose. ~1.9M pings/sec must not touch a durable DB. Fix: persistent connections + Kafka keyed by trip_id into an in-memory Tracking Service. Non-durable by design - a lost ping is superseded in 4s; a crashed Tracking node rebuilds its shard from ~1 min of Kafka retention.

4. ETA compute cost (the assignment’s core risk). Per-ping shortest paths are thousands of cores of wasted work. Fix: the cheap/expensive split - advance-along-cached-route arithmetic on most pings, a periodic weight re-sum every ~25s, and a full CH search only on route deviation. Traffic changes wake only affected trips via the edge -> trips reverse index. This cuts routing work by more than an order of magnitude and keeps ETAs traffic-fresh.

5. Traffic layer hot edges and jitter. A jam on a major road flags huge numbers of trips at once; raw speeds fluctuate and make ETAs flicker. Fix: windowed, smoothed aggregation (exponential moving average over ~1-2 min per edge) so weights are stable, plus batched REFRESH - coalesce all trips flagged by one edge change into a batch and re-sum their remaining routes in one pass rather than one-by-one.

6. Hot trips / celebrity shares. A shared trip that goes viral (a public figure’s ride) could have thousands of viewers, breaking the “fan-out is tiny” assumption. Fix: detect high-viewer trips and fan out through a secondary broadcast tier (a per-trip topic that edge nodes subscribe to once and re-broadcast locally), so a 10K-viewer trip does not do 10K individual cross-node sends per ping. This is the one place we borrow the broadcast pattern, and only for the rare hot trip.

7. Map-matching CPU. Snapping ~1.9M pings/sec to the road graph is real compute. Fix: map-matching is embarrassingly parallel and sharded by trip_id alongside the Tracking Service; each shard matches only its trips using the region’s road graph in memory. It is a bounded local computation (candidates near one point), not a graph search.

8. Reconnect storms. A regional network blip drops and re-establishes millions of connections. Fix: snapshot-on-subscribe (no replay) keeps each reconnect cheap (one state read, one message), and jittered client reconnect backoff spreads the herd. The registry rebuilds on subscribe; dead entries expire by heartbeat TTL.

9. Cross-region trips and boundaries. A trip near a region edge, or a rider viewing from another continent. Fix: pin a trip’s tracking and ETA to the region its roads are in (driver, roads, and traffic are co-located), so the latency-critical loop never crosses regions. A far-away viewer connects to the nearest edge, which subscribes to the trip’s home-region fan-out over a backbone link - one cross-region stream per remote viewer, not per ping-hop.

10. Single points of failure. Fix: Ingest Gateways and edge nodes are stateless (rebuild from reconnect + Kafka); Tracking shards rebuild from the log; the registry, speed layer, and Kafka are replicated. The road-graph/CH data is read-only and replicated to every ETA node. No single box whose loss stops tracking - at worst a shard rebuilds while its viewers briefly see a frozen car, then catch up on the next snapshot.

11. Client bandwidth and battery. Pushing every ping to a backgrounded app drains battery and data. Fix: adaptive update rate - when the app reports it is backgrounded, drop the viewer to a lower cadence (e.g. every 15s) or pause and resume with a snapshot on foreground. The driver’s ingest rate stays constant (needed for ETA/traffic); only the viewer egress adapts.

Wrap-Up

The trade-offs that define this design:

  • Targeted push over polling or broadcast. Positions reach viewers through a trip_id-keyed pub/sub whose fan-out degree is bounded by viewers-per-trip (a handful), so total egress is inbound-times-a-small-constant - the opposite of a broadcast feed, and the reason 7.5M viewers is tractable.
  • Cheap/expensive ETA split over per-ping routing. Most pings just advance along a cached route (arithmetic); periodic refreshes re-sum edge weights (microseconds); full contraction-hierarchy searches happen only on deviation - keeping millions of ETAs traffic-fresh without a datacenter of routing CPU.
  • Static topology preprocessed, dynamic weights streamed. Contraction hierarchies exploit that roads do not move; the live speed layer changes only the weights, and an edge -> trips reverse index wakes exactly the trips a new jam affects.
  • Server cleans, client smooths. Map-matching and outlier rejection happen server-side (needs the road graph); motion interpolation happens client-side along sent road geometry (needs no extra ping rate) - smoothness for free without inflating the ingest firehose.
  • Everything ephemeral and eventually consistent. No money, no assignment, so no strong consistency anywhere - live state is in-memory and rebuildable, only the final route is archived once, and freshness beats agreement throughout.

One-line summary: a live-tracking-and-ETA system where each driver’s map-matched GPS ping flows through a trip_id-keyed pub/sub to the small fixed set of viewers watching that trip in under a second, while the ETA is kept traffic-fresh by advancing along a cached contraction-hierarchy route on most pings, re-summing live edge weights periodically, and re-routing only on deviation - all in-memory, best-effort, and rebuildable from a minute of the location stream.