Viam supervadet vadens (дорогу осилит идущий)

Есть много счастливчиков, которым повезло работать в ситуации, когда объёмы по-настоящему огромны и требования кажутся невыполнимыми. Но есть те, кому по настоящем крупно повезло! Я говорю о тех, кто решал задачи в пространствах, где размерность больше 1.

Давайте разбросаем осколки по всей земле?

---

Я пишу статьи скорее для себя, чтобы собрать в более компактном виде своё собственное представление о вопросе. А от вас я ожидаю, что вы поймёте, простите и не будете закидывать помидорами. Но указывать на ошибки приветствуется?

Краткое содержание этой статьи:

1. А нужно ли это гео-шардирование мне? и вообще гео?

2. Индексация

3. Шардирование по зонам

4. Кросс-сегментный запрос

5. Как построить зоны для виртуальных сегментов

6. Часовые пояса

Цикл:

1. Первая статья из цикла статей посвященных шардированию. В ней я рассказал в принципе про шардирование, описал шардирование по идентификатору и немного раскрыл тему решардинга.

2. В этой статье я рассказываю про шардирование по гео-данным.

3. В третьей статье посмотрим, как шардирование может обеспечить отказоустойчивость при записи данных.

4. В четвёртой статье посмотрим, как шардирование можно применять для исторических данных.

5. В пятой статье рассмотрим достаточно глубоко решардинг

6. В шестой статье рассмотрим особые обстоятельства для шардирования. Рассмотрим связь шардирования и репликации, немного затронем CQRS

7. Начиная с седьмой статьи рассмотрим прототипы сервисов с применением шардирования

А нужно ли это гео-шардирование мне? и вообще гео?

“А нужно ли мне именно гео-разделение?” – это самый первый вопрос, которым стоит задаться. Обычно, многие задачи, связанные с распределением чего-либо в пространстве, не требуют работу с координатами. Вполне можно опираться на естественные ключи, такие как город или страна, или номеру машины. Именно гео-разделение данных может пригодится тогда, когда вам нужно искать что-то по координатам. И сильно ограничивать выборку кроме координат больше нечем.

Если вы уверены в том, что вам нужно именно гео-разделение, но если у вас мало объектов, малый объём данных и нет каких-то особых требований, то скорее всего шардирование вам не нужно. Для размещения и работы с гео-объектами можно воспользоваться уже готовыми инструментами, например, postgresql+postgis или geoSearch в mongo. Для того, чтобы реализовывать что-то своё, стоит убедиться, что как минимум, эти два популярных инструмента вам точно не подходят. Правильный выбор инструмента и более качественное изучение его возможностей может позволить решить задачу не деля данные на части. Однако я рекомендую хотя бы один раз из академических соображений разработать гео-поиск, без шардирования, не используя готовые инструменты, а используя библиотеку S2 (https://github.com/golang/geo/tree/master/s2) и ей подобные, и замерить производительность.

Всё, что будет написано ниже, не будет опираться на готовые инструменты.

Шардирование по географическому положению – шардирование, в способе разбиения на сегменты
которого присутствуют координаты (2 мерные данные). В этой статье будем
рассматривать именно это определение. Если бить данные по странам, или по континентам,
то это относится к особым обстоятельствам для шардирования и будет рассмотрено
в эпизоде 6. Также выбор “ближайшего источника” будет
рассмотрен в эпизоде 6.

Примеры, когда не нужно гео-разделение

У нас есть много дарксторов. У каждого есть координаты. И мы принимаем решение хранить данные рядом стоящих дарксторов вместе, так как у них один куратор. У дарксторов скорее всего есть поле район, город или регион. И гораздо “понятнее” опираться на идентификатор города, а не на координаты.

Другой более понятный вариант: нужно найти 10 ближайших курьеров для даркстора. Курьер может работать только в одном дарксторе. Для этой задачи хранилище для координат курьеров можно индексировать по идентификаторам дарксторов. А поняв, что, например, в дарксторе не бывает более 100 активных курьеров, можно просто выбирать всех из хранилища для конкретного даркстора и затем на сервисе фильтровать по удалённости.

Ещё один пример: нужно хранить трекер машин. Эту информацию можно индексировать по номеру машины. Важно, что при этом вам не нужно искать “машины по близости”, а только отображать для конкретной машины её перемещение.

Индексация

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

Давайте рассмотрим задачу: нужно найти 10 ближайших кофеен в радиусе 10 км.

Для поиска в пространстве сразу вспоминается три принципа поиска: k-d-деревья и r-деревья, сетка и кривая Гильберта. Принципов больше, но я остановлюсь на этих, которые покрывают большую часть задач.

K-d-деревья и r-деревья

Про k-d-деревья можно почитать тут https://habr.com/ru/articles/312882/

Про r-деревья можно почитать тут https://habr.com/ru/articles/666904/

Статьи выше дают общее понимание принципа, но не дают понимания, как эти деревья применить к шардированию. Этого понимания не дам вам и я, так как на практике не применял эти деревья. Однако два следующих способа я применял, и они достаточно эффективны.

Сетка

Давайте разобьём пространство на сегменты. Например: по долготе нарежем на 360 частей и по широте на 180. Итого получаем 64800 ячеек. Можно сделать разбиение более мелким шагом, например по 1’ (1 минуте) (~233млн ячеек). С учётом того, что 1° широты примерно 111.4 км, а 1’ широты 1.86 км, то сетка получается достаточно мелкая.

Далее каждой ячейке сетки мы присваиваем номер
(идентификатор). Это можно сделать, задав номер ячейки согласно правилу,
например: id = (lat+90)*360+(long+180).
И вуаля, мы индексируем по идентификатору, ожидая, что в каждой ячейке будет
разумное количество объектов. Если придётся шардировать, то используя сетку
можно делать шардирование по идентификатору, в эпизоде 1 эта тема была
раскрыта.

Кривая Гильберта

Классная статья от badoo, показывающая способ применения https://habr.com/ru/companies/badoo/articles/352754/

Суть в том, что через всё ограниченное пространство можно нарисовать заполняющую пространство кривую, которая позволяет определить число cell_id для каждой точки пространства. Для получения cell_id определяется параметр level, который определяет точность. Чем больше level, тем точнее определяется положение. Для этого подхода верно, что если cell_id рядом, то и координаты рядом, обратное не верно, однако в большинстве случаев тоже выполняется.

Используя кривые Гильберта, можно индексировать по cell_id. Шардирование по идентификатору тоже будет работать.

Решение задачи поиска

Для сетки и кривой Гильберта решение задачи по поиску ближайших выглядит в общем виде так:

1. Индексировать по сетке или кривой Гильберта точки кофеен

2. Выбрать ячейки или cell_id входящие в круг 10 км от искомой точки (ниже рисунок)

3. Выбрать из сегментов, относящихся к найденным ячейкам или cell_ids все кофейни

4. Из выбранных кофеен отобрать 10 самых ближайших к искомой точке

Как индексировать зоны

Сделаем шаг в сторону и решим задачу поиска зон. Дан набор зон. Нужно найти те, в которые попадает точка.

1. Для каждой зоны найдём набор cell_id для заданного level. Уровень лучше подбирать исходя из размера зон.

2. Сделаем индекс по cell_id как индексирующее поле и номер зоны как искомое. Получится что-то типа map[cell_id][]zone_id.

3. Для точки найдём cell_id для заданного level.

4. По индексу из п2 найдём список зон.

5. Проверим вхождение точки в зону для каждой найденной зоны.

Здесь мои редакторы написали, что хотят подробностей. Их есть у меня?

Задача: у нас есть зоны размером с регион России, и они покрывают 98% площади, и есть зоны размером с квартал Москвы. Зоны равноценны и, в основном, не пересекаются. Нужно найти в каких зонах находится точка. Решение: делаем 2 индекса: один с уровнем, который хорошо подходит для разбиения больших зон, например, level_big = 8, и второй с уровнем level_small = 12, который хорошо подходит для зон размером с квартал. В данном примере для большого уровня не более 400K уникальных значений, для малого не более 100KK, но из них будет использоваться малое количество ~2%, то есть не более 2KK. В какой тип индекса засовывать зону можно определять по площади. Например, до 10км^2 в малые больше в большие. Сложность поиска будет линейно зависеть от количества зон в ячейке из каждого индекса.

Размеры для уровней: https://s2geometry.io/resources/s2cell_statistics.html

На таком же принципе можно строить поиск пересечения зон. Можно выбрать набор cell_id для искомой зоны и искать пересечения по наборам cell_id с известными зонами. Фактически будет поиск в отсортированных списках.

Шардирование по зонам

На данный момент мы разобрались как индексировать, теперь перейдём к шардированию. В эпизоде 1 было рассмотрено шардирование, где для разделения данных было введено понятие виртуального сегмента.

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

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

Для дальнейших действий возьмём за основу кривые Гильберта и cell_id.

Для поиска по зонам, нам нужно сделать индексирование зон. Это удобно сделать, выбрав не очень большой level (zone_level) и получив для каждой зоны набор cell_id. Если выбрать очень большой уровень zone_level можно получить очень большое количество cell_id, что сделает индекс большим по объёму. Если сделать zone_level слишком маленьким, можно потерять суть индексирования, получится так что в одном cell_id будет много зон и задача сведётся к перебору.

Логика на маршрутизаторе будет выглядеть так:

1. Получаем cell_id для точки, с уровнем zone_level.

2. Находим зону, которая соответствует cell_id, и определяем для неё виртуальный сегмент.

3. Отправляем запрос на поиск в виртуальный сегмент.

4. Полученный ответ отправляем наружу.

Чем хорошо брать за основу кривые Гильберта?

Свойство, что если cell_id рядом, то и координаты рядом, позволяет минимизировать количество серий cell_id на каждую зону и свести к минимуму сложность описания принципа шардирования.

Регулирование zone_level, позволит делать разное разбиение в зависимости от задачи.

В рамках сегментов не обязательно выбирать одинаковый уровень получения cell_id, для городов можно взять уровень побольше, а для остальной местности поменьше. А вообще можно задать более интересную логику, пример логики с расходящимися кругами, которая хорошо подходит для городов, где на каждом шагу по 10 кофеен:

1. Выбрать список cell_id входящих в круг 1 км

2. Выбрать все точки основываясь на индексации по cell_id и из них выбрать 10 ближайших в радиусе 1 км

3. Если точек недостаточно, то расширить круг до 2 км и повторить с п1

Кросс-сегментный запрос

А теперь стоит рассмотреть случай, когда точка и её 10 километровые окрестности попадает на границу 2х или более зон. В этом случае нужно сходить в оба (или больше) сегмента и достать оттуда кофейни, удовлетворяющие условию, и затем объединить списки на маршрутизаторе.

Впервые мы столкнулись с бизнес-логикой на маршрутизаторе.

Логика на маршрутизаторе будет выглядеть так:

1. Получаем cell_id для точки, с уровнем zone_level.

2. Находим зоны, которые соответствует cell_id, и определяем для них виртуальный сегменты.

3. Отправляем запрос на поиск в каждый виртуальный сегмент.

4. Полученные результаты агрегируем и оставляем только 10 ближайших точек.

5. Полученный ответ отправляем наружу.

Видно, что придётся искать в 4х зонах и ещё в сегменте “остальное” (это точки, которые попали между зонами). И да, искать придётся во всех зонах, так как интересующий нас объект может попасть в любую из них.

Кросс сегментная запись

Ещё более сложным вариантом станет решение задачи: получить 10 ближайших машин такси в радиусе 10 км. Предположим, что машина такси шлёт свои координаты 1 раз в 30 секунд и если не шлёт 3 минуты, то машину нужно убрать из поиска.

В этом случае машина может переезжать из зоны в зону, из сегмента в сегмент. Для сохранения корректности данных нужно в этом случае убрать координаты машины из старого полигона (задав разумный радиус, для нашей задачи: 120км/ч*3 мин~6 км) и вставить в новый и делать это можно независимо. Простой учёт этой ситуации заставит нас сделать на маршрутизаторе дедубликацию и сложное внесение изменений, состоящее из 2х параллельных действий. А возможно, стоит хранить прошлые координаты в дополнительном разрезе, в рамках машины, чтобы получить факт того, что поменяется зона. Эту тему раскроем в CQRS в 6 эпизоде.

Как построить зоны для виртуальных сегментов

Экспертный handmade

Если нет понимания, то можно начать с построения зон “экспертным” способом. Группа экспертов анализирует предполагаемое распределение объектов и строит зоны, по своему разумению.

Этот способ хорош, когда не набрана статистика. Так же этот способ позволяет определить зоны в случае, если автоматизация алгоритмов сложна и нет ресурсов на её реализацию. Экспертный способ, позволяет учитывать аномалии, когда, например, эксперт “видит”, что нужные зоны ограничены реками, оврагами, жд путями, и прочими географическими особенностями.

Автоматика

Кстати, пример про такси ещё интересен тем, что полигоны для разбиения можно строить исходя из статистики запросов.

Как один из вариантов формирования таких зон можно рассмотреть ситуацию, когда мы определяем точки концентрации и из них начинаем растить зону.

Как растить зону

Зоны могут иметь разные формы.

Самым простым способом является формировать зону “прямоугольного вида”, то есть от и до по широте и долготе. Для таких зон способ роста достаточно прост, можно по какому-либо алгоритму смещать каждую из сторон. Делать это нужно пока не достигли соседней зоны или пока не выполнится какое-нибудь условие, показывающее, что зона достигла достаточного размера. Такими условиями могут быть количество попавших в зону объектов и максимальный размер зоны, а также другие факторы.

Ещё одним простым способом является формирование зоны в форме правильного многоугольника (например шестиугольника) с центром в конкретной точке. Тут рост вообще максимально прост, увеличение радиуса от центра. Принципы остановки, такие же, как и для “прямоугольного вида”.

Более сложной формой является, например, набор квадратов, шестиугольников или треугольников. Однако такие зоны позволяют более “качественно” описать форму зоны, которую создаёт автоматика. Выбирается форма объектов и с помощью алгоритма “волны” заполняется пространство. Волновой алгоритм описан тут https://habr.com/ru/articles/745294/, он легко адаптируется под построение зон. Для понимания гексагональных элементов подходит статья https://habr.com/ru/articles/319644/.

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

Отдельно стоит отметить объединение и сталкивание зон во время роста. Решать, как делать, нужно исходя из здравого смысла, но учесть факт сталкивания зон обязательно нужно. Возможно, вы придумаете как удачно работать с перекрытием зон, однако перекрытие зон одного вида и одной значимости может привести к неопределённой ситуации. С другой стороны зоны разного вида и разной значимости могут перекрываться и конфликта с определением зоны в этом случае не возникает.

Можно увидеть, что там, где зоны сталкиваются рост останавливается, и зоны не покрывают полностью всё пространство.

Как определять точки концентрации

Точка концентрации – исходная зона, в которой есть достаточное количество объектов для выделения их в отдельный виртуальный сегмент. На самом деле наличие большого количества объектов в зоне не обязательно, но принцип выбора должен обеспечивать оптимальное распределение зон и максимальную селективность их в будущем.

Один из способов выбора точек может быть таким:

1. Идём по каждой точке

2. Точка является точкой концентрации если:

   1. Рядом в радиусе R1 есть много объектов

   2. Рядом в радиусе R2 нет уже определённых точек концентрации

3. По найденным точкам концентрации определяем зоны, выбранным способом, например одним из тех, которые были определены в прошлом разделе [Как растить зону].

4. Определить точки, попавшие в зоны.

5. Для точек, не попавших в зоны, выборку можно начать с п1 применив другие настройки или направить в зоны, определённые как “остальные”

Ещё один способ может быть основан на сетке или кривой Гильберта, на примере последней:

1. Определяем уровень грануляции level.

2. Для каждой точки определяем cell_id для данного уровня.

3. Cell_id с достаточным количеством объектов определяются как точки концентрации.

Интересно, а какие точки брать для задачи построения зон?

Для задачи с кофейнями, очевидно, что координаты кофеен.

А вот для ближайших машин, возможно использовать координаты самих машин (где машины чаще встречаются). А можно использовать координаты из статистики поиска (какие точки чаще запрашивали). Стоит отметить, что второй вариант даст меньшую нагрузку на шардирование при поиске, а первый даст меньшую нагрузку при записи и решардинге.

Так какие параметры?

На этом этапе хочется услышать, а сколько всё же взять в километрах и штуках. Это как раз вопрос исследований вашей конкретной задачи. Но можно исходить из следующих соображений:

Давайте будем растить зону так, чтобы в зоне было примерно N точек. Давайте возьмём пристрелочный радиус R1. И будем считать? что прирост зоны идёт гексагональными полигонами с радиусом R1. И попробуем найти точки концентрации, исходя из того что в радиусе R1 находится N/7 точек. Почему N/7? Потому, что берём точку и её окрестности (7 полигонов). Радиус R2 до соседних точек давайте возьмём как R2 = 6*R1, что бы у каждой зоны получилось вырасти хотя бы на 1 слой.

Нашли такие точки, хорошо! Если есть такие точки концентрации и в них уже больше N/2 объектов, то кажется нужно уменьшить радиус R1 в двое и повторить операции. Иначе растим от найденных точек концентрации зоны так, чтобы помещалось N объектов с погрешностью. Выкидываем попавшие в зоны точки, повторяем работу уменьшив количество точек в двое (Nпоиска = N/2). Можно так продолжать до тех пор, пока не получится неприемлемо мало точек на конечно-получившуюся зону, например N/8. Далее стоит разбивать на зоны “остальное”

Зоны “остальное”

Отдельный вопрос как строить зоны для виртуальных сегментов “Остальное”.

Самый простой вариант – не рисовать зону, а сделать сегмент по принципу “если никуда, то значит сюда”.

Более сложный вариант – сделать несколько зон. Это может потребоваться, если объектов, не попадающих в обычные зоны, достаточно много, и виртуальный сегмент “Остальное” становится “супер” сегментом. Их можно строить автоматически также, как и обычные зоны, но с другими параметрами, или нарисовать экспертным образом.

Часовые пояса

Одной из особенностей гео-шардинга является то, что нагрузка на разные виртуальные сегменты может быть разной, и зависеть от часового пояса. Как пример, можно рассмотреть случай, когда на дальнем востоке утро и идёт нагрузка на сегменты, связанные с дальним востоком, в Москве в это время ночь. Хочется отметить, что распределять виртуальные сегменты стоит с учётом изменений нагрузки, связанной с часовым поясом. С другой стороны, не стоит переоценивать этот эффект, так как может случиться так что на весь дальний восток нагрузки меньше, чем на округ Москвы.

Заключение

Мы не рассмотрели решардинг детально. Общие представления о решардинге можно посмотреть в эпизоде 1. Тема решардинга и кросс шардинговых запросов будет больше раскрыта в эпизоде 5.

Спасибо за то, что прочитали до конца.

Следующая тема

Следующая статья будет через 2-3 месяца и будет посвящена шардированию для гарантированного сохранения

Литература

Крайне рекомендую вот такой небольшой набор источников. Это прям полезный матерьял?

1. (badoo о гильбертовой кривой) https://habr.com/ru/companies/badoo/articles/352754/

2. (k-d-деревья) https://habr.com/ru/articles/312882/

3. (r-деревья) https://habr.com/ru/articles/666904/

4. (немного s2 библиотеке) https://s2geometry.io/

5. (golang s2) https://pkg.go.dev/github.com/golang/geo/s2 https://github.com/golang/geo/tree/master/s2

6. (алгоритм волны) https://habr.com/ru/articles/745294/

7. (гексагональные координаты) https://habr.com/ru/articles/319644/

8. (Размеры для уровней) https://s2geometry.io/resources/s2cell_statistics.html

Благодарности

Спасибо, что прочитали и проревьюили мои прошлые версии этой статьи

Денис К., Влад В., Артём З., Анна С., Дмитрий Г., Филипп Б.

Вы супер!