System Design Problem

Design an ETA Calculation Service

21st April 20264.42748 views22 min read
archAllgeo-distributed
Commonly Asked By:UberLyftGoogleGrab

Interview Setup

Interview Prompt

Design an ETA calculation service for a ride-hailing or navigation app. Given origin, destination, and mode, return accurate travel time estimates that reflect live traffic. Support single ETAs, batch driver-to-pickup queries, and live updates during an active trip.

Clarifying Questions (ask before designing)

QuestionWhy it matters
What is the latency budget for a single ETA vs a batch of 20?A 100ms single and 500ms batch SLO drives caching and compute trade-offs because the engine cannot afford to run full routing 20 separate times.
How accurate must ETAs be in terms of deviation from actual travel time?A requirement within ±10% accuracy justifies an ML correction layer on top of the physics-based route engine.
Is this for matching (many drivers to one pickup) or passenger display?
  • Matching needs reverse Dijkstra and H3 ETA matrix at O(1)
  • display needs full route + traffic.
How fresh must traffic data be?60-second freshness requires Flink aggregation on 10M GPS points/sec, not hourly historical averages.

Scope

In scope

  • Point-to-point and batch ETA APIs
  • Live traffic ingestion and segment speed aggregation
  • Contraction hierarchies routing with traffic weights
  • ML correction from historical trip data
  • H3 ETA matrix for coarse matching
  • WebSocket ETA updates during active navigation

Out of scope (state explicitly)

  • Map tile rendering and client display (covered in Map Rendering and Navigation)
  • Driver dispatch and ride-matching orchestration (covered in Ride-Sharing Service)
  • Turn-by-turn voice guidance

Functional Requirements

Confirm routing engine capabilities and traffic telemetry sources. The service requires point-to-point estimation, real-time traffic integration, batch queries for driver dispatch, and graceful fallback when telemetry lags.

In the room: when live traffic is stale, ETAs silently degrade, so explain how monitoring Flink consumer lag alerts the team to stale data.

  • Point-to-point ETA: Estimate travel time with current traffic
  • Multi-stop ETA: Routes with multiple waypoints
  • ETA for pickup: How long until a driver reaches a pickup point
  • Historical ETA: "How long does this trip usually take on Tuesday at 8 AM?"
  • Batch ETA: Compute for N origin-destination pairs efficiently
  • ETA updates: Continuously update as trip progresses
  • Multi-modal: Driving, walking, cycling, transit

Non-Functional Requirements

ETA returned in under 500ms; traffic freshness under 60 seconds for ride-hail use cases.

  • Accuracy: ETA within ±10% of actual travel time
  • Low Latency: Single ETA in < 100 ms; batch of 20 in < 500 ms
  • High Throughput: 500K ETA requests/sec peak
  • Freshness: Traffic conditions reflected within 60 seconds
  • Availability: 99.99%
  • Graceful degradation: Fall back to historical patterns
  • Global: Support all major cities

Capacity Estimations

Routing requests per second and road segment count drive graph storage and traffic aggregation.

MetricCalculationValue
ETA requests / secFrom ETA requests / day ÷ 86400 (+ peak factor in value)500K peak
Single ETA latency targetGiven (assumption documented in value)< 100 ms
Batch ETA (20 pairs) targetGiven (assumption documented in value)< 500 ms
Active road segments trackedGiven (assumption documented in value)50M globally
Traffic updates / secFrom Traffic updates / day ÷ 86400 (+ peak factor in value)10M GPS data points
Road graph size (in-memory)Given~300 GB globally
ETA model featuresGiven~50 per query
ETA cache hit rateGiven~30%

Architecture Diagram

We combine a static road graph using Contraction Hierarchies with real-time segment speeds from GPS probes in Redis, apply traffic overlays to chosen routes, and return travel time estimates with confidence intervals. Batch matrix APIs answer multi-candidate queries in a single graph search, closely integrating with driver location streams from Real-Time Vehicle Tracking and tile vector geometries from Map Rendering & Navigation.

In the room: when Flink lag exceeds 60 seconds, ETAs drift silently, so emphasize alerting on traffic freshness SLO budget burn.

Loading...

Component Deep Dives

Three-Layer ETA Architecture

Accuracy comes from stacking three layers: a fast graph router, real-time segment speeds aggregated from millions of GPS probes, and a machine learning correction model trained on historical trip outcomes. Each layer addresses a distinct source of estimation error.

Traffic telemetry streams from vehicle probes into streaming aggregations that continuously update Redis speed hashes. When stream workers lag, a multi-tier fallback hierarchy protects latency budgets without crashing dependent services.

ETA Calculation Pipeline: Three-Layer Architecture

Layer 1: Route Engine ETA (physics-based)
  Find route via Contraction Hierarchies (< 1 ms)
  For each segment: time = distance / speed (min of speed_limit, traffic_speed)
  
Layer 2: Traffic-Adjusted ETA
  traffic_speed = Redis GET traffic:{segment_id} → current avg speed
  If no traffic data: use historical avg speed
  Add turn penalties (15-60s per major turn) and signal delays

Layer 3: ML Correction Model ⭐ (secret sauce)
  Gradient Boosted Trees (XGBoost/LightGBM)
  Features: route, traffic, temporal, weather, historical, spatial
  Output: correction_factor
  Final ETA = route_engine_ETA x correction_factor

Traffic Aggregation Pipeline

1. GPS Ingestion (10M points/sec) → Kafka
2. Map Matching (Flink): GPS point → road segment
3. Segment Speed Aggregation (Flink, 60-sec window):
   avg_speed = median(speeds), confidence = min(1.0, sample_count / 10)
4. Store in Redis: HSET traffic:{segment_id} speed {s} confidence {c}
   TTL: 120 seconds
5. Fallback hierarchy: real-time → recent → historical → speed_limit x 0.7

Batch ETA: Matching System Integration

Many-to-One Routing:
  Reverse Dijkstra from destination → find all 20 origins
  ~5 ms for 20 origins (vs 20 ms for separate queries)

ETA Matrix (pre-computed):
  H3 cells (resolution 9 ≈ 175m), pre-compute cell-to-cell ETAs within 30 km
  ~500M pairs x 4 bytes = 2 GB per city → O(1) lookup
  Accuracy ±2-3 min, good enough for initial matching

Refinement: After narrowing to top 3, compute exact ETA with full route + traffic

Event Bus Design (Kafka)

Topic: gps-traces
  Partitions: 256 (scale Flink map-matching parallelism)
  Partition key: vehicle_id (preserves per-vehicle GPS ordering for HMM map-matching)
  Retention: 24h (high-volume telemetry at 10M points/sec)
  Replication factor: 3, min.insync.replicas: 2

Producer: fleet GPS ingest (MQTT bridge, idempotent producer)
  Event: { event_id, vehicle_id, lat, lng, speed, heading, timestamp }

Consumer groups:
  1. traffic-aggregation: Flink map-match → 60s tumbling window median speed per segment
     → HSET traffic:{segment_id} {speed, confidence, updated_at} in Redis (TTL 120s)
  2. trip-completion: completed trip actual_duration → ClickHouse for ML retrain
  3. anomaly-detector: flag impossible speeds and GPS jumps for device health

Sync path (GET /eta): route engine + Redis traffic lookup + ML correction → return < 100ms
Async path: GPS never blocks ETA reads; Flink lag > 60s → degrade to historical speeds
DLQ: gps-traces-dlq after 3 retries; alert when consumer lag > 60s

API Design

ETA Estimation and Streaming APIs

The service exposes endpoints for single point-to-point estimates, batch driver-to-pickup queries, coarse hexagonal matrix lookups, and WebSocket connections for active trip updates.

Single ETA

HTTP
GET /api/v1/eta?origin_lat=37.7749&origin_lng=-122.4194&dest_lat=37.3382&dest_lng=-121.8863&mode=driving&departure_time=now
Response: 200 OK
{
  "eta_seconds": 1920,
  "eta_display": "32 min",
  "distance_meters": 72400,
  "confidence": 0.85,
  "traffic_level": "moderate",
  "breakdown": {
    "route_engine_eta": 1680,
    "traffic_adjustment": 180,
    "ml_correction": 60
  }
}

Batch ETA

HTTP
POST /api/v1/eta/batch
{
  "origins": [
    {"lat": 37.78, "lng": -122.41, "id": "driver-1"},
    {"lat": 37.77, "lng": -122.43, "id": "driver-2"}
  ],
  "destination": {"lat": 37.7749, "lng": -122.4194},
  "mode": "driving"
}
Response: 200 OK
{
  "etas": [
    {"id": "driver-1", "eta_seconds": 240, "distance_meters": 1200},
    {"id": "driver-2", "eta_seconds": 480, "distance_meters": 2100}
  ]
}

ETA Matrix

HTTP
GET /api/v1/eta/matrix?origin_h3=892830926cfffff&dest_h3=89283092e3fffff

Live ETA Update (WebSocket)

JSON
// Server pushes every 60 seconds:
{
  "type": "eta_update",
  "session_id": "nav-uuid",
  "remaining_eta_seconds": 1080,
  "remaining_distance_meters": 35200,
  "traffic_ahead": "moderate",
  "route_changed": false
}

Common Error Responses

400 Bad Request: invalid input, missing required fields, or malformed JSON payload
401 Unauthorized: missing or invalid authentication token or API key
403 Forbidden: authenticated caller lacks required permissions for this resource
404 Not Found: requested resource ID does not exist
409 Conflict: duplicate write or version conflict, retry with a unique idempotency key
422 Unprocessable Entity: syntactically valid request failed semantic business validation
429 Too Many Requests: rate limit quota exceeded, client should honor Retry-After header
500 Internal Error: unexpected server failure, retry safely with an idempotency key
503 Service Unavailable: downstream dependency is unavailable or overloaded, retry with exponential backoff
440 Login Timeout: WebSocket connection session expired, client reconnect is required

Data Model

Redis: Live Traffic + ETA Cache

traffic:{segment_id} → Hash { speed, confidence, updated_at } (TTL: 120s)
eta_matrix:{origin_h3}:{dest_h3} → INT (eta_seconds) (TTL: 300s)
eta_cache:{origin_geo6}:{dest_geo6}:{mode}:{hour} → INT (TTL: 300s)
hist_speed:{segment_id}:{dow}:{hour} → FLOAT (no TTL, updated weekly)

ClickHouse: Historical Trip Data

SQL
CREATE TABLE completed_trips (
    trip_id         UUID,
    origin_lat      Float64, origin_lng Float64,
    dest_lat        Float64, dest_lng Float64,
    origin_h3       UInt64, dest_h3 UInt64,
    distance_meters UInt32,
    predicted_eta   UInt32, actual_duration UInt32,
    departure_hour  UInt8, day_of_week UInt8,
    is_holiday      UInt8,
    weather         Enum8('clear'=0,'rain'=1,'snow'=2,'fog'=3),
    route_segments  Array(UInt64),
    mode            Enum8('driving'=0,'walking'=1,'cycling'=2),
    created_at      DateTime
) ENGINE = MergeTree()
PARTITION BY toYYYYMM(created_at)
ORDER BY (origin_h3, dest_h3, departure_hour, day_of_week);

ML Model Store

Model: gradient_boosted_trees_v23.pkl
  50M trips trained, 50 features, ~50 MB in memory
  Inference time: < 1 ms per prediction
  Retrained weekly, A/B tested before deployment

Fault Tolerance

ConcernSolution
Traffic service downFall back to historical speed patterns
ML model errorCircuit breaker: bypass ML if latency > 50ms or error > 5%
Route engine crash
  • Multiple replicas
  • fallback to pre-computed ETA matrix
Stale traffic data
  • TTL on Redis keys
  • use historical + confidence=LOW flag
GPS data pipeline lag
  • Flink checkpointing
  • if lag > 5 min, switch to historical
ETA cache thundering herdSingleflight: only compute once for concurrent identical requests

Additional Considerations

Interview Walkthrough

  • 25-minute cut

    Skip arch50 and arch75 depth unless interviewing for a staff-level role.

    • State latency budget: sub-100ms single ETA, sub-500ms batch matrix for driver matching (5 min)
    • Three-tier pipeline: Haversine filter, Contraction Hierarchies query, and traffic overlay from Redis (6 min)
    • Traffic ingestion: GPS probes into Flink aggregation with Redis traffic keys on 60 to 120s TTL (5 min)
    • Expose batch ETA API for matching N drivers to one pickup without N separate graph searches (5 min)
    • Staff only: live traffic staleness monitoring and client-side reroute on polyline deviation (4 min)
  • Open with the latency budget: sub-100 ms single ETA and sub-500 ms batch, meaning every design choice must strictly justify its place in that latency envelope.
  • Describe a three-tier pipeline: Haversine filter, Contraction Hierarchies road distance, and full routing with live traffic plus ML correction.
  • Explain the traffic ingestion path: GPS probes, Flink streaming aggregation, and Redis segment speeds with TTL-based staleness fallbacks.
  • Cover batch and matrix APIs for driver matching, including pre-computing H3-cell ETA matrices for hot corridors to avoid redundant routing computations.
  • Mention caching with singleflight to prevent thundering herd on identical origin-destination pairs during rush hour.
  • Discuss display smoothing and percentile ETAs (P50 for riders, P90 for delivery promises) to manage user trust when raw estimates jitter.
  • Common pitfall: computing full routing for every candidate driver in a pool of 50 without the Haversine or Contraction Hierarchies pre-filter causes latency to blow past the SLA.

Live ETA Updates: Smoothing

displayed_eta = 0.7 x previous + 0.3 x raw
Only show change when delta > 2 min or > 10%

Why: GPS jitter → ETA fluctuates ±1 min
Without smoothing: "17 min" → "18 min" → "17 min" → confusing

Time-Dependent Routing

Trip starts at 5:30 PM, arrives at 6:30 PM (rush gets worse)

For each segment: estimated_arrival = departure + sum(previous_times)
  traffic_speed = predicted_speed(segment_id, estimated_arrival)

predicted_speed: within 60 min → real-time + trend; 1-3h → blend 30/70; 3h+ → historical only

ETA Percentiles

Single ETA = 28 min doesn't capture uncertainty.
Better: "28 min (25-35 min range)"

Quantile regression: p10, p50, p90 models
  Rider display: P50 (median)
  Delivery promise: P90 (90% confidence)
  Matching: P50 for ranking, flag if P90 too high

Engineering Trade-offs

Filtering Hierarchy and Model Selection Trade-Offs

Balancing fast spatial heuristics, graph shortest-path searches, and statistical machine learning models allows the system to satisfy strict latency budgets while preserving high accuracy. Review caching trade-offs in Caching Patterns & Invalidation.

Haversine vs Road Distance vs Routing ETA

LevelMethodTimeAccuracyUse Case
1Haversine< 1 μs50-200% offInitial filter (5 km)
2Road Distance (CH)< 1 msDistance correct, time roughRank top 20
3Routing ETA + Traffic + ML10-50 ms±10%Final ETA to user

XGBoost vs Deep Learning for ETA

XGBoost ⭐:
  - Tabular features → GBT excels (often beats DL on structured data)
  - Inference < 1 ms (vs DL: 5-50 ms)
  - Interpretable feature importance
  - Trains in minutes on 50M samples

When DL wins: sequence modeling (LSTM on GPS trace), GNN for spatial dependencies
Google Maps: GBT for base ETA + GNN for spatial traffic prediction

💬Review

Help Us Improve

How helpful was this walkthrough?

Click a star to rate. We actively use this feedback to refine and update our system design content.

Placeholder
Optional but highly appreciated!

Discussion

Share your thoughts, ask questions, or help others.

Loading comments...