ETA Service

TL;DR

Separate the write-heavy location pipeline from the read-heavy ETA path. Keep static road topology in a preprocessed routing graph, apply live segment-speed overlays from a Kafka/Flink traffic pipeline, and run fast route queries in memory. Recalculate only after meaningful progress or route deviation, write the latest result to Redis, and push updates through a dedicated SSE service. Geographic tile sharding lets routing capacity and traffic fan-out scale with demand instead of loading the whole world on every server.

The design treats every ETA as an estimate with explicit freshness and accuracy targets. The main correctness boundaries are ordered driver pings, bounded-staleness traffic fallback, idempotent asynchronous updates, trip-scoped push authorization, and a graph build/customization process that can be rolled out without taking routing offline.

Scope and assumptions

• The service covers road routing for a pickup/origin and dropoff/destination, active-trip ETA refresh, live traffic overlays, route-deviation rerouting, and rider updates. Turn-by-turn navigation, multimodal routing, user-reported incidents, and historical analytics remain below the line.
• The scale figures are illustrative planning assumptions: 10M active rides, 100M ETA requests per minute, 10-second driver pings, a 200ms p99 initial-ETA target, 30-second traffic freshness, and 2-second rider-update propagation.
• Contraction Hierarchies (or a customization-compatible hierarchical routing variant) is a candidate for static topology acceleration. Actual latency, memory, and server counts require benchmarks on the chosen graph and traffic-customization method.
• ETA results are estimates, not guarantees. Static base speeds are the fallback when live data is missing or stale; accuracy targets should be measured against trip outcomes.
• Coordinates, driver identity, and trip authorization are sensitive. Authentication is shown at the API boundary; retention and privacy policy for raw location data must be defined by the deployment.

What is an ETA service?

An ETA service takes two coordinates (pickup and dropoff) and returns the time a driver will arrive. The apparent simplicity collapses fast: your road network graph has millions of edges, traffic conditions change every minute, and you need a fresh answer in under 200ms for every one of 100 million requests per minute.

This question brings graph algorithms, real-time stream processing, geospatial data structures, and push-notification design into one system.

Functional Requirements

Core Requirements

1. Given a pickup and dropoff location, return an estimated travel time.
2. ETA updates continuously as the driver moves (every 5-15 seconds).
3. Live traffic conditions and road closures are incorporated into the estimate.
4. ETA recalculates automatically when the driver deviates from the predicted route.

Below the Line

• Turn-by-turn navigation instructions.
• Multi-modal routing (transit, walking, cycling).
• Traffic incident reporting from user-submitted data.
• Historical ETA accuracy reports and analytics dashboards.

The hardest part in scope: Computing a route ETA on a real-world road network in under 200ms requires pre-processed hierarchical graph structures and real-time traffic overlays. The routing algorithm choice receives a dedicated deep dive.

Turn-by-turn navigation is below the line because it requires storing and serving a fully rendered instruction set per maneuver, which involves 10-50x more data than a single ETA number plus a separate rendering pipeline. A later extension would compute the full path during the routing step and serialize the maneuver sequence alongside the ETA result.

Multi-modal routing is below the line because each transport mode (bus, subway, walking) uses a different graph topology and scheduling model. Combining them requires a transit schedule database and a separate graph search pass.

Traffic incident reporting is below the line because it requires a moderation pipeline to reject false reports and a classification model to distinguish genuine accidents from normal congestion signals. It does not affect the core routing or push architecture in this design.

Historical ETA accuracy dashboards are below the line because they require a separate OLAP store and aggregation pipeline for post-trip analysis. They do not affect real-time latency or correctness.

Non-Functional Requirements

Core Requirements

• Latency target: Initial ETA returned in under 200ms p99. Live ETA updates reflected within 2 seconds of a driver location ping.
• Freshness target: Traffic conditions reflected within 30 seconds of a real-world change (an accident slowing a corridor, a road closure).
• Scale assumption: 10M concurrent active rides. 100M ETA requests per minute (roughly 1.67M per second).
• Availability target: 99.99% uptime. Availability over consistency. A 30-second stale ETA is acceptable; a 503 error is not.
• Accuracy target: Average ETA error within 10% of actual travel time at the 80th percentile.

The rates, timings, graph sizes, memory footprints, and accuracy figures below are illustrative targets or benchmark assumptions, not guarantees. Validate them with the selected road graph, hardware, traffic model, client mix, and regional workload.

Under 200ms latency for route computation means we cannot run a naive Dijkstra search on a full city-scale road network at request time. New York's road network has roughly 370,000 nodes and 950,000 edges, and full Dijkstra with no preprocessing takes 100-500ms on that graph. Pre-processing is mandatory.

99.99% availability over consistency means the design tolerates slightly stale traffic data before accuracy degrades meaningfully. A driver going 5 mph instead of 10 mph on one segment changes that segment's contribution by 1-2 minutes on a 20-minute trip overall.

Below the Line

• Sub-second global traffic update propagation.
• ML-based historical pattern modeling (time-of-day, day-of-week speed adjustments).

Sub-second global propagation is deferred because the freshness target is 30 seconds, not 1 second. Achieving sub-second would require per-ping streaming writes with a very different Redis write pattern and a much tighter Flink window, significantly increasing infrastructure cost for marginal accuracy gain.

ML-based historical modeling is deferred because it requires an offline training pipeline and inference infrastructure. The static CH speed overlay already satisfies the 10% accuracy NFR without it.

Read/write ratio: For every 1 driver GPS ping written, expect 10-15 ETA reads (rider app updates, internal recalculation triggers, pricing engine queries). The location ingestion layer is write-heavy at millions of pings per second. The ETA query layer is read-heavy. These two paths need independent scaling or the write pipeline saturates the routing nodes.

State this separation early: the write-heavy ingest path and read-heavy query path have different bottlenecks and must scale independently.

30-second answer / outline

“I would keep the static road graph and dynamic traffic data on separate paths. A preprocessed hierarchical routing graph answers origin-to-destination queries in memory; GPS pings go through Kafka and a windowed processor that publishes smoothed segment speeds to a Redis overlay and routing-server fan-out. The location path emits a recalculation event only after meaningful movement, or a reroute event when the driver leaves the route. An ETA updater writes the latest result to Redis and a dedicated push service sends it over SSE. Geographic tiles, stale-data fallbacks, idempotent consumers, and graph hot-swaps handle scale and failure.”

5-minute explanation

1. Start with the two workloads: driver pings are high-volume writes; ETA requests and rider streams are latency-sensitive reads. Separate them before choosing storage or compute.
2. Compute the initial route: map coordinates to graph nodes, run the in-memory hierarchical routing engine, and return an ETA plus a route/trip identity.
3. Add live traffic: validate pings, publish them to Kafka, map-match them to road segments, aggregate speeds in a short window, and distribute the overlay without rewriting static topology on every ping.
4. Refresh only when needed: movement thresholds and route-adherence checks emit recalculation or reroute events. The updater recomputes against the current position and caches the result; riders read the cache or receive a push event.
5. Close on scale and correctness: shard routing by geographic tile, use static-speed fallback for missing traffic, reject out-of-order pings, make Kafka consumers idempotent, and monitor freshness, p99 latency, route accuracy, and push lag.

45-minute interview approach

This is an interview plan for the design question, not a claim that the article should take 45 minutes to read.

• 0-5 minutes — Clarify scope: confirm road-only routing, trip lifecycle, route output versus navigation instructions, update cadence, supported geography, and accuracy/freshness expectations.
• 5-10 minutes — Requirements and capacity: state the illustrative active-trip, ping, request-rate, latency, availability, freshness, and accuracy assumptions. Separate stale-but-usable responses from hard failures.
• 10-17 minutes — APIs and entities: sketch initial ETA, current ETA, driver location, and SSE endpoints; identify Route, RoadSegment, DriverLocation, ETAResult, and TrafficSnapshot.
• 17-25 minutes — Baseline routing path: draw coordinate snapping, routing service, graph store, and result cache. Quantify why full-graph Dijkstra is not sufficient and evolve to a preprocessed hierarchy.
• 25-33 minutes — Traffic and update flows: walk ping ingestion, map matching, windowed aggregation, speed overlay distribution, meaningful-movement recalculation, and route-deviation rerouting.
• 33-40 minutes — Deep dives: compare Dijkstra, A*, and CH/customization; discuss tile sharding, Kafka partitioning, Redis fallback, SSE connection ownership, and cross-region routing.
• 40-45 minutes — Reliability, security, and follow-ups: cover out-of-order/duplicate pings, graph rollout, stale traffic, backpressure, trip-scoped authorization, location retention, monitoring, and what changes for multimodal or long-haul routing.

Core Entities

• Route: A computed path between two geographic coordinates, represented as an ordered list of road segment IDs with total distance and initial ETA.
• RoadSegment: An edge in the road network graph. Stores static geometry (start node, end node, distance in meters) plus a dynamic field for current travel speed updated from the traffic ingestion pipeline.
• DriverLocation: Real-time position snapshot (driver_id, latitude, longitude, speed, heading, timestamp). Written every 5-15 seconds per active driver.
• ETAResult: The current estimated arrival for a trip (trip_id, eta_seconds, route_id, computed_at). Cached and refreshed on each meaningful location update.
• TrafficSnapshot: Aggregated speed data per road segment, derived from GPS probe vehicles and third-party data feeds. Applied as an overlay on RoadSegment edge weights.

Detailed schema (indexes, partition keys, and denormalization decisions) is defined in the deep dives. The entities above are enough to reason about the API and data flow.

API Design

Start with one endpoint per core functional requirement.

FR 1 - Compute an initial ETA:

POST /eta
Body: { origin: { lat, lng }, destination: { lat, lng } }
Response: { eta_seconds: 1140, route_id: "rt_abc123", estimated_arrival_at: "2026-04-02T10:23:00Z" }

POST because we are computing a new resource (a route), not fetching a pre-existing one. The route_id in the response lets the client subscribe to updates without re-sending coordinates on every subsequent call.

FR 2 - Get current ETA for an active trip:

GET /trips/{trip_id}/eta
Response: { eta_seconds: 840, driver_location: { lat: 37.78, lng: -122.41 }, updated_at: "2026-04-02T10:14:30Z" }

The rider app calls this on each polling cycle. The updated_at field lets the client detect stale responses if the driver location pipeline falls behind.

FR 3 - Driver pushes a location update:

POST /drivers/{driver_id}/location
Body: { lat, lng, speed, heading, timestamp }
Response: 204 No Content

Every ping triggers ETA recomputation if the driver has progressed significantly (more than 100 meters or 30 seconds since the last trigger). We detail the threshold logic in the deep dives.

FR 4 - Subscribe to live ETA updates via SSE:

GET /trips/{trip_id}/eta/stream
Response: text/event-stream
  data: { eta_seconds: 820, updated_at: "..." }
  data: { eta_seconds: 790, updated_at: "..." }

The rider app opens this persistent connection once. The server pushes each new ETAResult over the stream as the driver moves. We detail the push mechanism in Deep Dive 3.

High-Level Design

1. Return an ETA given a pickup and dropoff location

The core path: the client submits two coordinates, the ETA Service computes a route on the road network, and returns a travel time estimate.

Components:

• Client: Rider or driver app sending POST /eta with origin and destination.
• ETA Service: Receives the request, finds the nearest road network nodes to the coordinates, calls the Routing Engine, and returns the result.
• Routing Engine: Runs the graph search algorithm against the road network. Treat it as a black box in this flow; the algorithm choice is detailed in Deep Dive 1.
• Road Network DB: Stores the graph (nodes are intersections, edges are road segments with distance and speed). Read-heavy, infrequently updated.

Request walkthrough:

1. Client sends POST /eta with origin and destination coordinates.
2. ETA Service finds the nearest graph nodes to both coordinates using a geospatial index.
3. ETA Service calls Routing Engine with the source node and destination node.
4. Routing Engine runs the shortest-path algorithm and returns an ordered list of segment IDs plus total travel time.
5. ETA Service caches the result keyed by trip_id.
6. ETA Service returns eta_seconds and route_id to the client.

This diagram shows the initial ETA computation only. The traffic ingestion pipeline and real-time update loop come in the next two requirements.

2. Incorporate live traffic conditions

A static road network gives wrong answers fast. A corridor that normally flows at 35 mph drops to 5 mph during an accident. Without live traffic, an ETA on that corridor can be wrong by 6-7x until the jam clears. For example, a static graph could return an 8-minute ETA while the rider experiences 40 minutes in gridlock.

The fix is a Traffic Ingestion Pipeline that continuously collects GPS speed data from driver probe vehicles, aggregates it per road segment, and updates edge weights in the Road Network DB. Every driver in the fleet is already a traffic sensor.

Components added: