Хабрахабр

Как мы добавили подъезды на карту и сократили размер баз на 10%

Входы в организации мы показываем аж с 2013 года, а подъезды — вроде бы те же входы. В конце прошлого месяца 2ГИС начал отображать подъезды. Все внутренние продукты и процессы готовы, всего-то нужно дособрать ещё чуть-чуть да подправить отображение в UI. Так почему только сейчас?

Эта статья про то, какие были сложности и как мы их решили.
Во-первых, подъезд — это не вход. Кроме стандартного ответа «Были другие приоритеты» есть и не совсем стандартный: «Не всё так просто». Некорректно и определение «(многоуровневый) блок квартир с общим входом». Так, в один подъезд может вести несколько входов, обычно с разных сторон здания. Бывает, что один вход ведёт на первый этаж подъезда, а другой — на второй и последующие этажи.

Подъезды с двумя входами

Во-вторых, подъезды хочется искать.

Подъезды в результатах поиска

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

Дом с не самой очевидной нумерацией подъездов

Помимо номеров подъездов встречаются и названия (как правило, из одной буквы).

Буквы в названиях подъездов

Или даже как в Калининграде — отдельный адрес присваивается именно подъезду.

Независимая нумерация подъездов в Калининграде

Решили — и собрали диапазоны квартир, правда, пока без поэтажной привязки. В-третьих, мы решили, что если уж делать поиск подъездов, то почему бы сразу не поддержать и поиск по номеру квартиры. В старых домах Санкт-Петербурга нумерация довольно странная: квартиры 1 и 3 могут находиться в одном подъезде, а квартира 2 — в противоположной части здания. Как и с подъездами, у квартир могут быть не только числовые названия (чаще всего встречаются варианты с буквой «а»), да и диапазоны далеко не всегда непрерывны.

Типичный подъезд старого Петербурга

Лирическое отступление про валидацию данных

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

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

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

Выводы:

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

Приступаем к решению

Первые два пункта требуют изменений как во внутренних продуктах, так и во внешних, но это — рутина. Последний же — совсем другое дело. Поскольку мы не любим расстраивать пользователей, поставили себе ограничение: данные должны быть доступны офлайн, а их добавление не должно увеличить размер баз.

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

Сокращаем объём данных

Уменьшать можно двумя способами:

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

Эволюция формата хранения данных до наступления эры подъездов

Самый первый и самый простой вариант

Традиционный способ сохранить сложные данные — нормализовать их, поместить в табличную базу данных и создать вспомогательные индексы. Когда-то 2ГИС так и делал, разве что для уменьшения размера содержимое каждой таблицы сортировалось таким образом, чтобы как можно чаще значения ячеек совпадали со значениями из предыдущей строки. Столбцы мы хранили независимо, а последовательности одинаковых значений схлопывали.

Сильно упрощённый пример оптимизации хранения таблицы со зданиями:

Пример оптимизированного хранения таблиц

Впрочем, в то время эти таблицы использовались не только для получения данных для отображения, а практически для всех задач, включая поиск по тексту и различные типы поиска проезда. Нормализация позволяет уменьшить избыточность, но есть и негативная сторона — для формирования UI-элемента для какого-то объекта приходится делать несколько запросов, обращающихся к большому количеству таблиц. Для всех этих задач нормализованные данные как раз позволяли уменьшить количество обрабатываемой информации.

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

Карточки и связи

Упрощаем работу

Как можно упростить работу с данными? Получать разом все данные, необходимые для отрисовки карточки, по идентификатору объекта. Поскольку онлайн-версия и так получает от API все данные за один запрос в формате JSON, можно заодно и объединить форматы, используемые всеми нашими продуктами.

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

Возьмём для примера Москву, как самый большой из наших проектов. Наивный подход хранения json’ов — использование key-value базы данных. Полученный размер почти в шесть раз больше, чем у предыдущего описанного варианта, и это ещё без связей и свойств. Даже в максимально простом виде — для каждого объекта хранится сам json, 8 байт идентификатора и символ-разделитель — справочник займёт 1,9 ГиБ.

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

Сжимаем данные

Нормализация — не единственный способ устранения избыточности. Второй популярный способ — сжатие. lzma-архив нашего невероятно толстого файла занимает всего 55 МиБ.

Конечно, использовать напрямую такой формат мы не можем, так как для доступа к произвольному объекту нужно распаковать все данные, хранящиеся раньше, да и lzma-архивы распаковываются не сильно быстро.

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

Формат бинарного хранилища

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

Осталось связать эти данные с идентификаторами объектов. В таком формате хранятся все данные — json’ы, связи и свойства. Это позволяет нам уменьшить размер ссылок, просто отсортировав содержимое бинарных хранилищ по уменьшению частоты встречаемости.
Для каждого идентификатора нам нужно хранить одну или несколько пар <номер хранилища, номер данных в хранилище>.
Упрощённый формат связей идентификатора объекта и данных в хранилищах
Все порядковые номера, смещения и размеры хранятся в сжатом формате, похожем на UTF-8, где маленькие значения занимают всего один байт.

Сортировка и уменьшение размера

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

Ускоряем поиск данных

У описанного формата есть одна проблема. Чтобы найти номер объекта, хранящего индексы для указанного идентификатора, нам нужно прогнать бинарный поиск внутри данных первого объекта. Для этого нужно либо загрузить 10,9 МиБ в память, либо сделать 21 дополнительное чтение. Оба решения нам не подходят, а потому мы уменьшаем число чтений, храня данные в виде дерева.

Формат дерева быстрого поиска данных по идентификатору

Мы добавили три уровня дерева и уменьшили количество дополнительных чтений до четырёх (а на самом деле, с учётом кэширования прочитанных ранее узлов дерева, даже до 1–3). Группируем данные по 32 объекта, а в промежуточных уровнях храним по 128 первых идентификаторов вложенных узлов. Цена — чуть менее 400 КиБ.

Это понятно. На данном этапе мы довольно эффективно храним связи и свойства, но json’ы занимают много места. Но, с другой стороны, тем больше работы нам нужно совершить, чтобы прочитать отдельный объект. Чем больше размер страницы, тем больше туда попадает объектов и тем лучше алгоритм сжатия способен определить, какая информация избыточна. Следовательно, нужно помочь алгоритму лучше справляться со своей работой. Json’ы же — довольно большие объекты, а потому в одной странице их находится совсем немного.

Разбиваем json’ы на части

Во-первых, многие объекты имеют совпадающие схемы данных, различаются только значения атрибутов. Во-вторых, многие значения атрибутов совпадают даже у объектов с разными схемами. Выделим схемы и значения атрибутов в отдельные хранилища, а сами json’ы будем хранить в виде: ссылка на схему + ссылки на значения атрибутов.

Разбиение json’а на схему и данные

Значит, мы можем вынести их в отдельный файл и вместо них хранить номер. В нашей схеме данных количество названий атрибутов ограничено. Также сделаем ещё несколько изменений, попутно учитывая, что json’ы у нас всегда являются объектами.

Реальный формат хранения схем json-объектов

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

Но не зря же всё это было! Устанавливаем размер страницы в 1 КиБ и оказывается, что пока мы оптимизировали формат так, чтобы, с одной стороны, чтение не было сильно медленным, а с другой — данные запаковывались максимально хорошо, мы… уже обошли «оптимизированные таблицы» и по размеру, и по удобству использования. Натравливаем zlib и проверяем, что на фоне остальной работы чтение данных из базы занимает незначительное время. Максимальный выигрыш должен быть от сжатия значений атрибутов, свойств и схем. Удовлетворённые результатом, переключаемся на другие задачи.

Избавляемся от ненужного

Начинаем уменьшать с поиска данных, от которых можно избавиться. Оказывается, что за время существования формата мы научились обходиться без самой большой связи. Это 10% размера!

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

Распределение пользователей по версиям

Распределение пользователей по версиям

В самом верху — распределение пользователей по последним версиям Android-приложения. Снизу — iOS.

Несложно заметить, что пользователи iOS-устройств обновляются гораздо охотнее, но даже среди них пользователей старых версий очень много.

Также мы до сих пор выпускаем новые данные для замороженной версии под Windows Phone. И пусть пользователи WP8 составляют лишь малую долю от нашей аудитории, в абсолютных числах это почти 200 000 в месяц.

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

Приятный бонус от проделанной работы — уменьшение размера ежемесячных обновлений, так как удалённая связь сильно изменялась от месяца к месяцу, раздувая размер diff’ов.

Пока решили не трогать. Если посмотреть на оставшиеся данные, то суммарно можно выжать ещё те же 10%, однако цена будет несопоставимо больше.

Оптимизируем текущий формат хранения

Как было написано выше, мы делали страницы размером 1 КиБ и запаковывали не все бинарные хранилища.

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

Чем больше размер страницы, тем более эффективно сжимаются данные, но тем медленнее происходит выборка данных. Следующий пункт — выбор оптимального размера страницы. После тестов решаем увеличить размер до 8 КиБ. И если с увеличением размера страницы расходы по времени и памяти растут линейно, то выигрыш становится всё менее заметным.

Влияние размера страницы на большие выборки

Это означает, что по-хорошему нужно выбирать разные размеры для хранилищ в зависимости от сценариев использования хранящихся в них данных.
Если увеличение страницы ожидаемо замедляет маленькие выборки, то вот большие — от сотен элементов — при этом даже ускоряются.

Суммарно только эти два пункта позволяют уменьшить базу на 18%!

Меняем формат сжатия

zlib, конечно, классика, но zstd обеспечивает большую скорость распаковки при большей же степени сжатия. Более того, zstd позволяет сначала построить единый словарь для всех имеющихся данных, а затем сохранить его один раз и сжать им все страницы. Таким образом, мы прилично замедляем процесс формирования файла с базой данных, но зато выжимаем дополнительные 8%.

Добавляем подъезды

Простой способ

Самый простой способ — сделать каждый подъезд отдельным объектом, отдельно их индексировать (по грубым оценкам +10% размера индекса) и отдельно же в данных для отрисовки карты хранить их геометрию.

На предыдущих этапах мы выиграли более чем достаточно, чтобы успокоиться и работать с подъездами по привычной схеме, но… на момент старта работ мы не были в этом уверены, а работа над альтернативным форматом шла параллельно. Такой способ раздует базу суммарно на 3%.

Подробная оценка, для заинтересованных

Попробуем оценить увеличение размера пакета с базой данных на каждый объект:

8 байт — идентификатор,
6 байт — номера используемых хранилищ (данные + пять свойств; свойства выделены из основных данных и хранятся в бинарном виде, так как часто нужны для большого числа объектов разом),
3 байта — индекс в хранилище данных,
2 байта — смещение данных объекта,
5 байт — значения данных — 2 байта на схему, 3 байта в среднем на информацию о квартирах (считаем, что будет много повторяющихся и сами данные хранятся один раз),
6 байт — смещения данных координат (остальные свойства имеют много повторяющихся значений и будут схлопнуты),
8 байт — значения координат.

В случае Москвы это 4,5 МиБ для более чем 124 тысяч собранных входов. Итого 38 байт на объект.

Ещё 1 МиБ. Далее нам нужно хранить ещё и связь между домом и входами, это 2,5 байта на каждый жилой дом и 8 байт на каждый вход.

Теперь считаем, сколько всё это займёт в карте.

Для полилиний первая точка всегда занимает 8 байт, а все последующие хранятся в виде diff’ов нужной точности. Во-первых, мы должны хранить геометрии. Большая часть входов состоит из двух точек, не сильно удалённых друг от друга, а потому можно считать, что сама геометрия будет занимать 10 байт. Здесь нас устроит точность до дециметров. Итого 1,2 МиБ.

Индекс — такое же бинарное хранилище, как и всё остальное, только в данных хранится назначение связи (1 байт), номер слоя (1 байт) и номер объекта (3 байта). Ещё нам нужно связать идентификатор входа и объект с его геометрией. Итого ещё 1,5 МиБ. Плюс по 8 байт на идентификатор, а также дерево быстрого поиска.

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

Суммируя всё, получаем 14,2 МиБ, что как раз чуть больше 3%.
10% индекса поиска — это 5,9 МиБ.

Текущий вариант

Вместо того, чтобы индексировать подъезды и раздувать поисковый индекс, мы ищем дома, но дополнительно размечаем слова запроса и выделяем из него адреса (актуально для поиска подъездов в Калининграде), подъезды и/или квартиры. Таким образом, на выходе у нас есть идентификатор дома и типизированные текстовые поля, по которым мы должны найти нужный нам подъезд.

Примечание

С одной стороны он позволяет нам сократить размер базы, а с другой ставит ограничения на формат ввода — подъезды не будут находиться по многим запросам, которые были бы правильно обработаны при использовании честного поиска.
Это спорный пункт.

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

Последнее стоит раскрыть подробнее.

Такие входы можно хранить в виде точка + направление, т.е. Во-первых, замечаем, что большинство входов состоит из двух точек и имеют одинаковую длину. экономить по 1 байту на каждый вход.

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

Что, если для здания добавить новое свойство — его целочисленное «направление», а для каждого входа выделить ещё два — целочисленные смещения в дециметрах вдоль и перпендикулярно линии направления? Центральные точки зданий у нас уже есть. Учитывая, как у нас хранятся json’ы с информацией, геометрия входа в среднем будет занимать чуть более двух байт.

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

Ранее мы просто говорили карте «покажи такие-то объекты», а теперь при отображении входов добываем эти данные из json’а и добавляем на карту динамические объекты. Минус — усложнился код. К моменту отображения стрелочек входов json’ы соответствующих объектов у нас уже есть, то есть нет необходимости дополнительно идти в базу. Тут всё не сильно страшно. С отображаемыми точками подъездов всё несколько хуже — теперь нам приходится в фоне определять, какие дома видны, вытаскивать данные этих домов из базы данных, разбирать json’ы, и, если там есть входы, создавать для них динамические объекты.

Примечание

Даже с учётом всевозможных оптимизаций и довольно быстрой работы всё равно совершаем дополнительные действия, без которых можно было обойтись, увеличив размер базы на 0,2% (972 КиБ для Москвы).
Неоднозначное решение.

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

3% превратились в 0,5%. Сколько нам это дало? Можно было бы ещё меньше, но мы оставили в данных идентификаторы (которые довольно плохо сжимаются), чтобы упростить обработку сообщений пользователей о неточных входах.

Результат

Мы добавили большое количество подъездов, при этом сократив размер файла с данными карты на 0,5% и уменьшив на 26,6% размер файла с данными справочника. Последний по-прежнему является самым большим из наших файлов, но он — лишь один из четырёх «тяжёлых» файлов, так что общее изменение получилось более скромным — 10,1%.

Изменение размеров базы Москвы с течением времени

Размер баз со временем немного подрастёт (по текущей оценке та же Москва увеличится на 0,4%), но в любом случае цель выпустить подъезды, не увеличив размер, более чем достигнута. Подъезды собраны пока не все.

Что дальше?

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

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

И, конечно, будем править ошибки, которых пока что имеется.

One more thought: используйте JSON разумно

Из написанного выше напрашивается вывод, что можно не сильно думать о бинарных форматах и просто использовать JSON. Это не совсем так. У нас это работает, так как единомоментно нам нужно получать от силы несколько десятков объектов. Плюс мы используем rapidjson, а он очень шустрый и потребляет мало памяти.

Также стоит ограничивать передачу данных в формате JSON из C++ в UI, написанный на другом языке.

Во-первых, вам придётся превратить его в строку.

Во-вторых, парсеры, доступные из UI-части, будут повторно эту строку разбирать, и будут делать это заметно медленнее.

Лучше самостоятельно доставать из JSON’а все данные, а на сторону UI прокидывать простые интерфейсы, адаптированные для отображения конкретных элементов.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть