Ride-Hailing ETA & Routing System Architecture Questions
System design and architecture questions modeled on large-scale ride-hailing and on-demand mobility platforms: how a production-grade ETA (estimated time of arrival) and routing system is built and scaled. Covers real-time driver and GPS telemetry ingestion, map-matching (point-to-segment snapping, Hidden Markov Model approaches), road-graph representation and geospatial indexing (H3, S2, quadtrees), routing algorithms (Dijkstra, A*, contraction hierarchies) versus ETA prediction models, live traffic-data integration, caching and API contract design, multi-region and geo-distributed deployment, fault tolerance, and data consistency trade-offs at rideshare scale. Questions reason about the general system-design problem faced by this class of platform, not any single company's non-public internal implementation.
MediumSystem Design
85 practiced
Design a multi-region deployment for the ETA and routing platform to provide low-latency responses in Europe, North America, and Asia. Account for data sovereignty, geo-failover, configuration synchronization, and how to route client requests to the optimal region while preventing cross-region consistency issues.
Sample Answer
Requirements:- Low-latency ETA/routing in EU, NA, APAC (<100ms for regional clients)- Data sovereignty: certain PII/geofenced data must remain in-region- Geo-failover and high availability (RTO minutes, RPO seconds)- Configuration sync (routes, map tiles, model params) consistent across regions- Avoid cross-region consistency issues for operational data (rides, bookings)High-level architecture:User → Edge CDN + Regional API Gateway → Regional ETA/Routing Cluster (stateless services) + Regional Data Plane (stateful stores) → Async cross-region sync / control planeKey components and choices:1. Regional compute: Deploy identical microservices in three regions (EU, US, APAC) behind local API gateways. Services are stateless and autoscale.2. Edge routing: Use GeoDNS/Global Load Balancer (e.g., Route53/Traffic Director) with latency+geoproximity policy and health checks to route clients to nearest healthy region. Failover policy shifts traffic if regional health fails.3. Data plane: - Region-local authoritative stores for sensitive PII and transactional data (Postgres/CockroachDB with region-local writes or regional primary clusters). - Global read replicas for non-sensitive aggregated data (time-series metrics, maps). - Use per-region write ownership: each region is source-of-truth for entities originated there.4. Cross-region consistency: - Use asynchronous, idempotent event streams (Kafka/CDC) for eventual replication of non-sensitive data. Include versioning (logical timestamps) and conflict resolution rules (last-writer-wins for metrics; explicit merge for bookings via leader election). - For strong consistency where needed (e.g., unique booking IDs), use a coordination service: partition by customer region and route writes to that region; for cross-region operations use a distributed transaction only if unavoidable (but avoid for latency).5. Configuration sync & model deployment: - Central control plane (CI/CD) to push config and model artifacts to region-local S3/buckets. Use atomic rollouts with feature flags and Git-backed config; services watch config via versioned S3 + cache invalidation. For critical model parameters, use a signed version manifest and rolling activation.6. Data sovereignty: - Keep PII and compliance-bound data in-region; any cross-region replication anonymizes or strips PII. Provide audit logs and encryption keys per region (KMS with regional keys).7. Geo-failover: - Health probes at edge + regional health endpoints. On failover, Global LB shifts traffic; region receiving failover may handle increased load via autoscaling and cached read replicas. For ownership transfers, implement leader re-election for affected partitions and mark sources accordingly.8. Observability & testing: - Centralized telemetry aggregator with regional collectors (metrics, traces). Chaos testing for region failovers.Trade-offs:- Asynchronous replication favors availability and latency but provides eventual consistency; acceptability depends on business needs.- Strong global consistency increases latency; prefer partitioned ownership to maintain low latency.This design prioritizes regional low-latency, compliance, and resilient failover while limiting cross-region consistency by assigning clear ownership and using well-defined async replication and control-plane-driven config synchronization.
HardSystem Design
70 practiced
Architect an end-to-end ETA and routing platform for global scale: 100M daily users, 10B location updates/day, 99th percentile API latency <200ms. Outline key services, data flows, consistency assumptions, cross-region concerns, cost/latency trade-offs, and major failure modes you would mitigate.
Sample Answer
Requirements recap:- 100M DAU, 10B location updates/day (~115k updates/sec average, peaks higher), 99th %ile API latency <200ms globally, high availability and correctness of ETA/routing.High-level architecture (per-region active-active):- Edge API Gateway (global anycast + CDN) → Auth & Rate Limiting → Read path for ETA (fast) and Write path for location updates.- Streaming ingestion: Kafka/Cloud PubSub per region with geo-replicated topics for durability.- Real-time processing: Stateful stream-processing (Flink / Kafka Streams) that: - Ingests location updates, maintains in-memory actor/state per vehicle/user (Redis/Pulsar state-backed or RocksDB in Flink). - Runs routing/ETA microservices (fast heuristics + RB-tree graph snapshots).- Global routing data: Hierarchical tile graph store (vector tiles) stored in regionally-cached object store + precomputed multi-resolution routing graphs (graph partitions).- Routing engine: Hybrid approach: - Fast approximate ETA: contraction-hierarchy / landmark-based A* using cached partitions in-memory (serves most requests <50ms). - Accurate rerun: on-demand detailed shortest-path if needed (background/async).- Serving cache: Multi-layer LRU caches per region (in-memory, Redis cluster, edge CDN for static assets).- Database: OLTP for metadata (Cassandra / DynamoDB multi-region), long-term telemetry in data lake (S3/BigQuery).- Control plane: Model/store for traffic models (ML), push to streaming jobs.Data flows:1. Device → Edge → publish update to local Kafka.2. Stream job updates in-memory state & writes compacted state to Redis and async to DB.3. ETA request consults local cache/state + routing graph; if cache miss, compute using in-memory graph and return.4. Background pipelines aggregate telemetry to update traffic ML models and re-bake graph weights.Consistency & correctness:- Strong read-after-write for a single region via stateful stream processors and Redis (session affinity): a user's recent update must be visible locally immediately.- Cross-region eventual consistency for non-critical global aggregates. Use logical clocks and last-write-wins for vehicle position in multi-region conflict.- For routing deterministic correctness, use monotonic traffic weight updates: new weights applied epochally to avoid oscillation.Cross-region concerns:- Active-active regions with geo-routing via latency-based DNS/anycast; state sharding by home region + geo-replication for failover.- Minimize cross-region calls on critical path (keep state & graph local). Use async replication for durability.- GDPR/data locality: store PII per-region; replicate only pseudonymized telemetry.Cost vs latency trade-offs:- Cache more in-memory (higher cost) to meet 200ms 99th percentile. Use multi-tiered caching to reduce memory footprint.- Approximate routing reduces CPU cost but may decrease accuracy; serve “fast approximate + async accurate” for heavy load.- Batch ML updates to save compute; more frequent updates improve ETA accuracy at higher cost.Capacity planning:- Provision Kafka partitions and Flink task slots for peak QPS (use 2-3x headroom), autoscale hot partitions, use backpressure and sampling when overloaded.- Target 200k writes/sec ingestion capacity, scale Redis clusters horizontally with sharding.Failure modes & mitigations:- Burst overload: circuit breakers, graceful degradation (serve cached/approximate ETAs), sampled telemetry.- Regional outage: failover routing, promote replica region state (async RTO <2 min), drain and replay Kafka logs.- State loss: durable checkpoints for stream processors, write-ahead to object store.- Inconsistent graph weights causing bad routes: versioned graph rollout with canary traffic and rollback.- Network partition: prefer local reads; use conflict resolution strategies; avoid blocking global consensus on request path.- Cold cache storm: pre-warm caches for hotspots; use probabilistic prefetch and bloom filters to avoid thundering herd.Operational concerns:- Heavy observability: real-time SLO dashboards, per-region p99 latency alarms, tracing, canary deployments for graph/ML changes.- Cost controls: tiered storage, spot instances for non-critical batch jobs, autoscaling policies.This design prioritizes low-latency local reads, resilient ingestion, and staged routing fidelity so the platform meets p99 <200ms while maintaining global scale and operational safety.
EasySystem Design
91 practiced
As a Solutions Architect designing Lyft's ETA service, list and describe the core components required for a production ETA platform (for example: location ingestion, map-matching, routing engine, ETA estimator, caching layer, API gateway, monitoring). Assume SLA targets of 99% ETA requests <100ms and peak load of 100k req/s. For each component, explain responsibilities, statefulness, and how they interact end-to-end.
Sample Answer
Requirements brief: handle 100k ETA requests/s, 99% <100ms latency. Core components (responsibilities, statefulness, interaction):1) Location Ingestion- Responsibility: receive device GPS/heartbeat streams, validate, enrich (timestamp, accuracy).- Stateful: short-lived buffers for ordering; otherwise stateless.- Interaction: pushes cleaned location events to streaming bus (Kafka) and to short-term cache.2) Map-Matching- Responsibility: snap raw GPS to road-segments/links and infer heading/speed.- Stateful: small per-vehicle sliding window to smooth; mostly stateless compute.- Interaction: subscribes to ingestion stream, emits matched positions to routing/estimator topics.3) Routing Engine- Responsibility: compute route geometry and base travel-time estimates using road graph and live traffic.- Stateful: read-only graph + caches for popular routes/tiles; no per-request state.- Interaction: on ETA request, returns route and segment IDs + baseline travel times to ETA Estimator.4) ETA Estimator (core ML/hybrid)- Responsibility: predict per-segment travel times and aggregate into ETA; incorporate historical models + live probe data + incidents.- Stateful: maintains models and recent per-segment statistics (in-memory feature store).- Interaction: queries routing engine for segments, reads cached per-segment features, returns ETA.5) Caching Layer / Edge Lookup- Responsibility: extremely low-latency store for hot ETAs (e.g., popular origin-destination tiles), segment travel-times.- Stateful: strongly-consistent or eventually-consistent in-memory caches (Redis, Aerospike) with TTL and invalidation hooks.- Interaction: API gateway checks cache first; estimator updates cache on recompute or TTL expiry.6) API Gateway / Front Door- Responsibility: accept client ETA requests, auth/quotas, do cache fast-path, route to estimator, aggregate response.- Stateful: stateless (stores routing metadata like rate-limits in separate store).- Interaction: calls cache -> if miss, fan-out small parallel calls to routing engine + estimator, return response.7) Streaming & Message Bus- Responsibility: high-throughput transport for telemetry, traffic aggregation, model inputs; durable.- Stateful: persistent logs.- Interaction: connects ingestion -> map-matching -> feature pipeline -> estimator.8) Feature Store / Real-time Aggregator- Responsibility: compute per-segment aggregates (rolling medians, percentiles) from live probes.- Stateful: time-series store (in-memory + long-term), windowed aggregations.- Interaction: feeds estimator and cache; updated from stream.9) Monitoring, Alerting, Observability- Responsibility: latency SLOs, QPS, error rates, data freshness, model drift.- Stateful: metrics DB + traces.- Interaction: provides dashboards and automated alerts; triggers fallback behavior on degradation.10) Fallback & Degradation Manager- Responsibility: ensure SLA under load: serve cached or routing-based ETA if estimator overloaded.- Stateful: small policy store.- Interaction: sits in API path to choose graceful fallback.End-to-end flow: client -> API Gateway -> cache hit? return. Miss -> gateway requests route from Routing Engine, obtains matched positions (or uses last matched), calls ETA Estimator (reads features from feature store), writes result to cache, responds to client. Streaming components continually update map-matching, feature store, and models.Scalability & latency notes:- Push critical read-path components (cache, API gateway, estimator instances) to edge/regions.- Use sharding by geotile for caches, routing, feature store to keep working set local.- Optimize estimator for micro-batching and SIMD; use async fan-out and tail-latency protection (hedged reads).- SLO design: 99% <100ms requires cache + edge compute for >90% of requests; heavier compute paths limited and parallelized; autoscale with warm pools.
MediumSystem Design
87 practiced
Design the observability plan for ETA & routing systems: define key metrics (latency p50/p90/p99, ETA error distribution, cache hit ratio, model drift), logging strategy, dashboards, and alerting thresholds. Explain which signals are used for incident detection vs long-term model health monitoring.
Sample Answer
Requirements & constraints:- Real-time ETA & routing for users/drivers with SLA on latency (interactive UI <300–500ms), ETA accuracy goals (median error <15s, 90% <60s), and scalability (10k req/s).- Need both immediate incident detection and long-term model health.High-level plan:- Instrument at ingress, routing engine, model prediction, cache layer, and client SDKs. Use distributed tracing, structured logs, and time-series metrics pushed to Prometheus/metric store; store aggregated telemetry in data lake for drift analysis.Key metrics (per endpoint / region / model version / request type):- Latency: p50/p90/p99 end-to-end and per-stage (network, model inference, routing) — e.g., SLO: p90 < 400ms, p99 < 1.5s.- ETA error distribution: median error, MAE, RMSE, percent within 5/15/60s; bias (mean signed error).- Cache: hit ratio, stale-hit rate, TTL expiration rate.- Throughput & errors: requests/sec, success rate, 4xx/5xx.- Model health: PSI/Population Stability Index, KL divergence, feature drift per feature, prediction distribution changes, confidence/uncertainty stats.- Serving infra: CPU, memory, queue lengths, GC pause, thread pool saturation.Logging strategy:- Structured JSON logs with request_id, trace_id, user_id (hashed), model_version, route_id, timestamps for stages, input features summary (hash/quantiles, not PII), predicted ETA, actual arrival time.- Sample full-feature logs at 0.1–1% for privacy and volume; store aggregated features for drift analysis.- Correlate traces to metrics via trace_id; capture spans for network, model inference, DB/cache calls.Dashboards:- Incident ops dashboard: global p99 latency, error rate, requests/sec, cache hit ratio, top regions by latency, real-time tail latency heatmap, recent failed requests with traces.- ETA quality dashboard: rolling MAE/RMSE, bias, distribution histograms, % within thresholds, per-route/per-vehicle-type breakdown.- Model drift dashboard: PSI/KL per feature, alertable feature importance changes, model version comparison, retrain candidate list.- Capacity dashboard: CPU/memory, queue lengths, autoscaler activity.Alerting thresholds (examples; tune to baseline & SLOs):- Incident detection (pager): - p99 end-to-end latency > 2s for 5min OR p90 > 1s for 10min. - Error rate > 1% for 5min or sudden 3x spike vs 5-min baseline. - Cache hit ratio drops > 20% absolute vs baseline for 10min. - Serving queue length > threshold (approaching capacity) for 5min.- ETA regressions (page or page-to-oncall with lower urgency): - Median ETA error increases by >25% vs 24h baseline for 30min. - %within15s drops below target (e.g., <70%) for 30min.- Model drift / long-term (notify / SRE + ML owner): - PSI > 0.2 or KL divergence above threshold for key features over 24–72h window. - Significant change in feature importance or model confidence distribution. - Sustained bias (signed error) beyond acceptable bound for 24–72h.Signals: incident detection uses near-real-time operational signals (latency p99, error spikes, cache hit ratio, queue lengths) and rapid degradation of ETA accuracy (sharp drop in %within thresholds over minutes). Long-term model health uses aggregated statistical signals (PSI/KL over days, RMSE trends, bias drift, feature distribution shifts) and sampled detailed logs for root cause.Runbook actions:- For latency/errors: rollback config, scale instances, clear caches, increase timeouts, inspect traces.- For ETA regressions: switch to fallback model/version, increase sampling for logs, run compare job between versions.- For drift: trigger retrain pipeline, schedule human review, run offline A/B tests before promotion.SLOs & ownership:- Define SLOs (latency SLOs with error budget), assign alert ownership (SRE for infra incidents, ML engineer for model drift, product for ETA accuracy regressions). Periodically review thresholds using historical baseline and implement automated “burn-rate” alerting to protect error budget.
MediumTechnical
114 practiced
You want to validate ETA model improvements in production without impacting users. Propose an experiment plan: canary/A-B testing approach, metrics to measure (ETA error, cancellation, arrival variance), required sample sizes, and rollback criteria. Describe guardrails to prevent revenue or safety regressions.
Sample Answer
Plan overview: run a staged canary → A/B experiment that isolates ETA model changes behind a feature flag; start with a small canary, evaluate key signals (statistical + business), then ramp to full A/B if safe.Experiment design- Canary: 1% of live traffic for 24–48h (smoke test for data/latency edge cases).- A/B test: random assignment user-trip-level, 50/50 hold vs treatment for robust metrics; run until statistical power reached or max 2 weeks.- Progressive ramping: 1% → 5% → 25% → 50% with checks at each step; automated rollback on breaches.Metrics to measure (primary + secondary)- Primary: ETA error (e.g., MAE and RMSE between predicted and actual arrival time), and arrival-time variance (distribution of residuals).- Secondary (business/safety): trip cancellations, late arrivals (>X mins), customer complaints/NPS delta, driver reassignments, conversion/revenue per trip.- Observability signals: model inference latency, feature distribution drift, percent of trips with missing features, server errors.Statistical plan & sample size- Pre-specify alpha=0.05 (two-sided), power=0.8.- Use two-sample t-test on MAE (or bootstrap if non-normal). Sample size formula: n ≈ 2*(Z1-α/2 + Z1-β)^2 * σ^2 / Δ^2- Example: baseline MAE=120s, σ≈180s, target detectable improvement Δ=12s (10%): Zs sum ≈ (1.96+0.84)^2 ≈7.84 → n ≈ 7.84 * (180^2) / (12^2) ≈ 1,764 per arm → ~3.5k trips total. Inflate by 30% for filtering/segmentation → ~5k.- For rarer signals (cancellations), compute sample for proportion test or use aggregated safety window and longer run.Rollback criteria (hard & soft)- Hard automatic rollback (immediate): relative increase in cancellations or safety incidents > X% absolute (e.g., +0.5 pp) or >2× baseline SD within 24h; critical SLA breaches (e.g., latency > threshold).- Soft/manual rollback: statistically significant degradation in primary metric (p<0.05) and business impact threshold exceeded (e.g., >1% revenue loss over 48h).- Predefine monitoring windows (hourly for first 24h, daily thereafter).Guardrails to prevent revenue/safety regressions- Must-pass checks at each ramp: no increase in cancellations, no rise in late-arrival rate beyond pre-set bounds, and inference latency within SLO.- Use stratified analysis: examine impact across geography, time-of-day, trip length, device types to detect localized regressions.- Quarantine experiment traffic: cap daily % of revenue impacted and flag high-value segments to remain on control unless tested separately.- Fallback mechanism: real-time canary traffic switch + automated rollback orchestration (feature-flag with health-check rules).- Audit & logging: full request trace sampling, store predicted vs actual for offline replays, and implement alerting to ops/trust & safety teams.Reporting & governance- Pre-register hypothesis, metrics, sample-size, and rollback rules.- Run post-hoc analysis for heterogenous effects; if improved, run longer run to confirm and then plan rollout with monitoring.- Keep stakeholders (product, ops, legal) in loop; require safety sign-off before >50% roll.This plan balances statistical rigor, gradual exposure, and strict business/safety guardrails so model improvements are validated without harming users or revenue.
Unlock Full Question Bank
Get access to hundreds of Ride-Hailing ETA & Routing System Architecture interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.