Design
Uber
Connect Riders with Drivers in real-time. The hard part isn't the app; it's efficiently querying "Who is near me?" when everyone is moving.
Requirements
Functional
- 1. Rider can see nearby drivers.
- 2. Rider can request a ride.
- 3. Driver accepts ride and sees route.
- 4. Driver location updates every 4 seconds.
Non-Functional
- 1. Real-time: Location updates must be fast.
- 2. Consistency: If a driver takes a ride, they must disappear for others instantly.
- 3. Geospatial Scale: Efficient spatial queries.
Geospatial Indexing
Bad Idea: SELECT * FROM drivers WHERE lat BETWEEN x AND y...
This is too slow (O(N)). We need to index 2D space.
Grid Approach (Naive)
Divide map into fixed squares.
Problem: Downtown NY has 1000 drivers per cell. Rural Kansas has 0. Uneven distribution.
Dynamic Grids (QuadTree / Geohash)
Recursively divide the map based on density.
If a cell has > 500 drivers, split it into 4 smaller cells.
QuadTrees vs Geohash
Geohash
Encodes Lat/Long into a string. e.g., u4pruydqqvj.
- Longer string = More precision.
- Shared prefix = Close proximity (mostly).
- Pro: Just a string. Easy to store in Redis/DB.
- Con: Edge cases (two close points might have different prefixes).
QuadTree
Tree data structure. Root is the world. 4 children.
- Leaf nodes store drivers.
- Pro: Perfect for K-Nearest Neighbor search.
- Con: Hard to update. If a driver moves, you might need to rebalance the tree.
Handling Location Updates
Drivers send updates every 4 seconds. Millions of writes per second. Database will die.
Driver Object in Redis
We don't need persistent history for "Find Driver". We only need current location. Set TTL (Time to Live) to 15 seconds. If driver app crashes, they disappear automatically.
Matching Service
The "Dispatch" System
Rider requests ride.
Service queries Redis for drivers in user's Geohash (and neighbors).
Service filters drivers (status=AVAILABLE, car_type=X).
Service locks the driver (Distributed Lock / Optimistic Locking).
Prevent two riders from booking same driver.
Send offer to Driver. If accepted, trip starts. If rejected, try next nearest.