mufassall

Шпаргалка · Данные и хранение

Геопоиск: кто рядом

14 мин · Средний · mufassall.dtwin.uz/ru/l/geo-search/

← Открыть урок

Проблема

Приложение такси должно найти десять ближайших свободных водителей вокруг пассажира, а 50 000 водителей присылают свою позицию каждые 4 секунды. Почему обычный индекс не помогает и как geohash, соседние ячейки, quadtree и ячейки S2/H3 отвечают на вопрос «кто в радиусе 2 км» за миллисекунды.

Чему вы научитесь

  • Почему B-tree по широте и долготе всё равно читает полосу через весь город
  • Geohash: близкие точки имеют общий префикс, и ячейка становится одним ключом
  • Края ячеек: всегда смотрите соседей, а затем фильтруйте по точному расстоянию
  • Горячие ячейки в плотном центре: деление quadtree, ячейки S2 и H3, шардинг по ячейке
Итоговая сцена
70%40%10%40%

Диаграмма как код

Итоговая схема урока в виде текста: вставьте её в 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_geo2

Mermaid: последовательность запросов

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 8

D2

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_geo2

PlantUML: последовательность запросов

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

PlantUML: компоненты

@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 0001 200
Пропущен ближайший0%0%
Водители-призраки00

Шаги

  1. Проблема Расстояние считается для каждого водителя

    Пассажир открывает приложение и вызывает машину.

  2. Проблема Индекс по широте читает полосу

    Следующая идея — ограничивающий прямоугольник: широта и долгота в пределах ±2 км, плюс индекс по lat.

  3. Решение Geohash: две координаты в один ключ

    Geohash снова и снова делит мир на сетку и записывает путь короткой строкой.

  4. Проблема Ближайший водитель за границей

    Пассажирка стоит в 40 м от восточной границы своей ячейки.

  5. Решение Читаем ячейку и 8 соседних

    Гео-индекс принимает центр и радиус.

  6. Кейс 12 500 обновлений позиции в секунду

    Приложение каждого водителя присылает позицию каждые 4 секунды: 12 500 записей в секунду.

  7. Решение Убираем замолчавших водителей

    Рядом с позициями индекс хранит, когда каждый водитель последний раз выходил на связь.

  8. Проблема Вечер пятницы в центре города

    В 18:30 в пятницу в одной центральной ячейке ждут 3 100 водителей, а вокруг неё ищут 900 пассажиров в секунду.

  9. Решение Quadtree: ячейки следуют плотности

    Quadtree начинается с одного квадрата на весь город и делит квадрат на четыре, как только в нём больше 200 водителей.

  10. Кейс Ячейки S2 и H3 и шардинг по ячейке

    Библиотеки делают то же на сфере.

  11. Итоги Итог

    Пять правил для «кто рядом».

Термины

Geohash
Широта и долгота кодируются одной короткой строкой: точки с длинным общим префиксом обычно рядом. При поиске поблизости запрашивают нужную ячейку и 8 соседних, ведь близкая точка может оказаться за границей ячейки.
Квадродерево (quadtree)
Дерево, которое делит карту на четыре квадрата, а переполненный квадрат снова на четыре. В центре города ячейки мелкие, в пустыне крупные, поэтому точек в каждой ячейке примерно поровну.