# 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>`.
| Индекс | SkipList | HashMap | SkipList | HashMap | SkipList | HashMap | SkipList | HashMap |
| Упорядоченность | да | нет | да | нет | да | нет | да | нет |
| Значение | bytes на диске | bytes на диске | `T` in-memory | `T` in-memory | `T` zerocopy | `T` zerocopy | `[u8; V]` inline | `[u8; V]` inline |
| Кодек | — | — | `Codec<T>` | `Codec<T>` | zerocopy | zerocopy | — | — |
| Hook | `WriteHook<K>` | `WriteHook<K>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `TypedWriteHook<K,T>` | `WriteHook<K>` | `WriteHook<K>` |
| FixedStore backend | нет | нет | нет | нет | да | да | да | да |
| Репликация | да | да | да | да | только Bitcask | только Bitcask | только Bitcask | только Bitcask |
| Шифрование | да | да | да | да | только Bitcask | только Bitcask | только Bitcask | только Bitcask |
## Стоимость операций
### Чтение (get)
| 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
| 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 блокирует весь шард.
## Итерация
| 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
| `FromBytes + IntoBytes + Immutable + Copy + 'static` | + `Send + Sync + Hash + Eq` |
### Значение
| 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.
| Disk I/O на чтение | нет | нет |
| Latency | ~50-400 ns (зависит от индекса) | ~50-400 ns (идентично) |
### Операции записи
| 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:
| Disk location | DiskLoc 12 bytes (`offset, len, file_id, shard_id`) | slot_id 4 bytes (`u32`) |
| **Разница на запись** | — | **-8 bytes** |
| 1M | 8 MB |
| 10M | 80 MB |
| 100M | 800 MB |
Остальное потребление (SkipList node ~60B или HashMap bucket ~50B, значение V bytes inline) — одинаковое.
### Disk usage
| 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
| Алгоритм | 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
| Background I/O | compaction storms | нет |
| p99.9 latency spikes | да (compaction + write buf flush) | нет |
| Репликация (GSN log shipping) | да | нет (нет append-only лога) |
| Crash safety при update | старое значение сохраняется (append) | возможна потеря ключа (partial overwrite) |
### Когда какой backend
| Частые обновления одних и тех же ключей | **FixedStore** |
| Предсказуемая latency без spikes | **FixedStore** |
| Минимальное потребление диска | **FixedStore** (1x vs 1.3-2x) |
| Быстрая recovery | **FixedStore** (~10x) |
| Нужна репликация (log shipping) | **Bitcask** |
| 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 | **TypedTree** + RapiraCodec (`hints: false`) |
| Сложные структуры + point lookups | **TypedMap** + RapiraCodec (`hints: false`) |
| 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` (default: `true`) управляет генерацией и использованием hint файлов при recovery.
- **VarTree/VarMap** — рекомендуется `hints: true`. Без hints recovery читает все значения с диска.
- **ConstTree/TypedTree/ZeroTree и Map-аналоги** — рекомендуется `hints: false`. Значения малы или декодируются в памяти, полный скан быстр. Отключение hints экономит дисковое пространство и время на close/rotation.