SSTable

SSTable (Sorted String Table, таблица отсортированных строк) — это структура данных для хранения большого объёма пар «ключ-значение» в отсортированном по ключу виде на диске. SSTable обеспечивает эффективный последовательный доступ и высокую производительность при чтении, особенно в системах, где данные редко обновляются на месте, а запись производится путём добавления новых файлов. Является ключевым компонентом ряда распределённых баз данных и систем хранения, таких как Bigtable (Google), LevelDB, RocksDB, Apache Cassandra и ScyllaDB.

История и происхождение

Концепция SSTable была впервые описана в 2006 году в исследовательской работе Google, посвящённой распределённой базе данных Bigtable. Разработчики Bigtable (Фэй Чанг, Джеффри Дин и другие) столкнулись с необходимостью хранить и обрабатывать петабайты структурированных данных на тысячах серверов. Традиционные реляционные базы данных не справлялись с такими объёмами и требованиями к масштабируемости. SSTable стала одним из фундаментальных строительных блоков Bigtable, обеспечивая надёжное и эффективное хранение данных на диске.

Впоследствии идея SSTable была заимствована и развита в проектах с открытым исходным кодом. В 2011 году компания Google выпустила LevelDB — легковесную библиотеку для хранения ключей и значений, целиком основанную на SSTable. В том же году Facebook (признана экстремистской и запрещена в РФ) представила RocksDB — форк LevelDB, оптимизированный для работы на серверах с флеш-памятью и многоядерными процессорами. RocksDB, в свою очередь, стал основой для многих современных систем, включая Apache Cassandra (начиная с версии 3.0) и ScyllaDB.

Устройство и структура

SSTable представляет собой неизменяемый файл, который состоит из двух основных частей: блоков данных и индекса.

Блоки данных (Data Blocks)

Данные разбиваются на блоки фиксированного размера (обычно от 4 до 64 КБ).
Внутри каждого блока записи (пары «ключ-значение») хранятся в отсортированном по ключу порядке.
Для повышения эффективности сжатия блоки могут быть сжаты (например, с помощью алгоритмов Snappy, LZ4 или Zstd) перед записью на диск.

Индекс (Index Block)

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

Блум-фильтр (Bloom Filter, опционально)

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

Схема размещения

Типичная структура SSTable-файла (сверху вниз):

Заголовок (Header): информация о версии, размере блока, типе сжатия.
Блоки данных (Data Blocks): последовательность блоков с отсортированными записями.
Блок метаданных (Meta Index Block): указатели на дополнительные метаданные (например, на Блум-фильтр).
Блум-фильтр (Bloom Filter Block): сам фильтр (если используется).
Индексный блок (Index Block): список начальных ключей блоков данных.
Footer: указатели на начало индексного блока и блока метаданных.

Принцип работы

SSTable является неизменяемой структурой: после записи на диск её содержимое не может быть изменено. Это кардинально отличает её от традиционных B-деревьев, используемых в реляционных СУБД.

Запись

Запись в систему, использующую SSTable, происходит не напрямую в файл, а через промежуточный буфер в оперативной памяти — MemTable (in-memory table). MemTable также поддерживает данные в отсортированном виде (обычно с помощью красно-чёрного дерева или скип-листа). Когда MemTable достигает определённого размера, она:

Замораживается (становится неизменяемой).
Сбрасывается на диск в виде нового SSTable-файла.
Освобождается для новых записей.

Чтение

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

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

Сжатие (Compaction)

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

Удаляются дублирующиеся записи (остаётся только последняя версия).
Удаляются записи, помеченные как «удалённые» (tombstones).
Данные пересортировываются и пересжимаются.

Классификация и разновидности

Хотя базовая концепция SSTable одинакова, реализации различаются в деталях.

По способу сжатия

Level-based (LevelDB, RocksDB): SSTable-файлы организованы по уровням (Level 0, Level 1, ...). Новые файлы попадают на Level 0. Сжатие происходит между уровнями, постепенно перемещая данные на более низкие уровни. Это минимизирует амплитуду записи (write amplification).
Size-tiered (Cassandra, ScyllaDB): SSTable-файлы группируются по размеру. Сжатие объединяет файлы примерно одинакового размера в один файл большего размера. Этот подход проще, но может приводить к большей амплитуде записи.

По формату

LevelDB SSTable: простой формат, оптимизированный для однопоточного доступа. Индекс и Блум-фильтр хранятся в конце файла.
RocksDB SSTable: расширенный формат, поддерживающий множество типов сжатия, разные типы Блум-фильтров, а также дополнительные метаданные.
Apache Cassandra SSTable: использует формат, близкий к Bigtable, с поддержкой сжатия на уровне блоков и статистикой по ключам.

Применение

SSTable является основой для многих современных систем, работающих с большими объёмами данных.

Распределённые базы данных

Apache Cassandra: использует SSTable как основное хранилище на диске. Данные записываются в MemTable, а затем сбрасываются в SSTable. Сжатие выполняется по стратегии size-tiered или level-based.
ScyllaDB: альтернативная реализация Cassandra на C++, также основанная на SSTable. Известна высокой производительностью и эффективным использованием аппаратных ресурсов.
Bigtable (Google): оригинальная система, в которой SSTable была впервые применена.

Встраиваемые движки

LevelDB: легковесная библиотека, используемая в браузере Chrome (для хранения cookies и кэша), а также в ряде других приложений.
RocksDB: высокопроизводительный движок, используемый в MySQL (как замена InnoDB), Apache Flink, Apache Kafka (для хранения метаданных), а также в игровых серверах и системах реального времени.

Системы управления базами данных (СУБД)

Apache HBase: реализация Bigtable с открытым исходным кодом, также использующая SSTable (через HFile — собственный формат, основанный на SSTable).
Apache Accumulo: ещё одна реализация Bigtable, использующая SSTable.

Преимущества и недостатки

Преимущества

Высокая скорость записи: запись является последовательной (append-only) и не требует случайных операций ввода-вывода.
Эффективное сжатие: данные хранятся в сжатом виде, что экономит дисковое пространство.
Простота и надёжность: неизменяемость файлов упрощает резервное копирование, восстановление и репликацию.
Хорошая производительность чтения: благодаря индексам и Блум-фильтрам чтение выполняется за O(log N) или O(1) в среднем.

Недостатки

Амплитуда записи (Write Amplification): процесс сжатия многократно перезаписывает данные, что может приводить к износу SSD-накопителей.
Сложность сжатия: алгоритмы сжатия (compaction) требуют тщательной настройки и могут потреблять значительные ресурсы процессора и диска.
Задержки при чтении: при большом количестве SSTable-файлов чтение может замедляться из-за необходимости проверять несколько файлов.
Не подходит для частых обновлений: обновление записи приводит к созданию новой версии, а не к изменению существующей, что увеличивает объём хранимых данных до момента сжатия.

Интересные факты

Название «SSTable» является аббревиатурой от «Sorted String Table», но в исходной статье Google было написано как «SSTable» (с большой буквы S).
Формат SSTable в LevelDB и RocksDB является открытым и документированным, что позволяет создавать собственные инструменты для работы с этими файлами.
В RocksDB существует возможность использовать «упорядоченные» (sorted) и «неупорядоченные» (unsorted) SSTable, хотя последние редко применяются на практике.

Источники

Chang, F., Dean, J., Ghemawat, S., et al. (2006). Bigtable: A Distributed Storage System for Structured Data. OSDI.
LevelDB GitHub repository: документация и исходный код.
RocksDB GitHub repository: документация и исходный код.
Apache Cassandra Documentation: «Storage Engine».
ScyllaDB Documentation: «SSTable Format».

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →