Работа с геолокациями в режиме highload
При разработке ПО часто возникают интересные задачи. Одна из таких: работа с гео-координатами пользователей. Если вашим сервисом пользуются миллионы пользователей и запросы к РСУБД происходят часто, то выбор алгоритма играет важную роль. О том как оптимально обрабатывать большое количество запросов и искать ближайшие гео-позиции рассказано под катом.
Задача поиска ближайшего соседа
В процессе разработки сервиса push-уведомлений Pushwoosh возникла достаточно известная задача. Имеется много геозон. Геозона задается географическими координатами. Когда пользователь проходит мимо одной из таких геозон(например закусочная) ему должно приходить push-уведомление(«Йоу, заходи к нам и подкрепись с 20% скидкой). Для простоты будем считать радиус всех геозон одинаковым. В условиях большого количества геозон и большого количества пользователей(у нас их 500 миллионов!), которые постоянно перемещаются — поиск ближайшей геозоны должен осуществляться максимально быстро. В англоязычной литературе эта задача известна как Nearest neighbor search. На первый взгляд кажется, что чтобы решить эту задачу нужно посчитать расстояния от пользователя до каждой геозоны и сложность данного алгоритма линейна O(n), где n — количество геозон. Но давайте решим эту задачу за логарифм O(log n)!
Географические координаты
Нужно обратить внимание что x — это долгота, y — широта(Google Maps, Яндекс.Карты и все остальные сервисы указывают долготу первой).
Географические координаты можно перевести в пространственные — просто точка (x,y,z). Кому интересно более подробно можно посмотреть википедию.
Количество знаков после запятой определяет точность:
| Градусы | Дистанция |
|---|---|
| 1 | 111 km |
| 0.1 | 11.1 km |
| 0.01 | 1.11 km |
| 0.001 | 111 m |
| 0.0001 | 11.1 m |
| 0.00001 | 1.11 m |
| 0.000001 | 11.1 cm |
Если нужна точность до одного метра, то следует хранить 5 знаков после запятой.
Geohashing
Пусть у нас есть сервис, которым пользуются миллионы людей, и мы хотим хранить их географические координаты. Очевидный подход в данном случае завести в таблице два поля — широта/долгота. Можно использовать double precision(float8), который занимает 8 байт. В итоге нам потребуется 16 байт для хранения координат одного пользователя.
Но есть и другой подход, который называется geohashing. Идея простая. Широта и долгота кодируется в число, которое затем кодируется в base-32. Карта разбивается на матрицу размера 4×8 и каждой ячейке присваивается некоторый символ(alphanumeric). 
Чтобы повысить точность, каждая ячейка разбивается на более мелкие, при этом к коду добавляются символы(если быть точным цифры, а после происходит кодирование в base-32).
Разбиение можно производить до необходимой точности. Такой код уникален для каждой точки.
Подробно алгоритм построения я описывать не буду, о нем можно почитать в википедии. Его идея похожа на арифметическое кодирование. Данный код обратим. Многие технологии уже имеют встроенные методы для работы с гео-хешами, например, MongoDB.
Пример: координаты 57.64911,10.40744 будут закодированы в u4pruydqqvj (11 символов). Если требуется меньшая точность, то и код будет меньше.
Особенность данного кода в том, что ОБЫЧНО близлежащие точки имеют одинаковый префикс. И можно посчитав разницу между гео-хешами определить близость двух точек. Но к сожалению данный алгоритм не точен, это хорошо видно из предыдущих изображений. Ячейки с кодами 7 и 8 находятся дальше друг от друга, чем ячейки 2 и 8.
В качестве примера приведу картинку, где гео-хеш дает неверный результат(geohashdelta — разность между геохешами без base32)
Если точностью в задаче можно пренебречь, то можно создать в таблице поле geohash, добавить по нему индекс и производить поиск за логарифм.
Полный перебор
Можно написать хранимую процедуру
Но в итоге будет Seq Scan, что очень не приятно.
K-d tree и R tree
Что делать, когда точностью пренебречь не получается? Для этого уже есть специальная структура данных K-d tree. Можно перевести широту и долготу в (x,y,z) построить по ним дерево и производить поиск по дереву в среднем за логарифм.
PostGIS
PostGIS — это расширение, которое значительно расширяет обработку географических объектов в РСУБД PostgreSQL.
Для решения нашей задачи будет использовать трехмерную систему координат SRID 4326(WGS 84). Данная система координат определяет координаты относительно центра масс Земли, погрешность составляет менее 2 см.
Если у вас ubuntu-подобная система, то PostGIS можно установить из пакета(для PostgreSQL 9.1):
И подключить необходимые экстеншены:
С помощью \dx можно посмотреть все установленные экстеншены.
Создадим отношение с индексом по полю location
После чего для поиска ближайшей геозоны можно воспользоваться следующим запросом
Здесь — distance operator. Мы посчитали дистанцию и нашли ближайшие 10 геозон!
СТОП скажите Вы! Ведь данный запрос должен просмотреть все записи в таблице и посчитать расстояние до каждой геозоны O(n).
Давайте посмотрим EXPLAIN ANALYZE запроса
Index Scan! Где же магия?
GiST-индекс реализованный PostGIS поддерживает distance operator при поиске. Также данный индекс может быть составным!
Данный функционал можно реализовать и без использования PostGIS, воспользовавшись индексом btree-gist, но PostGIS предоставляет удобные методы для перевода широты и долготы в WGS 84.
