Requirements
- Drivers stream their location every few seconds.
- A rider request must find nearby available drivers fast.
- The system must handle dense city centers and sparse rural areas.
High level design
The heart of the system is a spatial index that answers nearby queries efficiently.
- Location ingestion: drivers send updates to a location service that writes to an in memory geospatial store.
- Spatial index: encode each location into a geohash or an S2 cell so nearby points share a prefix or cell id.
- Matching: a rider request looks up the rider cell and adjacent cells, ranks candidates by distance and eta, then dispatches an offer.
Bottlenecks
- Update volume: millions of frequent writes mean the index lives in memory and is partitioned by region.
- Hot cells: busy downtown cells get split into finer cells to spread load.
- Stale locations: expire entries that have not updated recently so matches use fresh positions.
Tradeoffs
- Coarse cells reduce index size but return more candidates to filter.
- Fine cells give precise neighborhoods but multiply cell management overhead.
Key idea
Location matching is a high write geospatial nearest neighbor problem solved by partitioning an in memory cell index by region and querying a rider cell plus its neighbors.