Marketplace, Dispatch, and Logistics System Design Questions

Map tiles, the road graph, and live traffic feed each serve distinct roles in ETA computation. Below I describe role, typical update cadence, approximate footprint, and how often an ETA call consults each in a high-throughput system.

Map tiles

• Role: Visual/semantic rendering (map imagery, POIs, tile indexes) and quick client-side geography; not used directly for routing decisions except for display and heuristics (e.g., zoom/context).
• Update frequency: days–weeks (styling or imagery), incremental changes more rarely.
• Footprint: Large (GBs–TBs globally), delivered via CDN in small tiles (e.g., 256px PNG/MB vector tiles ~10s KB each).
• Query frequency per ETA: rarely; typically none on backend routing per request. Frontend fetches tiles as user navigates, not per-ETA.

Road graph

• Role: Canonical routing model: nodes, edges, turn restrictions, speeds, link lengths used to compute shortest-paths and base travel time.
• Update frequency: minutes–hours for fresh edits (crashes/corrections slower); major topology updates daily.
• Footprint: Moderate (tens–hundreds GB for large regions), sharded/indexed.
• Query frequency per ETA: consulted on every ETA — route search or heuristic lookup. In high-throughput systems use in-memory/partitioned graph or precomputed route caches so each ETA triggers a few reads (edge weights along candidate subgraph), often O(path length) accesses.

Live traffic feed

• Role: Provides time-varying speed multipliers or incident data to adjust base edge travel times to current conditions.
• Update frequency: seconds–minutes (real-time telemetry).
• Footprint: Small (streaming deltas, MBs/min), but can be large aggregated.
• Query frequency per ETA: consulted on every ETA; the system applies most-recent feed when scoring candidate routes. Implemented as a fast in-memory cache or time-series lookup (per-edge or per-tile), so each ETA reads only impacted edges (often a few KB of state).

Design notes: to scale, keep map tiles on CDN, road graph in memory/partitioned with precomputed indexes, and traffic in low-latency caches; combine via layered weights so ETA uses static graph + latest traffic multipliers, minimizing per-request IO.

Requirements & goals:

• Maintain ETA accuracy, reliability, and unbiasedness in production; detect regressions fast with low false alarms and actionable alerts.

Metrics to track:

• Point accuracy: MAE (minutes), Median Absolute Error — MAE captures average error; median is robust to outliers.
• Squared error: RMSE to penalize large misses.
• Bias: Mean Error (predicted − actual) to detect systematic early/late predictions.
• Tail / user-impact: Proportion of trips > 5/10/15 minutes late (P>5, P>10, P>15).
• Calibration & uncertainty: Calibration curve, Expected Calibration Error (ECE) for probabilistic estimates; coverage of predicted intervals (e.g., 80% CI).
• Timeliness & availability: % of requests with an ETA returned within latency budget; model inference latency p95.
• Data/feature health: population drift (KL-divergence), missing-field rate, distribution shifts.

SLOs / SLAs (examples, tune to business):

• MAE SLO: MAE <= 2.0 minutes (30-day rolling) for primary city.
• Tail SLOs: P>10min <= 5% (7-day rolling).
• Calibration SLO: interval coverage within ±3 percentage points of nominal.
• Availability SLO: 99.9% successful ETA responses under latency threshold (200ms p95).
• Error budget: allow temporary breach with incident process.

Alerting thresholds & logic:

• Multi-tier alerts:
  • Info (non-urgent): relative change > 10% vs baseline for MAE/Median over 24h.
  • Warning: absolute breach of SLO (e.g., MAE > 2.2) sustained > 6 hours OR tail metric increase > 20% relative AND p-value < 0.01 (stat test).
  • Critical: MAE > 3.0 or P>15min > 2% for >1 hour, or service availability below SLO.
• Use statistical tests (CUSUM or EWMA) for drift detection to avoid noise; require both relative change and statistical significance.
• Alert on feature drift (KL > threshold) or schema/missingness spikes.
• Tie alerts to runbooks: suggested remediation (rollback, revert features, increase sampling, retrain).

Offline tests (detect regressions before deploy):

• Holdout backtests with time-based splits simulating production window; compare MAE/RMSE/bias to champion.
• Cross-validation focusing on recent data and edge segments (rush-hour, weather).
• Champion–challenger A/B with shadow predictions on real traffic; compute uplift/loss by segment.
• Permutation tests and bootstrap to assess statistical significance of metric differences.
• Feature-corruption tests (simulate missing/shifted features).
• Stress tests on latency and batch throughput.

Online tests & monitoring (detect regressions quickly):

• Canary rollout with real-time metric comparison (canary vs baseline) and automated rollback if thresholds exceeded.
• Shadow mode: run new model in parallel for X% of traffic; compute online MAE and tail metrics without affecting users.
• Real-time drift detectors for inputs and predictions (EWMA/CUSUM) and calibration monitors.
• Fast-sampling telemetry: sample recent trips (e.g., last 10k) and compute rolling metrics at 5–15 minute cadence.
• User-impact monitoring: correlate ETA errors with downstream KPIs (cancellations, complaints, driver reassignments).

Instrumentation & tooling:

• Dashboards for rolling windows (1h, 24h, 7d, 30d), segmentation (city, hour, device), and alerts integrated in PagerDuty/Slack.
• Store prediction + actual + features for sampled requests (observability store) for quick root cause and retraining.
• Automated retrain pipelines with canary evaluation and gated promotion.

This plan balances accuracy (MAE/median), user impact (tail metrics), confidence (calibration), and operational reliability (latency/availability), with statistical alerting and both offline and online safety nets to catch regressions early.

Start with goals: protect individual drivers’ exact trajectories while preserving ETA model utility (accuracy, latency). Key techniques:

• Differential privacy (DP): add calibrated noise to location updates or aggregated counts. Central DP: noise applied at server during aggregation; Local DP: noise applied on-device before upload (stronger privacy, higher utility loss). Choose epsilon based on risk tolerance; use advanced composition and privacy budgets across time to limit cumulative leakage. For ETA, apply DP to aggregated route statistics or travel-time histograms rather than raw points to retain usefulness.

• k-anonymity (spatial): publish location only if ≥k drivers share the same coarse cell/time window. Simple and intuitive but vulnerable to background knowledge and spatio-temporal linking; not provably robust.

• Geo-hashing / lowering resolution: reduce precision (e.g., from meters to 100–500m tiles) or round coordinates to grid centroids. Lowers re-identification risk with predictable impact on ETA — tune tile size by measuring ETA degradation on validation data.

• Local aggregation / edge processing: compute per-device summaries (e.g., segment travel times) locally and only transmit aggregates. Combine with secure aggregation protocols so server sees only sums or averages, preventing inspection of individual traces.

• Complementary measures: temporal subsampling, adding lull/noise to timestamps, delaying reports, using pseudonym rotation, and synthetic data generation for offline model training.

Trade-offs:

• Privacy vs utility: stronger privacy (smaller epsilon, larger tiles, more noise) degrades ETA accuracy and increases calibration/bias. Local DP and frequent pseudonym changes reduce linkage but harm fine-grained personalization.
• Latency vs privacy: batching/delays improve privacy but reduce real-time responsiveness.
• Complexity vs deployability: secure multiparty or homomorphic methods are privacy-strong but operationally heavy.

Regulatory considerations:

• Location data is personal under GDPR/UK-GDPR; require lawful basis (consent or legitimate interest), purpose limitation, minimization, DPIA for high-risk processing, and retention limits.
• CCPA/CPRA: provide opt-outs, data subject rights (access, deletion).
• Industry best practice: document privacy budget, provide transparency to users, enable opt-in/opt-out, maintain logs for audits, and consult legal/compliance when tuning privacy parameters.

Practical approach: run A/B tests measuring ETA degradation vs privacy settings; start with coarse geo-hashing + server-side DP on aggregated travel-time bins, use local aggregation where low latency isn’t critical, and iterate with monitoring, DPIA, and user controls.

High-level difference:

• Map tiles are spatially keyed, relatively static binary artefacts (images/vector tiles) that change when base map edits occur. They’re read-heavy and cacheable long-term.
• Route/ETA results are computed, context-dependent (origin, destination, time, vehicle profile, live traffic) and much more volatile.

Invalidation strategies:

• Map tiles:
  • Versioned tiles: include map-tile version or timestamp in cache key; on data change increment version for affected tile ranges.
  • Granular invalidation: track changed geometries → compute tile covering set and purge only those tiles.
  • TTL: long TTLs (hours–days) with background revalidation.
• Route/ETA:
  • Short TTLs tied to traffic update cadence (seconds–minutes).
  • Event-driven invalidation: when traffic incident or road closure arrives, invalidate route cache entries that include impacted edges using a reverse index (edge → cached routes).
  • Staleness scoring: return cached ETA with confidence + fast recompute when confidence low.

Memory/storage trade-offs:

• Tiles: large storage footprint but highly reusable. Use compressed binary stores (CDN/edge) and hierarchical storage (SSD for hot, S3 for cold). Precompute popular zooms/areas.
• Routes/ETAs: smaller per-entry size but enormous combinatorial space (origin/dest/time/profile). Cache only popular origin-destination pairs, intermediate legs, or graph heuristics (cached shortest-path segments). Prefer computed-on-demand with short cache lifetime.

Edge vs regional orchestration:

• Edge (CDN/POP): serve tiles for low latency and offload origin. Push popular tiles; use long TTLs and versioned keys to avoid mass purges. For ETA, edge can serve very short-lived cached responses for repeat queries in the same POP, but coordination is limited.
• Regional caches (near compute region): hold warm route computation results, precomputed routing graphs, traffic snapshots. Use them as authoritative short-term caches and for invalidation coordination: when a traffic event occurs, regional controller invalidates regional entries and sends targeted purge to edges for affected POPs.
• Cost/latency balance: prefer long-lived tiles at edges; keep routing computation and sensitive caches regional to reduce cross-region invalidations and recompute cost. Use metrics-driven caching (hit rate, recompute cost) to adjust TTLs and prefetching.

Requirements & constraints:

• Provide ETA for routes and pickups with high availability (99.9%); graceful degradation when mapping/traffic upstream or internal components fail; expose confidence; support regional outages; bounded staleness.

High-level architecture:

• Core ETA service receives origin/dest, route polyline, optional traffic delta from upstream. Components: Ingest (upstream adapters), ETA Engine (model + heuristics), State Store (replicated), Cache (read-through), API Gateway.

Fallback algorithms (priority order):

1. Live model: ML + real-time traffic (when upstream ok).
2. Recent-snapshot model: last successful traffic-enriched model + recent deltas (if partial upstream).
3. Historical averages: time-of-day / day-of-week travel-time profiles per road segment aggregated over weeks.
4. Topology heuristics: free-flow speed estimates from speed limits and road class.
5. Conservative upper-bound: add safety margin (e.g., +20–30%) to ensure reliability.

State replication & data resilience:

• Use strongly-consistent writes for critical metadata (leader-follower with quorum, e.g., Raft) and eventual for analytics (Kafka-backed event store). Keep hourly snapshots of aggregated historical stats in S3 and a hot HBase/Bigtable region-replicated store for low-latency reads. Cache warmers maintain per-region recent snapshots in Redis cluster with cross-AZ replication.

Degraded-mode API & confidence:

• API returns: eta_ms, confidence_score (0–1), mode (LIVE, SNAPSHOT, HISTORICAL, HEURISTIC), data_age_ms, warning_code. Clients can choose to display conservative ETAs or show “approximate” badges when confidence < threshold.

Operational runbooks (detect & recover):

• Detection:
  • Built-in health endpoints, synthetic transactions simulating route requests, alert on increased error rate, latency, or fallbacks ratio > X%.
  • Monitor upstream adapter failures, Kafka consumer lag, and replication lag metrics.
• Recovery:
  • If upstream traffic fails: switch adapter to snapshot mode; increase safety margin; notify downstream with degraded mode flag.
  • If ETA engine instance fails: auto-scale replacement; redirect traffic using load balancer; restore from warm snapshot.
  • If state store partitioned: read-only fallback to cached snapshots; isolate region and failover quorum.
• Postmortem checklist:
  • Capture timeline, root cause, fallback used, customer impact, restore steps.
  • Update historical aggregation retention or warmers if gap caused by missing telemetry.
  • Run smoke tests and synthetic checks before returning to LIVE.

Trade-offs & testing:

• Trade-off: stronger consistency increases latency; prefer quorum for critical metadata but eventual for analytics.
• Test with chaos engineering (kill upstream adapters, inject latency), regular disaster drills, and SLA-driven SLO dashboards.

This design prioritizes transparency (confidence/mode), predictable graceful degradation, and operational playbooks to keep the ETA service useful even under partial failures.