LSM-Tree Architecture
Apache Paimon — это открытый формат lakehouse-хранилища, спроектированный для стриминговых и батчевых workload’ов на object storage. Проект был создан в Alibaba как внутренняя система для обработки 100+ PB данных, затем передан в Apache Software Foundation как Flink Table Store (2022), переименован в Apache Paimon (2023) и получил статус Top-Level Project в апреле 2024. Версия 1.0 GA вышла в январе 2025, текущая стабильная — 1.3.1 (ноябрь 2025).
В Модуле 11 мы разобрали Delta Lake (append-only transaction log), в Модуле 12 — Iceberg (каталог + дерево metadata файлов), в Модуле 13 — Hudi (timeline + FileGroup/FileSlice). Paimon идёт другим путём: в основе его storage engine лежит LSM-дерево (Log-Structured Merge Tree) — та же структура данных, что используется в RocksDB, LevelDB и Apache HBase.
Этот курс использует engine-agnostic подход. Paimon — это формат и протокол хранения. Основной движок — Apache Flink, но Paimon также поддерживает Spark, StarRocks, Trino, Presto и Doris. Библиотека pypaimon (чистый Python с версии 1.3, без JVM) поддерживает как чтение, так и запись таблиц.
Почему LSM-дерево для озера данных?
Delta Lake, Iceberg и Hudi хранят данные как иммутабельные файлы (Parquet). При update или delete они создают новые файлы или log-записи. Paimon добавляет уровень абстракции: данные организованы как LSM-дерево внутри каждого bucket’а, что даёт несколько преимуществ:
Append-only (Delta/Iceberg)
Append-only формат: каждая операция создаёт новый файл. Update = копирование всего файла с изменённой строкой. Amplification растёт линейно с размером файла.LSM-Tree (Paimon)
LSM-дерево: записи буферизуются в памяти (MemTable), сбрасываются как sorted run, объединяются через компакцию. Мелкозернистые обновления без перезаписи файлов.LSM-дерево оптимизирует запись за счёт чтения. Для стриминговых pipeline’ов, где данные поступают непрерывно (Flink checkpoint каждые 1-2 минуты), это идеальный компромисс: мелкозернистые upsert без перезаписи больших файлов.
Анатомия LSM-дерева в Paimon
Каждый bucket в Paimon-таблице содержит собственное LSM-дерево. Дерево состоит из трёх компонентов:
MemTable (in-memory, sorted by PK)
Write-ahead буфер в памяти. Все входящие записи (insert, update, delete) сначала попадают сюда. Сортировка по primary key внутри MemTable. Размер контролируется write-buffer-size (по умолчанию 256 МБ).MemTable
MemTable — это in-memory буфер записи, аналог Write-Ahead Log в классических БД:
| Параметр | Значение | Описание |
|---|---|---|
write-buffer-size | 256 MB (по умолчанию) | Максимальный размер MemTable до flush |
write-buffer-spillable | false | Можно ли сбросить MemTable на диск при нехватке памяти |
page-size | 64 KB | Размер страницы внутри MemTable |
Записи в MemTable сортируются по primary key. Когда размер превышает write-buffer-size, MemTable flush’ится на object storage как новый sorted run на Level 0.
MemTable хранится в памяти Flink TaskManager (или Spark executor). При crash до flush данные из MemTable теряются. Flink восстанавливает их из последнего checkpoint — это не WAL в классическом смысле, а буфер между checkpoint’ами. Для батчевых job’ов: если job упадёт до commit, MemTable-данные потеряны и job нужно перезапустить.
Sorted Run и SST-файлы
Sorted run — это набор SST-файлов (Sorted String Table), отсортированных по primary key:
SST File = Parquet + Paimon Metadata
Один SST-файл — это обычный Parquet-файл с дополнительными metadata. Paimon использует Parquet как физический формат хранения, добавляя свои поля: _KEY_*, _VALUE_KIND (для операций +I/-U/+U/-D), sequence number.Ключевое отличие от Delta Lake / Iceberg: SST-файлы — это не просто Parquet с данными. Они содержат _VALUE_KIND, который кодирует тип CDC-операции. Это позволяет Paimon нативно поддерживать changelog semantics — тему Урока 03.
Уровни (Levels)
LSM-дерево организовано в уровни:
| Параметр | Значение | Описание |
|---|---|---|
num-levels | 2 (по умолчанию) | Количество уровней LSM-дерева (не считая Level 0) |
num-sorted-run.compaction-trigger | 5 | Компакция запускается когда sorted runs на Level 0 ≥ этого значения |
num-sorted-run.stop-trigger | 10 | Запись блокируется при ≥ этого количества sorted runs (backpressure) |
Параметр num-sorted-run.stop-trigger — механизм backpressure: если компакция не успевает за записью, Paimon блокирует запись до завершения компакции. Это предотвращает неограниченный рост sorted runs и деградацию чтения.
Стратегии компакции
Компакция — процесс объединения sorted runs для уменьшения read amplification. Paimon поддерживает две стратегии:
Universal Compaction
Universal compaction (по умолчанию) — стратегия, заимствованная из RocksDB:
Характеристики:
- Минимальное количество sorted runs (обычно 1-2) → лучшая скорость чтения
- Высокий write amplification: каждая компакция перезаписывает все данные
- Подходит для workload’ов с преобладанием чтения
Sorted-Run Compaction
Sorted-run compaction (аналог leveled compaction в RocksDB) — более гранулярная стратегия:
Характеристики:
- Меньший write amplification: merge только пересекающихся диапазонов
- Больше sorted runs на промежуточных уровнях → медленнее чтение
- Подходит для write-heavy workload’ов (стриминг)
Выбор стратегии
В Модуле 13 мы видели аналогичный компромисс в Hudi: COW (read-optimized, high write amp) vs MOR (write-optimized, merge on read). Paimon решает ту же проблему через стратегию компакции вместо двух разных типов таблиц.
Write Amplification vs Read Amplification
Центральный компромисс LSM-дерева:
| Метрика | Определение | Paimon контекст |
|---|---|---|
| Write Amplification | Сколько раз одна запись перезаписывается на диск за время жизни | Каждая компакция перезаписывает данные. Universal: весь sorted run. Sorted-run: только пересекающийся диапазон |
| Read Amplification | Сколько sorted runs нужно прочитать для одного запроса | Больше sorted runs = больше merge при чтении. Компакция уменьшает число sorted runs |
| Space Amplification | Сколько дискового пространства занимают устаревшие версии записей | До компакции: старые версии записей живут в нижних sorted runs. После: очищены |
Редкая компакция
Редкая компакция: sorted runs накапливаются на Level 0. Запись быстрая (нет overhead от компакции), но чтение должно merge-ить 5-10 sorted runs. Подходит для write-only стриминга с редким чтением.Частая компакция
Частая компакция: sorted runs постоянно объединяются. Чтение быстрое (1-2 sorted runs), но каждая компакция перезаписывает данные. Подходит для read-heavy workload'ов с умеренной записью.Write Path: от записи до snapshot
Полный путь записи в Paimon:
Входящая запись (INSERT / UPDATE / DELETE)
Входящая запись: INSERT, UPDATE или DELETE. В стриминговом режиме — Flink checkpoint trigger. В батчевом — завершение job. Запись содержит primary key + данные + тип операции.MemTable (in-memory sorted buffer)
Запись добавляется в MemTable (in-memory, sorted by PK). MemTable — это skip-list или red-black tree, зависит от реализации. Записи с одинаковым PK merge-ятся в MemTable: последний UPDATE перезаписывает предыдущий.Flush → новый Sorted Run (Level 0)
MemTable сбрасывается на object storage как новый sorted run на Level 0. Физически — набор SST-файлов (Parquet). Каждый SST-файл ≤ target-file-size (128 МБ). Flush не блокирует запись — новый MemTable создаётся немедленно.Compaction (merge sorted runs)
Компакция объединяет sorted runs: merge по primary key, применение delete-маркеров, удаление дубликатов. Выбор стратегии: universal (все → один) или sorted-run (поуровневая). Компакция может быть синхронной (блокирует commit) или асинхронной.Snapshot (immutable table state)
Snapshot фиксирует состояние таблицы после записи: список всех SST-файлов, manifest, schema version. Snapshot — иммутабельный. Читатели используют snapshot для консистентного чтения. Аналог commit в Delta Lake.Snapshot в Paimon — аналог commit в Delta Lake и snapshot в Iceberg. Каждый snapshot содержит полную информацию о состоянии таблицы: какие SST-файлы существуют, их уровни, schema version, и watermark (для стриминга). Snapshots хранятся в директории snapshot/ в корне таблицы.
Физическая структура таблицы
На object storage Paimon-таблица выглядит так:
Для партиционированной таблицы структура добавляет уровень:
table_name/
├── schema/
├── snapshot/
├── manifest/
├── pt=2024-01-01/
│ ├── bucket-0/
│ │ ├── data-abc123.parquet (SST file)
│ │ └── data-def456.parquet (SST file)
│ └── bucket-1/
│ └── data-ghi789.parquet
├── pt=2024-01-02/
│ └── bucket-0/
│ └── data-jkl012.parquet
└── tag/Сравнение с другими форматами
| Аспект | Delta Lake | Iceberg | Hudi | Paimon |
|---|---|---|---|---|
| Update model | COW / DV | COW / position delete | COW / MOR | LSM merge |
| Write amplification | Высокий (COW) | Высокий (COW) | Средний (MOR) | Контролируемый |
| Streaming native | Частично | (LSM) | ||
| Changelog native | (CDF) | CDC (log files) | (_VALUE_KIND) | |
| Компакция | OPTIMIZE | rewrite_data_files | async services | universal/sorted-run |
Paimon — единственный из четырёх форматов, где LSM-дерево является фундаментальной структурой данных, а не оптимизацией поверх файлов. Это делает его наиболее эффективным для streaming-first workload’ов с частыми мелкозернистыми обновлениями.
Ключевые выводы
- LSM-дерево — фундамент Paimon: MemTable → sorted runs → уровни с компакцией
- SST-файл — Parquet с дополнительными системными колонками (_VALUE_KIND, _SEQUENCE_NUMBER)
- Компакция — механизм управления компромиссом write amp vs read amp
- Universal — merge всех sorted runs, лучше для чтения; sorted-run — поуровневый merge, лучше для записи
- Snapshot — иммутабельное состояние таблицы, аналог commit в Delta Lake
- Backpressure (
num-sorted-run.stop-trigger) — защита от неограниченного роста sorted runs при отставании компакции