Geo Search: MongoDB vs S2 Geometry

Степан Пестерников, Avito.

Transcript

1. Москва, 2020 Geo Search MongoDB vs S2 Geometry
2. Москва, 2020 Пестерников Степан Backend разработчик • Работаю в Avito BX Geo • GitHub: @pshopper
3. Москва, 2020 Go и Geo в Avito • 12 сервисов на Go • Хранилище гео-объектов на MongoDB • Более 25000 запросов в секунду
4. Москва, 2020 Go и Geo в Avito
5. Москва, 2020 Go и Geo в Avito
6. Москва, 2020 Go и Geo в Avito
7. Москва, 2020 Немного теории • Геоданные • Полигоны
8. Москва, 2020 Геоданные • Долгота • Широта • Высота
9. Москва, 2020 Полигон
10. Москва, 2020 Гео-поиск Задачи: • Рассчёт расстояние от точки до точки или полигона • Поиск ближайшего полигона или точки • Попадание точки в полигон
11. Москва, 2020 Немного истории MongoDB Replica Set Geo Queries Bottleneck 6k connections 300 Mbps Geo Queries Geo Queries … PHP PHP PHP
12. Москва, 2020 Миграция на Go Geo Queries … PHP PHP PHP Go PHP Go MongoDB Replica Set RPC RPC Go RPC Geo Queries Geo Queries … 100 Connections
13. Москва, 2020 Что дальше? Новые проблемы? • Поиск ближайшего полигона в MongoDB выполняется более 500ms • Задача проверки на попадание в полигон более 20 миллионов координат • Запросы мимо кэша • Задержки сети и точки отказа • MongoDB не покрывает наши запросы по функциональности • Постоянное обновление геоданных
14. Москва, 2020 Geo Database & Libraries • Redis • Elastic • Postgres • Tile38 & BuntDB • Go S2 Geometry
15. Москва, 2020 Tile38 • RealTime geofencing • Redis протокол • R-Tree индекс • Поиск ближайшего (k-nearest neighbor algorithm)
16. Москва, 2020 S2 Geometry • S2 Cells • Shape Index
17. Москва, 2020 S2 Cells
18. Москва, 2020 S2 Cells
19. Москва, 2020 S2 Polygons
20. Москва, 2020 Go S2 Geometry vs MongoDB • MongoDB использует S2 Geometry C++ • Неоптимальный алгоритм поиска ближайшего полигона или точки
21. Москва, 2020 Неоптимальный алгоритм MongoDB … Точка Точка … … …
22. Москва, 2020 Неоптимальный алгоритм MongoDB Так как все Авито- локации сосредоточены в полигоне России, то при поиске из-за пределов полигона, алгоритм сводится к «поиску полным перебором»
23. Москва, 2020 Миграция на Go S2 Geometry • Особенности работы и реализации • Нагрузочное тестирование • Сравнение с MongoDB
24. Москва, 2020 Особенности работы • Проверка на вхождение в полигон через Shape Index • В Shape Index не портирован поиск ближайшего полигона* • Поиск ближайшего полигона на основе S2 Cells и B-Tree индекса *https://github.com/golang/geo/issues/59
25. Москва, 2020 Особенности реализации • Координаты должны идти по порядку в одном направлении • Не должно быть повторяющихся координат • Обязательно проверять валидность • Возможно расширять встроенный тип полигона
26. Москва, 2020 Нагрузочное тестирование 6 подов в k8s по 500 Mi Memory и 1 CPU
27. Москва, 2020 Особенности реализации Построение Shape Index* *Фикс - https://github.com/golang/geo/pull/65
28. Москва, 2020 Сравнение с MongoDB 3 дата-ноды MongoDB на железе по 8 Gb Memory и 8 CPU
29. Москва, 2020 В итоге • Поиск ближайшего полигона ускорился в 60 раз • Проверка на вхождение в полигон ускорилась в 500 раз • Возможность держать нагрузку более 10000 запросов в секунду • Гео-индекс хранится в памяти приложения • Устранены задержки сети и точки отказа
30. Москва, 2020 В итоге • Появились возможности проводить эксперименты и АБ-тесты с полигонами • Снизили трудозатраты на обновление геоданных • Избавились от миграций
31. Москва, 2020 Полезные ссылки • https://s2geometry.io/ • https://habr.com/ru/company/badoo/blog/352754/ • https://tile38.com/ • https://docs.mongodb.com/manual/geospatial-queries/ • https://github.com/golang/geo
32. Москва, 2020 Вопросы?