Как мы делаем карту для тех, кто делает карту

bjmvpdzrnzorpblynxuivqvdapg.png

Продуктами 2ГИС пользуются 30 млн горожан. Чтобы огромный набор данных попал к конечному пользователю, мы используем множество внутренних продуктов, о которых очень редко рассказываем.

Однажды на Хабре уже была статья о нашем внутреннем продукте — векторном редакторе геометрий. Чудеса нейминга привели нас к трём точкам — Fiji. До них проект назывался так: «Новая карта» → «Новая новая карта» → «Новая новая новая карта». Три года назад мы приступили к реализации Fiji и рассказали о прототипировании UI, сегодня — погрузимся в технические детали и расскажем о том, как создать быстрый и надежный ГИС-редактор.

Картографы и их запросы


Fiji — это продукт, в котором наши картографы создают карту. Хотите узнать, как выглядит обычный день картографа? Мы, разработчики, видим его примерно так:
st17qhjo6rt2ptvbcxhvwe-8reo.png

Большую часть времени картограф взаимодействует непосредственно с картой, которую сам и создаёт. Отзывчивая и быстрая карта, позволяющая видеть изменения онлайн, — такую задачу ставят перед нами 500 картографов, работающих в офисах 2ГИС от Новосибирска и Москвы до Праги и Сантьяго. Конечно же, у нас есть SLA для всех этих операций — навигация по карте максимум 3 секунды, обновление данных карты — 5 секунд.

Как же мы решаем эту задачу?


Очевидно, что у нас есть база данных, в которой хранятся все геообъекты. Первое, что приходит в голову, — это просто тянуть из неё все объекты, которые хочет увидеть картограф. Именно такой подход использовался в предыдущем поколении нашей картографической системы, когда база данных была отдельной для каждого города 2ГИС, а количество картографов не превышало пары десятков.

Одним из основных требований к новой системе была возможность создания карты всего мира, а не его отдельных частей в границах крупных городов. Предыдущий подход исключили, так как геопересечения на базе — очень дорогая операция. Например, для того, чтобы получить все здания Москвы, потребуется около двух минут, а если учесть, что картограф обычно видит не один слой, а 10–20, то ему приходилось бы выпивать довольно-таки много кофе во время ожидания загрузки :)

9oywrdimod_ur7amlyfnc3dik6s.png

Ещё один минус такого подхода — большие объёмы данных, которые тянет клиент с сервера. Например, здания Москвы весят более 20 мегабайт. База данных находится в нашем дата-центре в Новосибирске, а клиент может быть в Чили. Между Новосибирском и Чили пинг 300 мс. С такими показателями карта сразу перестаёт быть отзывчивой.

Растровые тайлы


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

d7xxsf8-mxrnfe05zbnm9ntlmv4.png
Пирамида тайлов

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

Вариант имеет право на существование, но нам он не подошёл, так как в любой момент каждый картограф может изменить:

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


Плюс при создании объектов картографы используют такой инструмент как «притяжка», позволяющий автоматически совмещать границы рисуемых рядом объектов. Для этого на клиенте нужна реальная геометрия отображаемых объектов, а у нас была бы только картинка.

Зарождение векторных тайлов


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

Плюсы очевидны и покрывают все минусы, перечисленные в предыдущих подходах. Идея классная, но для её воплощения нам пришлось пройти достаточно долгий путь и столкнуться с рядом проблем.

Сразу же хочется отметить, что хоть некоторые и считают нашу Землю плоской, но это всё-таки не так:) Несмотря на это, в мире картографов гораздо удобнее видеть плоскую проекцию и работать с плоскими координатами.

В качестве проекции у нас используется EPSG:3395 — WGS84 / World Mercator. Именно на этой проекции мы и создаём тайловую сетку с несколькими уровнями. На первом уровне имеем одну квадратную ячейку, в которой находится весь мир, то есть она покрывает территорию размером примерно 40 000 на 40 000 км.

daam59oeso_upddwmsdi5jfka6w.png
Тайловая сетка первого уровня

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

wovspuahtuueonthw-luxk_r35m.png
Тайловая сетка второго уровня

Всего у нас 16 уровней. Таким образом на последнем уровне получаем ячейки, покрывающие территорию размером примерно 1 200 на 1 200 метров. Дальнейшее дробление никаких ощутимых выигрышей в размерах тайлов не даст, но приведёт к значительному увеличению количества тайлов.

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

У каждого тайла есть свой уникальный адрес вида: Тип_объекта/уровень_масштаба/строка/столбец/

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

dvz97y89tcnmsz_-brijvnjwais.png

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

Как устроена работа с тайлами в Fiji?


Схематично картина работы с тайлами у нас выглядит так:

vsiftdwre_chhy5b6zntiakqwb8.png

Центральная БД — тут хранятся все наши объекты, создаваемые картографами. Используем MSSQL 2016. На данный момент в ней примерно 75 млн геообъектов и весит она 450 гигабайт.

Карт-сервер — «мозг» системы, через который проходят все бизнес-операции — создание, обновление, удаление объектов.

Тайл-серверы — лёгкие Java-приложения, которые могут быть развёрнуты практически на любой машине. Логика в них предельно проста — по запросу от клиента отдать необходимый тайл, если он уже есть. Если его нет, то создать новый, отдать клиенту и сохранить на будущее. Кроме того, нужно периодически обновлять имеющиеся тайлы по информации об измененных объектах, получаемой от картсервера.

В качестве хранилища тайлов используем PostgreSQL, отдельную базу для каждого сервера.

Тайл-серверы мы располагаем рядом с большими группами пользователей — европейская часть России, Новосибирск, Владивосток. Благодаря тому, что эти сервера независимы друг от друга, мы можем в любой момент исключить из раздачи или добавить новый сервер.

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

Тайлы в клиенте используются только для отображения и геокодинга. Геометрии из тайлов не подходят для редактирования, так как они могут быть сильно упрощены, либо обрезаны границами тайлов. Поэтому для редактирования мы просто получаем весь объект из БД по идентификатору.

Для отображения тайлов мы используем свой собственный рендер. Долгое время сидели на чужом платном, пробовали различные бесплатные варианты, но ни один из них не удовлетворил нашим потребностям. В итоге написали свой, который поддерживает отрисовку через DirectX и GDI+.

Оптимизация тайлов


Чем меньше весит тайл, тем быстрее он доходит до клиента. Мы использовали несколько оптимизаций, позволивших уменьшить вес тайлов:

  • Проекция WGS84 оперирует метрами, мы же ограничиваемся точностью в один сантиметр, поэтому можем работать с координатами как с целочисленными значениями. Поскольку геометрия объекта внутри тайла состоит из довольно близко расположенных между собой точек, то координаты этих точек выгоднее хранить не в абсолютном виде, а как смещения относительно предыдущей точки. В каждом тайле первая точка первого объекта хранится в абсолютных координатах, а все остальные — как смещение относительно предыдущей точки. Это позволяет уменьшить размер тайла в 8 раз!
  • Многие типы объектов нет смысла отображать на мелких масштабах, например, нет смысла показывать все здания, когда на экране мы видим страну. Для каждого типа объектов мы определили нижнюю границу видимости тайлов, чтобы не запрашивать их с клиента и, соответственно, не создавать на сервере.
  • На всех видимых уровнях, кроме последнего (шестнадцатого), используется простая генерализация. Представим, что максимальный масштаб тайла — изображение 256 на 256 пикселей. Из всех точек объекта, попавших в один и тот же пиксель, оставим одну. Результат сильно нарушит исходную геометрию — квадратный дом может превратиться в точку. Маловероятно, что картограф будет доволен результатом, не увидев честную негенерализованную геометрию при приближении один к одному.
  • Мы используем битовый флаг, когда геометрия объекта полностью покрывает тайл. Это актуально для больших объектов, покрывающих множество тайлов — районы, населённые пункты и, конечно же, страны.


С задачей справились и быстро доставили на клиент геометрию.

Всегда ли это работает?


В идеальном мире — всегда. В реальности же геометрии не всегда хватает для полноценного отображения объекта. Например, картографу хочется увидеть все участки дороги, перекрытые на 9 мая, или же просто названия улиц.

Для решения этой ситуации можно хранить в тайле вместе с геометрией всю атрибутивную информацию. Чаще всего это сильно избыточно: у одних только зданий может быть до двадцати атрибутов.

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

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

Что дальше?


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

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


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

Итак, если хотите сделать свой ГИС-редактор, то вот несколько советов:

  • Используйте растровые тайлы там, где нужна только статичная картинка и данные меняются редко. Например, планы зданий.
  • Везде, где может понадобиться динамичность отображения данных и реальная геометрия — используйте вектор.
  • Каким бы мощным не был ваш SQL-сервер, не стоит возлагать на него всю работу с геоданными. Если данных немного, то в начале может быть всё хорошо — не впадайте в заблуждение. Нагрузка и рост объёма данных никогда не остановятся.
  • Не забывайте про оптимизации объёмов передаваемых по сети данных. Постарайтесь найти места, где можно безболезненно показывать не оригинальную геометрию, а её упрощение.
  • Не забывайте отдыхать — путешествуйте, гуляйте, используйте карты, чтобы не потеряться :)

© Habrahabr.ru