Chapter 21 — Design a Ride-Sharing App (Uber)
Chapter 21 — Design a Ride-Sharing App (Uber)
Hey everyone! Welcome back to Namaste System Design! 🙏
Uber is a fantastic interview problem because it adds a brand-new dimension: location. Millions of drivers move around a live map, pinging their position every few seconds, and when you request a ride we must instantly find the nearest available driver. "Find things near a point, at massive scale" is a genuinely tricky problem. Let's solve it.
Step 1 — Clarify Requirements
FUNCTIONAL: ✔ Drivers continuously share their live location ✔ Rider requests a ride from point A → B ✔ System matches rider to the nearest available driver ✔ Track the trip live; handle completion NON-FUNCTIONAL: ✔ Low latency matching (find driver in ~seconds) ✔ Handle huge volume of location updates (drivers ping ~every 4s) ✔ Highly available; location can be eventually consistent ✔ Accurate matching (truly nearest available driver) SCOPE: "Focus on live location + rider-driver matching."
Step 2 — Estimate Scale
Say 1M active drivers, each pings location every 4 sec
→ 1M / 4 ≈ 250,000 location writes/sec 😳 (write-heavy!)
→ We CANNOT store every ping in a slow disk DB. Live locations
live in FAST in-memory storage (Redis), updated constantly.
→ Trip records (start/end/payment) go to a durable DB.
Step 3 — The Core Problem: "Find Nearby Drivers"
When you request a ride at a location, we need all available drivers within a few km — fast. A naive scan ("check the distance to all 1M drivers") is far too slow. We need a geospatial index.
┌─────────────────────────────────────────────────────────────┐ │ THE IDEA: divide the world map into a GRID of cells. │ │ Then "nearby" = "in my cell + neighboring cells" — │ │ a tiny lookup instead of scanning the whole planet. │ └─────────────────────────────────────────────────────────────┘
┌────┬────┬────┐ Rider is in cell E. To find nearby │ A │ B │ C │ drivers, we only check cell E + its 8 ├────┼────┼────┤ neighbors — NOT all 1M drivers. │ D │ E★ │ F │ ├────┼────┼────┤ ★ = rider. Drivers indexed by cell. │ G │ H │ I │ "Who's in E, D, F, B, H..." → instant. └────┴────┴────┘
Real techniques for the grid
• GEOHASH → encodes lat/long into a short string; nearby
points share a prefix. "Drivers with geohash 9q8yy*"
• QUADTREE → splits dense areas into finer cells (a busy
city gets tiny cells; an empty desert stays coarse).
• S2 / H3 → Google's & Uber's real libraries for this.
Redis has built-in GEO commands (GEOADD / GEOSEARCH) that do
exactly this — perfect for the live location store.
Step 4 — High-Level Design
[ Driver apps ] ── location pings every 4s ──▶ [ Location service ]
│ update
▼
[ Redis GEO index ]
(driver → live cell)
[ Rider app ] ── "request ride @ A" ──▶ [ Matching service ]
│ 1. GEOSEARCH Redis
│ for nearby, available drivers
│ 2. pick best (distance/ETA)
│ 3. offer ride to driver
▼
[ Trip service ] → [ Trip DB ]
(durable record of the trip)
TRACE A RIDE REQUEST: ───────────────────── 1. Rider requests at location A 2. Matching service GEOSEARCHes Redis: available drivers near A 3. Ranks candidates by ETA (not just straight-line distance) 4. Sends the request to the top driver; they accept/decline 5. On accept → create a Trip in the durable DB, notify rider 6. During trip → live location streamed rider ↔ driver
Step 5 — Deep Dive: Handling the Location Firehose
250,000 writes/sec of "driver X is now at (lat,lng)":
✔ Store in REDIS (in-memory) — disk DBs can't take this rate.
We only need the LATEST position, so we OVERWRITE, not append.
✔ Location updates are EVENTUALLY consistent — if a driver's
dot is 2 seconds stale, that's totally fine.
✔ Partition/shard the location service by REGION (city) so no
single node handles the whole planet's pings. A driver in
Delhi only affects the Delhi shard.
Matching subtleties
• Nearest by ROAD/ETA, not straight-line — a driver across a
river is "close" on a map but far by road.
• Avoid double-booking: when offering a ride, LOCK/mark the
driver as "pending" so two riders don't grab the same driver.
• If the top driver declines → offer to the next candidate.
• Surge pricing → when demand ≫ supply in a cell, raise price.
Step 6 — Bottlenecks & Trade-offs
⚠ Write firehose → Redis in-memory + overwrite latest only
⚠ Hotspot cities → shard location index by region/geohash
⚠ Matching races → lock driver during offer to prevent
double-booking
⚠ Redis is a SPOF → Redis cluster with replicas
⚠ Trip durability → trips/payments in a durable DB (not Redis)
⚠ Consistency → live location eventual; trip state strong
(you don't want a "ghost" charge)
Interview Questions — Quick Fire!
Q: How do you efficiently find nearby drivers?
"A naive approach of computing distance to every driver is far too slow at scale. Instead we use a geospatial index that divides the map into a grid of cells, so 'nearby' becomes 'in my cell and its neighbors' — a tiny lookup. Techniques include geohashing, where nearby points share a string prefix, quadtrees that subdivide dense areas, and libraries like S2 or H3. Redis even has built-in geo commands for this."
Q: How do you handle the massive volume of location updates?
"With around a million drivers pinging every few seconds, that's hundreds of thousands of writes per second — too much for a disk-based database. We keep live locations in an in-memory store like Redis, and since we only care about the latest position we overwrite rather than append. Location data is treated as eventually consistent, and we shard the location service by region so no single node handles the whole world."
Q: What's a geohash?
"A geohash encodes a latitude and longitude into a short string such that geographically close points share a common prefix. That property lets us find nearby locations with a simple prefix match instead of computing distances everywhere, which makes proximity search fast and index-friendly."
Q: How do you prevent two riders from being matched to the same driver?
"When the matching service offers a ride to a driver, it marks that driver as pending or locks them so they're excluded from other searches. If the driver accepts, they become busy; if they decline or time out, they're released and offered to the next rider. This locking during the offer window prevents double-booking."
Q: Which data is eventually consistent and which is strongly consistent here?
"Live driver locations can be eventually consistent — a dot being a couple of seconds stale is harmless. But trip state and payments must be strongly consistent and durable, stored in a reliable database, because you can't have a ghost trip or an incorrect charge. So we split fast, eventual location data in Redis from authoritative trip data in a durable store."
Key Points to Remember
| Concept | Key Takeaway |
|---|---|
| New dimension | Location. Core problem = "find nearby, fast, at scale." |
| Geospatial index | Grid the map (geohash / quadtree / S2/H3) → "nearby" = my cell + neighbors. |
| Location firehose | 250k writes/sec → Redis in-memory, overwrite latest, shard by region. |
| Matching | Rank by ETA not straight-line; lock driver during offer to avoid double-booking. |
| Consistency split | Location = eventual (Redis) · trips/payments = strong & durable (DB). |
What's Next?
The grand finale! Chapter 22 tackles the heaviest system of all: Design Video Streaming (YouTube / Netflix). How do you store and stream petabytes of video to a billion viewers without buffering? CDNs, transcoding, and adaptive streaming take center stage.
Keep designing, keep scaling! See you in the next one!
Post a Comment