Продуктами 2ГИС пользуются 30 млн горожан. Чтобы огромный набор данных попал к конечному пользователю, мы используем множество внутренних продуктов, о которых очень редко рассказываем.
Однажды на Хабре уже была статья о нашем внутреннем продукте — векторном редакторе геометрий. Чудеса нейминга привели нас к трём точкам — Fiji. До них проект назывался так: «Новая карта» > «Новая новая карта» > «Новая новая новая карта». Три года назад мы приступили к реализации Fiji и рассказали о прототипировании UI, сегодня — погрузимся в технические детали и расскажем о том, как создать быстрый и надежный ГИС-редактор.
Картографы и их запросы
Fiji — это продукт, в котором наши картографы создают карту. Хотите узнать, как выглядит обычный день картографа? Мы, разработчики, видим его примерно так:
Большую часть времени картограф взаимодействует непосредственно с картой, которую сам и создаёт. Отзывчивая и быстрая карта, позволяющая видеть изменения онлайн, — такую задачу ставят перед нами 500 картографов, работающих в офисах 2ГИС от Новосибирска и Москвы до Праги и Сантьяго. Конечно же, у нас есть SLA для всех этих операций — навигация по карте максимум 3 секунды, обновление данных карты — 5 секунд.
Как же мы решаем эту задачу?
Очевидно, что у нас есть база данных, в которой хранятся все геообъекты. Первое, что приходит в голову, — это просто тянуть из неё все объекты, которые хочет увидеть картограф. Именно такой подход использовался в предыдущем поколении нашей картографической системы, когда база данных была отдельной для каждого города 2ГИС, а количество картографов не превышало пары десятков.
Одним из основных требований к новой системе была возможность создания карты всего мира, а не его отдельных частей в границах крупных городов. Предыдущий подход исключили, так как геопересечения на базе — очень дорогая операция. Например для того, чтобы получить все здания Москвы, потребуется около двух минут, а если учесть, что картограф обычно видит не один слой, а 10?20, то ему приходилось бы выпивать довольно-таки много кофе во время ожидания загрузки :)
Ещё один минус такого подхода — большие объёмы данных, которые тянет клиент с сервера. Например, здания Москвы весят более 20 мегабайт. База данных находится в нашем дата-центре в Новосибирске, а клиент может быть в Чили. Между Новосибирском и Чили пинг 300 мс. С такими показателями карта сразу перестаёт быть отзывчивой.
Растровые тайлы
Следующий вариант, который мы рассматривали, — это использование растровых тайлов. Ничего нового, очень популярный подход для загрузки определенного экстента карты. Весь мир бьётся на несколько уровней масштаба (zoom level), каждый из которых делится на равные квадраты. В итоге получаем пирамиду тайлов, покрывающих мир.
Пирамида тайлов
Так мы уходим от постоянных геопересечений при каждом запросе клиента. Кроме того, растровые картинки значительно легче сырых бинарных геометрий. Тайлы можно подготовить один раз, разложить по распределённым серверам и периодически актуализировать.
Вариант имеет право на существование, но нам он не подошёл, так как в любой момент каждый картограф может изменить:
- Набор отображаемых слоёв или их порядок. Это значит, что пришлось бы иметь отдельные тайлы для зданий, рек, дорог и на клиенте городить логику по наложению тайлов друг на друга в нужном порядке.
- Стилизацию любого слоя. То есть решить, что кварталы должны быть не коричневые, а зелёные с красной обводкой. Тогда нам пришлось бы перегенерировать все тайлы кварталов. Настройки стилизации индивидуальны.
- Стилизацию для отдельных объектов по какому-либо условию. Например, сделать все дома выше пяти этажей красными. С растрами это не получится.
Плюс при создании объектов картографы используют такой инструмент как «притяжка», позволяющий автоматически совмещать границы рисуемых рядом объектов. Для этого на клиенте нужна реальная геометрия отображаемых объектов, а у нас была бы только картинка.
Зарождение векторных тайлов
Мы подумали, что раз весь мир пользуется тайлами, а нам в основном нужны векторные данные, то почему бы не совместить эти две сущности в одну, сделав тайлы векторными. Мы также бьём все наши геоданные на тайлы, но храним в них не картинки, а геометрии и идентификаторы объектов, попавших в соответствующий тайл. Причём можно хранить не всю геометрию, а только нужную часть, обрезанную по границе тайла.
Плюсы очевидны и покрывают все минусы, перечисленные в предыдущих подходах. Идея классная, но для её воплощения нам пришлось пройти достаточно долгий путь и столкнуться с рядом проблем.
Сразу же хочется отметить, что хоть некоторые и считают нашу Землю плоской, но это всё-таки не так :) Несмотря на это, в мире картографов гораздо удобнее видеть плоскую проекцию и работать с плоскими координатами.
В качестве проекции у нас используется EPSG:3395 – WGS84 / World Mercator. Именно на этой проекции мы и создаём тайловую сетку с несколькими уровнями. На первом уровне имеем одну квадратную ячейку, в которой находится весь мир, то есть она покрывает территорию размером примерно 40 000 на 40 000 км.
Тайловая сетка первого уровня
На втором уровне делим нашу ячейку на четыре. На следующем уровне каждую из полученных ячеек делим ещё на четыре и так далее.
Тайловая сетка второго уровня
Всего у нас 16 уровней. Таким образом на последнем уровне получаем ячейки, покрывающие территорию размером примерно 1 200 на 1 200 метров. Дальнейшее дробление никаких ощутимых выигрышей в размерах тайлов не даст, но приведёт к значительному увеличению количества тайлов.
Мы используем уникальные тайлы для дорог, зданий, рек, кварталов. Благодаря этому на клиент передаются только необходимые для отображения в данный момент типы тайлов.
У каждого тайла есть свой уникальный адрес вида: Тип_объекта/уровень_масштаба/строка/столбец/
Адрес позволяет очень быстро сформировать запросы на необходимые для отображения тайлы по видимому экстенту и масштабу, переводя их в зумлевел, строку и столбец тайловой сетки. Как уже упоминалось выше, это гораздо проще пересечений произвольных геометрий.
Ещё один плюс векторных данных — мы можем показывать их на любом масштабе, который хочет пользователь, хоть один к одному. С растрами такого не сделать, там жёстко фиксированный набор масштабов, соответствующих выбранным для тайловой пирамиды уровнями.
Как устроена работа с тайлами в Fiji?
Схематично картина работы с тайлами у нас выглядит так:
Центральная БД — тут хранятся все наши объекты, создаваемые картографами. Используем MSSQL 2016. На данный момент в ней примерно 75 млн геообъектов и весит она 450 гигабайт.
Карт-сервер — «мозг» системы, через который проходят все бизнес-операции — создание, обновление, удаление объектов.
Тайл-серверы — лёгкие Java-приложения, которые могут быть развёрнуты практически на любой машине. Логика в них предельно проста — по запросу от клиента отдать необходимый тайл, если он уже есть. Если его нет, то создать новый, отдать клиенту и сохранить на будущее. Кроме того, нужно периодически обновлять имеющиеся тайлы по информации об измененных объектах, получаемой от карт-сервера.
В качестве хранилища тайлов используем PostgreSQL, отдельную базу для каждого сервера.
Тайл-серверы мы располагаем рядом с большими группами пользователей — европейская часть России, Новосибирск, Владивосток. Благодаря тому, что эти серверы независимы друг от друга, мы можем в любой момент исключить из раздачи или добавить новый сервер.
Клиенты — desktop-приложения, каждое из которых автоматически выбирает лучший для него тайл-сервер. Критерии отбора: скорость ответа и пропускная способность сети.
Тайлы в клиенте используются только для отображения и геокодинга. Геометрии из тайлов не подходят для редактирования, так как они могут быть сильно упрощены, либо обрезаны границами тайлов. Поэтому для редактирования мы просто получаем весь объект из БД по идентификатору.
Для отображения тайлов мы используем свой собственный рендер. Долгое время сидели на чужом платном, пробовали различные бесплатные варианты, но ни один из них не удовлетворил нашим потребностям. В итоге написали свой, который поддерживает отрисовку через DirectX и GDI+.
Оптимизация тайлов
Чем меньше весит тайл, тем быстрее он доходит до клиента. Мы использовали несколько оптимизаций, позволивших уменьшить вес тайлов:
- Проекция WGS84 оперирует метрами, мы же ограничиваемся точностью в один сантиметр, поэтому можем работать с координатами как с целочисленными значениями. Поскольку геометрия объекта внутри тайла состоит из довольно близко расположенных между собой точек, то координаты этих точек выгоднее хранить не в абсолютном виде, а как смещения относительно предыдущей точки. В каждом тайле первая точка первого объекта хранится в абсолютных координатах, а все остальные — как смещение относительно предыдущей точки. Это позволяет уменьшить размер тайла в 8 раз!
- Многие типы объектов нет смысла отображать на мелких масштабах, например, нет смысла показывать все здания, когда на экране мы видим страну. Для каждого типа объектов мы определили нижнюю границу видимости тайлов, чтобы не запрашивать их с клиента и, соответственно, не создавать на сервере.
- На всех видимых уровнях, кроме последнего (шестнадцатого), используется простая генерализация. Представим, что максимальный масштаб тайла — изображение 256 на 256 пикселей. Из всех точек объекта, попавших в один и тот же пиксель, оставим одну. Результат сильно нарушит исходную геометрию — квадратный дом может превратиться в точку. Маловероятно, что картограф будет доволен результатом, не увидев честную негенерализованную геометрию при приближении один к одному.
- Мы используем битовый флаг, когда геометрия объекта полностью покрывает тайл. Это актуально для больших объектов, покрывающих множество тайлов — районы, населённые пункты и, конечно же, страны.
С задачей справились и быстро доставили на клиент геометрию.
Всегда ли это работает?
В идеальном мире — всегда. В реальности же геометрии не всегда хватает для полноценного отображения объекта. Например, картографу хочется увидеть все участки дороги, перекрытые на 9 Мая, или же просто названия улиц.
Для решения этой ситуации можно хранить в тайле вместе с геометрией всю атрибутивную информацию. Чаще всего это сильно избыточно: у одних только зданий может быть до двадцати атрибутов.
Можно хранить только то, что нужно для подписей, но проблема в том, что набор необходимых атрибутов меняется непредсказуемо.
Мы решили делать помимо геометрических ещё и атрибутивные тайлы, для каждого атрибута — свой набор тайлов. Клиент сам определяет, тайлы каких атрибутов ему необходимы, и запрашивает их вместе с геометрическими.
Что дальше?
Мы решили множество нетривиальных задач, но ещё не все. Сейчас все силы сосредоточены на следующих проблемах:
- Время обновления тайлов для городов и областей оставляет желать лучшего. Сейчас мы просто удаляем старые тайлы и создаём новые по запросу от картографа. В эти моменты карта подтормаживает.
- Базы данных тайл-серверов различны. Это связано с тем, что группы картографов работают с разными частями карты — чилийцы не редактируют Дальний Восток. Однако, если их перекинет с ближайшего тайл-сервера на владивостокский, на котором нет нужных им тайлов, то карта опять же начнёт подтормаживать из-за генерации отсутствующих тайлов.
- Различия в базах не позволяют нам в случае проблем просто скопировать бекап соседнего сервера.
Чтобы ускорить Fiji, мы разрабатываем отдельное серверное приложение для создания и обновления тайлов. Оно будет расположено рядом с карт-сервером или группой тайл-серверов и поможет распространять тайлы по нужным тайл-серверам.
Итак, если хотите сделать свой ГИС-редактор, то вот несколько советов:
- Используйте растровые тайлы там, где нужна только статичная картинка и данные меняются редко. Например, планы зданий.
- Везде, где может понадобиться динамичность отображения данных и реальная геометрия — используйте вектор.
- Каким бы мощным не был ваш SQL-сервер, не стоит возлагать на него всю работу с геоданными. Если данных немного, то в начале может быть всё хорошо. Не впадайте в заблуждение — нагрузка и рост объёма данных никогда не остановятся.
- Не забывайте про оптимизации объёмов передаваемых по сети данных. Постарайтесь найти места, где можно безболезненно показывать не оригинальную геометрию, а её упрощение.
- Не забывайте отдыхать — путешествуйте, гуляйте, используйте карты, чтобы не потеряться :)
Комментарии (41)
BiTHacK
02.11.2017 11:44Почему используется именно WGS84, а не обычные глобальные координаты (те, что используются в навигаторах типа таких 55°45'38.4«N 37°37'42.2»E)? В чём преимущество других систем координат над обычными глобальными?
nct123
02.11.2017 13:15В навигаторах — и есть WGS84.
Если Вы имели ввиду — почему именно продольная проекция Меркатора, то она чаще всего используется, т.к. достаточно простая и глобальная, и локальные искажения небольшие (пропорции ширины и высоты небольшого объекта на карте сохраняются).
rumyash Автор
02.11.2017 13:29Глобальные координаты, которые Вы указали, это сферические координаты. То есть координаты на сфере как модели Земли. В реальности гораздо проще работать с плоскими координатами. Мы выбрали WGS84, потому что она покрывает весь мир (есть еще и такие, которые покрывают только часть земной поверхности, например, UTM) и сохраняет углы и формы.
То, что показывает навигатор, скорее всего просто пересчет из используемой им проекции в глобальные координаты, это очень простая операция. Мы в своем клиенте в статусбаре тоже такие координаты показываем.
red_dragon
03.11.2017 07:06Вы какую-то глупость сказали. WGS84 — это не формат представления данных а система геодезических параметров. Что как и относительно чего определяется, рассчитывается и так далее. И кстати, она глобальная. А в каком виде будут представлены конечные пространственные координаты, совершенно не важно. То есть 55°45'38.4«N = 55.760667° (есть ещё всякие промежуточные представления), а вот система координат будет зависеть от того, по каким правилам получены данные.
fall_out_bug
02.11.2017 13:31Проекция WGS84 оперирует метрами, мы же ограничиваемся точностью в один сантиметр, поэтому можем работать с координатами как с целочисленными значениями
Неверно. WGS84 — это эллипсоид (EPSG:4326).
А почему во внешнем сервисе вы используете EPSG:3857, а во внутреннем — EPSG:3395?rumyash Автор
03.11.2017 07:32Когда мы начинали делать свой продукт, в конечных вообще были UTM-проекции, для каждого города 2ГИС своя. А нам нужен был весь мир и выбрали EPSG:3395. Потом конечные продукты решили использовать EPSG:3857, а мы не стали у себя что-то менять. Конвертация не вызывает проблем, и если вдруг в какой-то момент конечные продукты захотят использовать другую проекцию, мы легко это поддержим.
VJean
02.11.2017 14:05Внутри остался бейсик или полностью отказались от модулей? В т.ч. тестирование картографом карты на ошибки и привязку карточек?
Раньше снимки подгружались с диска машины, за которой работал картограф, либо с «рядом» стоящего сервера. Отказались от этого?rumyash Автор
03.11.2017 07:09Проекта ДГПП, в котором был бейсик, уже нет:) Он был разделен на несколько независимых частей, одной из которых стал Fiji. Используем .NET-стек и немного Java. Вся работа с карточками организаций происходит в другой системе, картограф в этом не участвует.
Для космоснимков используется отдельный сервис, который отдает данные на клиента по протоколу WMS, никакого локального хранения.
Oval
02.11.2017 16:21Проекция WGS84 оперирует метрами,
Градусами, минутами и секундами.
Даже выбранный вами Меркатор метрами не оперирует, а некоторыми условными единицами, я бы сказалfall_out_bug
02.11.2017 16:32Картографическая проекция (WGS84 — это вообще не проекция) всегда оперирует метрам. Насколько эти метры соответствуют местности — другой разговор :)
AllexIn
02.11.2017 20:54В каждом тайле первая точка первого объекта хранится в абсолютных координатах, а все остальные — как смещение относительно предыдущей точки.
Очень и очень странное решение…
Никогда такое в голову не приходило при реализации тайловых систем…
Зачем такая сложная логика с первой точкой, если можно просто работать в локальной системе координат тайла?rumyash Автор
03.11.2017 07:10Что-то я давно в код тайлов не заглядывал, каюсь. Сейчас там в точности такая реализация, как Вы описали.
mamont80
03.11.2017 07:03У меня масса вопросов.
1. Зачем вам в тайле флаг того что объект в тайле полностью?
2. Как вы решили проблему места для подписи? Геометрия в тайлах порезана, склеивать её накладно по CPU. Как определить середину объекта, чтоб подписать? Или какой у вас алгоритм?
3. Как вы храните тайлы? Я так понял 1 тайл = 1 BLOB в SQL Server? Не думали использовать key-value NoSQL БД?
4. Какая у вас тайловая сетка? Регулярная? Т.е. на максимальном 16-м зуме существуют все тайлы в которые попадает хотябы 1 объект?
5. Что за странный рендер DirectX и GDI+, я так предполагаю что векторные тайлы рендерятся в растровые GDI+, а потом растровыми манипулирует DirectX для плавности? Или это 2 разных рендера: для экрана и для принтера?
Подкину вам идею для быстрого внесения изменений в тайлы, которая сделана у нас: на таблицу БД с данными вешается триггер, который пишет все изменения в отдельную таблицу истории, старую версию записи и новую версию записи. Отдельный сервис считывает историю и зная где объект был и куда переместился знает какие тайлы необходимо обновить, что в них удалить и что добавить. Обращения к основной таблице не происходит.
Ещё таблица истории может передаваться в сыром виде на клиент. Пока изменения не внесены в тайлы, эти объекты берутся из истории, а в тайлах игнорируются. Тем самым практически нет проблем с неактуальным отображением. Это в кратце.rumyash Автор
03.11.2017 07:031. Только для небольшой оптимизации — флаг вместо четырех координат, если тайл полностью покрывает объект. Чтобы нарисовать заливку в этом тайле, если она нужна. Очень актуально для больших объектов типа населенных пунктов, районов и т.д.
2. Для некоторых типов объектов картографы специально ставят точку, в которой должна быть подпись, мы ее храним как отдельный атрибут и потом используем в отрисовке. Для всех остальных случаев подпись может дублироваться, если объект попал в несколько тайлов, для нас это нормальная ситуация, никакой склейки геометрий не делаем. Это касается только нашего внутреннего продута, в конечных же продуктах свои алгоритмы расставления подписей.
3. В SQL Server хранятся оригинальные геометрии, сами же тайлы лежат в отдельных базах PostgreSQL. В них один тайл это одна запись в таблице. Однако помимо простой операции получения по ключу нам иногда нужны и более хитрые запросы, поэтому в таблице есть и другие колонки. Key-value хранилище в таких случаях нам не подходит.
4. Сетка регулярная, в итоге получается, что у нас есть все тайлы, которые явно запрашивали пользователи. Если запроса на тайл не было, специально мы его не создаем.
5. Для отрисовки тайлов используется GDI+. А вот для для отображения трекеров при редактировании объектов у нас есть два режима в клиенте — DirectX и GDI+. Первый выигрывает на большом количестве точек и трекеров. Однако на большом зоопарке машин картографов иногда он не работает, поэтому можем отображать трекеры средствами GDI.
Спасибо за предложенные идеи по ускорению. Чтение изменений у нас примерно так и сделано. Про дополнительное получение необработанных изменений с клиента интересно, но может не подойти нам по причине сильной отдаленности некоторых клиентов от центральной БД, попробуем поэкспериментировать.
Amistad
03.11.2017 07:05Есть в планах сделать карту мира на уровне названий стран и городов? Периодически нужно прикидывать что где, в общих чертах, а оффлайновой карты найти не смог.
Такое пригодится и туристам, планирующим цепочки полетов.fall_out_bug
03.11.2017 10:46Любое приложение на базе openstreetmap вам подойдет. Конкретные рекламировать не буду :)
buldo
03.11.2017 07:12Уже который раз удивляюсь «неужели человек, который придумал название для продукта не попробовал его загуглить?»
Как минимум с 2008го года существует вот такое Fiji, который является одно из сборок ImageJ.
А вообще видео одну из версий Вашей Fiji на конференции и был удивлён скоростью работыrumyash Автор
03.11.2017 07:14Это наш внутренний продукт, которым извне никто не пользуется, поэтому задачи придумать уникальное название не было. А может мы просто плохо гуглили тогда:)
kivadim
03.11.2017 07:14А почему на картинке из «Подвигать карту» в «Нарисовать объект» идут 2 однотипные стрелки?
(промаркированы красным и зеленым ромбами на картинке по ссылке: Подвигать карту)rumyash Автор
03.11.2017 07:19Это всего лишь картинка, отражающая множество частых операций картографа. Вы же не думаете, что они после каждого действия «Поправить объект» идут пить кофе?
Avenger911
03.11.2017 10:19Вы же не думаете, что они после каждого действия «Поправить объект» идут пить кофе?
Ну… Почему бы и нет? ;-)
leonidshikhmatov
04.11.2017 05:58Спасибо, интересно. А как относительные координаты сокращают дату аж в 8 раз?
rumyash Автор
04.11.2017 06:00Если хранить координату как два double-числа, то она будут занимать 16 байт. Для генерализованных тайлов можно сделать относительную систему координат для каждого тайла и предположить, что в клиенте он будет рендериться в картинку максимального размера 256 на 256 пикселей. Тогда все координаты можно преобразовать в целочисленные значения от 0 до 255 и хранить в байте, то есть всего два байта на координату. Это справедливо только для генерализованных тайлов. Для обычных же можно перейти к целочисленным координатам, пересчитанным относительно угла тайла. Значения будут гораздо меньше оригинальных, и из можно хранить переменным числом байт, используя алгоритм ZigZag из Google Protocol Buffers.
gonchik
Спасибо большое! Не расскажите, как вы пришли к тайловым серверам и интересно, почему выбран у в качестве центрального бд геоданных ms sql server?
rumyash Автор
К тайловым серверам пришли постепенно. Сначала у нас был один тайл-сервер, который стоял рядом с мап-сервером в новосибирском дата-центре и обслуживал местных пользователей. Потом пользователей становилось все больше, а их география росла. Один сервер не справлялся, так как запросов становилось очень много и много времени терялось на пингах от удаленных клиентов. Мы решили просто замасштабироваться и ставить тайл-серверы поближе к группам пользователей. Сейчас у нас их девять.
MSSQL был выбран с самого начала, потому что у нас были на него лицензии, был опыт работы плюс наша команда администрирования умеет его хорошо готовить.
gonchik
Спасибо!