Привет, Хабр! Меня зовут Марко, я работаю в Баду в команде Платформы.
Не так давно на ГоферКон Россия 2018 Я рассказал вам, как работать с координатами.
Для тех, кто не любит смотреть видео (и кому интересно, конечно), публикую текстовую версию своего отчета.
Введение
Сегодня у большинства людей в мире есть смартфон с постоянным доступом к Интернету.Говоря цифрами, в 2018 году смартфон воля почти 5 миллиардов человек, и 60% из них наслаждаться мобильный интернет. Это огромные цифры.
Компаниям стало легко и просто получать координаты пользователей.
Эта простота и доступность породили (и продолжают создавать) огромное количество сервисов, основанных на координатах.
Мы все знаем такие компании, как Убер , игры, которые покорили мир, такие как Вход И Покемон Го .
Ну и в любом банковском приложении вы можете увидеть рядом банкоматы или скидки.
Мы в Badoo также очень активно используем координаты, чтобы предоставить нашим пользователям лучший, наиболее актуальный и интересный для них сервис.
Но о каком использовании идет речь? Давайте посмотрим на примеры наших услуг.
Геосервисы в Badoo
Первый пример: Meetmaker и Geousers
Badoo — это прежде всего сервис знакомств.Место, где люди знакомятся друг с другом.
Одним из важных критериев при поиске людей является расстояние.
Ведь в большинстве случаев москвичка хочет познакомиться с парнем, который находится от нее в паре километров или хотя бы тоже живет в Москве, а не в далеком Владивостоке.
Сервисы, которые подбирают вас к людям для игры «Да/Нет» или показывают пользователей вокруг вас, ищут людей по критериям, которые соответствуют вашим потребностям, в определенном радиусе от вас.
Второй пример: Геобордер
Для того, чтобы ответить на вопросы о том, в каком городе находится пользователь, в какой стране или, еще точнее, например, в каком аэропорту или в каком университете, мы используем сервис Geoborder, который занимается так называемыми геозонирование .
Самый простой способ ответить на эти вопросы — рассчитать расстояние от пользователя до центра города или университетского центра, но этот подход очень неточный и зависит от большого количества граничных условий.
Поэтому у нас очень точные границы стран, городов и важных объектов (например, университетов и аэропортов, о которых я говорил).
Эти границы определяются полигонами.
Имея набор таких границ, мы можем понять, находится ли пользователь внутри полигона, или найти ближайший к нему полигон.
Соответственно, мы можем сказать, в каком он городе, или найти ближайший к нему город.
Третий пример: Bumpd
У нас есть очень популярная функция Bumped Into, которая в фоновом режиме постоянно ищет пересечения пользователей во времени и пространстве и показывает, что с этим мальчиком или этой девочкой вы регулярно находитесь в одном и том же месте в одно и то же время или идете по одной и той же дороге.
регулярно.
Пользователям очень нравится эта функция, поскольку это еще один повод для знакомства и тема, с которой можно начать разговор.
Четвертый пример: Геокэш — кэширование геоинформации, «добыть» которую дорого.
Ну и последний пример, который я упомяну, связан с кэшированием геоинформации.
Представьте, что вы используете данные, например, Booking.com, который предоставляет вам информацию об отелях вокруг вас, но каждый раз заходить на Booking.com — это слишком долго.
Ваша интернет-труба, вероятно, довольно узкая, как эта яма суслика.
Возможно, сервис, в который вы обращаетесь за передачей данных, взимает плату за каждый запрос, и вы хотите немного сэкономить.
В этом случае было бы неплохо иметь уровень кэширования, который позволит существенно сократить количество запросов к медленному или дорогостоящему сервису и предоставить внешнему интерфейсу очень похожий API. Сервис, который будет понимать, что обо всех или большинстве отелей в данном районе он уже знает, эти данные относительно свежие, и, соответственно, вам не придется обращаться к внешнему сервису, чтобы их получить.
Мы решаем подобные проблемы с помощью сервиса Geocache.
Особенности геосервисов
Мы с вами уже поняли, что координат много, координаты важны, и на их основе можно создать много интересных сервисов.Ну и что дальше? В чем именно дело? Чем координаты отличаются от любой другой информации, полученной от пользователя? И я бы сказал, что есть две особенности.
Во-первых, геоданные трехмерны, а точнее двумерны, так как в общем случае высота нас не интересует. Они состоят из широты и долготы, причем поиск чаще всего происходит одновременно в обоих.
Представьте, что вы ищете в любой области.
Стандартные индексы в обычных СУБД не оптимальны для такого использования.
Во-вторых, для многих задач требуются более сложные типы данных, такие как полигоны, о которых мы говорили выше на примере сервиса Geoborder в Badoo. Полигоны, конечно, состоят из координат вершин, но они требуют дополнительной обработки, да и поисковые запросы по этим типам данных тоже сложнее.
Мы уже видели запросы «Найти ближайший к точке многоугольник» или «Найти многоугольник, включающий данную точку».
Зачем писать собственный сервис?
Чтобы реализовать эти функции, многие СУБД включают в себя специальные индексы, адаптированный для многомерных данных, а также дополнительные функции, позволяющие работать с такими объектами, как полигоны или полилинии.
Вероятно, наиболее ярким примером является ПостГИС — расширение популярной СУБД PostgreSQL , обладающий широчайшими возможностями по работе с координатами и географией.
Но использование готовой СУБД – не единственное и не всегда лучшее решение.
Если вы не хотите разделять бизнес-логику вашего сервиса между ним и СУБД, если вы хотите чего-то, чего нет в СУБД, если вы хотите полностью управлять своим сервисом и не быть ограниченными возможностями масштабирования любой СУБД , например, то вы можете захотеть интегрировать в свой сервис возможность поиска и работы с геоданными.
Этот подход, несомненно, более гибкий, но он также может быть намного сложнее, поскольку СУБД — это решение «все в одном», и многие инфраструктурные вещи, такие как репликация, уже сделаны за вас.
Репликация и собственно алгоритмы и индексы работы с координатами.
Но это не так уж и страшно.
Я хотел бы познакомить вас с библиотекой, которая реализует большую часть того, что вам нужно.
Это своего рода куб, который можно легко встроить везде, где нужно работать с геометрией на сфере или искать по координатам.
С библиотекой под названием С2 .
С2
С2 — библиотека для работы с геометрией (в том числе на сфере), предоставляющая очень удобные возможности для создания геоиндексов.
До недавнего времени S2 был практически неизвестен и имел очень мало документации, но не так давно Google решил " переиздание «Он выложен в открытый исходный код, добавив обещание поддерживать и развивать продукт. Основная версия библиотеки написана на C++ и имеет несколько официальных портов или версий на других языках, включая версию Go. Сегодняшняя версия Go не на 100% реализует все, что есть в C++-версии, но того, что есть, достаточно для реализации большинства вещей.
Помимо Google, библиотеку активно используют в таких компаниях, как Форсквер , Убер , Визг , Хорошо Баду , Конечно.
А среди продуктов, использующих библиотеку внутри себя, можно выделить всем известную MongoDB. Но пока я не сказал ничего полезного о том, чем S2 удобен и почему позволяет легко писать сервисы с геопоиском.
Позвольте мне исправиться и углубиться во внутренности, прежде чем мы рассмотрим два примера.
Проекция
Обычно география предполагает использование одной из распространенных проекций земного шара на плоскость.
Например, мы все знаем Проекции Меркатора .
Недостаток такого подхода в том, что любая проекция так или иначе искажается.
Наш земной шар не очень похож на самолет. 
Помните известную картинку, сравнивающую Россию и Африку.
На картах Россия огромна, но на самом деле площадь Африки в два раза больше площади России! Это всего лишь пример искажения проекции Меркатора.
S2 решает эту проблему, используя чисто сферическую проекцию и сферическую геометрию.
Конечно, Земля тоже не совсем сфера, но искажениями в случае сферы в большинстве задач можно пренебречь.
Мы будем работать с одним или единичная сфера , то есть со сферой радиуса 1 и мы будем использовать такие понятия, как центральный угол , сферический прямоугольник и сферический сегмент .
Название S2 происходит от математического обозначения, обозначающего единичную сферу.
Но бояться не стоит, поскольку почти всю математику берет на себя библиотека.
Иерархические ячейки
Вторая (и самая важная) особенность библиотеки — концепция иерархического деления земного шара на ячейки (по-английски — cell).
Раздел является иерархическим, то есть существует такое понятие, как уровень (или уровень) ячейки.
И на одном уровне клетки примерно одинакового размера.
Ячейки можно использовать для определения любой точки на Земле.
Если использовать ячейку максимального, уровня 30, шириной менее сантиметра, то точность, как вы понимаете, будет очень высокой.
Ячейки более низкого уровня могут задать такую же точку, но точность будет меньше.
Например, 5 на 5 метров.
Ячейки можно использовать для определения не только точек, но и более сложных объектов, таких как полигоны и некоторые области (на картинке, например, вы видите Гавайи).
В этом случае такие фигуры будут определяться наборами ячеек (возможно, разного уровня).
Этот раздел очень компактен: каждую ячейку можно закодировать одним 64-битным числом.
Кривая Гильберта
Я упоминал, что ячейка задается одним 64-битным числом.Вот! Оказывается, координата или точка на Земле, которая по умолчанию задается двумя координатами, с которыми нам неудобно работать стандартными методами, может быть задана одним числом.
Но как этого добиться? Давайте посмотрим…
Как происходит это самое иерархическое разделение сферы? 
Сначала мы окружаем сферу кубом и проецируем ее на все шесть ее граней, слегка корректируя проекцию по мере удаления искажений.
Это уровень 0. Тогда мы можем разделить каждую из шести граней куба на четыре равные части – это уровень 1. И каждую из получившихся четырех частей можно разделить еще на четыре равные части – уровень 2. И так до тех пор, пока уровень 30.
Но на этом этапе у нас все еще есть двумерность.
И здесь нам на помощь приходит математическая идея из далекого прошлого.
В конце 19 века Давид Гильберт придумал способ заполнить любое пространство одномерной линией, которая поворачивается, складывается и таким образом заполняет пространство.
Кривая Гильберта является рекурсивным, что означает, что можно выбрать точность или плотность заполнения.
При необходимости любой небольшой кусочек можем заполнить плотнее.
Такой кривой мы можем заполнить наше двумерное пространство.
И если мы теперь возьмем эту кривую и растянем ее в прямую линию (как будто тянем за веревку), то мы получим одномерный объект, описывающий многомерный объект - одномерный объект или координату на этой линии, с которым удобно и легко работать.
Вот как выглядит заполнение кривой Гильберта Земли на одном из средних уровней: 
Еще одной особенностью кривой Гильберта является тот факт, что точки, находящиеся рядом на кривой, также находятся рядом в пространстве.
Обратное не всегда верно, но в большинстве случаев это тоже верно.
И мы тоже будем активно использовать эту возможность.
Кодирование в 64-битную переменную
Но почему мы можем закодировать любую ячейку одним 64-битным числом, которое, кстати, называется CellID? Давайте посмотрим.У нас есть шесть граней куба.
Шесть различных значений могут быть закодированы тремя битами.
Давайте вспомним логарифмы .
Затем мы разделили каждую из шести граней на четыре равные части 30 раз.
Чтобы задать одну из четырех частей, на которые мы делим ячейку на каждом уровне, нам достаточно двух битов.
Итого 3+2*30=63. И в конце мы установим один дополнительный бит, чтобы знать и быстро понимать, на каком уровне ячейка указана этим CellID.
Что нам дают все эти разбиения и кодирование кривой Гильберта в одно число?
- Мы можем закодировать любую точку земного шара с помощью одного CellID. В зависимости от уровня мы получаем разную точность.
- Мы можем закодировать любой двумерный объект на земном шаре с помощью одного или нескольких CellID. Точно так же мы можем играть с точностью, варьируя уровни.
- Свойство кривой Гильберта, заключающееся в том, что точки, находящиеся рядом на ней, находятся рядом в пространстве, а также тот факт, что наш CellID — это просто число, позволяют нам использовать для поиска обычное дерево, такое как B-дерево.
В зависимости от того, что мы ищем (точку или область), мы будем использовать либо сканирование get, либо сканирование диапазона, то есть поиск «от» и «до».
- Разбивка глобуса на слои дает нам простую основу для разделения нашей системы.
Например, на нулевом уровне мы можем разделить наш сервис на шесть экземпляров, на первом уровне — на 24 и т. д.
Мы напишем два простых сервиса, и первый — это просто поиск «вокруг».
Примеры
Напишем сервис для поиска людей вокруг
Мы создадим поисковый индекс.Нам понадобится функция для создания индекса, функция для добавления человека в индекс и, собственно, функция поиска.
Ну и тест.
Пользователь указывается по его ID и координатам, а поиск задается координатами поискового центра и радиусом поиска.type Index struct {} func NewIndex(storageLevel int) *Index {} func (i *Index) AddUser(userID uint32, lon, lat float64) error {} func (i *Index) Search(lon, lat float64, radius uint32) ([]uint32, error) {} func TestSearch(t *testing.T) {}
В индексе нам нужен B-дерево, в узлах которого мы будем хранить ячейку StorageLevel и список пользователей в этой ячейке.
StorageLevel — это компромисс между начальной точностью поиска и производительностью.
В этом примере мы будем использовать размер ячейки примерно 1 км на 1 км.
Функция Less необходима для работы B-дерева, чтобы дерево могло понять, какое из наших значений меньше, а какое больше.
type Index struct {
storageLevel int
bt
Теги: #s2 #geo #Go #golang #программирование #Go #Геоинформационные услуги
-
Введение В Хранилище Ceph В Картинках
19 Oct, 24 -
Режем Патриотизм
19 Oct, 24 -
Nodeconf Eu 2013 – Впечатления
19 Oct, 24
