Uber

Ride-Hailing Service

Design Uber, a ride-hailing service that tracks millions of moving drivers, finds the best nearby driver for each ride request in seconds, and never gives one driver two rides.

Overview

A ride-hailing service connects a rider who wants a trip with a driver who is close by and free. Almost every part of it depends on where things are right now: drivers' positions change every few seconds, a rider's request has to be matched in a few seconds, and prices react to supply and demand in each neighborhood.

The design splits into a very write-heavy side and a latency-sensitive side. Millions of drivers send their position every few seconds, which is far more writes than any other part of the system, but only the latest position matters. When a rider asks for a car, the system must find free drivers near the pickup, estimate how long each would take to arrive, offer the ride to one, and make sure no other rider gets the same driver.

Questions to ask first

How many rides and drivers? — 20 million ride requests a day; 5 million drivers online at the busiest time
How often do drivers report location? — Every 4 seconds while online
How fast must matching be? — A driver offered within a few seconds of the request
Can a driver decline? — Yes; an offer times out after about 15 seconds and goes to the next driver
Shared rides, deliveries? — Out of scope
Payments? — Charge after the trip; payment internals out of scope

What you will be able to do

Size the location update stream and keep only what matters: each driver's latest position.
Index moving drivers by hexagon cells and search outward from a pickup.
Offer a ride to one driver at a time without ever double-booking a driver.
Explain ETA as a routing estimate refined by a learned correction, and surge as supply and demand per cell.
Shard by geography and handle hot spots such as a stadium emptying.

Key concepts

Location updates
Geospatial index
H3 hexagons
Nearby search
Dispatch and offers
Driver state machine
ETA
Surge pricing
Sharding by geography

Functional requirements

Drivers go online and report their location while online
Riders see nearby cars and an estimated pickup time
Riders request a ride; the system offers it to a nearby driver
A driver accepts or declines; declined or expired offers go to the next driver
Both sides see each other's location during pickup and the trip
Show a fare estimate before the request, and charge after the trip

Non-functional requirements

Find candidate drivers in under 100 ms at p99 (a target we chose)
A location update is visible to matching within about 5 seconds
A driver is never assigned to two active rides
A requested ride is never lost, even if a server fails mid-dispatch
Losing one area's servers does not affect other areas

Interview questions

How do you find the nearest drivers quickly?
How do you handle over a million location updates a second?
How do you make sure a driver is not given two rides?
How is ETA calculated?
How does surge pricing work, as a system?
What happens when a big event ends and thousands request rides at once?
How would you shard the system?