Cheat sheet · Data & storage
Geo search: who is nearby
The problem
A taxi app must find the ten nearest free drivers around a rider, while 50 000 drivers send their position every 4 seconds. Why a normal index does not help, and how geohash, neighbour cells, a quadtree and S2/H3 cells answer "who is within 2 km" in milliseconds.
What you learn
- Why a B-tree on latitude and longitude still reads a stripe of the whole city
- Geohash: nearby points share a prefix, so a cell becomes one key lookup
- Edge cells: always search the neighbours, then filter by exact distance
- Hot cells in a dense centre: quadtree splits, S2 and H3 cells, sharding by cell
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_rider(["Rider app"])
n_drivers(["Driver apps"])
n_api["Matching API"]
n_db[("Drivers DB")]
n_geo{{"Geo index"}}
n_geo2{{"Geo index 2"}}
n_rider --> n_api
n_drivers --> n_api
n_api --> n_geo
n_api --> n_geo
n_api --> n_geo2Mermaid: request sequence
sequenceDiagram
participant n_api as Matching API
participant n_db as Drivers DB
participant n_geo as Geo index
participant n_drivers as Driver apps
participant n_geo2 as Geo index 2
Note over n_api,n_db: Distance computed for every driver
n_api->>n_db: SELECT id, lat, lng FROM drivers
n_db-->>n_api: 10 rows, Seq Scan on drivers
Note over n_api,n_db: An index on latitude reads a stripe
n_api->>n_db: CREATE INDEX drivers_lat ON drivers (lat)#59;
n_db-->>n_api: Index Scan using drivers_lat
Note over n_api,n_geo: Geohash: turn two coordinates into one key
n_api->>n_geo: geohash(41.3110, 69.2797) = tz6x9q
Note over n_api,n_geo: The nearest driver is across the border
n_api->>n_geo: rider at tz6x9q, 40 m from its east border
Note over n_api,n_geo: Read the cell and its 8 neighbours
n_api->>n_geo: GEOSEARCH drivers FROMLONLAT 69.2797 41.3110 BYRADIUS 2 km ASC COUNT 10
n_geo-->>n_api: 1) d_7730 0.12 km
Note over n_drivers,n_api: 12 500 position updates a second
n_drivers->>n_api: POST /v1/drivers/d_1842/location HTTP/1.1
n_api-->>n_drivers: GEOADD drivers 69.2810 41.3121 d_1842
Note over n_api,n_geo: Drop drivers who went silent
n_api->>n_geo: ZADD drivers:seen 1795543324 d_1842
Note over n_api,n_geo: Friday evening in the city centre
n_api->>n_geo: 18:30 Friday, city centre
Note over n_api,n_geo: A quadtree: cells follow density
n_api->>n_geo: quadtree: split a square into 4 when it holds #62; 200 drivers
Note over n_api,n_geo2: S2 and H3 cells, and sharding by cell
n_api->>n_geo2: cover circle(41.3110, 69.2797, 2 km) with H3 res 8D2
direction: right
n_rider: "Rider app" {
shape: rectangle
}
n_drivers: "Driver apps" {
shape: rectangle
}
n_api: "Matching API" {
shape: rectangle
}
n_db: "Drivers DB" {
shape: cylinder
}
n_geo: "Geo index" {
shape: hexagon
}
n_geo2: "Geo index 2" {
shape: hexagon
}
n_rider -> n_api
n_drivers -> n_api
n_api -> n_geo
n_api -> n_geo
n_api -> n_geo2PlantUML: request sequence
@startuml
participant "Matching API" as n_api
database "Drivers DB" as n_db
collections "Geo index" as n_geo
participant "Driver apps" as n_drivers
collections "Geo index 2" as n_geo2
note over n_api, n_db : Distance computed for every driver
n_api -> n_db : SELECT id, lat, lng FROM drivers
n_db --> n_api : 10 rows, Seq Scan on drivers
note over n_api, n_db : An index on latitude reads a stripe
n_api -> n_db : CREATE INDEX drivers_lat ON drivers (lat);
n_db --> n_api : Index Scan using drivers_lat
note over n_api, n_geo : Geohash: turn two coordinates into one key
n_api -> n_geo : geohash(41.3110, 69.2797) = tz6x9q
note over n_api, n_geo : The nearest driver is across the border
n_api -> n_geo : rider at tz6x9q, 40 m from its east border
note over n_api, n_geo : Read the cell and its 8 neighbours
n_api -> n_geo : GEOSEARCH drivers FROMLONLAT 69.2797 41.3110 BYRADIUS 2 km ASC COUNT 10
n_geo --> n_api : 1) d_7730 0.12 km
note over n_drivers, n_api : 12 500 position updates a second
n_drivers -> n_api : POST /v1/drivers/d_1842/location HTTP/1.1
n_api --> n_drivers : GEOADD drivers 69.2810 41.3121 d_1842
note over n_api, n_geo : Drop drivers who went silent
n_api -> n_geo : ZADD drivers:seen 1795543324 d_1842
note over n_api, n_geo : Friday evening in the city centre
n_api -> n_geo : 18:30 Friday, city centre
note over n_api, n_geo : A quadtree: cells follow density
n_api -> n_geo : quadtree: split a square into 4 when it holds > 200 drivers
note over n_api, n_geo2 : S2 and H3 cells, and sharding by cell
n_api -> n_geo2 : cover circle(41.3110, 69.2797, 2 km) with H3 res 8
@endumlPlantUML: components
@startuml
left to right direction
agent "Rider app" as n_rider
agent "Driver apps" as n_drivers
component "Matching API" as n_api
database "Drivers DB" as n_db
stack "Geo index" as n_geo
stack "Geo index 2" as n_geo2
n_rider --> n_api
n_drivers --> n_api
n_api --> n_geo
n_api --> n_geo
n_api --> n_geo2
@endumlRecap
Five rules for "who is nearby".
1) An ordinary index on lat or lng reads a stripe; turn the position into a cell key (geohash, S2, H3). 2) Always read the cell and its neighbours, then sort by exact distance. 3) Keep fast-changing positions in memory and expire silent drivers. 4) Let cells follow density: a quadtree or several resolutions. 5) Shard by a coarse cell and give hot areas their own shard.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Search p95 | 900 ms | 35 ms |
| Drivers read | 50 000 | 1 200 |
| Nearest missed | 0% | 0% |
| Ghost drivers | 0 | 0 |
Steps
- Problem Distance computed for every driver
A rider opens the app and asks for a car.
- Problem An index on latitude reads a stripe
The next idea is a bounding box: latitude and longitude within ±2 km, with an index on
lat. - Fix Geohash: turn two coordinates into one key
Geohash splits the world into a grid again and again, and writes the path as a short string.
- Problem The nearest driver is across the border
A rider stands 40 m from the east border of her cell.
- Fix Read the cell and its 8 neighbours
The geo index takes a centre and a radius.
- Case 12 500 position updates a second
Every driver app sends its position every 4 seconds: 12 500 writes a second.
- Fix Drop drivers who went silent
Next to the positions, the index keeps when each driver was last heard from.
- Problem Friday evening in the city centre
At 18:30 on Friday, 3 100 drivers wait in one central cell and 900 riders a second search around it.
- Fix A quadtree: cells follow density
A quadtree starts with one square for the city and splits a square into four whenever it holds more than 200 drivers.
- Case S2 and H3 cells, and sharding by cell
Libraries do the same on a sphere.
- Recap Recap
Five rules for "who is nearby".
Terms
- Geohash
- Latitude and longitude encoded as one short string: points sharing a long prefix are usually close. A nearby search asks for the cell and its 8 neighbours, because a close point can sit just across a cell border.
- Quadtree
- A tree that splits the map into four squares and splits any crowded square into four again. Cells are small in a city centre and large in a desert, so each cell holds roughly the same number of points.