# armdb: сравнение Tree и Map типов

## Обзор

Все типы с `[u8; V]` inline-значениями (Const*, Zero*, Fixed*) поддерживают два durability backend'а через generic `D: Durability`:
- **Bitcask** (default) — append-only log + compaction
- **Fixed** — fixed-slot pwrite, без compaction

`FixedTree` и `FixedMap` — type aliases: `FixedTree<K, V> = ConstTree<K, V, Fixed>`, `FixedMap<K, V> = ConstMap<K, V, Fixed>`.

|  | **VarTree** | **VarMap** | **VarTypedTree** | **VarTypedMap** | **TypedTree** | **TypedMap** | **ZeroTree** | **ZeroMap** | **ConstTree** | **ConstMap** |
|--|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| Индекс | SkipList | HashMap | SkipList | HashMap | SkipList | HashMap | SkipList | HashMap | SkipList | HashMap |
| Упорядоченность | да | нет | да | нет | да | нет | да | нет | да | нет |
| Значение | bytes на диске | bytes на диске | bytes на диске, декод в `T` | bytes на диске, декод в `T` | `T` in-memory | `T` in-memory | `T` zerocopy | `T` zerocopy | `[u8; V]` inline | `[u8; V]` inline |
| Кодек | — | — | `Codec<T>` | `Codec<T>` | `Codec<T>` | `Codec<T>` | zerocopy | zerocopy | — | — |
| Hook | `WriteHook<K>` | `WriteHook<K>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `WriteHook<K>` | `WriteHook<K>` |
| FixedStore backend | нет | нет | нет | нет | нет | нет | да | да | да | да |
| Репликация | да | да | да | да | да | да | Bitcask: GSN / Fixed: events | Bitcask: GSN / Fixed: events | Bitcask: GSN / Fixed: events | Bitcask: GSN / Fixed: events |
| Шифрование | да | да | да | да | да | да | только Bitcask | только Bitcask | только Bitcask | только Bitcask |

## Стоимость операций

### Чтение (get)

| Тип | Сложность | Disk I/O | Блокировка | Возврат |
|-----|:---------:|:--------:|:----------:|---------|
| ConstTree | O(log n) | нет | lock-free | `Option<[u8; V]>` (Copy) |
| VarTree | O(log n) | cache miss → pread | lock-free на cache hit | `Option<ByteView>` (RC) |
| TypedTree | O(log n) | нет | lock-free | `Option<TypedRef<T>>` (guard) |
| ZeroTree | O(log n) | нет | lock-free | `Option<T>` (Copy) |
| ConstMap | O(1) | нет | shard mutex (кратко) | `Option<[u8; V]>` (Copy) |
| VarMap | O(1) | cache miss → pread | shard mutex (кратко) | `Option<ByteView>` (RC) |
| TypedMap | O(1) | нет | shard mutex (кратко) | `Option<TypedRef<T>>` (guard) |
| ZeroMap | O(1) | нет | shard mutex (кратко) | `Option<T>` (Copy) |

### Запись (put)

Все типы: **shard mutex + запись на диск**. Bitcask backend: append в log. FixedStore backend: pwrite в слот (in-place). Разница в кодировании значения:

При обновлении существующего ключа: ConstTree/ZeroTree выполняют SeqLock write (inline, без heap-аллокации). TypedTree/VarTree — RCU swap (Box + AtomicPtr::swap + seize::retire).

| Тип | Кодирование | Возврат старого значения |
|-----|-------------|:-----------------------:|
| ConstTree | нет (байты как есть) | `Option<[u8; V]>` |
| VarTree | нет | нет (`DbResult<()>`) |
| TypedTree | Codec::encode_to | `Option<TypedRef<T>>` |
| ZeroTree | zerocopy to_bytes | `Option<T>` |
| ConstMap | нет | `Option<[u8; V]>` |
| VarMap | нет | нет (`DbResult<()>`) |
| TypedMap | Codec::encode_to | `Option<TypedRef<T>>` |
| ZeroMap | zerocopy to_bytes | `Option<T>` |

### CAS / Update

| Тип | cas | update | Блокировка при CAS |
|-----|:---:|:------:|:------------------:|
| ConstTree | да | да | shard mutex |
| VarTree | да | да | shard mutex + **возможен disk I/O** |
| TypedTree | да (`T: PartialEq`) | да | shard mutex |
| ZeroTree | да | да | shard mutex |
| ConstMap | да | да | shard mutex |
| VarMap | да | да | shard mutex + **возможен disk I/O** |
| TypedMap | да (`T: PartialEq`) | да | shard mutex |
| ZeroMap | да | да | shard mutex |

> VarTree/VarMap: CAS и update читают текущее значение под shard lock. При промахе block cache — disk I/O блокирует весь шард.

## Итерация

| Тип | iter() | range() | prefix_iter() | DoubleEndedIterator | reversed |
|-----|:------:|:-------:|:-------------:|:-------------------:|:--------:|
| ConstTree | да | да | да | да | да |
| VarTree | да | да | да | да | да |
| TypedTree | да | да | да | да | да |
| ZeroTree | да | да | да | да | да |
| ConstMap | — | — | — | — | — |
| VarMap | — | — | — | — | — |
| TypedMap | — | — | — | — | — |
| ZeroMap | — | — | — | — | — |

**Стоимость итерации:**
- ConstTree, TypedTree, ZeroTree — lock-free, zero I/O
- VarTree — per item: block cache lookup, возможен disk I/O

## Потребление памяти

Disk location: DiskLoc (12 bytes) для Bitcask, slot_id (4 bytes) для FixedStore. Таблица показывает Bitcask; для FixedStore — вычесть 8 bytes из location.

| Тип | На запись (приблизительно) | Примечание |
|-----|---------------------------|------------|
| ConstTree (Bitcask) | ~60 bytes (SkipList node, SeqLock inline) + V + 12 | значения + DiskLoc inline, VLA tower |
| ConstTree (Fixed) | ~60 bytes (SkipList node, SeqLock inline) + V + 4 | slot_id вместо DiskLoc, **-8B/entry** |
| VarTree | ~60 bytes (SkipList node, VLA) + Box\<DiskLoc\> 12 bytes | значения на диске, BlockCache отдельно |
| TypedTree | ~60 bytes (SkipList node, VLA) + sizeof(T) + 12 bytes (DiskLoc) in Box\<TypedData\> | T на куче, управляется seize |
| ZeroTree | как ConstTree | обёртка над ConstTree (оба backend'а) |
| ConstMap (Bitcask) | ~50 bytes (HashMap bucket) + V + 12 bytes (DiskLoc) | значения inline в HashMap |
| ConstMap (Fixed) | ~50 bytes (HashMap bucket) + V + 4 bytes (slot_id) | **-8B/entry** |
| VarMap | ~50 bytes (HashMap bucket) + 12 bytes (DiskLoc) | значения на диске, BlockCache отдельно |
| TypedMap | ~50 bytes (HashMap bucket) + sizeof(T) + 12 bytes (DiskLoc) | T на куче, управляется seize |
| ZeroMap | как ConstMap | обёртка над ConstMap (оба backend'а) |

Экономия FixedStore при 100M entries: **800 MB**.

**BlockCache** (VarTree, VarMap): отдельный бюджет, блоки по 4096 байт, 2-tier LRU.

## Требования к типам

### Ключ K

| Tree-типы | Map-типы |
|-----------|----------|
| `FromBytes + IntoBytes + Immutable + Copy + 'static` | + `Send + Sync + Hash + Eq` |

### Значение

| Тип | Bounds |
|-----|--------|
| Const{Tree,Map} | фиксированный `[u8; V]` |
| Var{Tree,Map} | произвольные `&[u8]` |
| Typed{Tree,Map} | `T: Send + Sync`, требуется `Codec<T>` |
| Zero{Tree,Map} | `T: FromBytes + IntoBytes + Immutable + KnownLayout`, `size_of::<T>() == V` |

### T: Clone

Только для `compact()` в TypedTree и TypedMap. Все остальные операции — без Clone.

## Полный список методов

Общие для всех типов (любой backend):
- `get`, `put`, `insert`, `delete`
- `cas`, `update`, `fetch_update`
- `contains(&self, &K) -> bool`
- `len(&self) -> usize`
- `is_empty(&self) -> bool`
- `atomic(&self, &K, FnOnce(&mut Shard)) -> DbResult<R>`
- `shard_for(&self, &K) -> usize`
- `flush(&self) -> DbResult<()>`

Только Bitcask backend:
- `open(Config, ...) -> DbResult<Self>`
- `close(self) -> DbResult<()>`
- `flush_buffers(&self) -> DbResult<()>`
- `config(&self) -> &Config`
- `compact(&self) -> DbResult<usize>`
- `sync_hints(&self) -> DbResult<()>`
- `migrate(...)` , `replay_init(...)`

Только FixedStore backend:
- `open(FixedConfig, ...) -> DbResult<Self>`
- `close(&self) -> DbResult<()>`

Только Tree-типы (SkipList):
- `iter()`, `range()`, `prefix_iter()`, `first()`, `last()`

Только Var{Tree,Map}:
- `warmup(&self) -> DbResult<()>`

Только Zero{Tree,Map}:
- `as_inner(&self) -> &Const{Tree,Map}` (только Bitcask)

## Bitcask store vs FixedStore

Сравнение двух durability backend'ов для коллекций с фиксированным размером значений. API слой (ConstMap/ZeroMap/ConstTree и т.д.) ортогонален — любая коллекция с `[u8; V]` inline-значениями может работать поверх любого backend'а.

- **Bitcask store** — append-only log + compaction. Используется в ConstTree, ConstMap, ZeroTree, ZeroMap и др.
- **FixedStore** — fixed-slot файл с pwrite in-place. Используется в FixedTree, FixedMap.

### Операции чтения

Чтение **идентично** для обоих backend'ов: значения хранятся inline в in-memory индексе (SkipList или HashMap). Обращения к диску нет. Backend не участвует в read path.

| | Bitcask | FixedStore |
|--|:------:|:---------:|
| Disk I/O на чтение | нет | нет |
| Latency | ~50-400 ns (зависит от индекса) | ~50-400 ns (идентично) |

### Операции записи

| | Bitcask | FixedStore |
|--|:------:|:---------:|
| Disk write | append в log файл | pwrite в фиксированный слот |
| Семантика | новая запись в конец файла | перезапись существующего слота |
| Latency (p50) | ~300-800 ns | ~300-800 ns |
| Latency (p99.9) | **~1-5 ms** (write buf flush под lock) | **~10-50 μs** (fdatasync после unlock) |
| Compaction | обязательна | не нужна |
| Write amplification | высокий (append + compaction rewrite) | 1x |

Средняя latency сравнима — оба пишут через shard mutex + memcpy в kernel buffer. **Критическое различие — tail latency**: Bitcask делает write buffer flush под shard lock (~1-5 ms spike), FixedStore вызывает fdatasync после release mutex (~10-50 μs, не блокирует writers).

### Потребление памяти

In-memory index одинаковый для обоих backend'ов (SkipList или HashMap). Единственная разница — размер disk location:

| | Bitcask | FixedStore |
|--|:------:|:---------:|
| Disk location | DiskLoc 12 bytes (`offset, len, file_id, shard_id`) | slot_id 4 bytes (`u32`) |
| **Разница на запись** | — | **-8 bytes** |

| Записей | Экономия FixedStore |
|--------:|---------:|
| 1M | 8 MB |
| 10M | 80 MB |
| 100M | 800 MB |

Остальное потребление (SkipList node ~60B или HashMap bucket ~50B, значение V bytes inline) — одинаковое.

### Disk usage

| | Bitcask | FixedStore |
|--|:------:|:---------:|
| Space amplification | 1.3-2x (мёртвые записи до compaction) | 1x |
| Файлы на шард | множество .data + .hint | 1 файл (fixed.data) + sidecar (fixed.bitmap) |
| Рост | автоматически (новые .data файлы) | по grow_step слотов (ftruncate) |
| Disk usage предсказуем | нет (зависит от compaction) | да (N × slot_size + header) |

### Recovery

| | Bitcask | FixedStore |
|--|:------:|:---------:|
| Алгоритм | scan всех .data файлов (+ hint files) | scan одного fixed.data |
| Время (10M entries) | ~1-10 s | ~300 ms (dirty), ~100-200 ms (clean) |
| Clean shutdown ускорение | hint files | bitmap sidecar |

### Operational

| | Bitcask | FixedStore |
|--|:------:|:---------:|
| Background I/O | compaction storms | нет |
| p99.9 latency spikes | да (compaction + write buf flush) | нет |
| Репликация (GSN log shipping) | да | нет (нет append-only лога) |
| Репликация (event-based) | нет | да (`FixedReplicationTarget`, `fixed_replication/`) |
| Crash safety при update | старое значение сохраняется (append) | возможна потеря ключа (partial overwrite) |

### Когда какой backend

| Сценарий | Backend |
|----------|---------|
| Частые обновления одних и тех же ключей | **FixedStore** |
| Предсказуемая latency без spikes | **FixedStore** |
| Минимальное потребление диска | **FixedStore** (1x vs 1.3-2x) |
| Быстрая recovery | **FixedStore** (~10x) |
| Нужна репликация (log shipping, GSN) | **Bitcask** |
| Нужна репликация для fixed-slot коллекций | **FixedStore** (event-based) |
| Append-mostly workload (логи, события) | **Bitcask** |
| Crash safety критична (не терять ключи) | **Bitcask** (append безопаснее overwrite) |
| Variable-size значения | **Bitcask** (FixedStore только фиксированные) |

---

## Когда что использовать

| Сценарий | Рекомендация |
|----------|-------------|
| Маленькие фиксированные значения + ordered scans | **ConstTree** (`hints: false`) |
| Маленькие фиксированные значения + point lookups | **ConstMap** (`hints: false`) |
| Большие или переменные значения + ordered | **VarTree** (`hints: true`) |
| Большие или переменные значения + point lookups | **VarMap** (`hints: true`) |
| Сложные структуры (String, Vec) + ordered, помещаются в RAM | **TypedTree** + RapiraCodec (`hints: false`) |
| Сложные структуры + point lookups, помещаются в RAM | **TypedMap** + RapiraCodec (`hints: false`) |
| Сложные структуры + ordered, данные не помещаются в RAM | **VarTypedTree** + RapiraCodec (`hints: true`) |
| Сложные структуры + point lookups, данные не помещаются в RAM | **VarTypedMap** + RapiraCodec (`hints: true`) |
| repr(C) структуры фиксированного размера + ordered | **ZeroTree** (`hints: false`) |
| repr(C) структуры фиксированного размера + point lookups | **ZeroMap** (`hints: false`) |
| Данные не помещаются в RAM | **VarTree** или **VarMap** (`hints: true`) |
| Минимальная латентность чтения | любой in-memory тип (не Var) |
| Частые обновления фиксированных значений | **FixedTree** / **FixedMap** (FixedStore backend) |
| Счётчики, rate limiters, метрики | **FixedTree** / **FixedMap** |
| Предсказуемая latency без compaction spikes | **FixedTree** / **FixedMap** |

### Конфигурация hint файлов

`Config::hints` по умолчанию `None` — каждый `open()` разрешает по типу коллекции (Var → `true`, inline → `false`). Явный `Some(x)` переопределяет.

- **VarTree/VarMap** — при `None` получают `hints: true`. Без hints recovery читает все значения с диска.
- **ConstTree/TypedTree/ZeroTree и Map-аналоги** — при `None` получают `hints: false`. Значения малы или декодируются в памяти, полный скан быстр. Отключение hints экономит дисковое пространство и время на close/rotation.
