Ride Sharing

Step 1 — Clarify the requirements

Before drawing a single box, pin down scope. Ride-sharing is broad, and the interviewer wants to see you carve out the core. Three functional requirements matter for the matching backend: match a rider to a nearby available driver in real time; ingest high-frequency driver location updates; and run the trip lifecycle (requested, accepted, arrived, started, completed, paid) including surge pricing. Everything else — onboarding, ratings, maps and routing tiles, payment processing, fraud — you explicitly defer so you can go deep on the part that is genuinely hard.

The non-functional requirements are where this problem earns its 'hard' rating, so state them as numbers, not adjectives. Matching must be low-latency: a request returns a candidate driver in well under a couple hundred milliseconds (we target a p99 of 120ms). The system must absorb a flood of location writes without falling over — the location stream, not the matches, is the dominant workload. And it must be regionally isolated and highly available: a failure in one city or one network link must not take down others, and the city must keep matching (we target 96 percent success) through partitions and node deaths.

Good clarifying questions to ask out loud: How fresh must driver locations be — seconds or minutes? (Seconds: stale positions wreck ETAs and match quality.) Is a slightly stale or sub-optimal match acceptable if it is fast? (Yes — matching is best-effort and eventually consistent.) Must trip state and money be strongly consistent? (Yes — that is the one place you cannot lose or double-count.) Do trips cross regions? (Rarely — an airport run — so treat it as a handoff, not the common case.) Those answers split the system cleanly into an AP side (location and matching, tolerant of staleness) and a CP side (trip lifecycle and payments, which must be exact).

• Functional: nearby-driver matching, high-frequency location ingest, trip lifecycle plus surge pricing.
• Non-functional: geospatial matching at p99 ≤ 120ms, absorb the location firehose, regional isolation and high availability (≥ 96 percent match success).
• Explicitly out of scope: routing/maps, payment rails, ratings, onboarding — name them so you can go deep on matching.
• Key dichotomy to surface early: location and matching are AP (stale-tolerant); trips and money are CP (exact).

Step 2 — Back-of-the-envelope: the firehose dominates

The single most important number in this design is the ratio of location pings to ride requests. Assume on the order of one million drivers online concurrently at peak across a large operating footprint. Driver apps ping their position roughly every 4 seconds — frequent enough for good ETAs, infrequent enough to stay affordable. That is 1,000,000 / 4 = 250,000 location writes per second. Ride requests are tiny by comparison: even tens of millions of trips per day work out to only hundreds to a couple thousand matches per second at peak. Pings outnumber matches by roughly 100:1 — and in practice often several times more. Internalize that asymmetry; it dictates the entire architecture.

Now size the data. A location ping is small — driver id, latitude, longitude, timestamp, and a status flag, call it 40 bytes. At 250k pings/sec that is about 10 MB/sec of ingress. Durably writing every ping to a relational database would generate roughly 10 MB/sec × 86,400 ≈ 860 GB per day of pure churn — and almost all of it is wasted, because you only ever need the latest position per driver. The live working set is tiny: one million drivers × ~100 bytes (id, lat/lng, status, last-seen, a little metadata) ≈ 100 MB. That comfortably fits in RAM on a single node — which is exactly why an in-memory geo index is viable and a synchronous DB write per ping is not.

Trips are the opposite shape: low volume, high value, durable. Each match creates one trip record (~1 KB: rider, driver, route summary, fare, and a handful of state-transition timestamps), and a trip emits maybe six lifecycle events from request to payment. So the trips store sees on the order of (matches per second) × 6 writes — hundreds to low-thousands per second per region, not hundreds of thousands. The durable store is sized for trips and the occasional cache-miss read, never for the ping firehose.

The SysGym simulator collapses this into one region's combined request pipeline: a base of 15,000 requests per second ramping to 30,000 at rush hour (a 2x load factor), where the bulk is driver pings flowing into the ingest queue and geo index and rider matches are the smaller stream the matchers answer. That 15k-to-30k regime is precisely where two naive choices fall over — a single matching path, and a synchronous per-ping database write — and the estimation above is exactly why.

• ~250,000 location pings/sec versus hundreds-to-thousands of matches/sec — roughly a 100:1 write-to-match ratio, and often more.
• Durably storing every ping ≈ 860 GB/day of churn you overwrite anyway; the live working set is only ~100 MB and fits in memory.
• Trips: low volume, ~1 KB each, ~6 events per trip — the durable store is sized for trips, not pings.
• Simulator regime: 15,000 rps base, 30,000 rps at the 2x rush-hour peak — the point where naive designs break.

Step 3 — High-level architecture and why each piece exists

The request flows through six component types, each chosen to defend one of the SLOs. A regional load balancer is the front door; its single most important job is to keep a city's traffic inside that city's region (regional isolation) and to fan requests across matcher replicas. In the reference it is sized large (capacity 60,000 rps) so it is never the bottleneck — at the 30k peak it runs at 50 percent utilization.

Behind the LB sit the matching services — the stateless compute that, for each request, queries the geo index for nearby drivers, ranks them (ETA, heading, acceptance likelihood), and atomically claims one. Critically, there are two independent matcher pools, not one. Each pool is four replicas at 9,000 rps capacity, so a single pool absorbs 36,000 rps — more than the entire 30k regional peak. The deep dive shows why that redundancy is the difference between surviving a partition and stalling the city.

The location-ingest queue tames the firehose. Driver pings stream into it (Kafka-style, partitioned by driver or by cell) and consumers update the in-memory geo index; nothing is written synchronously to the durable store. The queue absorbs bursts so the index updates at a sustainable rate and a momentary spike never blocks producers. In the reference it drains at 35,000 rps behind an 80,000-request buffer.

The geo index is a cache: every driver's latest position held in memory, bucketed by a spatial grid so 'who is near this rider' is a small lookup rather than a scan. It serves the vast majority of reads locally (a 0.92 hit ratio in the reference) at ~2ms. The trips store is the durable system of record for trip lifecycle state — region-partitioned, strongly consistent, and deliberately kept off the location hot path. It sees only trip writes and the small fraction of geo reads that miss the cache (capacity 14,000 rps, running well under load).

One caveat worth stating in an interview: the simulator scores this pipeline as a single linear chain (LB → matchers → queue → geo index → trips store). In a real deployment, location ingest and trip storage are distinct paths that share the geo index — pings flow queue → geo index, while a match flows LB → matcher → geo index (read) and matcher → trips store (write). The component choices are identical; only the wiring is linearized to keep scoring tractable. Calling that out shows you understand the model rather than parroting it.

• Regional LB (cap 60k): keeps a city's traffic local and fans out to matchers; never the bottleneck (50% utilized at the 30k peak).
• Two matcher pools (4 × 9,000 rps each = 36k per pool): stateless geo-query + rank + atomic claim, with active-active redundancy.
• Location-ingest queue (drain 35k, buffer 80k): absorbs the ping firehose so the index updates at a sustainable rate.
• Geo index cache (0.92 hit ratio, ~2ms): in-memory latest positions, spatially bucketed for fast nearby lookups.
• Trips store (cap 14k): durable, region-partitioned, consistent trip lifecycle — off the location hot path.

Deep dive A — The location firehose and the in-memory geo index

This is the defining hard problem, and it is really two questions answered together: how do you find nearby drivers fast, and how do you ingest 250k location writes per second without melting a database?

Finding nearby drivers fast means never scanning all drivers. A linear scan computing haversine distance to every car is O(drivers) per request and dies the moment a city has tens of thousands of cars online. The standard answer is a geospatial index that buckets drivers into spatial cells — geohash, a quadtree, or Google S2. With geohash, a 6-character cell is roughly 1.2km × 0.6km and a 7-character cell roughly 153m square; you index each driver by the cell holding their latest position. A 'who is near me' query reads the rider's cell plus its eight neighbors (so a car just over a boundary is not missed) and ranks the handful of candidates — a constant-size lookup instead of a city-wide scan. S2 or an adaptive quadtree beats fixed geohash in practice because it uses finer cells where density is high (downtown) and coarser cells where it is sparse, keeping every cell's candidate list small.

Ingesting the firehose means not writing every ping to durable storage. You stream pings through a queue and update an in-memory geo index, keeping only the latest position per driver (an overwrite, not an append), so write amplification is bounded and the working set stays around 100 MB. Two worse-but-instructive alternatives frame the trade-off: writing every ping synchronously to SQL is correct in spirit but operationally fatal — hundreds of thousands of writes per second crush a relational store; and updating positions only once a minute is cheap but produces stale locations that ruin ETAs and match quality. Queue-plus-memory is the sweet spot — fresh-enough positions without durable write amplification.

Hot keys are the failure mode to anticipate. When a concert or a flight lets out, demand and supply concentrate in a few cells, which become hot for both reads (many riders querying the same area) and writes (many drivers pinging it). Mitigations: adaptive cell sizing so dense areas get finer cells with smaller candidate lists; shard the geo index by cell so writes spread across nodes and a hot cell is isolated; replicate hot cells for read scaling; and lean on surge pricing, which is itself a demand-shaping mechanism that thins the stampede. Because the index is in-memory and writes are overwrites, even a hot cell's write pressure is bounded — you are not appending an unbounded log, just updating a few thousand driver slots in place.

• Bucket drivers into spatial cells (geohash / quadtree / S2); query the rider's cell plus its 8 neighbors, then rank — constant-size lookup, not an O(drivers) scan.
• Stream pings through a queue and keep only the latest position per driver in memory — no synchronous per-ping DB write, no append churn.
• Stale-but-cheap (once-per-minute) trades match quality away; synchronous SQL trades away survival. Queue-plus-memory wins.
• Hot cells (events, airports): adaptive cell sizing, shard by cell, replicate hot cells, and let surge shape demand.

Deep dive B — Surviving the partition, idempotent trips, and async surge

The reliability story is a sequence of scripted failures during the rush-hour surge, each teaching one defense. First, a region partition cuts the link between the load balancer and a matcher at the 16-second mark. With a single matching path, that cut severs all matching for its duration — the city goes dark on matches. The fix is redundant matcher paths: two independent pools behind the same LB. When one LB-to-matcher edge is cut, the LB reroutes all traffic to the surviving pool. This only works if each pool can absorb the full regional peak alone, which is why each pool is 4 × 9,000 = 36,000 rps against a 30,000 rps peak. That headroom is deliberate — it is the price of an active-active, fully redundant second matcher path inside the region (each pool independently covers the whole peak, so either can take over).

Second, a matcher dies at 24 seconds. Because matchers are stateless and replicated, losing one replica drops a pool from 36,000 to 27,000 rps; combined with the second pool, the region still fields 63,000 rps against a 30k peak, so nothing drops. The lesson: keep the matcher stateless — all state lives in the geo index and trips store — so a death is a capacity dent, not a correctness event.

Third, the trip lifecycle must be an idempotent state machine, and the match must atomically claim a driver. Idempotency matters because clients retry: a rider's flaky network may resend 'request ride,' and a driver app may resend 'accept.' Attach an idempotency key (a client-generated request id) to trip creation so a retry returns the existing trip instead of creating a duplicate or double-charging, and guard each transition (requested → accepted → arrived → started → completed) so a duplicate or out-of-order event is a no-op. When a matcher selects a driver it must atomically claim it — a compare-and-set on the driver's status in the geo index, or a short-lived per-driver lock — so two simultaneous requests cannot both be assigned the same car. This is the one spot on the matching path that demands strict correctness despite the otherwise best-effort design.

Fourth, surge pricing is computed asynchronously per region, not per request. Surge moves slowly — it tracks the supply/demand ratio in a cell over tens of seconds — so a streaming aggregation recomputes a multiplier per cell every few seconds from open requests versus available drivers, and the matcher just reads the current value. Recomputing surge globally on every request would be both wasteful and wrong, conflating a slow-moving regional signal with a per-request operation; a fixed price ignores supply and demand entirely. Async per-region aggregation is the correct, cheap answer.

• Two matcher pools, each sized for the full peak (36k vs 30k), so a partitioned LB-to-matcher link reroutes to the survivor with zero drops.
• Stateless, replicated matchers: a dead replica is a capacity dent (36k → 27k), never a correctness problem.
• Idempotency keys on trip creation, guarded state transitions, and an atomic compare-and-set driver claim prevent duplicates and double-assignment.
• Surge: async per-region/per-cell aggregation every few seconds — not per-request, not fixed.

Bottlenecks under load and how to scale them

Tie each scaling move to the metric it defends, because that is exactly how the gym scores you. The graded SLOs are availability (≥ 0.96, served / total over the run), p99 latency (≤ 120ms, the median of per-tick p99 so it is robust to brief chaos spikes), throughput (≥ 15,000 rps, the median served load), saturation (≤ 0.90, the 90th-percentile worst-node utilization), and cost (≤ 13 provisioned units, where each compute replica bills as one).

Bottleneck one: matcher capacity, defending throughput and availability. The under-tuned starter runs three replicas at 4,500 rps = 13,500 rps total, below even the 15,000 rps throughput floor and far below the 30,000 peak, so requests drop wholesale. Two pools of four 9,000-rps replicas give 72,000 rps of matching, so the median served load lands around 24,000 rps and clears the 15k floor with room to spare. Matchers are stateless, so this is pure horizontal scale-out; in production you autoscale on CPU and queue depth.

Bottleneck two: the ingest queue, defending saturation and availability. If it cannot drain the firehose, its buffer overflows, pings drop, and the geo index goes stale — degrading every match. The starter's 12,000 rps drain saturates instantly at the 30k peak; raising it to 35,000 rps drain with an 80,000 buffer holds utilization near 0.86 at peak (about 0.90 once you add the simulator's ±5 percent wiggle), which is exactly what keeps the 90th-percentile saturation at or under the 0.90 target. The queue is the saturation-defining component here, so size it deliberately; in production you scale it with partitions and consumers.

Bottleneck three: the geo index and the trips store, defending latency and availability under the cache slow-down and DB-blip failures. Latency stays low only because geo lookups come from the in-memory index (~2ms) and not the durable store: at the median ~24k load the full-path p99 works out to about 77ms, and even the rush peak is roughly 109ms — both under 120. Raising the cache hit ratio from the starter's 0.80 to 0.92 does double duty: it lowers latency and shrinks the blast radius of the trips-store outage. When the store blips at the 30-second mark, only the cache-miss fraction is exposed; at a 0.92 hit ratio that is 8 percent of traffic, lifting whole-run availability to about 0.989, whereas the 0.80 starter's 20 percent miss fraction would drag it toward 0.97. Higher hit ratio is the cheapest availability you can buy. The geo-index latency spike at 38 seconds raises path latency briefly, but because graded latency is a median of per-tick p99, a six-second spike does not move the score.

Bottleneck four: cost discipline, defending the ≤ 13 footprint. The temptation is to over-build — a global mega-cluster, a database per city replicated everywhere. The reference lands at exactly 12 units (1 LB + 4 + 4 matcher replicas + 1 queue + 1 cache + 1 trips store), under the budget of 13. Regional partitioning is what makes lean possible: each region runs its own right-sized fleet instead of one oversized global pool, which simultaneously bounds blast radius and keeps latency local.

• Matchers (throughput/availability): scale out stateless replicas — two pools of 4 × 9,000 rps clear the 15k floor and the 30k peak; autoscale on CPU and queue depth.
• Ingest queue (saturation): raise drain to 35k and buffer to 80k so peak utilization stays ≈ 0.86–0.90, holding p90 saturation ≤ 0.90; scale by partitions and consumers.
• Geo index + trips store (latency/availability): keep geo reads in memory (~2ms → ~77ms median p99); a 0.92 hit ratio both lowers latency and cuts the DB-outage blast radius to 8 percent → ~98.9 percent availability.
• Cost: region-partitioned, right-sized fleets land at 12 units ≤ 13 — no global mega-cluster.

Key trade-offs to articulate

A strong answer names its trade-offs rather than presenting the design as obviously correct. The central one is consistency versus availability, resolved by splitting the system. Location and matching are AP: stale positions and the occasional sub-optimal match are acceptable in exchange for speed and survival, so they live in an in-memory, best-effort index. Trip state and money are CP: they live in a durable, strongly-consistent store with idempotent transitions, because a lost or duplicated trip or charge is unacceptable. Putting the whole system on either extreme — durably writing every ping, or treating payments as eventually consistent — is the classic mistake.

Freshness versus write cost is the second trade-off, and the simulator scores it directly. Pinging every few seconds keeps ETAs and matches accurate but multiplies write volume; pinging once a minute is cheap but stale. Queue-plus-in-memory resolves it — freshness without durable write amplification — but it is a deliberate choice with a cost (more moving parts, a buffer that overflows if under-sized), not a free lunch.

Regional isolation versus global features is the third. Partitioning by city bounds blast radius, keeps latency local, and shrinks each geo index to a manageable working set — but it complicates genuinely cross-region trips (an airport run between two regions) and global supply rebalancing, which now need an explicit handoff or a higher-level coordinator. You accept that complexity because the isolation and latency wins dominate for the common case. Finally, redundancy versus cost: two full matcher pools roughly double matcher spend but are what survive the partition and the node death. The ≤ 13 budget is the forcing function — generous enough for a fully redundant second matcher path (12 units), but not for an over-provisioned global cluster, mirroring the real-world pressure to be both resilient and lean.

• Consistency split: AP for location/matching (in-memory, stale-tolerant), CP for trips/money (durable, idempotent) — never one extreme for both.
• Freshness vs write cost: every-few-seconds pings via queue-plus-memory beat both synchronous SQL and once-a-minute staleness, at the cost of more moving parts.
• Regional isolation vs global features: partitioning bounds blast radius and latency but makes cross-region trips and supply rebalancing an explicit handoff.
• Redundancy vs cost: two full matcher pools cost more but survive partition and death; the ≤ 13 budget funds a fully redundant second pool (12 units), not a mega-cluster.