# Design a Ride-Sharing System (Uber-style Core Platform) Design the core backend of a ride-sharing platform like Uber. Riders open the app, see nearby drivers, request a ride; the system matches each rider to a nearby available driver, tracks the trip, and updates positions in real time. Your design should focus on the parts of the system that are hardest at scale: ingesting a firehose of driver location updates, matching riders to drivers using geospatial search, and keeping the matching consistent and available under failures. ### Constraints & Assumptions - Global service, on the order of **3M active drivers** and **15M daily riders**; assume a peak of roughly **1,000,000 driver location updates per second** during rush hour. - Active drivers send a location ping (driver id, lat, lng, timestamp, status) every **3–5 seconds** while online. - Rider-facing operations: "show nearby drivers" and "request ride" should feel instant — target **p99 < 200 ms** for the nearby-drivers query and **single-digit seconds** end-to-end to confirm a match. - A driver must never be concurrently assigned to two active trips; a rider must never be charged for or shown two simultaneous drivers. - The system should stay **available** (riders can still request, drivers can still update) under regional network partitions and partial datacenter loss. - Out of scope: pricing/surge details, payments, fraud, maps/routing internals — assume an external routing/ETA service exists. ### Clarifying Questions to Ask - What is the geographic granularity of "nearby" (radius in km, or top-N closest), and does it vary by city density? - Are location pings best-effort (lossy, latest-wins) or must every ping be durably stored for analytics/audit? - What is the acceptable staleness of a driver's displayed position (e.g., up to 5 s old)? - How strong must match consistency be — is a brief double-offer to a driver acceptable if only one can win, or must offers be globally exclusive? - What is the read/write ratio between location writes and nearby-driver reads, and how bursty is demand (events, weather)? - Single region first, or multi-region active-active from day one? ### Part 1 — Real-time driver location ingestion (~1M writes/sec) Design the path that ingests driver location pings at peak (~1,000,000/sec) and makes the freshest position queryable for matching. Cover the transport/protocol from device to backend, how you absorb and partition the write load, what you persist versus keep in memory, and how you bound staleness and storage growth. ```hint Where to start Separate the *hot* "latest known position per driver" (a small, constantly-overwritten key→value, latest-wins) from the *cold* historical trail (append-only stream for analytics). They have completely different storage characteristics. ``` ```hint Absorbing the firehose Put a partitioned log / message bus (e.g., Kafka) between edge gateways and the consumers, partitioned by driver id or geo-shard, so ingestion scales horizontally and decouples write spikes from downstream processing. The hot index can live in an in-memory store (Redis) keyed by driver id and by geo-cell. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 2 — Matching service & geospatial indexing Design the matching service: given a rider's pickup location, efficiently find candidate nearby available drivers and select one. Explain the geospatial indexing scheme that makes "find available drivers within radius R" fast at this scale, and how candidates are ranked and offered. ```hint Geospatial index Map 2D lat/lng to a 1D sortable key so points can be range-scanned and sharded: geohash, S2 cells, or Uber's H3 hexagonal grid. "Nearby" becomes "look up the rider's cell plus its neighboring cells." ``` ```hint Making it fast Maintain an in-memory index of cell → set of available drivers, updated from the location stream. Query only the relevant cells (and ring of neighbors) instead of scanning all drivers; widen the ring if too few candidates. ``` #### Clarifying Questions for this Part - Should matching optimize purely for proximity/ETA, or also driver acceptance rate, ratings, or fairness across drivers? - Is a dispatch offered to one driver at a time (sequential) or broadcast to several with first-accept-wins? #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 3 — High availability & partition tolerance Discuss how the system stays available and behaves sensibly under failures: lost datacenters, network partitions between regions, and degraded connectivity to a city. Address replication, failover, and graceful degradation. ```hint Frame with CAP, per data type Different data has different needs: location pings tolerate loss/staleness (favor availability), while trip/assignment state needs stronger guarantees. Decide A-vs-C *per subsystem* rather than globally. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 4 — Consistency of matching (no double-booking) Detail the consistency strategy that guarantees a single driver is assigned to exactly one rider at a time even when multiple riders request the same nearby driver concurrently, and even across regions or retries. ```hint The core primitive This is mutual exclusion on a driver. You need an atomic "claim driver D for ride R if and only if D is currently free" — e.g., a conditional/compare-and-set write, a distributed lock with a lease/TTL, or routing all assignments for a driver/region through a single serialized owner. ``` ```hint Avoiding stuck state A claim must expire: if the chosen driver never confirms (crash, no network), a lease/timeout releases the driver so they aren't locked out. Make the assignment idempotent so retries don't create duplicate trips. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - How would you handle a "thundering herd" of riders requesting at the end of a major event in one small area — what breaks first, and how do you shed load gracefully? - How do cell-boundary effects (a rider exactly between two cells, or drivers clustered at a cell edge) distort matching, and how do you correct for them? - Extend the design to **multi-region active-active**: how do you keep a driver who crosses a region boundary from being double-assigned by two regions? - How would you instrument and monitor this system — what are the top 3 metrics and the alerts you would page on?