Design a Ride-Sharing App

Friday, 8 pm, Mumbai. The first heavy rain of the monsoon has stopped the local trains, and outside Andheri station Ananya opens a ride app along with thousands of other stranded commuters. Three free cars are within two kilometres of her. The best of them, Driver A, has just driven into an underpass and lost signal. Driver B, on one bar of network, will tap Accept twice. Within about 15 seconds Ananya should still see "Driver B, 5 min away", B must never be sent to two riders at once, and her ₹250 fare must be charged exactly once, however often a phone retries.

The product: a ride-sharing app for a large country. Riders see cars, autos and bikes nearby, get a price, book, watch the driver arrive and pay after the trip. Drivers go online, accept ride offers and get paid. Plan for 10 million rides a day and the evening rush. Ananya's booking, ride 812, runs through the whole chapter.

Ananya's ride looks simple on her phone. Underneath, the nearby places chapter searched for things that stay put and the maps chapter priced roads with live traffic; a ride-sharing app is a nearby search where every result is moving, and each result can serve only one rider at a time. Three problems follow: tracking about a million moving drivers, matching each request to a good driver in seconds, and running each trip reliably through to payment.

The scope for today, by who uses it:

Routing comes ready-made from the maps chapter, so the effort here goes into moving drivers, matching and trips. The qualities that shape the design, as numbers:

• Quick matching: most riders get a driver within about 15 seconds; everyone gets an answer within about 2 minutes.
• Live positions: the car on the rider's map is at most a few seconds behind the real one.
• One driver, one trip: never two riders for one driver, or two drivers for one rider. Correctness beats speed here.
• Nothing lost: a booked trip is never lost, and no trip is charged twice.
• Always on: 99.99% for booking, under an hour of downtime a year; an outage strands riders and costs drivers income.
• Private: each side sees the other's location only during the trip; calls use number masking, a temporary number that dies with the trip.

How much load does an evening of Ananyas create? Assume 10 million rides a day and 1 million drivers online at the evening peak, each driver's phone sending its position every 4 seconds, the interval the maps chapter used for navigation pings.

The full table adds what those three numbers imply:

Location updates outnumber bookings about 700 to 1, whether or not anyone books. The trips row uses Little's law: things in flight = arrival rate × time each one stays, which holds because the rush lasts hours, far longer than one trip.

The live driver map is tiny but restless: 1 M drivers × about 100 bytes (id, position, heading, cell, state, vehicle, time) is only about 100 MB, yet nearly all of it is rewritten every 4 seconds. Stored data stays modest: trip rows add about 10 GB a day (3.7 TB a year), route traces about 100 GB a day, and raw pings, about 700 GB a day, are kept only a few days.

With the load known, what do the two apps actually call? Riders make a few ordinary calls; drivers also stream positions and must receive offers within a second.

POST /v1/quotes   { pickup, drop, vehicle: "car" }    -> 200 { quoteId, fare: 250, surge: 1.25, expiresAt }
POST /v1/rides    { quoteId, paymentMethod: "card" }  -> 201 { rideId: 812, status: "requested" }
                  Idempotency-Key: one per booking, reused on retries
GET  /v1/rides/{rideId}                               -> 200 { status, driver, vehicle, etaSec }
POST /v1/rides/{rideId}/cancel                        -> 200 { cancellationFee }
PUT  /v1/drivers/me/availability  { online: true, vehicle: "car" }                -> 200
POST /v1/drivers/me/locations     { points: [{ lat, lng, heading, t }], tripId }  -> 202
POST /v1/offers/{offerId}/accept                      -> 200 { rideId }, or 409 if expired or taken
POST /v1/rides/{rideId}/events    { type: "arrived" | "start" | "end", code }  -> 200 { status }
WS   /v1/live     server pushes: offers to drivers; positions, trip status and nearby cars to riders

Positions and offers usually travel over the WebSocket; the HTTP lines show what they carry.

Quotes come first. Ananya's quoteId holds the ₹250 price for a few minutes, so the fare cannot change between seeing it and tapping Book. Booking carries an idempotency key, as in the abstractions chapter: if the rain-soaked network makes her app send the booking twice, she still gets one ride, not two drivers.

Both apps keep a WebSocket open: a two-way connection that stays up, so the server can push at any moment. Offers reach drivers in well under a second, and the rider's map moves without battery-draining polling. A session directory records which connection server holds each phone's socket, so an offer reaches the right one.

Behind those calls sit two kinds of data. Live state, where each driver is and whether they are free, changes every few seconds, is read in milliseconds and can be rebuilt from the next pings. Records, meaning trips, payments and ratings, change a few times per trip and must never be lost.

The relational trips table is sharded by city, because matching, trips and surge all stay inside one city, and trouble on Mumbai's shard leaves Delhi's alone. Load is not the reason: even the busiest city needs about a thousand writes a second at peak. payments.trip_id is unique, so no trip can hold two payments. A consumer of trip events copies each finished trip into rider_trips, keyed by rider, so "Your trips" reads one partition instead of every city's shard.

The live state is three kinds of key:

These keys live in an in-memory key-value store, partitioned by city, each driver: key with a TTL (time to live), as in the distributed cache chapter. Losing them is fine: every online driver pings again within seconds. The expiry doubles as the offline detector. A dead phone or a long tunnel stops the pings, and the entry vanishes after 30 seconds, like an expiring lease in the task scheduler chapter.

Now follow ride 812 through the whole system. Four services do the main work. Connection servers hold every phone's WebSocket and pass pings to the location service, which writes the geo index. The matcher finds, ranks and offers. The trip service owns each trip's state and the trips database. Payments and surge pricing sit to the side.

Two rules saved ride 812. Every offer has a deadline, so a dead phone cost Ananya 15 seconds rather than her booking, and every accept is a conditional update, so A's late tap could not take a ride that was already B's. The deep dives build each piece in turn: the index, the ranking, the offer race and the trip's states.

How did the matcher find A, B and C in milliseconds? The nearby places chapter indexed things that almost never move; drivers turn its numbers upside down:

Over 100,000 times the churn rules out batch rebuilds: refreshing every minute leaves a car 500 m behind at 30 km/h. So the index lives in memory and changes ping by ping:

Step 4 is rare. A car at 30 km/h covers about 33 m between pings, so crossing a length-6 cell, about 1.2 km × 0.6 km, takes 18 to 36 pings. Almost every ping is one overwrite in memory, which is why a handful of machines absorb 250,000 a second.

Two races need care. A batch delayed by a weak network can arrive after a newer one, so the overwrite applies only if its timestamp is newer; otherwise the car jumps backwards. And a cell move is two writes, so a crash between them can leave a stale id in a cell. That is harmless, because the cell sets are only an index: the matcher re-reads each driver:{id} entry, the truth, and skips ids whose entry is missing or elsewhere.

Partition by city. Matches rarely cross city lines, so each city gets one shard with a replica in another zone; a pickup near a boundary asks both. Mumbai, with perhaps 100,000 drivers online, sends 25,000 pings a second, easy for one in-memory node; the largest cities split further by cell prefix.

Before Ananya booked, her home screen showed cars and autos crawling around the station. It looks like decoration, yet it is the busiest read in the system, so size it like any other feature.

Assume about 1,750 riders a second open the app at the peak, as many as there are fare checks, and keep the map open for about 80 seconds. By Little's law, about 140,000 maps are open at once; refreshed every 4 seconds, that is about 35,000 refreshes a second.

Done naively, each refresh reads the 3 × 3 block of cells for every vehicle type, then every driver entry in them, about 170 in a busy area: roughly 6 million key reads a second, 24 times the 250,000 pings that write the index. Compute each cell's picture once, and push it over the socket the rider already holds:

Riders cluster in cities. A city of 1,000 km² has about 1,400 length-6 cells, so even fifteen busy cities make only about 20,000 watched cells. One snapshot each every 2.5 s is 8,000 snapshots a second; at about 20 entries each, roughly 160,000 key reads a second instead of 6 million. Each open map receives one small bundle every 2.5 s, about 56,000 pushes a second, and rounding plus missing ids mean nobody can follow one driver from the home screen.

Back to ride 812: which of the free cars should get the offer? Matching starts as a nearby search: free drivers of the right type in the pickup's cell and its eight neighbours, the 3 × 3 block from the nearby places chapter, which covers at least 600 m in every direction. Drivers who have missed two pings in a row are skipped, since they would likely miss the offer too. If fewer than about 10 turn up, the search widens ring by ring, up to a few kilometres.

Then it ranks by pickup time, not distance, because straight lines lie in a city. The matcher asks the maps chapter's routing service for each top candidate's driving time; one search from the pickup, following roads in reverse, reaches them all at once. Here is how Ananya's three candidates compare:

The nearest car as the crow flies, C, is the worst choice. Other signals then adjust the order: heading towards the pickup beats heading away, and a fairness rule stops one driver getting every ride.

Matching each request the moment it arrives, greedy matching, is simple but wasteful when requests bunch up. Suppose rider R1 asks first and drivers X and Y are free: X is 2 minutes from R1 and 3 from R2; Y is 3 minutes from R1 and 9 from R2. Greedy gives R1 the nearest driver, X, and leaves R2 waiting 9 minutes: 11 in total. Batch matching collects an area's requests for a second or two and solves an assignment problem, pairing riders and drivers for the lowest total: R1 gets Y and R2 gets X, 6 minutes in total and nobody waits more than 3. The price is a short delay before every match, worth paying outside a station at rush hour, not on a quiet night.

Choosing A was half the job; the driver must still say yes. A may never answer, and two matchers may want the same driver at once. Deadlines handle the first. Compare-and-set writes, which succeed only if the value is still what the writer expected, handle the second.

Offers expire after about 15 seconds. The matcher records each offer on the trip, with its driver and deadline (offered_to, offer_expires_at), before sending it. A decline or silence moves the offer to the next driver; after a few tries or about 2 minutes, the rider hears that no driver is free. Each request is a leased job, as in the task scheduler chapter, so if a matcher crashes, another picks up the trip, still requested, and carries on.

Four races can hit ride 812, and each has a guard:

Every guard is a write that checks before it changes. In the relational trips database, the accept looks like this:

-- Driver B accepts ride 812: only while it waits and B's offer is live.
UPDATE trips
   SET driver_id = 'B', status = 'accepted', assignment_no = assignment_no + 1
 WHERE id = 812 AND status = 'requested'
   AND offered_to = 'B' AND offer_expires_at > now();
-- 1 row changed: B has the ride.
-- 0 rows: read the trip. Already B's (a repeat)? Reply 200 again. Otherwise reply 409.

A unique index allowing each driver one active trip backs up the in-memory reservation.

Once B has the ride, what stops a flaky network from producing nonsense, such as a trip that ends before it starts? A state machine: a list of states and the only moves allowed between them.

Only two states are final, and every other state has a way out, so no trip can get stuck. The 4-digit code proves the right rider is in the right car. Here is ride 812 end to end:

B's app sent Start twice, yet the trip moved once, because each move is a conditional update like the accept: UPDATE trips SET status = 'on_trip' WHERE id = 812 AND status = 'arriving'. A repeat finds the trip already moved and gets the current state back; a forbidden move, such as ending a trip that never started, is refused.

Each move and its trip_events row commit in one transaction, and a relay publishes new rows to payments, receipts and ratings (the pub-sub chapter). This is the outbox pattern from the message queue chapter: a crash after saving cannot lose the event.

The state machine covers moves that apps ask for. Some moves have no message to trigger them: a trip stuck in requested for 2 minutes must become cancelled, "no driver found". A timer service, like the delayed tasks in the task scheduler chapter, fires these moves, so no trip waits forever.

The hard case is a driver who accepted and then went silent on the way. Suppose B's phone dies two streets from Andheri station. Waiting strands Ananya. Reassigning carelessly can send two drivers to one rider, or let B's late "arrived" land on the new driver's trip.

If B's phone comes back just as the timer fires, the conditional update settles it: whichever lands first wins, and the other finds the trip no longer in the state it expected. The assignment number is a fencing token, the idea the coordination chapter uses for locks: a message stamped with an old number can never act on a newer assignment.

The deep dives each handled one failure. Here they are side by side with the rest, as riders and drivers would notice them:

One pattern runs through the table: live state is rebuilt from the next pings, while records survive through replicas and conditional updates.

The real-time tier dominates the server bill: sockets, location shards and routing for ETAs are sized for the evening rush and run all day. Per-trip provider fees, for card payments and masked calls, can rival the servers.

Behind those responses sit choices that could reasonably go the other way. Each row names the condition that flips it:

Most rows trade a few seconds of waiting for fewer races or less load, and the numbers decide which side wins.

The ping interval shows that a trade-off can adapt instead of staying fixed. The app pings every 4 s while the car moves or is on a trip, every 10 s while it is parked and free, and at once when it starts moving or receives an offer. Capacity is planned for the evening peak, when most drivers move; at night, with most parked, the same rule cuts pings by about half.

The last row of the failure table needs a plan of its own. A 99.99% booking target allows about 52 minutes of downtime a year, 4.3 minutes a month. Losing a zone, one data centre within a region, must cost nothing visible. Losing a whole region may cost a minute or two, and only if every step is planned.

Each city is homed in one region, with a warm standby in another. Its matching, trips and payments run only in the home region, so every trip has one writer. The standby keeps an asynchronous copy of trips and payments and runs a small fleet of connection and location servers, ready to grow. Each kind of state recovers differently:

Live state is the easy part; records decide how long the pause lasts. Here is the plan if the region holding Mumbai fails at 8 pm, with Ananya mid-trip:

Payments dedupe on the trip id, so a capture sent just before the failure is never charged again from the standby; reconcile with the provider when the old region returns. Drill the failover every few months: a recovery plan nobody has tried is a backup nobody has restored.

Optional: how Ananya's ₹250 was priced, how surge works, and how payment never charges twice. The fare is worked out at quote time. The routing service from the maps chapter gives the trip's distance and driving time, and the city's rate card turns them into a price:

fare = (base + per_km × distance + per_min × time) × surge
     = (₹50  + ₹10 × 10 km       + ₹2 × 25 min)   × 1.25
     = (₹50  + ₹100              + ₹50)           × 1.25  =  ₹250

Example rates only. The quote stores the fare and multiplier, so the rider pays what they saw unless the trip changes.

Surge is a multiplier that rises when riders outnumber free drivers in an area. It trims demand from riders who can wait and draws drivers in from quieter areas. Every minute, a stream job turns each area's recent requests per free driver into a multiplier; an area might be a length-5 geohash cell, about 5 km across. An example curve:

Smooth the ratio over several minutes, move in small steps and cap it, so prices do not jump when a stadium empties; some regulators set caps of their own.

Payment completes after the trip, never inside it. Ananya pays by card, so booking placed a hold for ₹250: the money is reserved, not moved, and a cancelled trip releases it. The trip completed event lands on a queue, and a payment worker captures the final fare, or charges methods without holds, with the trip id as the idempotency key. A charge that keeps failing becomes dues, collected before the next booking. A ledger, where every debit has a matching credit, records each move: rider −₹250, driver +₹200, platform +₹50. The payments chapter goes deeper.

A 45-minute slot leaves about 40 minutes of design once introductions and your own questions are done. Here is ride-sharing on that clock.

Pick the deep dive from the interviewer's question. How do you find drivers fast? Go deep on tracking and the geo index. How does one driver never get two riders? Go deep on offers, deadlines and conditional updates. Retries or money? Walk the trip state machine and payment keyed by the trip id.

Interviewers change the problem to see whether your design bends or breaks. Try each one before opening the answer.