Location Based Service
Design Uber:
Scenario
Phase I:
- Driver report location
- Rider request Uber, match a driver with rider
Phase II:
- Driver deny / accept request
- Driver cancel matched request
- Rider cancel a request
- Driver pick up a rider / start a trip
- Driver drop off a rider / end a trip
Majority of QPS is from driver location update:
QPS = 50k , Peak = 150k
Storage for location = 0.5G/day
Service
- GeoService
- DispatchService
Schema:
Trip Table:
| Trip Table | |
|---|---|
| id | Primary key |
| rider_id | |
| driver_id | |
| lat | |
| long | |
| status | |
| created_timestamp |
Location Table
| Location Table | |
|---|---|
| Driver_id | Primary key |
| lat | |
| long | |
| updated_timestamp |
How to search for GEO location:
Google S2
- Hilbert Curve
- All location map to a 2^64 number
- If two GeoPointer is close, their Hilbert number would be close too
GeoHash
- Peano Curve
- Base32: 0-9, a-z(without a, i, l, o)
- Better Prefix match on geohash code means closer.
How to search for GeoHash Key in DB?
If SQL is used : LIKE query - select * from table where geohash like "9h9q%" (Still slow)
If Disk noSQL is used: range query - 9q9h0 --> 9q9hz
If Memcache/Redis is used: For each Driver, we store GeoHash in three keys: 9q9hvt, 9q9hv, 9q9h
Considering the high demand of write requests(updating geo location table), Redis is the most suitable DB for storing location info. For trip information, we can store it in SQL, as it is fairly low QPS and "transactional"
Scale
150k QPS is required, Redis > 100 QPS, so is 1-2 redis enough?
- what if one of it is down - lose money
- Solution: DB sharding! (Avoid single point failure and share QPS)
- How to shard? Shard based on city(location) - Geo Fence (define area that is a city)
How to deal with one Redis db is down?
- Replica by Redis it self
- Replica by user
- For each write, write 3 times, with key+(1-3), when read, we read from all 3 places depends on availability
- Use better NoSQL db like Riak/Cassandra since QPS is low after deciding using so many db servers.
- Riak/Cassandra have better reboot/recover ability