# ART вместо SkipList: research + архитектурная заготовка (почти спецификация)

Статус: research, без обязательства реализовывать. Закрывает пункт **R4** из
[space-optimization.md](../space-optimization.md) («ART / компактный индекс вместо SkipList —
2–4× на индексе, высокая цена, высокий риск»).
Research выполнен моделью Claude Fable 5 (автономный scheduled run, 2026-07-03).

Смежные документы: [design.md](../design.md) (раздел «In-Memory Index»),
[research/skiplist-node-compaction.md](./skiplist-node-compaction.md),
[research/seize.md](./seize.md), [research/ideas.md](./ideas.md) (строка про ART),
спека `26-06-12-skiplist-optimistic-presearch.md`.

---

## 1. TL;DR

- **Что даёт ART:** O(len ключа) точечный поиск вместо O(len × log n) сравнений, лучшая
  кэш-локальность, естественный O(k) prefix-seek, и — на кластеризованных Fuid-ключах —
  заметная экономия RAM-индекса (потенциально 1.5–2.5× на per-key overhead). Полный OLC-вариант
  дополнительно снимает главный оставшийся write-bottleneck: один `write_lock` на всё дерево.
- **Что стоит:** ~2–3 тыс. строк нового unsafe-тяжёлого кода + полный перенос loom/miri/fuzz
  обвязки (сегодня SkipList — 2204 строки, вылизанные тремя итерациями оптимизаций). Готового
  крейта «ART на seize, ключи 8–16 Б, reverse-итерация» в экосистеме **нет** — писать своё.
- **На хешированных ключах (Id64) выигрыша по памяти не будет** (sparse-ключи — худший случай
  ART: ~25–35 Б/ключ на внутренних узлах). Выигрыш концентрируется на Fuid/композитных
  BE-ключах с общими префиксами.
- **seize — да, использовать.** Retire с per-type reclaimer'ами ложится на ART-узлы
  (Node4/16/48/256 + листья) без трений; это ровно тот контракт отложенного освобождения,
  который требует конкурентный ART. Альтернативы не нужны, и это сохраняет правило проекта
  «одна система memory reclamation».
- **Рекомендация:** не запускать полную замену вслепую. Сначала фаза-0: прототип +
  бенч-гейт по памяти и insert-scaling на реальных профилях ключей (см. §10). Порог
  целесообразности из space-optimization.md остаётся в силе: сотни млн — миллиарды записей.

---

## 2. Текущее состояние (что именно заменяем)

Один `SkipList<N>` на **Tree-коллекцию** (не per-shard): `ConstTree`/`ZeroTree`,
`VarTree`/`VarTypedTree`, `TypedTree` — оба durability-бэкенда через параметр
`L: Location` (`DiskLoc` = 12 Б для Bitcask, `u32` slot для FixedStore).
Map-коллекции (`ConstMap`/`VarMap`/…) используют per-shard `HashMap` под Mutex —
**ART их не касается**.

Ключевые свойства, которые обязана сохранить замена:

| Свойство | Как сейчас (файл) |
|---|---|
| Ключи — байтовые срезы, лексикографическое сравнение | `key_cmp` в `skiplist/mod.rs:104` |
| `reversed: bool` — DESC-порядок, переключаемый между запусками | инвертированный компаратор |
| Lock-free чтение, guard на операцию/итератор | `seize::LocalGuard`, `collector.enter()` |
| Один writer в структуру одновременно | `write_lock: Mutex<()>` + optimistic pre-search |
| SeqLock inline `loc`+`value` (Const), inline `loc` (Var) | `node.rs:96`, `node.rs:295` |
| RCU `AtomicPtr<TypedData<T>>` (Typed) | `node.rs:437` |
| Weakly-consistent итерация, `DoubleEndedIterator` | `iter.rs`, `find_first_ge`/`find_last_lt`/`find_last` |
| Prefix/range-итерация | `prefix_bounds` + `find_first_ge` |
| Compaction CAS: `update_if_match(key, old_loc, new_loc)` | leaf SeqLock write (`const_tree.rs:188`) |
| Finger-курсор для batch-операций (`get_many`/`update_many`) | `finger.rs`, tier-3 sorted walk |
| Migrate: обход level-0 с мутациями через put/delete | inline apply, O(1) доп. памяти |
| loom + miri (Stacked Borrows) покрытие | `tests/loom_skiplist.rs`, `tests/miri_skiplist.rs` |

Память на запись после оптимизаций R1+R2 (одна аллокация на узел, VLA-tower):

| Узел | base | + tower (ср. ~11 Б) | итого |
|---|---:|---:|---:|
| `VarNode` (K=8) | ~40 Б | ~11 | **~51 Б** |
| `ConstNode` (K=8, V=16) | ~56 Б | ~11 | ~67 Б |
| `TypedNode` (K=8, T=64) | ~32 Б + Box(TypedData) ~92 | ~11 | ~135 Б |

Из ~51 Б VarNode «полезных» — 20 Б (ключ 8 + loc 12); инфраструктура SkipList —
tower_ptr (8) + tower (~11) + seq (8) + выравнивание ≈ **~31 Б/запись**. Это и есть
мишень ART.

---

## 3. Справка: что такое ART (Leis et al., ICDE 2013)

Radix-дерево со span = 8 бит и четырьмя адаптивными типами внутренних узлов:

| Узел | Ёмкость | Layout | Поиск |
|---|---|---|---|
| Node4 | ≤4 | 4 key-байта + 4 указателя | линейный |
| Node16 | ≤16 | 16 + 16 | SIMD (SSE2/NEON) |
| Node48 | ≤48 | 256-Б индекс → 48 указателей | 2 разыменования |
| Node256 | ≤256 | прямой массив 256 указателей | индексация |

Плюс **lazy expansion** (путь к единственному листу не материализуется) и
**path compression** (цепочки one-child узлов схлопываются в префикс заголовка;
pessimistic/optimistic/hybrid варианты). Высота ≤ длины ключа в байтах (≤8 уровней для
8-байтного ключа), ребалансировки нет — форма дерева детерминирована множеством ключей.

**Требование binary-comparable keys:** порядок обхода = байтовый лексикографический.
Наши ключи уже такие: SkipList сравнивает `key.as_bytes()` лексикографически, ключи —
zerocopy-структуры с BE-полями (`user_id: [u8; 8] // big-endian u64`). Семантика порядка
при переходе **не меняется** — важное преимущество совместимости.

Конкурентные варианты (Leis et al., DaMoN'16):

- **OLC (optimistic lock coupling)** — 64-битная версия в заголовке узла; читатели ничего не
  пишут, сверяют версию и **рестартуют с корня** при конфликте; писатели лочат 1–2 узла.
  ~44/148/143 LOC (lookup/insert/remove) против 29/95/87 у несинхронизированного. Рекомендация
  авторов по умолчанию.
- **ROWEX** — читатели никогда не рестартуют; цена — несортированные Node4/16, все читаемые
  поля атомарные, поле `level` в узле ради неатомарной замены префикса. Сложнее в тонкостях.
- Оба требуют **отложенного освобождения узлов** — читатель может держать указатель на уже
  отсоединённый узел. Это в точности контракт `seize::retire`.

---

## 4. Преимущества перехода

1. **Память на кластеризованных ключах.** Fuid (timestamp/shard/seq, BE) — лучший случай ART:
   общий timestamp-префикс схлопывается path compression, верхние байты плотные (Node256 с
   высокой заполненностью). Оценка per-key overhead индексной части: ~8–10 Б против ~31 Б у
   SkipList → **VarTree ~28–34 Б/запись вместо ~51** (1.5–1.8×), с thin-leaf дизайном (§6.3)
   — до ~2.5×. На «миллиардах» это десятки ГБ.
2. **Скорость точечного чтения.** O(k) спуск по байтам вместо O(log n) кэш-промахов по
   рассеянным узлам башни. В литературе ART на point-lookup в разы быстрее skip list
   (Wormhole paper фиксирует skip list как самый медленный ordered-индекс; блог-бенчи дают
   3–5×; консервативно ждём 1.5–3× на наших размерах).
3. **Prefix-seek за O(k).** `prefix_iter(user_id)` — спуск к узлу префикса и обход поддерева,
   вместо O(log n) поиска первого ключа. Для мессенджер-паттерна «последние N сообщений
   диалога» — прямое попадание.
4. **Снятие write-bottleneck (только при полном OLC).** Сегодня все писатели коллекции
   сериализуются на одном `write_lock` (optimistic pre-search сократил критическую секцию —
   3.4 Mops/s на 16 потоках, — но лок остался глобальным). OLC-ART даёт конкурентные вставки в
   разные поддеревья: в artsync-статье ~80–90 Mops lookup и линейный insert-scaling на 20
   потоках (2016 hardware); congee заявляет 150 Mops на 32 ядрах.
5. **Batch-операции естественнее.** Sorted finger-walk из `get_many` в trie превращается в
   спуск с переиспользованием общего префикса стека — проще и быстрее, чем skip-list finger.
6. **Recovery bulk-load.** Из отсортированного потока ART строится bottom-up почти без
   сравнений; hint-файлы можно сортировать по ключу на этапе генерации (см. открытый вопрос
   Q9).
7. **Детерминированная форма.** Нет рандомизированных высот → воспроизводимость в тестах,
   отсутствие «неудачных» башен.

## 5. Недостатки и риски

1. **Sparse-ключи — антислучай.** Хешированные `Id64` (равномерные 64-бит) дают полупустые
   нижние узлы: ~25–35 Б/ключ индексного overhead (ARCD15, Fig. 4) — **хуже или равно
   SkipList**. Если доминирующие коллекции ключуются Id64 — выигрыша по памяти нет вовсе.
2. **Объём и класс сложности работы.** Полный OLC insert/remove с grow/shrink узлов, path
   compression и конкурентной заменой префиксов — это самый сложный concurrent-код в проекте,
   выше классом, чем optimistic pre-search. Новая loom/miri/fuzz обвязка с нуля (текущие
   модели SkipList обесцениваются). Это доминирующая статья затрат.
3. **Нет готового крейта.** `congee` — ART-OLC, но только 8-байтные ключи, crossbeam-epoch
   (второй reclamation-стек в проекте — нарушение правила), нет reverse/prefix-итерации.
   `blart` — образцовый код (miri strict provenance, tagged pointers, DoubleEndedIterator),
   но однопоточный. `rart` — COW-снапшоты, не наш паттерн. Форк любого = поддержка чужой
   кодовой базы; своя реализация = п.2.
4. **Итерация под конкуренцией — слабее из коробки.** У SkipList weakly-consistent итерация
   бесплатна (level-0 связный список). В ART под OLC скан рестартует при конфликте версий;
   нужен resume-by-key протокол либо leaf-chain (§6.4). `next_back()` в конкурентных ART
   практически нигде не реализован — пишем сами.
5. **Горячая точка на монотонных вставках.** Fuid монотонен → вставки концентрируются в
   «правом крае» дерева; под OLC это рестарты писателей на одном узле (у SkipList
   монотонная вставка тоже сериализуется, так что регрессии нет, но и выигрыш п.4 на этом
   паттерне частично съедается). Смягчение: shard/seq биты ниже timestamp рассеивают
   нижние уровни.
6. **Удаления и усадка.** Shrink Node16→Node4 и схлопывание путей под конкуренцией — лок
   узла+родителя, замена, retire; многие реализации вообще не усаживают (space leak после
   массовых delete). Нужна явная политика (§9, Q8).
7. **Риск двойной поддержки.** Пока ART не вытеснит SkipList во всех Tree-коллекциях, живут
   две реализации индекса с двумя обвязками тестов.

---

## 6. Архитектурная заготовка (почти спецификация)

### 6.1 Scope и точка врезки

- Заменяется **только** `SkipList<N>` в Tree-коллекциях; Map-семейство не трогаем.
- Оба durability-бэкенда обслуживаются одним параметром листа `L: Location`
  (`DiskLoc` 12 Б / `u32`), как сейчас.
- API-поверхность (обязательный контракт, сигнатуры повторяют `skiplist/mod.rs`):
  `get`, `insert(node|key,…)`, `remove`, `len`, `find_first_ge`, `find_last_lt`,
  `find_last`, `collector()`, prefix/range итераторы + `DoubleEndedIterator`,
  finger-эквивалент для batch-walk, leaf-методы `read_loc/write_loc/read_value/
  write_data/load_data/swap_data`.
- Ввести `trait OrderedIndex<N>` (или generic-параметр коллекции `I: Index`) — чтобы
  SkipList и ART сосуществовали на переходный период и выбирались per-collection
  (см. Q4). Дефолт остаётся SkipList до прохождения бенч-гейтов.

### 6.2 Узлы

```rust,ignore
// Общий заголовок внутреннего узла (OLC)
#[repr(C)]
struct NodeHeader {
    version: AtomicU64,   // bit0 = locked, bit1 = obsolete, остальное — счётчик
    prefix_len: u8,       // hybrid path compression
    prefix: [u8; 8],      // первые ≤8 байт префикса pessimistic, хвост optimistic
    count: u8,            // занятые слоты
    kind: u8,             // Node4 | Node16 | Node48 | Node256 | Leaf-tag
}
```

- Дочерние указатели — **tagged pointers** (младшие биты: leaf/inner), как в blart.
- Node16 — SIMD-поиск ключевого байта (SSE2/NEON, за `cfg`; fallback — линейный).
- Для ключей фиксированной длины (у нас всегда `size_of::<K>()`) проблема
  «ключ-префикс-другого-ключа» отсутствует по построению — терминаторы не нужны.
  Инвариант закрепить `debug_assert!` на длину.

### 6.3 Листья — два варианта (решить на фазе-0)

**Fat leaf (консервативный, прямой перенос текущей семантики):**
лист = текущий узел без башни.

```rust,ignore
#[repr(C)]
struct VarLeaf<K> { key: K, seq: AtomicU64, loc: UnsafeCell<DiskLoc> }      // ~32 Б
#[repr(C)]
struct ConstLeaf<K, const V: usize, L> { key: K, seq: AtomicU64,
                                         loc: UnsafeCell<L>, value: UnsafeCell<[u8; V]> }
struct TypedLeaf<K, T> { key: K, data: AtomicPtr<TypedData<T>> }            // RCU как сейчас
```

Полная копия ключа в листе позволяет **optimistic path compression** (скип байтов при
спуске + финальная сверка ключа) и прямой перенос SeqLock/RCU-протоколов и
`update_if_match` компакции. Оценка VarTree K=8: лист 32 Б + внутренние ~8–10 Б/ключ
(dense) ≈ **40–42 Б/запись**.

**Thin leaf (агрессивный):** ключ не хранится — восстанавливается путём
(требует **pessimistic** path compression везде); для VarTree лист = только
`DiskLoc`, обновляемый RCU-свапом tagged-указателя в слоте родителя; для FixedStore
(`L = u32`) значение локации **инлайнится в сам слот** (нулевая аллокация листа).
Оценка: ~24–30 Б/запись (до 2.5× к текущим ~51), но: сложнее итераторы (ключ собирается
по стеку спуска), сложнее сверка при optimistic-чтениях, `update_if_match` требует
CAS-свапа вместо SeqLock-записи. Рекомендация: начинать с fat leaf, thin leaf — как
следующая итерация (аналогично тому, как node-compaction делался поверх работающего
SkipList).

### 6.4 Итерация

Два подхода, выбрать на фазе-0 (Q5):

1. **Stack-traversal + resume-by-key** (память: 0 доп. на лист). Итератор держит стек
   спуска (≤ len(K)+1 фреймов — влезает в SmallVec на стеке итератора); при провале
   version-check — re-seek `find_first_ge(last_returned + ε)`. Семантика получается
   ровно weakly-consistent (элемент не выдаётся дважды, пропусков нет — как у SkipList).
   `next_back()` — симметричный спуск к максимальному ребёнку.
2. **Leaf-chain** — двусвязный список листьев (как level-0 SkipList / B+-leaf chain):
   +16 Б/лист, зато итерация не зависит от структурных изменений дерева и `next_back`
   тривиален. Съедает заметную часть выигрыша по памяти — брать только если фаза-0
   покажет, что resume-by-key дорог на реальных сканах.

`reversed: bool`: в radix-дереве порядок фиксирован байтами, компаратор не подменишь.
Два способа: (а) **направление обхода** — `reversed=true` означает «`iter()` идёт
descending» (двунаправленный обход у ART симметричен, в отличие от SkipList); (б)
byte-flip ключей (`!b` на каждый байт) при вставке/поиске. Рекомендация — (а): без
трансформаций, `reversed` остаётся runtime-переключаемым между запусками (индекс
строится на recovery), `prefix_bounds`-логика упрощается.

### 6.5 Конкурентность — три варианта

| | A. Single-writer + OLC-читатели | B. Полный OLC | C. COW-снапшоты (rart-style) |
|---|---|---|---|
| write_lock дерева | остаётся | **снимается** | остаётся |
| Читатели | version-check + restart | version-check + restart | wait-free по снапшоту |
| Сложность | средняя | высокая | средняя, но чужой паттерн |
| Insert-scaling | как сейчас (~3.4 Mops) | потенциально ×N | хуже (аллокации на путь) |
| Что даёт | память + скорость чтения | всё из A + масштаб записи | снапшот-итераторы |

- **Вариант A** — писатели уже сериализованы существующим `write_lock`; per-node локи OLC
  вырождаются в version-bump'ы без contention, читателям остаётся стандартный
  restart-протокол. Минимальный прыжок сложности от текущей модели (это соответствует
  выводу web-research: «single-writer ART + lock-free readers — рассмотреть первым»).
- **Вариант B** — единственный, который улучшает масштаб записи; брать, только если
  профиль показывает упор в `write_lock` (после optimistic pre-search упор сместился в
  shard mutex и аллокатор — см. спеку 26-06-12).
- **Вариант C** отклонить: аллокационный шторм на каждый put противоречит цели «меньше RAM».

Рекомендация: **A как база, дизайн заголовка узла — совместимый с B** (то же поле
`version`), чтобы апгрейд до полного OLC был эволюцией, а не переписыванием.

### 6.6 Memory reclamation — seize (ответ на вопрос «стоит ли»)

**Да.** Аргументы:

1. Контракт OLC («узел нельзя освобождать, пока читатель может держать указатель»)
   — это в точности `guard.defer_retire(ptr, reclaim_fn)`, уже используемый в
   `skiplist/mod.rs:557`.
2. Гетерогенные узлы (Node4/16/48/256, листья разных типов) — per-type reclaimer'ы,
   тот же паттерн, что `SkipNode::reclaim`. Grow Node4→Node16 = собрать новый узел →
   CAS в родителе → retire старого: прямое применение API.
3. Hyaline держит длинные сканы без блокировки глобальной очистки — свойство, ради
   которого seize и выбирали (research/seize.md); для ART-итераторов с restart'ами
   оно так же критично.
4. Правило проекта «одна система reclamation» — congee с crossbeam-epoch его нарушил бы.
5. Прецеденты: papaya и flurry живут на seize; деревьев на seize в экосистеме нет —
   будем первыми, но препятствий в API нет (проверено по docs.rs seize 0.5.x:
   `Collector`, `LocalGuard`, `retire(ptr, unsafe fn(*mut T, &Collector))`).

Нюанс: у OLC-рестартов есть паттерн «читатель в цикле пере-входит в guard» — держать
**один guard на операцию** (не пересоздавать на рестарт), иначе теряется защита
указателей между попытками.

### 6.7 Интеграционные точки

- **Compaction** `update_if_match(key, old_loc, new_loc)`: lookup листа → сверка `loc` →
  SeqLock-запись (fat leaf) — переносится дословно.
- **Recovery**: сейчас per-shard потоки вставляют в один индекс под общим `write_lock`
  (боттлнек виден в PR #71). Для ART: (а) при варианте B — конкурентные вставки; (б) при
  варианте A —**bulk-build**: отсортировать батчи ключей (hint-файлы) и строить поддеревья
  bottom-up без синхронизации, финальная склейка под локом. Bulk-build — отдельная задача
  фазы 2, даёт recovery быстрее текущего.
- **Replication follower apply**: `apply_entry` — обычные put/delete, ничего специального.
- **Migrate**: обход + мутации через put/delete; с resume-by-key семантика сохраняется
  (изменение значения — RCU/SeqLock в листе, структура меняется только на insert/delete
  чужих ключей).
- **Batch ops (`get_many`/`update_many`)**: замена finger — «стековый спуск с откатом к
  общему префиксу» между отсортированными ключами; O(суммарной длины уникальных путей).
- **`len`**: `AtomicUsize` рядом с корнем, как сейчас.

### 6.8 Тестирование (обязательный объём)

- **miri** (strict provenance!) — tagged pointers требуют `ptr::with_addr`-дисциплины;
  blart здесь — прямой референс. Категории: аллокация/деаллокация всех типов узлов,
  grow/shrink, path-compression замены, SeqLock листа, итераторы + concurrent remove.
- **loom** — модели: (1) читатель против grow узла, (2) читатель против замены префикса,
  (3) SeqLock лист против читателя, (4) retire vs guard, (5) для варианта B — два
  писателя на смежных узлах. Бюджет состояний — как в текущих loom_skiplist моделях.
- **fuzz/proptest** — дифференциальный оракул против `BTreeMap<Vec<u8>, _>` (последовательный)
  и против SkipList (конкурентный, через общий trait) — вставки/удаления/сканы/prefix.
- **shuttle** (как у congee) — опционально, дешёвые рандомизированные interleavings там,
  где loom-модель не влезает.

---

## 7. Оценка памяти по профилям ключей (VarTree, ключ 8 Б, на запись)

| Профиль ключей | SkipList (сейчас) | ART fat-leaf | ART thin-leaf |
|---|---:|---:|---:|
| Fuid BE, плотная запись во времени | ~51 Б | ~40–44 Б | ~26–34 Б |
| Композитный (user_id BE, post_id BE), кластеризация по префиксу | ~51 Б (K=16: ~59) | ~44–52 Б | ~30–40 Б |
| Хешированный Id64 (uniform random) | ~51 Б | ~55–65 Б (**хуже**) | ~45–55 Б |

Цифры ART — оценки из литературы (dense ~7–10 Б/ключ inner, sparse ~25–35 Б/ключ, ARCD15)
плюс размер листа; **обязательны к замеру на фазе-0** на реальных дампах ключей. Const/Zero
выигрывают аналогично (минус башня и дубль инфраструктуры), Typed — меньше всех (доминирует
Box<TypedData>).

---

## 8. Brainstorming: спектр подходов (шире, чем «переписать индекс»)

1. **Свой ART на seize** (базовый сценарий этого документа) — варианты A/B из §6.5,
   fat/thin leaf из §6.3.
2. **Форк congee**: заменить crossbeam-epoch на seize, расширить ключи с 8 Б до generic
   `K: Key`, дописать reverse/prefix-итерацию. Оценка: объём доработок сопоставим со
   своей реализацией, при этом наследуем чужие инварианты без их loom-моделей. Годится
   как источник решений (SIMD Node16, OLC-протокол), не как база.
3. **blart как single-threaded ядро + собственная конкурентная обёртка** — не работает:
   конкурентность в ART нельзя навесить снаружи, она меняет layout узлов (ROWEX) или
   протокол доступа (OLC). blart — референс кода, не зависимость.
4. **Гибрид по уровням**: верх дерева (горячие, плотные уровни) — Node256 массивы почти
   без синхронизации, листовой «этаж» — текущие SkipList-сегменты. Снимает часть памяти
   башен, сохраняет итерацию. Экзотика; рассматривать, только если фаза-0 провалит
   итераторы ART.
5. **Per-collection выбор индекса** (`Config`/тип-параметр): ART для Fuid-ключёванных
   коллекций, SkipList для Id64-ключёванных. Честно отражает асимметрию выигрыша (§7),
   но фиксирует двойную поддержку навсегда.
6. **HOT (Height Optimized Trie)** — закрывает слабость ART на sparse-ключах (адаптивный
   span), ROWEX-синхронизация. Реализация ещё сложнее ART, Rust-референсов нет. Держать
   в поле зрения как «ART v2», не как первый шаг.
7. **Не-ART альтернативы той же цели (RAM)**: R3 insert-once режим (−8 Б seq с листа/узла),
   R5 ленивый keydir холодных шардов, либо вынос самой большой коллекции в fjall
   (space-optimization §4). Эти рычаги конкурируют с ART за тот же бюджет усилий —
   решение по ART надо принимать в этом контексте, а не изолированно.

## 9. Вопросы, которые должен решить пользователь до реализации

- **Q1. Профиль ключей.** Какая доля данных (по количеству записей) в целевых инсталляциях
  ключуется Fuid/композитными BE-ключами, а какая — хешированными Id64? Если Id64
  доминирует — проект теряет главный аргумент (память), остаётся только скорость чтения.
- **Q2. Целевой масштаб.** Реально ли планируются сотни млн — миллиарды записей на узел?
  При <100M текущий SkipList после R1+R2 уже «в единицах ГБ» и ART не окупается.
- **Q3. Модель конкурентности.** Достаточно ли A (single-writer, как сейчас), или нужен
  concurrent insert-scaling (B, полный OLC)? Определяет класс сложности и loom-бюджет.
- **Q4. Стратегия сосуществования.** Trait-абстракция индекса с per-collection выбором и
  дефолтом SkipList — или жёсткая полная замена после гейтов? (Влияет на публичный API
  коллекций и на то, сколько времени живёт двойная поддержка.)
- **Q5. Итераторы.** Stack-traversal + resume-by-key (0 Б доп.) или leaf-chain (+16 Б/лист,
  проще семантика)? Готовы ли принять рестарты сканов под тяжёлой записью?
- **Q6. Листья.** Fat leaf сразу (безопасный перенос SeqLock/компакции) с thin leaf как
  второй итерацией — согласны с такой последовательностью?
- **Q7. `reversed`.** Направление обхода на уровне итератора (рекомендация) — или byte-flip?
  Есть ли внешние ожидания, что `reversed` остаётся свойством *сравнения*, а не обхода?
- **Q8. Политика shrink.** Усаживать узлы при delete (сложнее конкурентно) или lazy
  (space leak после массовых удалений — критично ли для ваших TTL/retention паттернов)?
- **Q9. Recovery bulk-build.** Разрешаем ли сортировку hint-данных при recovery (CPU/время
  старта vs скорость построения)? Нужно ли сохранять текущий параллельный per-shard паттерн?
- **Q10. Бенч-гейты.** Какие пороги принятия? Предложение: (а) RAM-индекс на реальном дампе
  Fuid-ключей ≤ 0.7× SkipList; (б) get p50 ≤ 0.8×; (в) insert 16 потоков ≥ 1.0× (A) /
  ≥ 2× (B); (г) full-scan ≥ 0.8×; (д) recovery ≤ 1.0×. Провал (а) на реальных ключах =
  стоп проекта.
- **Q11. Судьба SkipList.** Удаляем после миграции или оставляем навсегда (см. Q4)?
  Двойная loom/miri-поддержка — постоянный налог.

## 10. Рекомендуемый порядок работ

| Фаза | Содержание | Выход |
|---|---|---|
| **0. Прототип + гейт** | Однопоточный ART (можно поверх blart-идей) + замер памяти/скорости на **реальных дампах ключей** обоих профилей; решение Q1–Q6 | go/no-go, выбор leaf/iter дизайна |
| 1. Ядро | Узлы, спуск, insert/remove, path compression, вариант A конкурентности, seize retire, miri | `art/` модуль, паритет API `get/insert/remove` |
| 2. Итераторы + интеграция | range/prefix/DoubleEnded, resume-by-key, `reversed`, trait-врезка в ConstTree/VarTree/TypedTree, compaction `update_if_match`, batch-walk | все Tree-коллекции работают на ART за фичей/конфигом |
| 3. Recovery bulk-build | Сортировка hint-батчей, bottom-up build, паритет с PR #71 | recovery ≤ текущего |
| 4. Верификация | loom-модели, fuzz-оракулы, стресс + бенч-гейты Q10 | отчёт по гейтам |
| 5. (опц.) OLC (B) | Per-node локи писателей, снятие `write_lock` | insert-scaling ×N |
| 6. (опц.) Thin leaf | Ключ-из-пути, инлайн u32-слотов FixedStore | ещё −20–30% RAM |

Ориентир трудоёмкости: фазы 1–4 сопоставимы с суммой проектов «skiplist + node-compaction +
optimistic-presearch» вместе взятых. Это подтверждает классификацию R4 как «полноценный
отдельный проект».

## 11. Вывод

ART — технически состоятельная замена с реальным выигрышем **именно на профиле
«мессенджер»** (Fuid/композитные BE-ключи, prefix-сканы, монотонные вставки): память
индекса 1.5–2.5×, чтение быстрее, prefix-seek O(k), плюс опциональный путь к
конкурентной записи. Но это самый сложный concurrent-код в проекте без готовых крейтов,
с полным пересозданием верификационной обвязки, и он **ничего не даёт на хешированных
ключах**. Решение должно приниматься по данным фазы-0 (реальные дампы ключей) и в
явном сравнении с конкурирующими рычагами R3/R5/fjall за тот же бюджет усилий. seize —
использовать однозначно; congee/blart — источники решений, не зависимости.

## Источники

- Leis et al., *The Adaptive Radix Tree* (ICDE 2013) — https://db.in.tum.de/~leis/papers/ART.pdf
- Leis et al., *The ART of Practical Synchronization* (DaMoN 2016) — https://db.in.tum.de/~leis/papers/artsync.pdf
- Leis et al., *Optimistic Lock Coupling* (IEEE DE Bull. 2019) — http://sites.computer.org/debull/A19mar/p73.pdf
- Alvarez et al., *A Comparison of Adaptive Radix Trees and Hash Tables* (ICDE 2015) — https://bigdata.uni-saarland.de/publications/ARCD15.pdf
- Binna et al., *HOT: Height Optimized Trie* (SIGMOD 2018 / TODS 2022)
- congee — https://github.com/XiangpengHao/congee ; blart — https://github.com/declanvk/blart ; rart — https://github.com/rdaum/rart-rs
- seize — https://docs.rs/seize ; papaya design notes — https://ibraheem.ca/posts/designing-papaya/
- DuckDB ART storage — https://duckdb.org/2022/07/27/art-storage
- Wormhole (ordered index comparison) — https://arxiv.org/pdf/1805.02200
- Локальные: `docs/space-optimization.md`, `docs/design.md`, `docs/research/{seize,skiplist-node-compaction,skiplist-iteration-alternatives,ideas,arch}.md`, спека `26-06-12-skiplist-optimistic-presearch.md`
