Индекс SSTable на префиксных деревьях в ScyllaDB

В ScyllaDB 2026.2 индекс SSTable на основе префиксного дерева (trie) стал форматом по умолчанию, заменив плоскую пару Summary.db + Index.db, которая использовалась в форматах me/md. Новый формат появился ещё в 2025.4 и обратно совместим на уровне диска с форматом BTI (Big Trie Index) из Apache Cassandra, но переписан с нуля на Seastar. На четырёх профилях нагрузки на чтение авторы зафиксировали рост пропускной способности от 30% до 230% и снижение задержки на 31-63% при практически неизменной производительности на запись.

Как работал прежний механизм

Поиск в форматах me/md обходит три структуры. Summary.db целиком находится в оперативной памяти с выборкой примерно по одной записи на каждые 2000 байт Data.db. Бинарный поиск по нему сужает диапазон ключа до конкретного окна в Index.db. Это окно считывается с диска и сканируется (порядка 800 записей на мегабайт), чтобы найти ключ партиции и его смещение в Data.db. Затем выполняются один seek и последовательное чтение уже из Data.db.

Для партиций с большим количеством строк кластеризации добавляется четвёртая структура: так называемый продвинутый индекс (promoted index), хранящийся прямо внутри записи Index.db. Это плоский список блоков ключей кластеризации с начальными и конечными ключами и смещениями, по которому тоже выполняется бинарный поиск.

Главных накладных расходов два. Summary.db всегда постоянно держится в памяти и никогда не вытесняется, занимая RAM независимо от того, обращается ли к нему нагрузка. А каждая запись в Index.db сохраняет свой ключ целиком, из-за чего одинаковые префиксы дублируются для каждого ключа.

Что пришло на замену

Форматы ms/mt убирают оба этих файла и вводят два новых:

Partitions.db хранит единое префиксное дерево, сопоставляющее ключ партиции со смещением в Data.db (для маленьких партиций) или смещением в Rows.db (для больших), а за ним идёт footer с метаданными first_key, last_key, partition_count и trie_root_pos. В Rows.db содержатся объединённые поддеревья ключей кластеризации для каждой партиции, где каждый ключ сопоставляется с байтовым смещением внутри своей партиции - именно это заменяет прежний promoted index. Файлы Data.db, Filter.db, Statistics.db и Scylla.db остаются байт в байт прежними.

Ключи предварительно проходят через bti_key_translation.cc, который преобразует их в последовательность байт, чей лексикографический порядок строго соответствует семантическому порядку CQL. Именно это позволяет побайтовой структуре корректно обрабатывать диапазонные запросы для типизированных колонок.

Приём с упаковкой в страницы

Самое интересное инженерное решение здесь не само префиксное дерево, а его компоновка при записи. Компонент trie_writer держит в стеке самый правый путь от корня к текущему узлу, ветвится от него для каждого нового ключа, накапливает узлы до тех пор, пока готовое поддерево не начинает превышать размер страницы, а затем сбрасывает дочерние поддеревья с выравниванием (padding), чтобы каждое помещалось ровно в одну страницу размером 4 KB. Узел и его потомки оказываются на одной странице, поэтому всё соседство в дереве считывается за один I/O даже при холодном чтении. Родительские узлы записываются после дочерних, так как родитель должен знать, где именно разместились его потомки. Коэффициент ветвления (fan-out) достигает 256.

Обычный поиск партиции требует от двух до шести обращений к страницам, а так как верхние страницы задерживаются в page cache операционной системы, на практике это часто выливается в ноль или один реальный I/O на диске.

Кроме того, ScyllaDB отошла от эталонной реализации Cassandra в гранулярности узлов. Cassandra хранит по одному символу на узел, а ScyllaDB объединяет символы в цепочки длиной до 300 байт. Структура страниц на чтении остаётся той же, но запись длинных ключей ускоряется в разы.

Работа с памятью полностью изменилась. В старой схеме summary всегда висел в памяти без возможности вытеснения. У дерева же вообще нет выделенного компонента в RAM - его верхние узлы живут в обычном OS page cache и при нехватке памяти вытесняются, как любые другие данные.

Бенчмарки

Тестирование проводилось на трёх узлах i8g.2xlarge в AWS, RF=3, три стойки, с измерением максимальной пропускной способности, при которой P99 задержка со стороны клиента не превышает 10 ms.

Тест 2 был спроектирован так, чтобы подчеркнуть преимущества дерева: только ключ партиции, никаких колонок кластеризации, полезная нагрузка около 8 байт на строку, 650M строк. Сжатие префиксов делает индекс настолько плотным, что при том же бюджете page cache помещается примерно в 3 раза больше верхних узлов дерева по сравнению с эквивалентным окном Index.db. Тест 4 создавался как максимально неблагоприятный - ключи кластеризации по 2048 байт с длинным общим префиксом, где отличаются только концевые байты (что максимизирует глубину и снижает выигрыш от разделения префиксов), но даже там дерево выиграло 73%.

Числа в приложении статьи в двух случаях чуть скромнее, чем в сводной таблице (в Тесте 2 указано >280k ops/s и >+211%; в Тесте 3 - ~30k ops/s и +50%), о чём полезно помнить при цитировании.

Даже при равной нагрузке картина задержек заметно меняется: в Тесте 1 при тех же 130k ops/s задержка P99 с деревом составила 3.19 ms против 6.28 ms в старом формате.

Почему это выигрывает и где выигрыша нет

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

Подтверждение первого пункта по метрикам: при одинаковой пропускной способности старые индексы требовали около 240 MB/s дискового чтения, а индексы на деревьях - около 33 MB/s. Нагрузка на пропускную способность хранилища упала примерно в семь раз.

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

Реальное граничное условие: при 100% попадании в кэш или 0% попадании формат индекса почти не играет роли, так как в первом случае до индекса ничего не доходит, а во втором - промахи идут по всем фронтам независимо от формата. Весь выигрыш проявляется в промежутке между ними, где как раз и находится подавляющее большинство рабочих нагрузок.

Связанные страницы

• lsm-tree - устройство SSTable и причины, по которым неизменяемому отсортированному файлу вообще нужен индекс; MemTable на базе skip-list представляет собой вторую половину той же архитектуры со стороны записи.
• levenshtein-trie - пример использования разделения префиксов для другой задачи (нечёткого поиска по словарю) и хорошая иллюстрация формы самой структуры данных.