Шпаргалка · Данные и хранение
Геопоиск: кто рядом
Проблема
Приложение такси должно найти десять ближайших свободных водителей вокруг пассажира, а 50 000 водителей присылают свою позицию каждые 4 секунды. Почему обычный индекс не помогает и как geohash, соседние ячейки, quadtree и ячейки S2/H3 отвечают на вопрос «кто в радиусе 2 км» за миллисекунды.
Чему вы научитесь
- Почему B-tree по широте и долготе всё равно читает полосу через весь город
- Geohash: близкие точки имеют общий префикс, и ячейка становится одним ключом
- Края ячеек: всегда смотрите соседей, а затем фильтруйте по точному расстоянию
- Горячие ячейки в плотном центре: деление quadtree, ячейки S2 и H3, шардинг по ячейке
Диаграмма как код
Итоговая схема урока в виде текста: вставьте её в Jira, GitLab, GitHub, Notion или документацию, там Mermaid рисуется сам. Есть варианты для D2 и PlantUML (Confluence, IntelliJ).
Mermaid: схема
flowchart LR
n_rider(["Приложение пассажира"])
n_drivers(["Приложения водителей"])
n_api["API подбора"]
n_db[("БД водителей")]
n_geo{{"Гео-индекс"}}
n_geo2{{"Гео-индекс 2"}}
n_rider --> n_api
n_drivers --> n_api
n_api --> n_geo
n_api --> n_geo
n_api --> n_geo2Mermaid: последовательность запросов
sequenceDiagram
participant n_api as API подбора
participant n_db as БД водителей
participant n_geo as Гео-индекс
participant n_drivers as Приложения водителей
participant n_geo2 as Гео-индекс 2
Note over n_api,n_db: Расстояние считается для каждого водителя
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: Индекс по широте читает полосу
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: две координаты в один ключ
n_api->>n_geo: geohash(41.3110, 69.2797) = tz6x9q
Note over n_api,n_geo: Ближайший водитель за границей
n_api->>n_geo: rider at tz6x9q, 40 m from its east border
Note over n_api,n_geo: Читаем ячейку и 8 соседних
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 обновлений позиции в секунду
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: Убираем замолчавших водителей
n_api->>n_geo: ZADD drivers:seen 1795543324 d_1842
Note over n_api,n_geo: Вечер пятницы в центре города
n_api->>n_geo: 18:30 Friday, city centre
Note over n_api,n_geo: Quadtree: ячейки следуют плотности
n_api->>n_geo: quadtree: split a square into 4 when it holds #62; 200 drivers
Note over n_api,n_geo2: Ячейки S2 и H3 и шардинг по ячейке
n_api->>n_geo2: cover circle(41.3110, 69.2797, 2 km) with H3 res 8D2
direction: right
n_rider: "Приложение пассажира" {
shape: rectangle
}
n_drivers: "Приложения водителей" {
shape: rectangle
}
n_api: "API подбора" {
shape: rectangle
}
n_db: "БД водителей" {
shape: cylinder
}
n_geo: "Гео-индекс" {
shape: hexagon
}
n_geo2: "Гео-индекс 2" {
shape: hexagon
}
n_rider -> n_api
n_drivers -> n_api
n_api -> n_geo
n_api -> n_geo
n_api -> n_geo2PlantUML: последовательность запросов
@startuml
participant "API подбора" as n_api
database "БД водителей" as n_db
collections "Гео-индекс" as n_geo
participant "Приложения водителей" as n_drivers
collections "Гео-индекс 2" as n_geo2
note over n_api, n_db : Расстояние считается для каждого водителя
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 : Индекс по широте читает полосу
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: две координаты в один ключ
n_api -> n_geo : geohash(41.3110, 69.2797) = tz6x9q
note over n_api, n_geo : Ближайший водитель за границей
n_api -> n_geo : rider at tz6x9q, 40 m from its east border
note over n_api, n_geo : Читаем ячейку и 8 соседних
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 обновлений позиции в секунду
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 : Убираем замолчавших водителей
n_api -> n_geo : ZADD drivers:seen 1795543324 d_1842
note over n_api, n_geo : Вечер пятницы в центре города
n_api -> n_geo : 18:30 Friday, city centre
note over n_api, n_geo : Quadtree: ячейки следуют плотности
n_api -> n_geo : quadtree: split a square into 4 when it holds > 200 drivers
note over n_api, n_geo2 : Ячейки S2 и H3 и шардинг по ячейке
n_api -> n_geo2 : cover circle(41.3110, 69.2797, 2 km) with H3 res 8
@endumlPlantUML: компоненты
@startuml
left to right direction
agent "Приложение пассажира" as n_rider
agent "Приложения водителей" as n_drivers
component "API подбора" as n_api
database "БД водителей" as n_db
stack "Гео-индекс" as n_geo
stack "Гео-индекс 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Итог
Пять правил для «кто рядом».
1) Обычный индекс по lat или lng читает полосу; превратите позицию в ключ ячейки (geohash, S2, H3). 2) Всегда читайте ячейку и её соседей, потом сортируйте по точному расстоянию. 3) Быстро меняющиеся позиции держите в памяти и удаляйте замолчавших водителей. 4) Пусть ячейки следуют плотности: quadtree или несколько разрешений. 5) Шардируйте по крупной ячейке и давайте горячим районам собственный шард.
Показатели: в начале и в конце
| Показатель | В начале | В конце |
|---|---|---|
| p95 поиска | 900 мс | 35 мс |
| Прочитано водителей | 50 000 | 1 200 |
| Пропущен ближайший | 0% | 0% |
| Водители-призраки | 0 | 0 |
Шаги
- Проблема Расстояние считается для каждого водителя
Пассажир открывает приложение и вызывает машину.
- Проблема Индекс по широте читает полосу
Следующая идея — ограничивающий прямоугольник: широта и долгота в пределах ±2 км, плюс индекс по
lat. - Решение Geohash: две координаты в один ключ
Geohash снова и снова делит мир на сетку и записывает путь короткой строкой.
- Проблема Ближайший водитель за границей
Пассажирка стоит в 40 м от восточной границы своей ячейки.
- Решение Читаем ячейку и 8 соседних
Гео-индекс принимает центр и радиус.
- Кейс 12 500 обновлений позиции в секунду
Приложение каждого водителя присылает позицию каждые 4 секунды: 12 500 записей в секунду.
- Решение Убираем замолчавших водителей
Рядом с позициями индекс хранит, когда каждый водитель последний раз выходил на связь.
- Проблема Вечер пятницы в центре города
В 18:30 в пятницу в одной центральной ячейке ждут 3 100 водителей, а вокруг неё ищут 900 пассажиров в секунду.
- Решение Quadtree: ячейки следуют плотности
Quadtree начинается с одного квадрата на весь город и делит квадрат на четыре, как только в нём больше 200 водителей.
- Кейс Ячейки S2 и H3 и шардинг по ячейке
Библиотеки делают то же на сфере.
- Итоги Итог
Пять правил для «кто рядом».
Термины
- Geohash
- Широта и долгота кодируются одной короткой строкой: точки с длинным общим префиксом обычно рядом. При поиске поблизости запрашивают нужную ячейку и 8 соседних, ведь близкая точка может оказаться за границей ячейки.
- Квадродерево (quadtree)
- Дерево, которое делит карту на четыре квадрата, а переполненный квадрат снова на четыре. В центре города ячейки мелкие, в пустыне крупные, поэтому точек в каждой ячейке примерно поровну.