Part 4 of 8 · 2 min read
Location
A fast index of moving points.
The question is "which free drivers are within 3 km of this point?" Scanning 2 million drivers per request would be too slow at 1,200 requests a second. Use a geospatial index (page 1 and Level 3 for related ideas).
Option 1: geohash. Cut the map into cells. A cell's name is a short string, and cells that share a prefix are near each other. Keep a map from cell to the set of drivers in it. A search computes the cell of the rider and its 8 neighbours, and reads their driver sets. A driver who moves to another cell is removed from the old set and added to the new one.
Option 2: quadtree or grid. A quadtree splits crowded areas into smaller cells. It adapts to density: a city centre has many small cells and a desert has few large ones.
Option 3: cell ids of a sphere (such as S2 or H3). Fixed hierarchical cells that cover the earth, with good neighbour lookups. Used in practice by large ride companies.
Where to keep it. In memory, in a fast store, partitioned by cell or region. A key-value store with geo queries, or a custom service, works. Because each update replaces the old position, no history is kept in this index (history is sent to a log for analytics, through a message queue, Level 12).
Hot cells. Airports and events concentrate drivers in one cell. Partition by smaller cells and spread them over servers, and limit the result size.
A worked example (made up). A search uses cells of about 1 km. The rider's cell and 8 neighbours cover about 3 km × 3 km. If each cell holds an average of 20 free drivers, the search reads about 180 candidates, then filters by true distance and ranks the best 10. That is far less than 2,000,000.
Updates. 500,000 updates a second is spread over many location servers by region. Updates are batched, and only a move across a cell edge changes the index, but every update still refreshes the position and a "last seen" time. A driver with no update for 30 seconds is treated as offline.
Read it as
The location index is a cache of "where is everyone right now". It can be rebuilt in seconds from incoming updates, so it needs speed more than durability.
Check yourself: 1. Why not scan all drivers? 2. How does a geohash search find neighbours? 3. Why is no history kept in the index?