Design Lyft — System Design Interview Guide

Functional requirements

• Rider requests a ride from current location to a destination with optional ride-type preference (standard, premium, shared)
• System matches riders to drivers based on proximity, driver preferences, and global supply-demand optimization
• Drivers receive ride offers with destination preview and can accept or decline
• Both rider and driver stream live GPS during the trip
• Dynamic pricing reflects local supply-demand imbalance per ride class
• Trip lifecycle states: requested, offered, accepted, in-progress, completed, rated

Non-functional requirements

• Match latency: <3 seconds from rider tap to driver assignment (p99)
• Match quality: maximize a weighted objective combining ETA, completion probability, and predicted earnings
• Location-update ingest: 1M+ drivers globally × 1 ping / 4 sec = 250K+ writes/sec
• Availability: 99.99% per region; degraded matching (longer ETAs) acceptable, full outage not
• Eventual consistency on driver state OK; ride-assignment must be linearizable (no double-booking)

Capacity estimation

Public 2024 scale anchors: Lyft handled ~700M trips in 2023 = ~2M/day = ~25/sec average, ~200/sec peak. Active drivers ~1-2M globally with peak online concentrations in major US metros (NYC peak ~50K drivers online).

Location pings dominate write QPS: 1M online drivers globally × 1 ping/4 sec = 250K writes/sec. Regional sharding means each city handles its own slice (NYC ~12K/sec, smaller markets <1K/sec). Match QPS: 200/sec global peak ≈ 5-20 matches/sec per active region.

Match candidate set: each rider request considers drivers within ~3-5 km, typically 30-300 candidates depending on market density. Each candidate is scored against several signals, so a single match decision is O(100) score computations, sub-millisecond.

Storage: trip metadata ~1 KB × 2M trips/day = 2 GB/day = ~700 GB/year, ~3 TB total with retention. Driver-state hot data lives in memory, not durable storage. Historical location pings for fraud and ML training: ~250K/sec × 100 bytes × 86,400 sec = ~2 TB/day raw, retained 30 days hot then sampled.

Driver and rider profile data ~10 KB/user × millions of users = ~10s of GB — small. Real-time supply-demand state per region (active drivers, queued requests, surge multiplier) is a few KB/region cached in memory.

High-level design

Five core services, all sharded by geographic region. The regional shard is the strongest design lever — trips almost never cross regions, so the global problem decomposes into N independent city problems.

Location ingest: drivers send GPS pings to a regional ingest service. The service updates an in-memory geospatial index (a geohash-based hashmap of cell_id → set of driver records). Each driver record holds location, status (offline / online-idle / on-trip), ride-type qualifications, and last-ping timestamp. Stale drivers (>30 sec without a ping) are marked offline and excluded from matching.

Match service is the heart of the system. When a rider taps 'request', the match service queries the in-memory index for candidate drivers within an initial radius (typically 2 km), expanding the radius if fewer than N candidates are found. Each candidate is scored along multiple dimensions (see deep dive); the highest-scoring candidate is offered the ride. If they decline, the next candidate is offered, with a TTL on each offer (~10-15 seconds) to prevent stale offers.

Pricing service maintains a per-region surge multiplier per ride class. It recomputes the multiplier every 30-60 seconds from rolling supply-demand counts (active drivers vs unmatched requests). Higher multipliers attract more drivers online; the platform's economic equilibrium runs through this surface.

Trip service writes the canonical trip record to a sharded relational store on each lifecycle event (requested, accepted, completed). Events are also published to a streaming log consumed downstream by analytics, fraud detection, and the ML training pipeline.

Client gateway: drivers and riders maintain persistent connections (WebSocket) to a regional gateway that brokers all real-time messaging (offers to drivers, status updates to riders). The gateway also handles authentication and rate limiting.

Deep dive — the hard problem

Two deep dives: the matching algorithm under multi-signal objectives, and supply-demand balancing through pricing.

Matching as optimization: the naïve answer is 'nearest driver wins', which Uber-style scenarios typically default to. Lyft-style emphasis pushes deeper: nearest is a poor proxy for the right driver. Production matching combines multiple signals into a weighted score per candidate. The standard signals are: predicted ETA (great-circle distance plus traffic factor), driver-completion probability (drivers with high cancel rates are penalized), match-experience score (the predicted user experience based on driver rating and vehicle quality), and economic signal (the predicted earnings for the driver, ensuring fair distribution of high-value rides).

A full solution treats matching as a bipartite assignment problem: instead of greedy nearest-first, batch-match all open requests against all available drivers every few seconds. The Hungarian algorithm (or a heuristic approximation at scale) optimizes the global assignment to minimize total cost across all rides. Batching adds 2-5 seconds of latency but produces better global outcomes — every rider gets a slightly worse single-match in exchange for everyone getting matched at all in supply-constrained moments.

For real-time UX, hybrid approaches exist: most requests match greedily (low latency), but during high-demand periods the system switches to batch matching with a small batching window. Discuss this tradeoff explicitly — interviewers care that you understand the matching algorithm choice has economic and UX consequences, not just latency.

Second: avoiding double-booking. Two riders requesting nearly simultaneously can both see the same driver as the top candidate. The match service reserves a driver with a short-TTL atomic compare-and-set ('reserve driver X for ride Y, expiring in 10 sec'). If the driver accepts, the reservation becomes an assignment; if they decline or the TTL fires, the driver returns to the pool. Within a region this requires a coordinator (a per-region match leader) that serializes assignment decisions. Mention this as the core consistency requirement.

Pricing and supply-demand: surge is the platform's primary market-clearing mechanism. The pricing service computes a multiplier from rolling supply-demand ratios per region per ride class — when demand outpaces supply, the multiplier rises, raising effective fares to riders and attracting more drivers online. The multiplier is bounded (typically 1.0x to 3.0x) and clipped to prevent extreme events. Pricing changes are eventually consistent — a rider sees the multiplier at request time, locked in for that ride.

Driver retention adds a second layer: drivers respond to predicted earnings, not surge alone. The system can offer 'bonus' bookings (guaranteed pay above market rate during low-supply windows) to keep drivers online. This is a separate optimization layer on top of base matching.

Third tradeoff: shared rides. Lyft Line / pooled rides match one car to multiple riders going similar directions. This is a constrained dial-a-ride problem: the matcher must find driver D and riders R1, R2 such that detouring D from R1's path to pick up R2 adds bounded extra time. Production systems prune by direction (the detour vector angle must be small) and by current load (a driver already serving one rider can pick up one more, no more). Mention but don't drill into pooled-ride detail unless asked.

Common mistakes

• Matching greedily on nearest-driver without acknowledging the multi-signal objective — production matching weighs ETA, completion, experience, and economics
• Designing a single global matcher instead of regional sharding — trips don't cross regions, so the problem decomposes
• Forgetting the assignment-reservation step — without atomic compare-and-set on driver state, double-booking is inevitable under concurrent requests
• Treating surge as a static multiplier — it must be recomputed continuously per region per ride class
• Skipping the batch-vs-greedy matching tradeoff — interviewers specifically probe this at senior+ levels

Likely follow-up questions

• How would you implement a scheduled ride feature (book now for tomorrow morning)?
• What changes if you have to support a 5-minute matching SLA where ANY waiting rider must be matched within 5 minutes even during severe supply shortage?
• How would your design handle a major event (concert, airport surge) where demand 50x's in 30 minutes?
• How would you implement driver-rider preference matching where some riders prefer female drivers and the system honors that preference legally and ethically?
• How would you detect fraudulent ride patterns (collusion between drivers and riders to game incentives)?