В интернете много статей о том, как можно использовать Redis для реализации задач гео‑поиска (поиск объектов поблизости, поиск объектов внутри определенной области и т..д). Во многих упоминается о том, что редис можно легко масштабировать горизонтально, добавляя шарды в кластер, при этом логика распределения данных по шардам он берет на себя, без необходимости реализовывать ее на уровне приложения. На деле же все оказывается не совсем так или совсем не так.
Для тех, кто не хочет много читать про то, как мы реализовывали гео‑поиск — ключевые слова: geoadd, georadius, пространственные индексы h3. Всем остальным — добро пожаловать под кат.
Предыстория
У нас в проекте мы собираем координаты с устройств и складываем эти координаты в БД Postgres. В функционале приложения есть возможность выбрать устройства, находящиеся внутри определенного радиуса от заданного местоположения. Пока данных было мало, все отлично работало внутри Postgres, поиск был реализован через расширение PostGIS, но когда темп их добавления перевалил за 50 ГБ за два‑три дня, запросы на гео‑поиск начали падать с таймаутами. Вдобавок, в Postgres мы храним все координаты устройств за определенный период наблюдения, а гео‑поиск нужен только по последним актуальным координатам устройств. Кажется, что оптимизировать Postgres — это тупиковый путь при постоянно увеличивающемся потоке данных и было принято решение разделить историю хранения и гео‑поиск.
В качестве движка для гео‑поиска мы выбрали Redis, потому что у нас уже к этому моменту был его шардированный кластер и разработчики умеют с ним работать. По документации, гео‑поиск в нем выглядит очень просто (и не забываем про статьи в интернете) и мы решили использовать его.
Гео‑поиск
Итак, по документации https://redis.io/docs/latest/develop/data‑types/geospatial/ все выглядит действительно очень просто. Здесь и далее код на python
Добавление координат пользователя:
self.r.geoadd("users_geo_location", lng, lat, user_id)Поиск пользователей в определенном радиусе:
users = self.r.georadius("users_geo_location", lng, lat, '1', unit='km')Все. Заполняем редис данными, пишем тестовый API метод поиска, пробуем, смотрим на результат. Без визуализации тут будет сложно что‑то протестировать, поэтому пользуемся API Яндекс карт для отображения данных
Вот так визуально выглядит поиск устройств в радиусе 1 километр. Метод возвращает нам идентификаторы 6 устройств, все кажется работает.
Начинаем разбираться дальше. Гео‑индекс под капотом у редиса — это упорядоченный массив zset (https://redis.io/docs/latest/develop/data‑types/sorted‑sets/). Созданный гео‑индекс имеет ключ users_geo_location, данные в редисе шардируются на основании наименования ключа. Таким образом у нас нет возможности «размазать» данные с координатами по шардам, все они будут записаны в единственный отсортированный массив и будут обрабатываться единственным шардом в кластере.
Для кого‑то это может быть не проблема, но для нас это потенциально узкое место, посмотрим, что можно с этим сделать.
Разбиение гео‑индекса
Мы пришли к выводу, что на стороне приложения мы должны реализовать запись данных координат не в единственный большой индекс, а создать много небольших индексов, которые будут распределены редисом по шардам кластера. Соответственно, координаты нам нужно группировать в какие‑то области и осуществлять поиск внутри этих областей. Для каждой из таких областей нужно получить уникальную строку, чтобы использовать ее в качестве ключа записи.
К счастью, самостоятельно нам тут придумывать ничего не нужно, существуют алгоритмы пространственного хеширования, которые как раз этим и занимаются, среди них S2, H3, geohash. Про некоторые уже рассказывалось на хабре — раз, два, три.
Принцип работы этих алгоритмов, если говорить простыми словами, следующий. Поверхность планеты разбивается на определенные области. По географическим координатам можно вычислить к какой области она принадлежит. Области имеют иерархию для разных масштабов карты (разный размер ячеек). В алгоритмах реализованы методы вычисления гео‑индекса (хэша) по координатам и обратно, поиск родительских или дочерних ячеек и т. д.
Мы остановились на H3 — https://h3geo.org/docs/
Вот так выглядит карта, разделенная на ячейки H3 c разрешением 3 (около 40 тыс ячеек на всю поверхность). Поиграться с размером ячеек можно тут.
В итоге, наш алгоритм помещения текущих координат устройства в Redis становится следующим
По прилетевшим координатам устройства высчитываем индекс h3 ячейки, в которую попадают эти координаты
Формируем ключ записи в Redis вида «h3_key:users_geo_location»
Записываем данные в гео‑индекс редиса через метод geoadd по сформированному ключу
Код на python для записи массива координат будет следующим:
def write_geo_cluster_data(self, geo_data):
p = self.cluster.pipeline()
for geo in enumerate(geo_data):
h3_id = h3.latlng_to_cell(lat=geo['lat']), lng=geo['lng']), res=3)
p.geoadd(h3_id + ":users_geo_location", geo['lng'], geo['lat'], geo['user_id'])
p.execute()Алгоритм поиска преобразуется к следующему
По координатам центра круга, в котором мы ищем устройства высчитываем индекс h3 ячейки
Выполняем поиск georadius в записи с ключом «h3_key:users_geo_location»
def find_geo_cluster_users(self, coords):
h3_id = h3.latlng_to_cell(lat=geo['lat']), lng=geo['lng']), res=3)
self.cluster.georadius(h3_id + ":users_geo_location", coords[1], coords[0], '1', unit='km')После заполнения данных можно посмотреть, как координаты распределяются по ячейкам H3
Теперь мы понимаем, что все наши координаты будут записаны в сотни или тысячи независымых ключей, которые редис разложит по шардам кластера.
Ниже на картинке статистика по ключам по двум шардам — почти равномерно.
Все казалось бы хорошо, но…
Поиск данных на пересечинии ячеек
Из‑за распределения координат по ячейкам и поиска данных в одной из ячеек, соответствующей центру круга поиска, мы сталкиваемся с ситуацией, когда искомые координаты лежат рядом с границей двух ячек, поиск мы ведем в одной из них и не можем найти данные в соседней.
Визуально это будет выглядеть так. Синяя диагональная линия — граница двух ячеек. Центр круга поиска лежит в нижней правой, мы высчитаем ее h3 хэш и не найдем в данном случае шесть координат в верхней левой. Поиск вернет только один результат, а на самом деле их семь.
Очевидно, что нам нужно выполнять поиск не по единственной ячейке, а по тем, на которые попадает круг поиска. Самый простой вариант — в лоб. Получить всех соседей текущей ячейки и выполнить поиск по ним. Решение очень простое, но мы вместо одного запроса на поиск всегда будем выполнять 7 запросов (текущая и шесть соседних), если нагрузка позволяет, можно пойти по этому пути, но хочется не делать лишних запросов к редису.
Правильным будет следующий подход.
Превращаем наш круг поиска в полигон — набор координат на поверхности земли, описывающий окружность в формате GeoJson
С помощью библиотеки h3 находим ячейки заданного разрешения, которые перекрывают найденный полигон
Выполняем поиск внутри найденных ячеек
Начнем по порядку. Для преобразования окружности требуемого радиуса в географические координаты используем библиотеку Proj (https://proj.org/en/stable/) которая может преобразовывать координаты из одной проекции в другую. Немного подробнее про проекции можно почитать на хабре вот тут.
Метод преобразования будет следующим:
def geodesic_point_buffer(lat, lon, radius):
from pyproj import CRS, Transformer
from shapely.geometry import Point
from shapely.ops import transform
# Azimuthal equidistant projection
aeqd_proj = CRS.from_proj4(f"+proj=aeqd +lat_0={lat} +lon_0={lon} +x_0=0 +y_0=0")
tfmr = Transformer.from_proj(aeqd_proj, aeqd_proj.geodetic_crs)
buf = Point(0, 0).buffer(radius * 1000) # distance in km
return transform(tfmr.transform, buf).exterior.coords[:]В результате выполнения метод вернет нам набор координат в формете GeoJson, соответствующий кругу на поверхности планеты заданным разиусом. Далее необходимо найти ячейки h3, которые «накрывают» вычисленный круг для выбранного масштаба. Выпоняется это следующим методом.
def find_cells_for_circle(self, lat, long):
outer_boundary = geodesic_point_buffer(lat, long, 1)
reverse_outer_boundary = [(point[1], point[0]) for point in outer_boundary]
poly = h3.LatLngPoly(reverse_outer_boundary)
cells = h3.h3shape_to_cells_experimental(poly, 3, 'overlap')
return cellsЧто тут необходимо прокомментировать. Во‑первых, для координат полигона пришлось изменить порядок следования lat и lng, потому что в результате, который возвращает трансформация в proj и в h3, они не совпадают.
Вообще, стоит отметить, что за порядком следования lat и long приходится постоянно следить в разных библиотеках и SDK он реализован по‑разному (если нет явного задания параметров по имени) и отсюда вылезают трудно отлавливаемые ошибки.
Во‑вторых, в H3 библиотеке поиск ячеек, которые перекрывают указанный полигон выполняется с помощью функции h3shape_to_cells. Эта функция считает, что ячейка принадлежит полигону, когда ее центр входит в него. Такое поведение нам не подошло, пришлось использовать функцию h3shape_to_cells_experimental, в параметрах которой можно условие, по которому считается, что ячейка и полигон пересеклись. В нашем случае нужно изменить дефолтный параметр center на overlap, который указывает, что пересечением считается любое частичное перекрытие.
Как вы поняли h3shape_to_cells_experimental является экспериментальной и в документации указано, что ее алгоритмы поиска ячеек в будущих релизах могут измениться, но кажется, на конечный результат это не должно повлиять.
Окончательный метод поиска нужных устройств будет следующим:
def find_geo_cluster_users(self, coords):
result_cells = self.find_cells_for_circle(coords[0], coords[1])
users = []
for h3_id in result_cells:
users += self.cluster.georadius(h3_id + ":users_geo_location", coords[1], coords[0], '1', unit='km')
return usersВ результате мы имеем, что координаты устройств записываются в небольшие по объему zset, которые в свою очередь шардируются по нодам кластера.
Мы избавились от проблемы записи всех гео‑данных в единственный шард кластера и действительно реализовали возможность горизонтального масштабирования для геоданных в Redis.
