skiplist

Header-only библиотека на C, реализующая параллельный lock-free skip-list - а именно splay-list, skip-list с опциональной адаптивной перебалансировкой, продвигающей горячие ключи ближе к вершине. Вся реализация построена на макросах препроцессора в include/sl.h, генерирующих типобезопасный код во время компиляции аналогично шаблонам C++, но без диспетчеризации функций и указателей void. Автор - Gregory Burd; двойная лицензия ISC или MIT.

Как это устроено

Основной алгоритм - Fraser/Harris: вставка через CAS на уровне 0 с последующим оптимистичным связыванием верхних уровней, удаление через пометку младшего бита прямого указателя (логическое удаление) и последующее отвязывание (физическое удаление), а также epoch-based reclamation (EBR), чтобы читатели не натыкались на освобождённую память. Уровень 0 представляет собой двусвязный список, что даёт двунаправленный обход за O(1) вместо обхода в обратном направлении за O(log n), требуемого обычными skip list'ами.

Splay-перебалансировка включается через SKIPLIST_SPLAY_REBALANCE. Она основана на работе Aksenov et al. 2020: узел с частотой обращений u/T стабилизируется на высоте K − 1 − log₂(T/u), поэтому ключ, к которому обращаются в 50% случаев, оказывается на глубине 1. Стоимость поиска для горячих ключей снижается с O(log n) до O(log(1/p)). Проход перебалансировки запускается только на путях только для чтения (поиск, проверка наличия, запросы позиции). Он никогда не вызывается при удалении, поскольку продвижение узла, готового к удалению, приведёт к висячим ссылкам на верхних уровнях после того, как EBR освободит память.

В README чётко оговорено, чего splay не даёт: "Это не делает splay-list таким же быстрым, как B+дерево" - раскладка по cache-line для этого не подходит даже с оптимизацией по высоте. Суть в том, чтобы ускорить выборку горячих ключей внутри самого skip list'а, а не обогнать другую структуру данных.

Состав API

Библиотека представляет собой набор независимых макрогенераторов - можно выбрать только нужные:

SKIPLIST_ENTRY(typename)        // embed in your node struct
SKIPLIST_DECL(...)              // core: init, insert, remove, search
SKIPLIST_DECL_ACCESS(...)       // high-level key/value interface
SKIPLIST_DECL_SNAPSHOTS(...)    // MVCC point-in-time snapshots
SKIPLIST_DECL_EBR(...)          // epoch-based reclamation
SKIPLIST_DECL_POOL(...)         // fixed-capacity cache-line-aligned pool allocator
SKIPLIST_DECL_ARCHIVE(...)      // binary serialization
SKIPLIST_DECL_VALIDATE(...)     // runtime integrity checks
SKIPLIST_DECL_DOT(...)          // GraphViz visualization

Параметры времени компиляции:

Однопоточный режим примерно на 30% быстрее lock-free режима в плотных циклах, так как в нём нет атомарных чтений и CAS. Пул-аллокатор поверх этого увеличивает пропускную способность последовательной вставки в два-три раза.

Показатели производительности

x86_64, N=100k, gcc 13 -O2:

Другие возможности

Снимки MVCC обеспечивают фиксацию состояния на определенный момент времени с возможностью восстановления. Двоичная сериализация использует пользовательские обработчики для каждого узла - библиотека не навязывает структуру ваших узлов. Проверка целостности и визуализация DOT упрощают отладку и валидацию.

Тесты покрывают 97% строк / 99% функций / 58% ветвлений реализации: 33 модульных теста под ASan/LSan/UBSan, 7 параллельных тестов под ThreadSanitizer, 6 тестов однопоточного режима, проверка утечек через Valgrind, а также эмпирический тест, воспроизводящий предсказания целевой высоты из статьи Aksenov 2020 для различных распределений доступа. В репозитории идут три системы сборки (обычный Make, autoconf, Meson).

Где это применимо

MemTable в lsm-tree - классическая сортированная структура в памяти, требующая вставки за O(log n) и упорядоченного обхода; стандартными вариантами здесь выступают skip list'ы и красно-чёрные деревья. И RocksDB, и LevelDB используют skip list'ы для MemTable. Lock-free реализация с двусвязным уровнем 0 (дешёвое сканирование в обратном направлении) и опциональными MVCC-снимками отлично ложится на шаблон MemTable + read-side snapshots, который уже применяется в этих движках. Однопоточный режим интересен сам по себе: во многих встраиваемых сценариях (хранилища конфигурации, среды выполнения DSL, внутрипроцессные кэши) lock-free не нужен, но требуются упорядоченный обход и компактность.

Репозиторий

codeberg.org/gregburd/skiplist - ISC OR MIT.