Новые способы хранения тайлов в Картах: как один сервер выдерживает 80k RPS / Хабр

80k RPS и 25 Гбит/с трафика тайлов с одного сервера — звучит как мечта для картографического сервиса? На самом деле это реально — если ваш способ отдачи тайлов спроектирован для этого.

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

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

Статическая и динамическая генерация тайлов

Тайл — это как кусочек пазла: один из квадратов 256 × 256 пикселей, которые браузер склеивает в карту.

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

на наименьшем уровне (zoom = 0) вся карта покрывается одним тайлом;
на следующем уровне (zoom = 1) вся карта умещается на четырёх тайлах;
на уровне больше (zoom = 2) карту покрывает сетка из 16 тайлов и так далее.

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

С увеличением производительности железа стало возможным динамически генерировать тайлы подробных масштабов на сервере (с некоторой офлайн‑предобработкой). Такой подход до сих пор используется во многих картографических сервисах, часто это стек вида Клиент → Кеширующий бэкенд → Рендерящий бэкенд → PostGIS. Однако с ростом количества пользователей картографических сервисов выросло и пиковое потребление CPU таких сервисов, при этом его утилизация остаётся низкой, так как инфраструктуру нужно держать в постоянной готовности к пиковым нагрузкам.

С появлением векторных тайлов и их рендерингом на клиенте, а также техники overzoom стало возможным вовсе отказаться от генерации отдельных тайлов для подробных масштабов (зумы 16+) и использовать данные из тайлов предыдущих масштабов (15-й зум). Наряду с этим, а также с ростом объёма и производительности SSD на серверах, статическая генерация тайлов снова становится актуальной, особенно учитывая возможности современной облачной инфраструктуры. Набор тайлов можно эффективно сгенерировать офлайн на большом вычислительном кластере и отдавать эти тайлы с сервера, который не будет делать почти никаких вычислений (производительность будет упираться в сеть, а не в CPU). При этом будут хорошо утилизироваться как ресурсы CPU (на кластере), так и ресурсы сервера. Об одном из таких подходов расскажу в следующем разделе.

Хранение статически сгенерированных тайлов

Существует множество способов хранения статически сгенерированных тайлов. Для небольших датасетов достаточно удобно хранить тайлы в файловой системе или в каком‑либо другом key‑value‑хранилище:

Храним на сервере в файловой системе с путями вида {prefix}/{z}/{x}/{y}.png и отдаём как статику.
Храним в S3 по ключу вида {z}/{x}/{y}, опционально перед S3 ставим кеш.
Храним на сервере в базе данных SQLite в формате MBTiles и отдаём с помощью mbtileserver.

Однако такие способы хранения обычно плохо масштабируются для больших датасетов. Файловые системы быстро упираются в лимиты по числу inode, занимают в разы больше места из‑за минимального размера блока, а простые операции копирования или удаления могут длиться минуты даже для небольших датасетов. Загрузка большого количества объектов в S3 имеет аналогичные проблемы с производительностью. Использование SQLite решает основные проблемы хранения большого количества тайлов, но требует наличия специализированного бэкенда, а также доставки датасета на все его инстансы.

В последние годы начали появляться новые форматы хранения тайлов, которые лучше используют возможности и особенности современной облачной инфраструктуры. Общая идея этих форматов следующая. Весь набор тайлов хранится в одном большом файле в S3. Клиент, который хочет получить некоторый тайл, с помощью нескольких запросов HTTP Range узнаёт, в каком месте файла находится нужный тайл (смещение и размер), и скачивает только эту часть файла. При этом в качестве клиента может выступать как бэкенд (специализированный сервер, отдающий содержимое тайла по координатам x, y и зуму z), так и фронтенд (получая данные напрямую из S3). Примеры таких форматов — Cloud Optimized GeoTIFF и PMTiles.

Основные различия таких форматов заключаются в устройстве индекса — способе получения по координатам x, y и z тайла его места хранения (смещение и размер) в файле. У каждого из таких форматов есть свои преимущества, но для наших сценариев использования (на серверной стороне, с высокой нагрузкой, с различными типами датасетов) они подходят плохо. Поэтому мы придумали свой ~~велосипед~~ способ хранения индекса, который позволяет эффективно хранить и отдавать тайлы как для датасетов большого размера (например, вся базовая подложка Карт), так и для значительного количества датасетов небольшого размера (например, экспериментальные слои). О нём и пойдёт речь далее.

Формат хранения

Заметим, что большая часть тайлов в датасетах (особенно на подробных масштабах) либо пустая (земля или фон), либо часто повторяющаяся (полигон, залитый одним цветом, — например, вода или растительность). Такие тайлы имеют одинаковое содержимое, поэтому мы можем использовать дедупликацию для хранения только одной копии такого тайла и использовать индекс, чтобы сохранить отображение из координат x, y и z тайла в уникальное место хранения тайла (его смещение и размер в файле). Количество тайлов с уникальной информацией на порядок меньше общего количества тайлов, даже для больших датасетов (пример расчёта для OSM).

Будем хранить файл с тайлами в таком формате:

Заголовок и метаданные: хранятся версия, позиции и размеры остальных секций внутри файла, а также прочая информация о датасете и настройках хранения данных.
Секция с дедуплицированными данными тайлов: последовательно хранится содержимое всех тайлов как есть, без каких‑либо разделителей.
Секция с индексом тайлов: для каждого тайла хранится его смещение внутри секции с данными и размер.

           Metadata   Tile Data   Tile Index  
            Length     Length      Length     
          <--------> <---------> <----------> 
+--------+----------+-----------+------------+
|        |          |           |            |
| Header | Metadata | Tile Data | Tile Index |
|        |          |           |            |
+--------+----------+-----------+------------+
         ^          ^           ^             
      Metadata   Tile Data   Tile Index       
       Offset     Offset      Offset

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

Простой формат индекса

На каждом уровне масштабирования z карта разбивается на тайлов. У каждого тайла есть порядковый номер [x, y], где x — номер тайла по оси X, y — номер тайла по оси Y.

В простом формате мы храним индекс линейно. Для каждого зума мы упорядочиваем тайлы (координаты x и y) на этом зуме по кривой Гильберта или кривой Мортона и сохраняем для каждого тайла 8 байт: 40 бит для смещения в файле и 24 бита для размера тайла. Сначала значений для зума 0, затем значений для зума 1, значений для зума 2 и так далее.

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

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

Недостатки формата:

Необходимо хранить смещения для всех тайлов: для 15-го зума это 8 × 4^15 = 8 ГБ данных. Для небольших датасетов это значительно превышает размер самих данных в тайлах.
Плохо масштабируется на зумы 16 и выше (индекс получается слишком большим).
Плохо кешируется (нет локальности между зумами).

Блочное хранение индекса

Попробуем устранить недостаток простого формата индекса, связанный с неудобством кеширования. При кешировании индивидуальных запросов по 8 байт кеш будет прогреваться очень медленно (для 15-го зума может потребоваться $4^{15}$ таких запросов). При кешировании блоками памяти кеш прогревается быстрее, но hit rate растёт не так сильно, как хотелось бы, поскольку смещения для каждого зума хранятся независимо (не локально по z).

Рассмотрим альтернативный способ. Представим весь набор тайлов в виде дерева по зумам, наподобие полного квадродерева:

Корень — тайл [x, y, z] = [0, 0, 0].
Дочерние узлы каждой вершины — все тайлы следующего зума, находящиеся пространственно внутри родительского тайла. Например, у тайла [x, y, z] будут дочерние тайлы:
- [2x + 0, 2y + 0, z + 1]
- [2x + 0, 2y + 1, z + 1]
- [2x + 1, 2y + 0, z + 1]
- [2x + 1, 2y + 1, z + 1]

И наоборот, у тайла [x, y, z] родительский тайл [x/2, y/2, z − 1].

Разделим дерево тайлов на два уровня. На первом уровне будут все тайлы первой половины зумов, на втором — все тайлы второй половины. Например, для зумов [0..15] первый уровень будет содержать все тайлы на зумах [0..7], а второй уровень — все тайлы на зумах [8..15]. Первый уровень состоит из одного поддерева с корнем в z = 0 и содержит 8 зумов, второй уровень состоит изподдеревьев с корнями в z = 8 и содержит 8 зумов.

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

Каждое поддерево содержит локальную часть индекса: все его тайлы находятся в некоторой ограниченной области карты и на последовательном диапазоне зумов. При запросе тайла из какого‑либо поддерева можно загрузить всё поддерево в кеш, рассчитывая на локальность запросов (соседние по x, y и z тайлы, скорее всего, окажутся в том же блоке).

Разреженный формат индекса

Заметим ещё одну особенность тайлов. Если тайл пустой (земля или фон) или часто повторяющийся (например, вода или растительность) на некотором зуме, то он, скорее всего, будет таким и на больших зумах. То есть если тайл где‑то в Тихом океане полностью залит водой на зуме 8, то он будет залит водой и на зумах с 9-го по 15-й^*.

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

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

При таком способе дедупликации у нас получаются тайлы трёх типов:

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

Обозначения: тайл-источник, тайл-дубликат, тайл-пустышка — Обозначения: тайл‑источник, тайл‑дубликат, тайл‑пустышка

Для каждого зума сохраним в индексе два массива значений:

Отсортированный набор тайлов‑источников. Для каждого такого тайла сохраним:
- 16 бит — координата x;
- 16 бит — координата y;
- 40 бит — смещение в файле;
- 24 бита — размер тайла.
Итого: 12 байт на тайл.

Отсортированный набор тайлов‑дубликатов. Для каждого такого тайла сохраним:
- 16 бит — координата x тайла‑дубликата;
- 16 бит — координата y тайла‑дубликата;
- 16 бит — координата x тайла‑источника (на который ссылается этот тайл‑дубликат);
- 16 бит — координата y тайла‑источника (на который ссылается этот тайл‑дубликат).
Итого: 8 байт на тайл.

Упрощенный пример схемы flatbuffers

struct LocationItem {
    // 16-bit tile coordinates (x and y) encoded with z-order curve (Morton code)
    tile_code: uint32 (key);

    // 40 bits for file offset and 24 bits for size
    tile_location: uint64;
}

struct LinkItem {
    tile_code: uint32 (key);
    link_code: uint32;
}

table SparseLocations {
    tiles: [LocationItem];
    links: [LinkItem];
}

table DenseLocations {
    locations: [uint64];  // tile_code -> tile_location
}

enum BlockType : uint32 { Invalid = 0, Dense = 1, Sparse = 2 }

table SparseBlock {
    block_type: BlockType;
    dense_locations: [DenseLocations];  // zoom -> DenseLocations
    sparse_locations: [SparseLocations];  // zoom -> SparseLocations
}

root_type SparseBlock;

Этой информации будет достаточно, чтобы восстановить исходное дерево тайлов (оно же индекс). Нам будет интересно как офлайн‑восстановление всего дерева (для возможности экспорта набора тайлов в другой формат), так и онлайн‑запросы к индексу (чтобы быстро получить место хранения конкретного тайла, не восстанавливая весь индекс).

В таком формате индекса для набора данных с пустыми тайлами (самый хороший случай) и зумами [0..15] нам потребуется сохранить 16 тайлов‑источников и 15 × 3 тайлов‑дубликатов, итого (16 × 12) + (15 × 3 × 8) = 552 байта для хранения всего индекса. Но лучше хранить не весь индекс целиком, а двумя уровнями (аналогично блочному формату). Для этого в листьях блока первого уровня можно хранить места хранения блоков второго уровня.

Преимущества формата:

Небольшой размер индекса, даже для больших датасетов. Для больших и плотных датасетов (например, базовой подложки) индекс обычно в три‑четыре раза меньше, чем в простом формате. Для маленьких и средних датасетов индекс обычно занимает меньше места, чем сами данные, и умещается в несколько десятков мегабайт.
Легко масштабируется на зумы 20+.
Хорошая кешируемость индекса. Кеш прогревается быстро, блоки небольшие.
Для обработки запроса не требуется парсить весь блок индекса и поддерживать его хранение в памяти.

Недостатки формата:

Нетривиальность алгоритма и его реализации.
Требуется ненулевая нагрузка на CPU (но всё равно небольшая).
Для холодного старта требуется дополнительный запрос в S3 для получения второго уровня индекса (хуже latency первого запроса).

Дедупликация поддеревьев (осторожно, алгоритмы)

Основная идея разреженного индекса — найти и сохранить только одну копию для каждого уникального поддерева тайлов. Для быстрого определения эквивалентности поддеревьев будем использовать алгоритм, похожий на нечто среднее между Merkle tree и цифровой сортировкой суффиксов циклической строки, используемой для построения суффиксного массива.

Здесь и далее под содержимым тайла будем понимать место хранения тайла в файле (смещение и размер), а под равенством тайлов — равенство мест их хранения.

Наш алгоритм состоит из двух проходов:

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

Шаг 1. Поиск эквивалентных поддеревьев (снизу вверх)

Присвоим каждому узлу дерева класс эквивалентности (относительно узлов того же зума). Классы эквивалентности двух узлов дерева на одном и том же зуме равны тогда и только тогда, когда:

их корневые тайлы имеют одинаковое содержимое;
все дочерние поддеревья попарно эквивалентны (рекурсивное условие).

Начнём с максимального зума (с листьев дерева). На этом уровне у тайлов нет дочерних тайлов, поэтому классы эквивалентности очевидны (проверяем равенство содержимого тайлов).

Итеративный шаг (от зума z + 1 к z, от листьев дерева к корню): предположим, что мы уже вычислили классы эквивалентности для всех тайлов на уровне z + 1, теперь нам нужно вычислить их для уровня z.

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

Шаг 2. Формирование индекса (сверху вниз)

После вычисления классов эквивалентности для всего дерева присвоим тайлам тип (тайл‑источник, тайл‑дубликат) и сохраним их в индексе. В процессе присвоения типа будем поддерживать инвариант: если тайл является тайлом‑дубликатом, то в его поддереве не может быть тайлов‑источников. И наоборот — у тайла‑источника все родители являются тайлами‑источниками.

Начнём с нулевого зума (с корня дерева). Тайл на этом уровне только один, и это всегда тайл‑источник. Сохраним его в списке тайлов‑источников.

Далее будем вычислять типы тайлов по уровням, но на этот раз будем действовать от меньших зумов к большим (от корня дерева к листьям). Пройдём по всем тайлам зума в порядке кривой Гильберта.

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

Обход по всем тайлам зума и разметка типа тайлов

Обход по кривой Гильберта важен: он гарантирует нам, что все тайлы в поддереве тайла‑дубликата будут пройдены позже всех тайлов этого же уровня‑зума в поддереве тайла‑источника.

Стоит отметить, что описанный алгоритм не всегда строит абсолютно минимальный по размеру индекс. Например, он не будет пытаться представить одно поддерево как другое, «почти такое же», с добавлением нескольких тайлов‑источников для исправления различий. Однако на практике он даёт отличные результаты, при этом оставаясь достаточно простым в реализации.

Онлайн‑запросы к индексу

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

Сначала определим тип запрашиваемого тайла:

Если тайл находится в списке тайлов‑источников, то берём его место хранения оттуда и возвращаем в качестве результата.
Если тайл находится в списке тайлов‑дубликатов, то смотрим на тайл‑источник, на который ссылается этот тайл‑дубликат, и берём место хранения оттуда.
Если тайла нет в этих списках, то это тайл‑пустышка. Он существует неявно, как часть скопированного поддерева. Чтобы найти его данные, нам нужно:
- найти предка нашего тайла, который был скопирован;
- определить, откуда (из какого поддерева) он был скопирован;
- найти в этом поддереве тайл, соответствующий нашему тайлу‑пустышке.
Назовём эти три действия «вверх», «в сторону» и «вниз».

Для действия «вверх» мы поднимаемся по дереву к родительским тайлам, на каждом шаге проверяя, не является ли текущий предок тайлом‑дубликатом (ищем его в соответствующем списке). Первого найденного предка‑дубликата мы назовём тайлом‑родителем.

Для действия «в сторону» мы находим у тайла‑родителя ссылку на его источник (тайл‑источник) в списке тайлов‑дубликатов.

Для действия «вниз» нам нужно найти в поддереве тайла‑источника тайл, который соответствует нашему исходному тайлу‑пустышке. Путь от тайла‑родителя до нашего тайла‑пустышки определяет, куда необходимо спуститься от тайла‑источника.

Обозначения: тайл-пустышка (запрашиваемый тайл), тайл-родитель (тайл-дубликат), тайл-источник, тайл-цель — Обозначения: тайл‑пустышка (запрашиваемый тайл), тайл‑родитель (тайл‑дубликат), тайл‑источник, тайл‑цель

Найти нужный нам тайл можно, используя бинарное представление координат тайла. Координаты x и y тайла имеют разрядность z бит на зуме z. Заметим, что старшие биты координат тайла‑пустышки и тайла‑родителя совпадают (у тайла [x, y, z] родитель [x/2, y/2, z − 1]). А путь вниз по поддереву от тайла‑родителя до тайла‑пустышки характеризуется младшими битами координат тайла‑пустышки. Тогда для получения нужных нам координат возьмём старшие биты тайла‑источника и младшие биты тайла‑пустышки.

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

Псевдокод

TileId changeRoot(TileId tile, TileId newRoot)
{
  uint32_t zDiff = tile.z - newRoot.z;
  return {
    .x = (newRoot.x << zDiff) + (tile.x & ((1U << zDiff) - 1)),
    .y = (newRoot.y << zDiff) + (tile.y & ((1U << zDiff) - 1)),
    .z = newRoot.z + zDiff,
  };
}

fbs::Location querySparse(const auto* locations, TileId tileId)
{
  auto findTile = [=](TileId tileId) -> const fbs::LocationItem* {
    return locations->Get(tileId.z)->tiles()->LookupByKey(encodeTileId(tileId));
  };
  auto findLink = [=](TileId tileId) -> const fbs::LinkItem* {
    return locations->Get(tileId.z)->links()->LookupByKey(encodeTileId(tileId));
  };
  auto resolveLink = [=](TileId tileId) -> TileId {
    return decodeTileId(findLink(tileId)->link_code(), tileId.z);
  };

  while (!findTile(tileId)) {
    TileId pTileId = tileId;
    while (!findTile(pTileId) && !findLink(pTileId)) {
      pTileId = parent(pTileId);
    }
    if (!findTile(pTileId)) {
      tileId = changeRoot(tileId, resolveLink(pTileId));
    }
  }

  return findTile(tileId)->location();
}

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

Всего мы можем сделать до z рекурсивных вызовов. При этом на каждом рекурсивном вызове делаем до z бинарных поисков в наборах тайлов‑источников и тайлов‑дубликатов. Итого получаетсяпамяти и примерно $O(z \cdot z \cdot \log 4^z) = O(z^3)$ времени, что для типичных картографических зумов можно считать константой.

Офлайн‑восстановление всего индекса

Иногда мы хотим восстанавливать весь индекс сразу (например, для экспорта тайлов в другой формат). Мы могли бы использовать для этого алгоритм онлайн‑восстановления, но зная, что нам необходимо восстановить всё дерево, мы можем сделать алгоритм быстрее и проще.

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

тип тайла (тайл‑источник, тайл‑дубликат, тайл‑пустышка);
для тайлов‑дубликатов и тайлов‑пустышек — ссылку на тайл‑источник, откуда в результате было взято содержимое.

Восстановим в три этапа на каждом уровне:

Восстановим все тайлы‑источники. Мы сохранили в индексе всю нужную информацию о них.
Восстановим все тайлы‑дубликаты. Мы уже восстановили информацию обо всех тайлах‑источниках, на которые они ссылаются.
Восстановим все тайлы‑пустышки. Обходим все отсутствующие тайлы уровня в порядке кривой Гильберта. Такие тайлы находятся внутри скопированного поддерева, для каждого из них:
- поднимемся на уровень выше, к родителю;
- извлечём из сохранённой информации ссылку на тайл‑источник;
- найдём в поддереве тайла‑источника тайл, который соответствует нашему тайлу‑пустышке (битовыми операциями, аналогично онлайн‑восстановлению).

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

Алгоритм работает за $O(4^{max(z)})$ времени и памяти, что для плотного датасета будет , где n — количество тайлов в блоке.

Плюсы, минусы и подводные камни

Плюсы подхода:

Высокая производительность. На датасете с векторными тайлами OSM у меня получалось достичь 80k RPS и 25 Гбит/с с одного сервера (конкретные цифры будут зависеть от датасета, профиля нагрузки и способа доставки датасета). Производительность упирается в сеть, а не в CPU.
Архитектурная простота. На бэкенде отсутствует какая‑либо сложная логика рендеринга тайлов, а также минимум точек отказа. Базовая реализация умещается в сотню строчек кода. Меньше кода — меньше багов.
Меньше проблем при переключении релизов данных. При динамической генерации тайлов в архитектуре Клиент → Кеширующий бэкенд → Рендерящий бэкенд → PostGIS переключение версий данных инвалидирует весь кеш, создавая пиковую нагрузку на рендеринг. Чтобы этого избежать, нужно реализовывать сложную логику плавного переключения релизов или предварительного прогрева кеша, что само по себе становится источником ошибок и усложняет инфраструктуру. Для статически сгенерированных тайлов этой проблемы не существует — рендеринг уже выполнен офлайн.
Быстрый старт. С холодного запуска первый тайл тяжёлого датасета можно получить за три лёгких запроса HTTP Range в S3 (не нужно скачивать весь датасет).
Гибкость для множества датасетов. Один сервер может одновременно отдавать множество различных датасетов, общий размер которых может не помещаться на диск одного сервера (например, архив исторических данных).
Простой процесс публикации датасета. Для этого нужно загрузить один файл в S3, после чего датасет будет доступен для всего сервиса.
Лёгкое масштабирование. Серверы можно сделать stateless или даже serverless, а горизонтальное масштабирование свести к поднятию новых инстансов без необходимости загружать данные на диски всех серверов и координировать состояние этой загрузки. Однако в таком случае нужно учитывать лимиты S3.
Можно обойтись без специализированного сервера. Формат позволяет перенести логику обработки формата на клиент и запрашивать данные напрямую из S3.
Простой интерфейс вида writeTile(x, y, z, data) и readTile(x, y, z) → data. Поверх него с помощью метаданных уже можно навесить необходимую для сервиса логику. Не требуется специальная обработка отсутствующих тайлов.

Минусы подхода:

Статичность датасета, значительно сложнее кастомизировать и персонализировать тайлы в зависимости от параметров запроса. Как мы сгладили этот недостаток, я расскажу далее.
Иммутабельность данных. Для упрощения кеширования используется предположение о неизменности данных в S3. Для обновления датасета нужно загружать в S3 новый файл.
Сложность инкрементальных обновлений. При обновлении любого тайла нужно перестраивать весь индекс.
Датасет хранится в одном файле. Гигантские датасеты размером 1 ТБ и более, не помещающиеся на одном сервере, могут потребовать особых подходов к загрузке в S3 (multipart‑запись по частям).

Выводы из разработки и эксплуатации

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

Одноуровневый индекс подходит только для локального хранения или для набора тайлов небольшого размера. Вне зависимости от попыток сжать этот индекс, накладные расходы на первый запрос получались слишком большими.
Лучше избегать необходимости нетривиальной распаковки индекса. Распаковка индекса на каждый запрос потребляет слишком много CPU, а готовых библиотек для производительного production‑ready‑кеша в памяти достаточно мало, и они не всегда могут подойти для вашего сервиса.
Лучше избегать лишних запросов в S3. Из‑за latency очень быстро заполняются очереди соединений, а при неаккуратной реализации — доступные порты и прочие ресурсы.
Не все форматы векторных тайлов одинаково удобны для статической отдачи. Иногда возникает необходимость объединить несколько источников тайлов при отдаче одного тайла. Некоторые популярные форматы векторных тайлов сейчас кодируются с помощью protobuf, а конкатенация protobuf‑сообщений является самым простым и производительным способом объединения двух тайлов (работает и для данных, сжатых gzip). Однако такой приём работает только для построчного, но не для поколоночного хранения данных в тайле. В этом плане, например, формат MVT удобнее формата MLT.
Статическая генерация тайлов не означает, что тайлы не могут быть кастомизированы в зависимости от параметров запроса (обычно это локаль пользователя). Мы можем разбить данные в тайле на две части — основную часть (не зависящую от параметров запроса) и несколько дополнительных частей (зависящих от параметров запроса). А при ответе пользователю использовать приём с конкатенацией, чтобы склеить основную часть с подходящей дополнительной частью.

Нагрузочное тестирование и сравнения

Целью этого сравнения было найти способ отдачи статически сгенерированных тайлов, который даёт максимальный RPS с полностью прогретым кешем (для первого нашего сценария использования). Про оптимизацию хранения в S3 (второй сценарий использования) расскажу в одной из следующих статей. Для динамической генерации тайлов похожее сравнение можно найти здесь.

Замерялось на конфигурации, аналогичной BA‑a704-4N-2×25G (AMD EPYC 9654, 96 CPU, сеть 25 Гбит/с) с помощью yandex‑tank на запросах из OSM tile_logs. Датасет large_z15 хранился локально на SSD с полностью прогретым page cache (отсутствие дисковых операций по мониторингам), остальные датасеты хранились в tmpfs.

Формат	small_z14	medium_z12	large_z15
Простой формат	100k+ RPS, 24 Гбит/с, 7 CPU	59k RPS, 25 Гбит/с, 9 CPU	80k RPS, 25 Гбит/с, 7 CPU
Разреженный формат	100k+ RPS, 24 Гбит/с, 19 CPU	59k RPS, 25 Гбит/с, 14 CPU	80k RPS, 25 Гбит/с, 42 CPU
Статические файлы	100k+ RPS, 24 Гбит/с, 5 CPU	59k RPS, 25 Гбит/с, 5 CPU	Fail¹
mbtileserver v0.11.0	51k RPS, 12 Гбит/с, 46 CPU	32k RPS, 14 Гбит/с, 36 CPU	40k RPS, 13 Гбит/с, 52 CPU
go‑pmtiles v1.29.1	38k RPS, 9 Гбит/с, 14 CPU	29k RPS, 12 Гбит/с, 17 CPU	36k RPS, 11 Гбит/с, 13 CPU

^¹^{Не хватило inode из‑за слишком большого количества файлов}

large_z15 — тайлы из 20251229.pmtiles, около 120 ГБ.
medium_z12 — тайлы из 20251229.pmtiles, только зумы [0..12], около 16 ГБ.
small_z14 — тайлы из 2024-12-27-netherlands.mbtiles, 52 071 тайл, около 650 МБ.

Заключение

Использование новых способов хранения тайлов позволило нам:

Упростить создание экспериментов с подложкой: значительно сократилось время и уменьшился набор необходимых разработчику знаний для разворачивания эксперимента с данными.
Сделать архивы подложки: регулярно сохраняя датасет в S3, мы можем достаточно дёшево смотреть, как выглядела подложка за несколько предыдущих дней, недель, месяцев, лет. Кроме продуктовой пользы, это также помогает отслеживать историю изменений в случае инцидентов.
Реализовать для части сервисов очень простой и производительный механизм graceful degradation. При этом не бояться пиковой нагрузки и переключения релизов данных.
Если будет интересно, то в следующей статье расскажу, как мы научились после переключения релиза сразу же отдавать максимальную нагрузку.
Упростить создание новых сервисов, отдающих тайлы.

При готовности смириться с недостатками подобного рода форматы могут также помочь:

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

Если вы пробовали похожие форматы или у вас есть идеи по улучшению — делитесь в комментариях!

Новые способы хранения тайлов в Картах: как один сервер выдерживает 80k RPS