Design a ride-hailing matching system similar to a taxi or rideshare application (e.g. Uber, Lyft, DiDi). The interview focuses on the **driver-location pipeline** and **nearby-driver lookup**: how high-frequency GPS updates from drivers are ingested, cleaned, and absorbed without overwhelming downstream services, and how a rider's pickup request is matched to nearby available drivers with low latency. Your design should cover requirements, the public API, data storage, the geospatial index, scaling, reliability, and the key trade-offs. At minimum, address each of the six areas below. They build on one another. 1. **High-frequency GPS ingestion** — drivers continuously upload GPS coordinates. How do you accept this write volume? 2. **Deduplication** — drop noisy / redundant / out-of-order GPS updates. 3. **Burst absorption** — smooth traffic spikes and protect downstream services from write bursts. 4. **Nearby-driver lookup** — a rider requests a ride; efficiently find nearby *available* drivers and match. 5. **Geospatial indexing trade-offs** — compare approaches such as **Quadtree** vs **H3** (hexagonal hierarchical grid). 6. **In-memory geospatial cache** — explain how **Redis GEO** (or a similar in-memory geo store) fits in. ```hint Where to start — the central insight The write path (driver GPS) and the read path (rider lookup) have completely different characteristics: writes are huge-volume and lossy-tolerant; reads are latency-sensitive and must be correct. **Decouple them.** Don't write every GPS point to your matching store synchronously. ``` ```hint Ingestion & burst absorption Where should a sudden burst of writes pile up — in your matching store, or somewhere cheaper that the read path never touches? Think about what sits *between* the accept-fast ingestion API and whatever updates the index, what property keeps one driver's updates in order, and how that buffer behaves when the index consumers fall behind. ``` ```hint Deduplication signals What distinguishes an update worth keeping from one you can safely throw away? Reason along a few independent axes — identity (is this literally the same point?), magnitude of movement, ordering relative to what you've already accepted, and physical plausibility — and ask what cheap, client-supplied token would let you make the ordering call as a single comparison. ``` ```hint Nearby-driver lookup — what the index holds and how you query it Should the hot lookup index hold *every* driver, or a filtered subset — and keyed by what? When your first search comes back with too few candidates, what's your move? And before you trust a driver the index returned, what properties should you re-check, and on what signal would you order the survivors? ``` ```hint Quadtree vs H3 Contrast on: adaptivity to density, stable global cell IDs, ease of distributed sharding, neighbor/ring expansion, and boundary handling. A Quadtree adapts to density but is a custom structure that's awkward to shard; H3 gives stable hexagonal cell IDs that shard and expand by ring trivially but is a fixed-resolution approximation needing post-filtering. ``` ```hint Redis GEO & double-assignment What is the minimal set of operations your hot index has to support as drivers move and go on/offline, and does your chosen in-memory geo store expose them directly? Separately, notice that two riders can race for the *same* driver: name where that race lives and what kind of atomic claim (think state machine + a single-winner transition) prevents both offers from landing. ``` ### Constraints & Assumptions You are not given exact production numbers, so state your own and design to them. Reasonable assumptions for a single large metro: - **Drivers:** ~100K online drivers in a busy city; each available driver emits a GPS update every ~1–4 seconds → on the order of $10^4$–$10^5$ location writes/second per city. - **Riders:** thousands of ride requests per minute at peak; each request needs a nearby-driver lookup. - **Latency:** nearby-driver lookup should return within a few hundred milliseconds (p99). - **Freshness:** matching should only consider driver locations seen in roughly the last 5–15 seconds. - **Scope:** focus on online matching (ingestion → index → match). Pricing, navigation/routing, payments, and the rider/driver mobile UX are out of scope except where they constrain the design. - **Geography:** the system is partitioned by city/region; the vast majority of requests are served by drivers in the same metro. ### Clarifying Questions to Ask - What scale are we targeting — one metro, one country, or global? What's the peak QPS for GPS writes and for ride requests? - How fresh must driver locations be for matching, and what p99 latency is acceptable for the lookup? - Do we need to persist the full historical GPS trail (for ETA models, fraud, replay), or only the current location? - Is matching one-to-one (offer to a single best driver) or broadcast (offer to several, first-accept wins)? - Are there vehicle types / pooling / driver-preference constraints that filter the candidate set? - What are the consistency requirements — can the location cache be eventually consistent if trip assignment is strongly controlled? ### What a Strong Answer Covers - **Read/write separation:** explicit recognition that GPS ingestion and matching are different workloads and a clean decoupling between them (queue/log in the middle). - **Back-of-envelope estimation:** a defensible write-QPS and storage estimate that justifies the architecture, not a generic component diagram. - **Ingestion correctness:** concrete validation, dedup, throttle/coalesce, and out-of-order handling rules — not just "we deduplicate." - **Geospatial index reasoning:** a real comparison (Quadtree vs H3 vs geohash vs Redis GEO) with a *recommendation tied to the requirements*, plus how boundary/cross-cell cases are handled. - **Matching path:** radius expansion, candidate filtering, ranking signals, and **preventing double-assignment** (state machine + reservation/lock). - **Scaling:** geographic partitioning (city → cell/shard) and how cross-boundary requests are served. - **Reliability & freshness:** cache rebuild from the log, staleness eviction, degradation under failure. - **Observability:** the metrics that tell you the system is healthy (write QPS, drop rate, consumer lag, lookup latency, match/acceptance rate, stale-record %). ### Follow-up Questions - A driver sits exactly on a cell/shard boundary, or a rider requests pickup there. How do you guarantee they aren't missed? - The location-index cluster for one city loses a node (or the whole Redis instance is cold-restarted). How do you rebuild the index and what's the user-visible impact? - How would you extend this to support surge pricing or ETA-based ranking without slowing the lookup path? - Drivers report being shown ride offers they never received, or being offered to two riders at once. Where in the design does this break, and how do you fix it?