Valkey 9.2 заменяет skiplist на B+-дерево fbtree: до 43% меньше накладных расходов памяти

В блоге Valkey описано изменение, которое войдёт в Valkey 9.2: структура skiplist (список с пропусками), на которой держатся большие упорядоченные множества (sorted sets), заменяется на fbtree, вариант B+-дерева с высокой степенью ветвления. Сейчас версия 9.2 проходит тестирование релиз-кандидата.

Почему меняют skiplist. Большие упорядоченные множества, превышающие порог listpack, хранятся как пара из skiplist и хеш-таблицы: хеш-таблица даёт поиск по элементу за O(1), skiplist, упорядоченный поиск по рангу или значению (score) за O(log n). Маленькие множества лежат в компактном listpack и изменение их не затрагивает. Минус skiplist в том, что каждый элемент занимает отдельный узел, отдельное выделение памяти, связанное с остальными указателями. На каждый узел приходится обратный указатель (8 байт) и в среднем 1,33 уровня прямых указателей и значений span (у каждого узла 25% шанс получить ещё один уровень). Уровень стоит 8 байт на указатель и 8 байт на span, итого около 29 байт на указатели и span на узел; с 8-байтовым score получается примерно 37 байт на узел, не считая самой строки элемента. Вторая проблема, кэш-промахи: узлы разбросаны по памяти, а каждый следующий шаг зависит от предыдущего, поэтому процессор вынужден ждать. Как грубую иллюстрацию авторы приводят около 1 нс для попадания в кэш L1 и около 100 нс для обращения к DRAM. Они ссылаются на исследование 2025 года о конкурентных индексах в памяти: на его тестовых нагрузках традиционные skiplist давали в 2,4-4,8 раза больше кэш-промахов, чем сопоставимое B-дерево, и в 2-8 раз меньшую пропускную способность (это не измерения Valkey).

Как устроен fbtree. Название, сокращение от Feature B+ Tree. Ветвление 61: узел содержит до 61 элемента или указателей на потомков. Размеры узлов подогнаны под классы выделения памяти jemalloc; 512-байтовый лист вмещает до 61 указателя на значение, то есть 61 элемент делят один узел. Score и элемент хранятся вместе как одно упакованное значение: нормализованные 8 байт score и следом байты элемента. Эффективный коэффициент ветвления skiplist, около 4 против 61 у fbtree, поэтому при той же сложности поиска O(log n) у дерева заметно меньше уровней и меньше дорогих обращений к памяти. Дополнительные оптимизации: во внутренних узлах рядом с границей каждого потомка (anchor, наибольший элемент в нём) хранится небольшой четырёхбайтовый признак (feature), а общий префикс границ вынесен отдельно, и признаки сравниваются параллельно через SIMD, часто ещё до чтения самого дочернего узла; листья связаны двусвязным списком, так что диапазонные команды вроде ZRANGE переходят от листа к листу, не поднимаясь по дереву, и могут подгружать следующий лист заранее; крайние левый и правый листья кешируются, поэтому ZPOPMIN и добавление в конец остаются на уровне skiplist; удаление диапазонов не требует перестройки окружающей структуры.

Что меняется для пользователя. По заявлению авторов, функционально ничего: команды и их поведение прежние. Единственное видимое отличие, OBJECT ENCODING для большого упорядоченного множества возвращает btree вместо skiplist. Если мониторинг, тесты или инструменты проверяют литеральную строку skiplist, их придётся обновить.

Память. Сравнивается только упорядоченный индекс; хеш-таблица и встраивание элементов не менялись. При последовательной вставке 5 млн 20-байтовых элементов накладные расходы на элемент (без самих данных элемента) упали с 50,3 до 28,5 байта, на 43%. При случайной вставке тех же элементов, с 50,3 до 32,0 байта, на 36%. Разница объясняется тем, что при случайной вставке остаётся больше частично заполненных узлов. Для множества из 5 млн элементов это примерно 109 МБ экономии при последовательных вставках и 92 МБ при случайных. Экономия считается на элемент, а не на байт данных, поэтому относительное сокращение общей памяти больше всего у множеств из множества мелких элементов и уменьшается с ростом размера элемента.

Производительность команд. Замеры сделаны на ветке pull request #4206 (oi/pr3-fbtree-v2) и не перезапускались для влитого коммита. Стенд: Graviton3 c7g.metal, 64 ядра, девять потоков ввода-вывода, глубина конвейера 10, упорядоченное множество из 3 млн элементов; каждый тест повторён пять раз, доверительные интервалы не превышали 2% для всех команд, кроме ZRANDMEMBER. Пропускная способность ZADD и ZREM выросла на 105% и 76%: они переставляют элементы в дереве и выигрывают больше всего от меньшей глубины и меньшего числа обновлений указателей. Диапазонные операции выигрывают меньше, потому что после удешевления обхода индекса основную долю затрат занимает формирование и возврат элементов. ZSCORE и ZRANDMEMBER почти не меняются, так как работают через хеш-таблицу, а не упорядоченный индекс. По словам авторов, реализацию многократно сравнивали со skiplist на полном сервере Valkey и дорабатывали, пока fbtree не сравнялся со skiplist или не превзошёл его на проверенных командах.

Призыв авторов: до GA опробовать релиз-кандидат 9.2 на реальной нагрузке, особенно если важны большие упорядоченные множества или команды ZADD, ZREM, ZRANK, ZCOUNT, и сообщать о найденных проблемах через issue.

Ключевые факты

  • В Valkey 9.2 (сейчас релиз-кандидат) skiplist в больших упорядоченных множествах заменён на fbtree, B+-дерево с ветвлением 61 и оптимизациями под память и SIMD.
  • В тесте на 5 млн 20-байтовых элементов накладные расходы упорядоченного индекса на элемент упали с 50,3 до 28,5 байта при последовательной вставке (−43%) и до 32,0 байта при случайной (−36%); экономия около 109 МБ и 92 МБ.
  • В отдельном замере на 3 млн элементов (Graviton3 c7g.metal, ветка PR, не перезапускался для влитого коммита) пропускная способность ZADD выросла на 105%, ZREM, на 76%; ZSCORE и ZRANDMEMBER почти не изменились.
  • Команды и их поведение прежние; видимое отличие одно, OBJECT ENCODING возвращает btree вместо skiplist, так что проверки на строку skiplist нужно обновить.

Почему это важно

Упорядоченные множества, рабочая лошадка Valkey для рейтингов, очередей по приоритету и выборок по диапазону. По словам авторов, в skiplist упорядочивание может обходиться дороже самих данных: около 37 байт на узел помимо строки элемента. Замена структуры без изменения команд снижает накладные расходы памяти на элемент на 36-43% в их тесте и ускоряет добавление и удаление. Это внутреннее изменение, но оно затрагивает все большие упорядоченные множества.

Кому это важно

Тем, кто эксплуатирует Valkey с большими упорядоченными множествами (выше порога listpack), особенно с множеством мелких элементов: по словам авторов, там относительная экономия общей памяти максимальна. Также тем, у кого мониторинг, тесты или инструменты проверяют строку skiplist в OBJECT ENCODING. Для маленьких множеств в listpack ничего не меняется.

Как это применить

Авторы просят до GA взять релиз-кандидат Valkey 9.2 и прогнать на реальной нагрузке, особенно если важны ZADD, ZREM, ZRANK, ZCOUNT, а о проблемах сообщать через issue. Заранее стоит найти в мониторинге и тестах проверки на skiplist и учесть, что вместо него теперь возвращается btree. Дата GA в тексте не названа.

Можно ли доверять

Это материал на сайте самого проекта Valkey, то есть оценки авторов реализации; имена авторов в тексте не указаны. Цифры по памяти получены в тесте на 5 млн элементов, замеры пропускной способности, в другом тесте на 3 млн элементов на Graviton3. Автор текста сам оговаривает, что замеры команд сделаны на ветке PR и не перезапускались для влитого коммита. Сравнения с Redis или другими базами в тексте нет. Цифры про 2,4-4,8 раза больше кэш-промахов относятся к стороннему исследованию 2025 года, а не к Valkey.

Риски и подводные камни

Цифры 36-43% относятся только к накладным расходам упорядоченного индекса на элемент, а не к общему потреблению памяти: хеш-таблица и данные элементов не менялись, и выигрыш в общей памяти падает с ростом размера элементов. Выигрыш зависит от порядка вставки: случайная даёт меньше (36%), чем последовательная (43%). Прирост пропускной способности замерен на ветке PR, а не на финальном коммите; ZSCORE и ZRANDMEMBER почти не ускоряются, диапазонные операции выигрывают умеренно. Версия 9.2 пока в стадии релиз-кандидата, а изменение видимого значения OBJECT ENCODING может сломать самописные проверки.