Базы данных
LSM-Tree: Log-Structured Merge-Tree
Facebook в 2016 году заменил InnoDB на MyRocks для хранения пользовательских данных. Результат: 50% меньше SSD storage = сотни миллионов долларов экономии. 2-3x выше write throughput. LSM-Tree не просто академическая концепция - это миллиарды долларов экономии в индустрии.
- **Facebook**: MyRocks (RocksDB) вместо InnoDB - 50% storage reduction на основных user tables
- **Discord**: ScyllaDB (C++ Cassandra с RocksDB-like LSM) для 4 триллионов сообщений
- **Kafka**: log compaction на RocksDB-подобных SSTables для compact topic storage
B-Tree и его проблемы при высоком write
B-Tree - основная структура индексов в PostgreSQL, MySQL, SQLite. Отлично работает для reads и balanced writes. Проблема: при write-heavy нагрузке B-Tree требует random I/O - вставить ключ в середину узла, обновить несколько страниц. SSD лучше HDD для random I/O, но всё равно медленнее sequential.
Write amplification у B-Tree: одна логическая запись вызывает несколько физических записей (WAL + dirty pages + checkpoint). Amplification factor 10-30x в типичных сценариях. LSM-Tree решает через batching.
PostgreSQL B-Tree страдает от write amplification при высокой нагрузке. Главная причина?
Структура LSM-Tree
LSM-Tree (Log-Structured Merge-Tree) - Aho, Dietz, Slater, 1996. Ключевая идея: все записи сначала в memory (MemTable), потом батчами на диск (SSTable). Диск всегда пишется sequential. Никакого random I/O при записи.
SSTable (Sorted String Table): immutable файл с ключами отсортированными по ключу. Каждая запись: key + value + timestamp. Bloom filter для каждого SSTable: O(1) проверить "точно НЕ содержит ключ" = избежать disk read.
LSM-Tree всегда пишет sequential. Почему это лучше random I/O?
Write Amplification и Read Amplification
Write Amplification (WA): сколько байт физически записывается на диск на 1 байт логических данных. LSM: WA = 10-30x из-за compaction (данные перемещаются много раз). B-Tree: WA = 2-10x. Read Amplification (RA): сколько SSTable файлов нужно проверить при чтении. LSM худший случай: проверить все уровни.
Bloom filter - вероятностная структура данных. Гарантирует: если фильтр говорит "НЕТ" - ключа точно нет. Если "ДА" - ключ вероятно есть (false positive rate ~1%). Allows skip disk read если ключ точно не в SSTable. Каждый SSTable имеет свой Bloom filter.
Приложение делает 99% writes и 1% reads. Какой storage engine предпочтительнее?
Compaction стратегии
Compaction - процесс слияния SSTable файлов: удаляет устаревшие версии ключей, освобождает место, поддерживает управляемое количество файлов на каждом уровне. Без compaction: read performance деградирует по мере накопления SSTable.
| Стратегия | Описание | Когда использовать |
|---|---|---|
| Leveled (LevelDB/RocksDB default) | Каждый level имеет max размер; L0->L1->L2 cascade | Read-heavy, много obновлений одних ключей |
| STCS (Size-Tiered) | Merge SSTables похожего размера | Write-heavy, редкие reads |
| TWCS (Time-Window) | Merge только SSTables одного временного окна | Time-series с TTL |
| FIFO | FIFO удаление старых files при overflow | Время-серия без compaction |
RocksDB использует Leveled compaction. Каждый Level N имеет максимальный размер (L1=256MB, L2=2.5GB, ...). Compaction с L0 на L1 происходит когда L0 достигает 4 файлов. Facebook написал RocksDB для хранения социального графа - 1+ миллиард edges.
После heavy write нагрузки производительность LSM reads упала. Что произошло?
RocksDB в продакшне
RocksDB - производительная LSM-Tree библиотека от Facebook/Meta. Используется как storage engine в MySQL (MyRocks), Cassandra (опционально), InfluxDB 1.x, TiKV (TiDB storage), CockroachDB, Kafka (log compaction).
TiKV - Rust реализация distributed key-value store поверх RocksDB + Raft. Используется как storage layer в TiDB (distributed SQL database от PingCAP). Architecture: Raft groups реплицируют RocksDB regions. Pingcap customers: Shopee, Bank of China.
LSM-Tree всегда медленнее B-Tree для чтения
LSM-Tree медленнее только при point reads без Bloom filter. С Bloom filter: false negative rate ~0, большинство "miss" lookups = один disk I/O. Для range scans после compaction LSM сопоставим с B-Tree.
RocksDB с Bloom filters показывает <1ms P99 для point reads в Facebook. Trade-off реален, но не катастрофичен при правильной настройке.
Facebook перевёл хранение данных пользователей с InnoDB на MyRocks (RocksDB). Главный выигрыш?
Итоги
- **LSM vs B-Tree**: LSM = write-optimized (sequential I/O, batching); B-Tree = read-optimized (O(log N) point lookup, меньше read amplification)
- **Compaction**: без compaction reads деградируют; Leveled для read-heavy, STCS для write-heavy, TWCS для time-series
- **RocksDB**: production-ready LSM библиотека; основа TiKV, MyRocks, InfluxDB, Kafka storage
Связанные темы
LSM-Tree - фундамент для нескольких БД:
- Cassandra — Cassandra использует LSM-tree (MemTable + SSTables) для write-heavy workloads
- Time-series БД — InfluxDB TSM (Time Series Merge-tree) - адаптация LSM для time-series
- NewSQL — TiKV (в TiDB) и CockroachDB используют RocksDB как storage layer
Вопросы для размышления
- Почему Bloom filter нельзя гарантировать отсутствие false positives, только отсутствие false negatives?
- Compaction создаёт write amplification. Почему LSM всё равно быстрее B-Tree при write-heavy?
- Как выбрать между Leveled и STCS compaction для конкретного workload?