Работа с геопространственными данными заведомо сложная задача, хотя бы потому что широта и долгота это числа с плавающей запятой и они должны быть очень высокоточными. К тому же, казалось бы, широта и долгота могут быть представлены в виде сетки, но на самом деле нет, не могут, просто потому что Земля не плоская, а математика - это сложная наука.

Например, чтобы определить расстояние большого круга между двумя точками сферы, исходя из их широты и долготы используется формула гаверсинуса, которая выглядит так:

Другая частая задача, связанная с широтой и долготой, это поиск количества точек в радиусе на поверхности Земли. То есть дан большой шар (Земля) и вы пытаетесь найти точки в радиусе на этом шаре. Но Земля, на самом деле, это не идеальная сфера, это все таки эллипсоид. Как можно догадаться, математические вычисления для такой операции становятся довольно сложными.

В этой статье мы разберемся как Redis нам может помочь свести вычисления к минимуму при работе с геоданными.

Redis

Redis, расшифровывается как Remote Dictionary Server и является быстрым, опенсорс хранилищем данных типа ключ-значение (key-value).

Сегодня Redis является одним из самых популярных опенсорс решений, и назван Stack Overflow "Самой Любимой" базой данных на протяжении 5 лет. Из-за своей скорости работы, Redis является популярным выбором для кешинга, менеджмента сессий, игр, аналитики, геопространственных данных, и т.д.

Вернемся к геоданным. Что такое геохэш?

Геохэш - это система представления координат в виде строки. Чтобы преобразовать широту и долготу в строку в геохэшинге используется кодировка Base32. Например геохэш координат Дворцовой площади в Санкт-Петербурге будет выглядеть так: udtscze2chgq. Переменная длина геохэша представляет переменную точность координат, другими словами чем короче геохэш, тем менее точные координаты он представляет. То есть более короткий геохэш будет представлять ту же самую геолокацию, но с меньшей точностью. Попробовать кодировку координат в геохэш можно на сайте geohash.org

Как Redis хранит геоданные?

Хранение геопространственных данных реализовано в Redis с использованием сортированных списков (ZSET) в качестве базовой структуры данных, но с кодированием и декодированием данных о местоположении на лету и новым API. Это значит, что индексирование, поиск и сортировку по конкретному местоположению можно скинуть на Redis с очень небольшим количеством строк кода и минимальными усилиями используя встроенные команды: GEOADD, GEODIST, GEORADIUS и GEORADIUSBYMEMBER.

Geo Set является основой для работы с геоданными в Redis — это структура данных, предназначенная для управления геопространственными индексами. Каждый Geo Set состоит из одного или нескольких элементов, каждый из которых состоит из уникального идентификатора, и пары координат - долготы и широты.

Команды для работы с геоданными

Чтобы добавить новый список (или новый элемент в существующий список) в хранилище Redis используется команда GEOADD. Для наглядности я буду приводить примеры команд в Redis, а также в Ruby клиенте для работы с Redis:

# Пример Redis:
GEOADD "friends" -74.00020246342898 40.717855101298305 "Mark B."
# Пример Ruby:
RedisClient.geoadd("friends", -74.00020246342898, 40.717855101298305, "Mark B.")    

Эти команды добавляют в Geo Set c названием "friends" координаты локации "Mark B.". В случае если Geo Set с таким названием нет в хранилище Redis, то он будет создан. Новая запись будет добавлена в индекс только в том случае, если записи с таким названием ("Mark B.") еще нет в списке. То есть Mark B. является уникальным идентификатором.

Также возможно добавление сразу нескольких записей с одним вызовом GEOADD, что может помочь снизить нагрузку на сеть и базу данных. Идентификаторы записей обязательно должны быть уникальными:

# Пример Redis:
GEOADD "friends" -74.00020246342898 40.717855101298305 "Mark B." -73.99472237472686 40.725856700515855 "Janet A."
# Пример Ruby:
RedisClient.geoadd("friends", -74.00020246342898, 40.717855101298305, "Mark B.", -73.99472237472686, 40.725856700515855, "Janet A.")

Для обновления индекса записи используется та же команда. Если GEOADD вызывается с уже существующими в Geo Set записями, Redis просто обновляет геоданные для это записи, как только Mark B. начинает движение, его локация может быть обновлена:

# Пример Redis:
GEOADD "friends" -76.99265963484487 38.87275545298483 "Mark B."
# Пример Ruby:
RedisClient.geoadd("friends", -76.99265963484487, 38.87275545298483, "Mark B.")    

Помимо добавления и обновления, естественно записи могут быть удалены из индекса. Для удаления записи из Geo Set в Redis предоставлена команда ZREM. ZREM принимает название индекса, из которого нужно удалить записи, и идентификаторы записей для удаления:

# Пример Redis:
ZREM friends "Mark B." "Janet A."
# Пример Ruby:
RedisClient.zrem("friends", "Mark B.", "Janet A.")

Гео индекс можно удалить полностью и, так как он хранится как ключ Redis, можно использовать команду DEL:

# Пример Redis:
DEL friends
# Пример Ruby:
RedisClient.del("friends")

Стоит учесть, что в Redis есть механизм экспирации индексов, если вы не указываете для индекса срок экспирации, то он не будет экспирирован никогда и будет занимать память. Чтобы этого не происходило, нужно использовать команду EXPIRE, передавая название индекса и число секунд для экспирации:

# Пример Redis:
EXPIRE friends 1000
# Пример Ruby:
RedisClient.expire("friends", 1000)

В Redis используется полу lazy механизм экспирации, это значит что индекс не экспирируется до момента пока к нему не обратились, если при обращении оказывается что время экспирации прошло, то результат не возвращается, а сам объект удаляется из хранилища. То есть до тех пор пока мы не запросим Geo Set он будет храниться в памяти бесконечно долго.

В Redis существует второй уровень экспирации - активный и рандомный. То есть это сборщик мусора, который рандомно читает разные ключи, и при обращении к ключу происходит стандартный механизм проверки экспирации.

Но, к сожалению, в Redis нет возможности экспирации непосредственно записей в индексе. Такую фичу придется разрабатывать самостоятельно.

Что с чтением и поиском по геоданным?

Есть несколько способов для чтения записей из индекса. Для начала можно использовать команды ZRANGE и ZSCAN. Эти команды итерируют по всем записям в индексе. Например чтобы вернуть все записи в индексе:

# Пример Redis:
ZRANGE friends 0 -1
# Пример Ruby:
RedisClient.zrange("friends", 0, -1)

Применительно к геоданным, есть две комманды для получения локации записи из индекса. Первая команда GEOPOS - возвращает координаты записи в индексе:

# Пример Redis:
GEOPOS friends "Mark B."
# Пример Ruby:
RedisClient.geopos("friends", "Mark B.")

Втора команда GEOHASH возвращает координаты записи в индексе закодированные в геохэш:

# Пример Redis:
GEOHASH friends "Mark B."
# Пример Ruby:
RedisClient.geohash("friends", "Mark B.")

Чтобы получить расстояние между двумя записями в индексе можно использовать команду GEODIST:

# Пример Redis:
GEODIST friends "Mark B." "Janet A."
# Пример Ruby:
RedisClient.geodist("friends", "Mark B.", "Janet A.", "km")

Результат команды будет возвращен дефолтно в метрах. Указать нужные единицы измерения можно передав команде четвертый аргумент, например: km для километров, m для метров, mi - для миль, ft - для футов.

Для поиска по индексу так же используются команды GEORADIUS и GEORADIUSBYMEMBER (для Redis версий меньше 6.2) или GEOSEARCH (для версий старше 6.2).

GEORADIUS и GEORADIUSBYMEMBER принимают параметры WITHDIST (выводит результаты + дистанцию от указанной точки/записи) и WITHCOORD (выводит результаты + координаты записей), а также параметр сортировки ASC или DESC (сортировка по дальности от точки):

# Примеры Redis:
GEORADIUS friends -73 40 200 km WITHDIST

вернет:
1) 1) "Mark B."
   2) "190.4424"
2) 1) "Janet A."
   2) "56.4413"

GEORADIUS friends -73 40 200 km WITHCOORD

вернет:
1) 1) "Mark B."
   2) 1) "-74.00020246342898"
      2) "40.717855101298305"
2) 1) "Janet A."
   2) 1) "-73.99472237472686
      2) "40.725856700515855"

GEORADIUS friends -73 40 200 km WITHDIST WITHCOORD
1) 1) "Mark B."
   2) "190.4424"
   3) 1) "-74.00020246342898"
      2) "40.717855101298305"
2) 1) "Janet A."
   2) "56.4413"
   3) 1) "-73.99472237472686
      2) "40.725856700515855"

# Пример Redis:
GEORADIUSBYMEMBER friends "Mark B." 100 km

Вернет:
1) “Janet A.”

# Пример Ruby:
RedisClient.georadiusbymember("friends", "Mark B.", 100, "km")

Команда GEOSEARCH для новых версий Redis имеет схожий синтаксис, и решает те же задачи. Синтаксис команды выглядит так:

Примеры Redis:
GEOSEARCH friends FROMMEMBER "Mark B." BYRADIUS 100 km ASC WITHCOORD WITHDIST WITHHASH
# вернет все записи в радиусе 100 км от Mark B. с координатами, расстоянием и геохэшем

GEOSEARCH friends FROMLONLAT -74.00020246342898 40.717855101298305" BYRADIUS 200 mi DESC COUNT 2
# вернет максимум 2 записи сортированые от самой дальней до самой близкой в радиусе 200 миль от центра с указанными координатами

Заключение

Простота реализации определения местоположения в Redis позволяет не только легко справляться с большим потоком геоданных, но и внедрять интеллектуальные функции в дополнение к простой обработке. Например, запрос записей в радиусе может помочь вам реализовать простые функции, например найти интересные места поблизости, отдавая пользователю только ближайшие к нему варианты. Если ваше приложение использует геоданные в каком либо виде, рассмотрите перенос сложных вычислений на Redis, возможно это повысит эффективность вашего приложения.

Для более детальной информации по использованию Redis и работы с геоданными, предлагаю ознакомиться с Redis for Geospatial Data whitepaper