mufassall

Cheat sheet · Data & storage

Geo search: who is nearby

14 min · Intermediate · mufassall.dtwin.uz/en/l/geo-search/

← Open the lesson

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
Final scene
70%40%10%40%

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_geo2

Mermaid: 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 8

D2

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_geo2

PlantUML: 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
@enduml

PlantUML: 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
@enduml

Recap

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

MetricStartEnd
Search p95900 ms35 ms
Drivers read50 0001 200
Nearest missed0%0%
Ghost drivers00

Steps

  1. Problem Distance computed for every driver

    A rider opens the app and asks for a car.

  2. 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.

  3. 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.

  4. Problem The nearest driver is across the border

    A rider stands 40 m from the east border of her cell.

  5. Fix Read the cell and its 8 neighbours

    The geo index takes a centre and a radius.

  6. Case 12 500 position updates a second

    Every driver app sends its position every 4 seconds: 12 500 writes a second.

  7. Fix Drop drivers who went silent

    Next to the positions, the index keeps when each driver was last heard from.

  8. 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.

  9. 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.

  10. Case S2 and H3 cells, and sharding by cell

    Libraries do the same on a sphere.

  11. 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.