# armdb — Design Document

Встраиваемое key-value хранилище на Rust, оптимизированное для NVMe.
Архитектура: **Sharded Bitcask** (Log-Structured, Append-Only).

---

## Цели и ограничения

### Цели
- Высокая производительность на NVMe (сотни тысяч IOPS)
- Sync API для чтения (`db.get(key) -> Option<Value>`)
- Sync API для записи (`db.put(key, value)`, `db.cas(key, expected, new)`)
- Prefix search по ключам
- Встроенная репликация (log shipping)
- Предсказуемая latency при смешанной нагрузке (read + write)

### Ограничения (by design)
- Single process (multi-thread внутри)
- Без WAL — допускается потеря последних незаписанных данных при аварии
- Без mmap
- Одна таблица (keyspace) на экземпляр

### Применение
- Индексы
- Пользовательские сессии
- Логи
- Read-реплики
- Кэши с персистентностью

---

## Зависимости

| Крейт | Назначение |
|-------|-----------|
| `rustix` | Системные вызовы (`pread`, aligned reads, fd management; `O_DIRECT` на Linux — opt-in через `Config.direct_io`, graceful fallback) |
| `rustix-uring` | io_uring: batch write, fsync, compaction I/O |
| `seize` | Epoch-based memory reclamation (Hyaline algorithm) — используется и для lock-free индекса, и для GC узлов |
| `crc32fast` | CRC32 чексуммы записей на диске |
| `xxhash-rust` | Хеширование ключей для маршрутизации по шардам |
| `zerocopy` | Zero-copy десериализация заголовков записей |
| `parking_lot` | `Mutex` per shard для write path |
| `quick_cache` | S3-FIFO value cache с weight-based eviction (настраиваемый лимит в байтах) |
| `ring` | *(optional, feature `encryption`)* AES-256-GCM шифрование данных на диске |

`scc` **не используется**. Индекс реализуется как собственный concurrent SkipList на `seize`, чтобы в проекте была одна система memory reclamation.

---

## Архитектура

### Общая схема

```text
                        ┌──────────────────────────┐
                        │      Public API           │
                        │  get / put / cas / delete │
                        │  prefix_iter / range      │
                        └────────────┬─────────────┘
                                     │
              ┌──────────────────────┼──────────────────────┐
              │                      │                      │
              ▼                      ▼                      ▼
   ┌──────────────────┐  ┌──────────────────┐  ┌──────────────────┐
   │   ConstTree<K,V> │  │   VarTree<K>     │  │   VarTree<K>     │
   │   index: SkipList │  │   index: SkipList │  │   (другой)       │
   └────────┬─────────┘  └────────┬─────────┘  └────────┬─────────┘
            │                      │                      │
            └──────────┬───────────┘──────────────────────┘
                       │
              ┌────────▼──────────┐
              │   Block Cache     │  S3-FIFO (quick_cache)
              │   4096-byte blocks│  e.g. max 1GB
              └────────┬──────────┘
                       │
            hash(key) % N  маршрутизация
                       │
      ┌────────────────┼────────────────────────┐
      │                │                        │
┌─────▼──────┐  ┌──────▼─────┐          ┌──────▼─────┐
│  Shard #0  │  │  Shard #1  │   ...    │  Shard #N  │
│  Mutex     │  │  Mutex     │          │  Mutex     │
│  RingBuf   │  │  RingBuf   │          │  RingBuf   │
│  Files     │  │  Files     │          │  Files     │
└─────┬──────┘  └──────┬─────┘          └──────┬─────┘
      │ io_uring        │ io_uring              │ io_uring
      ▼                 ▼                       ▼
[ NVMe Files ]   [ NVMe Files ]         [ NVMe Files ]
      │                 │                       │
      └────────┬────────┘───────────────────────┘
               │
        Replication Stream
               │
               ▼
        [ Follower Node ]
```

### Компоненты

**1. SkipList Index** — собственный concurrent SkipList на `seize`. Lock-free чтение, поддержка prefix scan и range iteration. Один индекс на каждый Tree.

**2. Block Cache** — S3-FIFO кэш 4096-байтных блоков (естественная единица O_DIRECT) с настраиваемым лимитом памяти. Отделён от индекса. Для `ConstTree` не используется (значения всегда inline). При cache hit один блок содержит данные для десятков мелких записей (пространственная локальность append-only формата).

**3. Shards** — $N$ независимых партиций (по умолчанию `num_cpus * 2`). Каждый шард: свои файлы на диске, свой write buffer, свой `Mutex`. Шард определяется по `xxh3(key) % N`.

**4. io_uring Engine** — batch write и fsync через io_uring с `SQPOLL`, registered buffers и registered files.

**5. Compactor** — фоновый поток, чистит устаревшие записи в immutable файлах.

**6. Replicator** — стримит новые записи на follower-ноды (log shipping per shard).

---

## In-Memory Index: SkipList на `seize`

### Почему SkipList, а не B+Tree или ART

| Критерий | SkipList | B+Tree | ART |
|----------|----------|--------|-----|
| Lock-free реализация | Простая (академическая база) | Сложная (splits/merges) | Средняя |
| Prefix search | Да (узлы отсортированы) | Да | Лучший O(K) |
| Range scan | Натурально (linked list) | Да (leaf chain) | Требует доп. работы |
| `seize` совместимость | Идеальная (retire отдельных узлов) | Сложная (retire целых страниц) | Хорошая |
| Сложность реализации | Низкая | Высокая | Средняя |

**Решение:** SkipList на `seize`. При необходимости можно заменить на ART позже — API тот же.

### Структура узла SkipList

Для `ConstTree`, `VarTree` и `TypedTree` используются разные узлы. Все узлы используют VLA (variable-length array) для tower вместо `SmallVec` — tower размещается в той же аллокации сразу после struct. Поле `tower_ptr` указывает на начало VLA для корректности Stacked Borrows. Логическое удаление кодируется tag-битом в `tower[0]` (отдельного `marked: AtomicBool` нет).

```rust,ignore
/// ConstNode — SeqLock inline data, VLA tower
#[repr(C)]
struct ConstNode<K: Key, const V: usize> {
    key: K,
    seq: AtomicU64,                    // SeqLock counter
    disk: UnsafeCell<DiskLoc>,         // 12 bytes inline
    value: UnsafeCell<[u8; V]>,        // inline, no heap
    height: u8,
    tower_ptr: *const AtomicPtr<Self>, // pointer to VLA tower
    // tower[0..height] follows in same allocation
}

/// VarNode — RCU disk pointer, VLA tower
#[repr(C)]
struct VarNode<K: Key> {
    key: K,
    disk: AtomicPtr<DiskLoc>,          // RCU pointer
    height: u8,
    tower_ptr: *const AtomicPtr<Self>,
    // tower[0..height] follows in same allocation
}

/// TypedNode — RCU data pointer, VLA tower
#[repr(C)]
struct TypedNode<K: Key, T> {
    key: K,
    data: AtomicPtr<TypedData<T>>,     // RCU pointer (DiskLoc + T)
    height: u8,
    tower_ptr: *const AtomicPtr<Self>,
    // tower[0..height] follows in same allocation
}
```

`ConstNode` хранит значение и `DiskLoc` inline, защищая их SeqLock (поле `seq`). Отдельной структуры `ConstData` нет — heap-аллокация при обновлении не требуется.

`VarNode` и `TypedNode` используют RCU (AtomicPtr swap + seize retire) для обновления данных.

Для `VarTree` значения хранятся отдельно — в Block Cache (см. ниже).

### Операции

```rust,ignore
struct SkipList<N> {
    head: *mut N,
    collector: seize::Collector,
    len: AtomicUsize,
    write_lock: Mutex<()>,
}

impl<N> SkipList<N> {
    /// Lock-free чтение. Возвращает ссылку, защищённую guard.
    fn get<'g>(&self, key: &[u8], guard: &'g seize::Guard) -> Option<&'g N>;

    /// Вставка: optimistic pre-search вне лока, валидация + линковка под write_lock.
    fn insert(&self, node: *mut N);

    /// Обновление значения в узле. Для ConstTree — SeqLock write (inline).
    /// Для VarTree — AtomicPtr swap на DiskLoc (RCU).
    /// Для TypedTree — AtomicPtr swap на TypedData (RCU).
    /// Вызывается на существующем узле после insert вернул Exists.
    fn update(&self, key: &[u8], node: *mut N, guard: &seize::Guard);

    /// Удаление: optimistic pre-search вне лока; mark + unlink + retire под write_lock.
    fn remove(&self, key: &[u8], guard: &seize::Guard) -> bool;

    /// Итератор по диапазону [start, end). Lock-free.
    fn range<'g>(&self, start: &[u8], end: &[u8], guard: &'g seize::Guard) -> RangeIter<'g, N>;

    /// Итератор по префиксу. Lock-free.
    fn prefix<'g>(&self, prefix: &[u8], guard: &'g seize::Guard) -> PrefixIter<'g, N>;
}
```

> SkipList внутренне работает с `&[u8]` срезами. Вызывающий код передаёт `key.as_bytes()` (через `IntoBytes`).

### Concurrency: optimistic pre-search + write_lock

Линковка новых узлов в tower выполняется plain `store` (не CAS) — это
корректно только при **одном линкере в момент времени**: все мутации tower
(линковка и helping-unlink) происходят строго под `write_lock: Mutex<()>`.
Читатели (`get`, итераторы) lock-free.

`insert`/`remove` используют **optimistic pre-search** (Herlihy–Shavit-style):

1. Поиск предшественников — вне лока (read-only, marked-узлы пропускаются
   без helping — helping вне лока был бы вторым писателем в tower slot).
   Successor каждого уровня фиксируется в точке решения внутри спуска —
   отдельный re-read после цикла дал бы внутренне рассогласованный frame,
   проходящий валидацию с неверной позицией (баг, пойманный loom-моделями).
2. Под локом — валидация per-level: `pred` не marked, `pred.tower(l)` всё
   ещё указывает на записанный succ; null succ легален (вставка в хвост
   уровня), не-null succ проверяется на mark.
3. При расхождении — полный locked-поиск с helping (fallback = прежний код).
4. Линковка — те же plain store.

Critical section — O(node_height) валидация + линковка, а не полный
O(log n) спуск. Same-key конкурентность не требует внешней сериализации:
`Exists`/`None` линеаризуются в момент наблюдения pre-search, дубликат
same-key insert ловится гарантированным провалом валидации уровня 0.

Бенчмарк фазы A `examples/insert_scaling.rs` (Ryzen 7 7700, 16 ядер,
prefill 8M, инсерты новых ключей в одно дерево):

| Потоки | До (поиск под локом) | После (optimistic) |
|-------:|---------------------:|-------------------:|
| 1 | 0.47 Mops/s | 0.47 Mops/s (1.00x) |
| 8 | 0.36 Mops/s (0.76x) | 3.14 Mops/s (6.73x) |
| 16 | 0.33 Mops/s (0.70x) | 3.40 Mops/s (7.28x) |

**Полный lock-free CAS-linking** (crossbeam-style) отклонён: максимальный
класс риска (retry-петли, обесценивание loom/miri-моделей), а после
optimistic-варианта упор смещается в shard mutex и аллокатор. Дизайн и
бенч-гейт: `docs/superpowers/specs/26-06-12-skiplist-optimistic-presearch.md`.

### Референс реализации

- `crossbeam-skiplist` — архитектура, layout узлов (полный CAS-linking отклонён, см. спеку optimistic pre-search)
- Herlihy & Shavit "The Art of Multiprocessor Programming", Chapter 14 — optimistic validate-после-поиска паттерн
- Заменить `crossbeam-epoch` на `seize` (API похож: `Guard`, `retire`)

---

## Типы данных

### Ключ

Генерик `K` с zerocopy trait bounds:

```rust,ignore
K: FromBytes + IntoBytes + Immutable + Copy + 'static
```

Длина ключа известна на этапе компиляции через `size_of::<K>()`. Не нужно хранить `key_len` в заголовке записи.

`[u8; N]` работает как fallback — самый простой вариант ключа:

```rust,ignore
let tree = ConstTree::<[u8; 16], 64>::open("data/posts", Config::balanced().build())?;
```

Для составных ключей — любой `repr(C)` zerocopy struct:

```rust,ignore
#[derive(FromBytes, IntoBytes, Immutable, Copy, Clone)]
#[repr(C)]
struct PostKey {
    user_id: [u8; 8],  // big-endian u64
    post_id: [u8; 8],  // big-endian u64
}

let tree = VarTree::<PostKey>::open("data/posts", Config::large_values().build())?;
```

Для `ConstMap`/`VarMap` ключ дополнительно требует `+ Send + Sync + Hash + Eq`.

### Значение

Два типа деревьев с разными стратегиями хранения значений:

```rust,ignore
/// Значения фиксированной длины — всегда inline в узле индекса
pub struct ConstTree<K, const V: usize> { .. }  // K: FromBytes + IntoBytes + Immutable + Copy + 'static

/// Значения переменной длины — ByteView + Value Cache
pub struct VarTree<K> { .. }  // K: FromBytes + IntoBytes + Immutable + Copy + 'static
```

### DiskLoc — позиция записи на диске

```rust
#[derive(Copy, Clone, Eq, PartialEq, Hash)]
#[repr(C)]
struct DiskLoc {
    offset: u32,
    len: u32,
    file_id: u16,
    shard_id: u8,
    _pad: u8,
}
// size: 12 bytes, no padding
```

---

## ByteView — контейнер для значений переменной длины

Вдохновлено `byteview` из fjall. Immutable byte slice: до 20 байт inline, больше — на куче с reference counting.

### Layout (24 байта на 64-bit)

```rust,ignore
const INLINE_SIZE: usize = 20; // на 64-bit системе

#[repr(C)]
union ByteViewRepr {
    short: ShortRepr,
    long: LongRepr,
}

#[repr(C)]
struct ShortRepr {
    len: u32,               // 4 байта
    data: [u8; INLINE_SIZE], // 20 байт
}

#[repr(C)]
struct LongRepr {
    len: u32,               // 4 байта
    prefix: [u8; 4],        // первые 4 байта значения (для быстрого сравнения)
    ptr: *const u8,         // 8 байт — указатель на heap
    ref_count: *mut AtomicU32, // 8 байт — shared ref count
}
```

### Семантика

```rust,ignore
impl ByteView {
    /// Создание из среза. <= 20 байт — inline, иначе heap alloc.
    fn new(data: &[u8]) -> Self;

    /// Clone без аллокации: инкремент ref_count для heap варианта.
    fn clone(&self) -> Self;  // O(1)

    /// Deref в &[u8].
    fn as_bytes(&self) -> &[u8];

    fn is_inline(&self) -> bool { self.len() <= INLINE_SIZE }
    fn len(&self) -> usize;
}

impl Drop for ByteView {
    fn drop(&mut self) {
        if self.is_inline() { return; }
        // decrement ref_count, free heap if last
    }
}
```

### Использование

- `VarTree::get()` возвращает `ByteView`
- Value Cache хранит `ByteView` (clone = инкремент ref_count, O(1))
- При eviction из кэша — `drop` декрементирует ref_count
- Клиент может держать `ByteView` сколько угодно — heap освободится когда последний владелец дропнет

---

## Block Cache (`quick_cache`)

### Назначение

Кэш 4096-байтных блоков для `VarTree`. Кешируется 4096-байтный aligned block (естественная единица O_DIRECT, буферы уже выровнены; на Linux `O_DIRECT` включается через `Config.direct_io`, default `false`). Отделён от индекса, чтобы:
- Можно было evict блоки без изменения индекса
- Размер кэша настраивается в байтах (e.g. 1GB)
- `ConstTree` не нуждается в кэше (значения всегда inline в узлах)

### Почему Block Cache, а не Value Cache

| Критерий | Value Cache (DiskLoc → ByteView) | **Block Cache (BlockKey → AlignedBuf)** |
|----------|----------------------------------|-----------------------------------------|
| Гранулярность | Одно значение | 4096-байтный блок |
| Пространственная локальность | Нет | **Да** — один промах кеширует ~128 записей (key=8, value=8) |
| Double-alloc | `pread → Vec → ByteView::from_vec` (2 аллокации) | **Нет** — `ByteView::new(&block[start..end])` (slice из кешированного блока) |
| O_DIRECT alignment (`Config.direct_io`) | pread читает aligned блок, выбрасывает лишнее | **Кеширует весь aligned блок** — ничего не выбрасывается |
| Большие значения | Эффективнее (кеш == размер value) | Waste (value 3KB в блоке 4KB) |

Append-only формат Bitcask обеспечивает высокую пространственную локальность: записи, сделанные рядом по времени, лежат рядом на диске. Block Cache использует это — один disk read кеширует данные для десятков ключей.

### Почему `quick_cache`

`quick_cache` реализует **S3-FIFO** — современный алгоритм (2023), который обгоняет LRU по hit rate и устойчив к scan-атакам (когда последовательный скан вытесняет горячие данные). 4-10x быстрее moka, ~21 байт overhead per entry.

### Caching policy

Не все блоки кэшируются. `Shard::read_block()` возвращает `(block, is_full_block)`:

- **Active file blocks** — НИКОГДА не кэшируются. `write_offset` включает данные в write buffer (ещё не на диске), поэтому `pread_block` может прочитать partial block с нулями в хвосте. После следующего flush те же байты заполнятся данными, но кэш будет содержать stale нули.
- **Immutable file blocks** — кэшируются только если блок полностью внутри файла: `block_offset + 4096 <= total_bytes`. Последний блок immutable файла (partial) не кэшируется.

Invalidation при compaction: `invalidate_file(file_id, total_bytes)` удаляет все блоки файла из кэша.

### Конфигурация

```rust
pub struct CacheConfig {
    /// Максимальный размер кэша в байтах. 0 = кэш отключён.
    pub max_size: u64,            // default: 0 (отключён)
    /// Примерное количество блоков (для преаллокации hash table).
    pub estimated_items: usize,   // default: 100_000
}
```

---

## Формат записи на диске

Каждая запись (entry) — это непрерывный блок байтов:

```text
┌──────────────────── Entry ─────────────────────────────────────┐
│                                                                │
│  ┌─────────┬─────┬──────────┬───────┬─────────┬───────────┐   │
│  │ GSN     │ CRC32    │ ValueLen │ Key     │ Value     │     │
│  │ 8 bytes │ 4 bytes  │ 4 bytes  │ K bytes │ V bytes   │     │
│  └─────────┴──────────┴──────────┴─────────┴───────────┘     │
│                                                               │
│  Padding: 0-7 байт до выравнивания по 8                      │
└───────────────────────────────────────────────────────────────┘
```

### Поля

| Поле | Размер | Описание |
|------|--------|----------|
| `gsn` | 8 | Global Sequence Number. Bits 63-60 = флаги (63 = tombstone, 62 = soft-delete (резерв), 61-60 = резерв), bits 59-0 = sequence |
| `crc32` | 4 | Чексумма от GSN + ValueLen + Key + Value |
| `value_len` | 4 | Длина значения в байтах (макс. ~4GB). Для tombstone = 0 |
| `key` | `size_of::<K>()` | Ключ фиксированной длины (`[u8; N]` или `repr(C)` zerocopy struct) |
| `value` | V | Значение (отсутствует для tombstone) |
| padding | 0-7 | До выравнивания по 8 байтам |

### Флаги и encoding в GSN

Отдельного поля `flags` нет. Старшие 4 бита GSN зарезервированы под флаги, остальные 60 — sequence. Бит 62 (soft-delete) и биты 61-60 зарезервированы под будущие фичи; этот билд всегда пишет их нулями, а ридеры срезают всю флаговую область при извлечении sequence (forward-compatible, без миграции):

```rust
const TOMBSTONE_BIT: u64   = 1 << 63;
const SOFT_DELETE_BIT: u64 = 1 << 62; // резерв под soft-delete
const FLAGS_MASK: u64      = 0xF000_0000_0000_0000; // биты 63-60
const SEQUENCE_MASK: u64   = !FLAGS_MASK;           // биты 59-0

fn is_tombstone(gsn: u64) -> bool { gsn & TOMBSTONE_BIT != 0 }
fn sequence(gsn: u64) -> u64     { gsn & SEQUENCE_MASK }
fn make_tombstone(gsn: u64) -> u64 { gsn | TOMBSTONE_BIT }
```

60 бит на sequence = 1.15 * 10^18 операций. Tombstone сохраняет порядковый номер — необходимо для репликации и compaction.

Тип значения (fixed/variable) — свойство дерева, хранится в `db.meta`. Для `ConstTree` поле `value_len` в header всегда равно `V` (для валидации при recovery).

Сжатие на уровне отдельных записей не применяется. Если потребуется — реализуется как block compression в immutable файлах на этапе compaction (см. раздел "Сжатие").

### Header (zerocopy)

```rust
#[derive(zerocopy::FromBytes, zerocopy::IntoBytes, zerocopy::KnownLayout)]
#[repr(C)]
struct EntryHeader {
    gsn: u64,         // bit 63 = tombstone, bits 0-62 = sequence number
    crc32: u32,
    value_len: u32,
}
```

Размер header: **16 байт**, alignment **8 байт**. Натуральное выравнивание, без `packed`.
Полный размер записи: `16 + size_of::<K>() + value_len + padding`.

---

## Read Path

### ConstTree — всегда из памяти

```text
get(key)
  │
  ▼
SkipList.get(key, guard) → &ConstNode
  │
  ▼
return node.value  // [u8; V], всегда inline, zero disk I/O
```

`ConstTree` **никогда не читает с диска** при обычных операциях. Все значения хранятся inline в узлах SkipList. Диск используется только для persistence и recovery.

### VarTree — трёхуровневый read path

```text
get(key)
  │
  ▼
SkipList.get(key, guard) → &VarNode { disk }
  │
  ▼
block_key = (disk.file_id, disk.offset & !4095)
  │
  ▼
1. Block Cache (lock-free)
cache.get(block_key) ──── hit? ──→ extract value → ByteView::new(...)
  │
  miss
  │
  ▼
2. Write Buffer (brief shard lock)
shard.lock() → write_buf.read(offset, len) ──── hit? ──→ ByteView::new(bytes)
  │
  miss (данные уже flushed на диск)
  │
  ▼
3. Disk Read + cache
pread_block(fd, block_offset) → if is_full_block { cache.insert }
  │
  ▼
extract value → ByteView::new(&block[start..start+len])
```

**Ключевые решения:**
- Кешируем 4096-байтные блоки — буферы выровнены под O_DIRECT (Linux: opt-in через `Config.direct_io`)
- Step 1 (cache hit): `Arc::clone()` = O(1), extract value как slice → `ByteView::new()` (inline для ≤20 байт)
- Step 2 (write buffer): данные ещё не на диске — brief shard lock, memcpy из буфера
- Step 3 (cache miss): один `pread` читает весь блок, кеширует (если полный), извлекает value
- Пространственная локальность: один miss кеширует данные для десятков соседних записей
- Value spanning: если value пересекает границу блока — читаем два блока, склеиваем
- `O_DIRECT` — обход page cache ОС на Linux (`Config.direct_io`, default `false`; probe + fallback если FS не поддерживает); на macOS — `F_NOCACHE`. Bulk-пути (recovery, compaction) остаются buffered + `posix_fadvise`

```rust,ignore
impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static> VarTree<K> {
    pub fn get(&self, key: &K) -> Option<ByteView> {
        let guard = self.collector.enter();
        let node = self.index.get(key, &guard)?;
        let disk = *node.load_disk();

        let block_offset = disk.offset & !4095;
        let start = (disk.offset & 4095) as usize;
        let len = disk.len as usize;

        // Получить блок из кэша или прочитать с диска
        let block = self.get_or_read_block(disk.shard_id, disk.file_id, block_offset)?;

        // Извлечь value из блока
        if start + len <= 4096 {
            Some(ByteView::new(&block[start..start + len]))
        } else {
            // Spanning: value пересекает границу блока
            let next = self.get_or_read_block(disk.shard_id, disk.file_id, block_offset + 4096)?;
            let mut combined = Vec::with_capacity(len);
            combined.extend_from_slice(&block[start..]);
            combined.extend_from_slice(&next[..len - (4096 - start)]);
            Some(ByteView::from_vec(combined))
        }
    }
}
```

---

## Write Path

```text
put(key, value) вызывается из любого потока
         │
         ▼
  shard_id = xxh3(key) % N
         │
         ▼
  ┌──────────────────┐
  │ shard.lock()     │  Mutex — захватываем конкретный шард
  └────────┬─────────┘
           │
  ┌────────▼─────────────────┐
  │ gsn = GLOBAL_SEQ.inc()   │  атомарный инкремент
  └────────┬─────────────────┘
           │
  ┌────────▼─────────────────┐
  │ serialize entry           │  Header + Key + Value + Padding
  │ copy to ring buffer       │  memcpy — наносекунды
  │ offset = buffer.position  │
  └────────┬─────────────────┘
           │
  ┌────────▼───────────────────────────────┐
  │ update SkipList Index                   │
  │   ConstTree: memcpy value into node     │
  │   VarTree: update node.disk = new loc   │
  └────────┬───────────────────────────────┘
           │
  ┌────────▼─────────────────┐
  │ shard.unlock()            │  клиент может читать новое значение
  └────────┬─────────────────┘
           │
           ▼
  (данные в WriteBuffer, ещё не на диске)
```

**Реализация:** `WriteBuffer` в `shard.rs` — `AlignedBuf` (4096-aligned, default 1MB) per shard. `append_entry()` копирует serialized entry в буфер (memcpy). DiskLoc предвычисляется из `base_offset + buffer_position`. VarTree чтение проверяет write buffer при Block Cache miss (для unflushed данных).

**Flush:**

```text
Условие: buffer полон OR tree.flush_buffers() OR tree.close() OR rotation
         │
         ▼
  ┌───────────────────────────┐
  │ Linux: uring.write_at()   │  весь буфер одним вызовом
  │ macOS: pwrite_at()        │
  │ (опционально fsync)       │
  └───────────────────────────┘
```

**Клиент не ждёт записи на диск.** Latency определяется только memcpy в буфер + обновление индекса (~100ns). При аварии теряются данные из незаписанного буфера (до `write_buffer_size` на шард). Для контроля durability: `tree.flush_buffers()` с `Compactor::start()` в качестве периодического таймера.

---

## CAS (Compare-And-Swap)

```rust,ignore
impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static> VarTree<K> {
    pub fn cas(
        &self,
        key: &K,
        expected: &[u8],
        new_value: &[u8],
    ) -> DbResult<()> {
        let shard_id = self.shard_for(key);
        let shard = &self.shards[shard_id];

        let _lock = shard.write_lock.lock(); // блокируем только этот шард

        // 1. Читаем текущее значение
        let current = self.get_under_lock(key, shard)?;

        // 2. Сравниваем
        match current {
            Some(val) if val.as_bytes() == expected => { /* OK, продолжаем */ }
            Some(_) => return Err(DbError::CasMismatch),
            None => return Err(DbError::KeyNotFound),
        }

        // 3. Пишем новое значение (под тем же lock)
        self.put_under_lock(key, new_value, shard)?;

        Ok(())
    }
}
```

CAS безопасен, потому что все операции над одним ключом маршрутизируются в один шард, а запись в шард сериализована через `Mutex`.

### Read/mutate error contract (Var collections)

For the disk-backed `VarTree`/`VarMap`/`VarTypedTree`/`VarTypedMap` families, a key
present in the index but whose value cannot be produced (I/O fault, decryption
fault, codec decode fault) is **never** reported as absent or mismatched on a
method that can carry an error:

- `get_or_err`, `cas`, `compare_delete`, `update`, `fetch_update` (and the
  `atomic()` shard handles' `get_or_err`) fail-fast with the real error.
- Lossy `Option` reads (`get`, `first`, `last`) stay lossy: `first()`/`last()`
  **skip** an unproducible boundary entry, matching `iter()`.
- Strict `try_get`/`try_first`/`try_last` return `DbResult<Option<…>>`, surfacing
  the boundary error instead of skipping.
- Note: `cas`/`compare_delete` compare the current value as **raw bytes** (the
  typed wrappers encode `expected` and delegate), so a byte-readable but
  codec-undecodable value yields `CasMismatch`/match, not a decode error. Typed
  `update`/`fetch_update` decode the current value and so propagate
  `CorruptedEntry`.

---

## Шардирование

### Маршрутизация

По умолчанию — хеш полного ключа. С prefix-based sharding — хеш первых N бит:

```rust,ignore
fn shard_for(&self, key: &K) -> usize {
    let key_bytes = key.as_bytes();
    let key_bits = size_of::<K>() * 8;

    if self.shard_prefix_bits == 0 || self.shard_prefix_bits >= key_bits {
        let hash = xxhash_rust::xxh3::xxh3_64(key_bytes);
        return (hash as usize) % self.shard_count;
    }

    let full_bytes = self.shard_prefix_bits / 8;
    let extra_bits = self.shard_prefix_bits % 8;

    let hash = if extra_bits == 0 {
        xxhash_rust::xxh3::xxh3_64(&key_bytes[..full_bytes])
    } else {
        let mut buf = vec![0u8; full_bytes + 1];
        buf[..full_bytes].copy_from_slice(&key_bytes[..full_bytes]);
        let mask = !((1u8 << (8 - extra_bits)) - 1);
        buf[full_bytes] = key_bytes[full_bytes] & mask;
        xxhash_rust::xxh3::xxh3_64(&buf)
    };

    (hash as usize) % self.shard_count
}
```

`shard_prefix_bits` задаётся в `Config` (по умолчанию 0 = полный ключ). Работает с `key.as_bytes()` срезом. Для составных ключей (например `PostKey { user_id, post_id }`) задать 64 — все посты одного пользователя в одном шарде.

### Параметры

- Количество шардов: `num_cpus * 2` по умолчанию (конфигурируемо)
- Фиксируется при создании базы (изменение требует пересоздания)
- Хранится в метаданных базы
- `shard_prefix_bits`: задаётся в `Config`, не влияет на recovery/compaction

### Структура шарда

```rust,ignore
struct Shard {
    id: u8,
    write_lock: parking_lot::Mutex<()>,
    active_file: ActiveFile,
    immutable_files: Vec<Arc<ImmutableFile>>,
    write_buffer: RingBuffer,
    dead_bytes: HashMap<u32, u64>,  // file_id -> dead bytes (для compaction)
}

struct ActiveFile {
    fd: OwnedFd,
    file_id: u32,
    write_offset: u64,
    size_limit: u64,  // при достижении — ротация
}

struct ImmutableFile {
    fd: OwnedFd,
    file_id: u32,
    total_bytes: u64,
    bloom: BloomFilter,  // для быстрого negative lookup
}
```

---

## Файловая структура на диске

```text
{db_path}/
├── db.meta                       # метаданные (16 bytes, version 2, magic "ARMD"): backend, shard_count, shard_prefix_bits, flags
├── shard_00/
│   ├── 000001.data               # immutable data file
│   ├── 000001.hint               # hint file (опционально, если hints=true)
│   ├── 000002.data               # immutable data file
│   ├── 000002.hint
│   └── 000003.data               # active file (текущий для записи)
├── shard_01/
│   ├── ...
└── shard_NN/
    ├── ...
```

### db.meta — проверка иммутабельных параметров

Формат: 4 байта, фиксированный размер.

```text
[0] shard_count        (u8, 1..=255)
[1] shard_prefix_bits  (u8)
[2] flags              (u8, bit 0 = encrypted)
[3] reserved           (0)
```

Создаётся при первом открытии базы. При повторном открытии — валидация:
- `shard_count` из конфига совпадает с сохранённым
- `shard_prefix_bits` из конфига совпадает с сохранённым
- Наличие/отсутствие `encryption_key` совпадает с флагом

При несовпадении — `DbError::FormatMismatch`. Размер файла строго 4 байта, иначе ошибка.

### Ротация файлов

Когда active file достигает `max_file_size` (по умолчанию 256MB):
1. Закрыть active file
2. Переименовать в immutable
3. Если `hints=true` — записать hint file для закрытого файла
4. Открыть новый active file с инкрементированным `file_id`

---

## Hint Files — быстрый старт

Hint file содержит только метаданные записей без значений:

```text
┌──────────────── Hint Entry ────────────────┐
│ GSN (8) │ Key (size_of::<K>()) │ Offset (8) │ Len (4)  │
└────────────────────────────────────────────┘
```

### Config: `hints: bool` (tunable, default: true)

Управляет генерацией и использованием hint файлов:
- `true` — hint файлы генерируются при ротации, close, drop. При recovery используются для быстрого старта.
- `false` — hint файлы не генерируются и не читаются. Recovery всегда через полный скан data файлов.

Рекомендации:
- **VarTree/VarMap**: `hints: true` — recovery без hints требует чтения всех значений с диска.
- **ConstTree/TypedTree/ZeroTree и Map-аналоги**: `hints: false` допустим — значения малы или уже в памяти, полный скан быстр.

Параметр tunable — можно менять между запусками без миграции. Старые hint файлы при `hints: false` просто игнорируются.

### Recovery (при старте)

```text
1. Прочитать db.meta → валидировать shard_count, shard_prefix_bits, encryption
2. Для каждого шарда параллельно (std::thread::scope):
   a. Найти все .data файлы, отсортировать по file_id
   b. Если hints=true — найти .hint файлы
   c. Для файлов с .hint — загрузить hint file в Index (SkipList)
   d. Для файлов без .hint (или если hints=false) — полный скан записей
   e. При скане: проверить CRC32, вставить в Index
   f. Битые записи в конце файла — обрезать (truncate)
3. Для ConstTree: прочитать значения с диска и вставить inline в узлы
4. Index готов к работе
```

Параллельное восстановление — каждый шард независим.

---

## Compaction

### Триггер

Для каждого immutable файла отслеживается `dead_bytes`. Когда `dead_bytes / total_bytes > 0.3` (30% мусора) — файл кандидат на compaction.

При каждом обновлении/удалении ключа:
```rust,ignore
// старая запись была в файле old_file_id
shard.dead_bytes[old_file_id] += old_entry_size;
```

### Алгоритм

```text
Фоновый поток (один на базу или один на N шардов):

1. ВЫБОР: найти шард с файлами, где garbage ratio > threshold
2. ВЫБОР ФАЙЛОВ: взять 2-4 immutable файла с наибольшим garbage ratio
3. СОЗДАНИЕ: открыть новый файл (merge_{file_id}.data.tmp)
4. ИТЕРАЦИЯ: для каждой записи в выбранных файлах:
   a. Проверить в SkipList Index: запись всё ещё актуальна?
      - Актуальна = Index указывает на этот файл и offset
      - Устаревшая = Index указывает на другой файл/offset → пропустить
   b. Если актуальна → записать в новый файл
   c. Запомнить новый offset
5. ПЕРЕКЛЮЧЕНИЕ: для каждого перенесённого ключа:
   - CAS в Index: (old_file, old_offset) → (new_file, new_offset)
   - Если CAS fail — ключ был обновлён во время компакции, помечаем dead в новом файле
6. ГЕНЕРАЦИЯ: hint file строится из записей где CAS успешен (live entries).
   Мёртвые записи (удалённые/перезаписанные во время компакции) исключаются.
   Это предотвращает воскрешение удалённых ключей при recovery.
7. ОЧИСТКА: удалить старые файлы (когда Arc<ImmutableFile> refcount = 0)
8. ПЕРЕИМЕНОВАНИЕ: merge_{file_id}.data.tmp → {file_id}.data
```

### Безопасность

- Compaction не блокирует ни чтение, ни запись
- Старые файлы удаляются только когда нет активных читателей (`Arc` refcount)
- Если процесс упал во время compaction — `.tmp` файлы удаляются при следующем старте

---

## Сжатие (Compression)

### Per-entry compression — нет

Сжатие отдельных записей **не используется**. Причины:
- Плохой compression ratio на маленьких значениях (< 1KB)
- CPU overhead на каждый read/write
- Усложняет inline-оптимизации

### Per-file compression — нет

Сжатие целого файла **невозможно** в текущей архитектуре:
- Random access `pread(offset)` требует несжатых данных
- Append-only запись несовместима с потоковым сжатием (нужно пересжать весь файл)

### Block compression в immutable файлах — future

Если сжатие понадобится, реализуется **поблочное** (4KB-64KB блоки) в immutable файлах при compaction:
- Active file всегда несжатый (append-only)
- При compaction: записи группируются в блоки, каждый блок сжимается отдельно (zstd)
- Random access: прочитать блок целиком, распаковать, извлечь запись
- Addressing меняется: `DiskLoc { block_offset, entry_offset_in_block }`
- Это не ломает текущую архитектуру, но усложняет read path

**Решение:** отложить до реальной необходимости. NVMe достаточно быстры, чтобы не сжимать.

---

## Итераторы и Reversed Ordering

### Один тип итератора на дерево

Каждое дерево предоставляет один тип итератора (`ConstIter`, `VarIter`), который возвращается из `iter()`, `range()` и `prefix_iter()`. Итератор реализует `Iterator` + `DoubleEndedIterator` и владеет `seize::LocalGuard` — гарантирует корректность при concurrent доступе.

```rust,ignore
// Все три метода возвращают один тип:
let all = tree.iter();                        // все записи
let range = tree.range(&start, &end);         // [start, end) по натуральному порядку ключей
let prefix = tree.prefix_iter(&user_id);      // по префиксу

// DoubleEndedIterator — обратная итерация и .rev()
let last_20 = tree.prefix_iter(&user_id).rev().take(20);
let oldest = tree.iter().next_back();
```

Для `VarTree` каждый `next()` / `next_back()` может читать с диска (через Block Cache). Записи с I/O ошибками пропускаются.

### Обратная итерация (DoubleEndedIterator)

`next_back()` реализован через reverse search от head — O(log N) per вызов, без `prev` pointer'ов в узлах SkipList. Структура узлов не изменена, 0 extra memory.

При `reversed=true` основной кейс (newest-first) — forward iteration через `next()`, O(1) per item. `next_back()` нужен редко (oldest-first в reversed tree).

### Consistency: weakly-consistent (не snapshot)

Итераторы **не делают snapshot**. Семантика — weakly-consistent (как в `java.util.concurrent` или `crossbeam-skiplist`):

- **Concurrent insert** — если `next()` ещё не прошёл эту позицию, новый узел будет виден. Если уже прошёл — нет.
- **Concurrent update (put на существующий ключ)** — итератор может увидеть как старое, так и новое значение (RCU swap).
- **Concurrent delete** — marked узлы пропускаются. Если `next()` уже вернул узел до delete — он уже отдан пользователю.
- **Memory safety** — `seize::LocalGuard` гарантирует что узлы не будут освобождены пока итератор жив. Use-after-free невозможен.

### Reversed ordering (`Config.reversed`)

Параметр `reversed: bool` в `Config` включает reverse comparator в SkipList. Forward iteration (`next()`) возвращает ключи по **убыванию** — "newest first".

```rust,ignore
let config = Config::balanced().build(); // reversed: true by default
let tree = VarTree::<[u8; 16]>::open("data/posts", config)?;

// prefix_iter возвращает последние посты пользователя первыми
let latest_20 = tree.prefix_iter(&user_id).take(20);
```

**Свойства:**
- Ключи на диске хранятся **как есть** (без трансформации)
- `reversed` можно менять между запусками без миграции — влияет только на in-memory index
- Reverse comparator: один `if` per comparison, ~0ns после branch prediction warmup
- Для пагинации "последние N записей" — просто `prefix_iter().take(N)`, без обратной итерации

**Внутренняя реализация:**
- `SkipList::key_cmp()` — `if reversed { b.cmp(a) } else { a.cmp(b) }`
- `prefix_bounds()` — вычисляет search key и end `Bound<K>` с учётом `reversed`
- `range()` — при `reversed` меняет местами start/end для корректного обхода
- `find_last_lt(key)` — O(log N) reverse search для `next_back()`
- `find_last()` — O(log N) поиск последнего узла для back cursor в `iter()`

---

## ~~Bloom Filters~~ (не применимо)

В Bitcask архитектуре полный in-memory index (SkipList) содержит все ключи. При `get()` для несуществующего ключа `index.get()` возвращает None мгновенно без disk I/O. Bloom filters были бы полезны в LSM-tree архитектуре или при partial index, но в текущей реализации не нужны.

---

## Репликация (Log Shipping) — feature `replication`

### Архитектура

```text
Leader                                         Follower
┌──────────────────────┐                      ┌──────────────────┐
│ Db (read-write)       │                      │ Db (read-only)    │
│                       │                      │                   │
│ append_entry()        │                      │ ReplicationClient │
│  └ write_buf.append() │                      │  └ append_raw     │
│  └ spsc.push(entry)  ─┼── per-shard SPSC ──▶│  └ apply to index │
│                       │    (streaming mode)  │                   │
│ ReplicationServer     │                      │                   │
│  └ ShardLogReader    ─┼── per-shard TCP ────▶│  (catch-up mode)  │
│    (file scan)        │                      │                   │
│                       │                      │                   │
│ CompactionGuard       │                      │ Independent       │
│ (protect unread)      │                      │ compaction        │
└──────────────────────┘                      └──────────────────┘
```

- **Leader**: принимает записи, стримит на followers
- **Follower**: обычный `Tree::open()` с теми же параметрами, записи из репликации
- **Per-shard**: каждый шард — независимый поток репликации (один TCP + один SPSC канал)

### Dual-mode streaming

| Режим | Источник | Когда | Latency |
|-------|----------|-------|---------|
| **Streaming** | SPSC ring buffer (`rtrb`) | Нормальная работа | ~10µs |
| **Catch-up** | `ShardLogReader` (file scan) | Reconnect, overflow, initial sync | Зависит от I/O |

Write-path hook в `append_entry()` — push `Vec<u8>` (moved, zero extra alloc) + `key_len` в lock-free SPSC канал (`rtrb`, capacity 8192). Overhead: ~10ns per write.

При переполнении SPSC (follower отстал): entry всё равно на диске → catch-up подберёт через `ShardLogReader`. Переключение обратно в streaming после наверстывания.

### Протокол

Binary framing: `[type:u8][len:u32 LE][payload]`

| Message | Direction | Payload |
|---------|-----------|---------|
| SyncRequest | F→L | shard_id, from_gsn, key_lens |
| ShardInfo | L→F | shard_count, max_file_size |
| EntryBatch | L→F | shard_id, entries:[entry_len + key_len + gsn + raw_data] |
| CaughtUp | L→F | shard_id, leader_gsn |
| Ack | F→L | shard_id, last_gsn |
| Heartbeat | both | — |
| Error | both | message |

`key_len` на wire → follower O(1) routing к дереву (без CRC-guessing).

### Routing записей к деревьям

Entries от разных деревьев интерливятся в одних shard файлах. Без `tree_id` в entry header — CRC32 служит дискриминатором.

**Streaming mode**: `key_len` известен из SPSC entry → O(1) lookup в `ReplicationRegistry.by_key_len`.

**Catch-up mode**: `ShardLogReader` пробует каждый K из `key_lens`:
1. Читает header (16B) → `value_len`
2. Пробует `last_matched_k` первым (cache hit ~90% — entries кластеризуются)
3. При miss: для каждого K — `entry_size(K, value_len)`, read, CRC check
4. Read-ahead buffer 64KB для минимизации syscalls

`ReplicationTarget` trait на каждом дереве:
- `apply_entry(key, value)` — streaming mode, O(1)
- `try_apply_entry(raw_bytes)` — catch-up mode, CRC match

### Compaction coordination

`CompactionGuard` trait — leader отслеживает `min_replicated_gsn` per shard (обновляется из Ack сообщений). `compact_shard_guarded()` пропускает файлы где max_gsn ≥ min_replicated_gsn. Max GSN определяется из hint files.

Unix file semantics: если follower читает файл через открытый fd, а leader удаляет (compaction), inode живёт пока fd открыт.

### Cursor

`ReplicationCursor` — per-shard, персистентный (`shard_NNN/repl.cursor`, 24 байта). Содержит `last_gsn`, `file_id`, `file_offset`. Сохраняется каждые 1000 entries. При рестарте follower продолжает с последнего cursor.

### GLOBAL_GSN на follower

После каждого apply: `GLOBAL_GSN.fetch_max(seq + 1, Relaxed)`. При promotion follower → leader новые записи получают корректные GSN. Никакого специального API для promotion не нужно.

### Инварианты

- `shard_count` follower == leader (валидируется через ShardInfo)
- Деревья одинаковые (те же K, V) — CRC routing гарантирует корректность
- Entries от неизвестных деревьев записываются на диск, не индексируются (recovery подберёт при создании дерева)
- CRC32 false positive: ~1/2^32 per entry — приемлемый риск
- Без WAL: потеря unflushed записей при crash leader = потеря на follower

### Overhead

| | Replication ON | Replication OFF |
|---|---|---|
| Leader write | +10ns (SPSC push) | 0ns |
| Follower apply | ~300-500ns/entry (index update bottleneck) | — |
| Network | ~1-5µs/entry (batched) | — |
| Sustained rate | ~500K entries/sec/shard | — |

### Реализация

| Файл | Назначение |
|------|-----------|
| `replication/mod.rs` | `ReplicationEntry`, `ReplicationRegistry` (dual-mode apply) |
| `replication/protocol.rs` | Wire format, frame I/O, message types |
| `replication/server.rs` | `ReplicationServer` (accept, dual-mode stream, CompactionGuard) |
| `replication/client.rs` | `ReplicationClient` (per-shard threads, reconnect, cursor) |
| `replication/cursor.rs` | `ReplicationCursor` (persist/load) |
| `replication/log_reader.rs` | `ShardLogReader` (catch-up, CRC boundary detection) |
| `replication/apply.rs` | `ReplicationTarget` trait |

> Раздел выше описывает репликацию **только для Bitcask backend**. FixedStore имеет отдельный стек — см. ниже.

### FixedStore репликация — `fixed_replication/`

FixedStore backend использует отдельный, независимый стек репликации (`armdb/src/fixed_replication/`). Механизм **event-based**: каждое слот-обновление публикуется как `FixedReplicationEvent` вместо GSN log entry. Протокол, порты и lifecycle не пересекаются с Bitcask-репликацией.

| Файл | Назначение |
|------|-----------|
| `fixed_replication/mod.rs` | `FixedReplicationTarget`, pub exports |
| `fixed_replication/server.rs` | `FixedReplicationServer` |
| `fixed_replication/client.rs` | `FixedReplicationClient` |
| `fixed_replication/protocol.rs` | Wire format |
| `fixed_replication/apply.rs` | `FixedReplicationTarget` trait |
| `fixed_replication/event.rs` | `FixedReplicationEvent` |
| `fixed_replication/engine_access.rs` | `ArcEngine`, `FixedEngineAccess` |
| `fixed_replication/cursor.rs` | `FixedReplicationCursor` |

Ключевые отличия от Bitcask-репликации:

| | Bitcask (`replication/`) | FixedStore (`fixed_replication/`) |
|--|--|--|
| Единица репликации | GSN log entry | `FixedReplicationEvent` (slot update) |
| Catch-up | `ShardLogReader` (file scan) | replay событий из cursor |
| CompactionGuard | нужен | не нужен (нет compaction) |
| Коллекции | VarTree, ConstTree, … (Bitcask) | ZeroTree, ConstTree, … (FixedStore backend) |

---

## io_uring конфигурация

> С #47 дефолтный Bitcask I/O backend — `Pwrite` (блокирующий `pwrite`).
> io_uring ниже — **opt-in** на двух уровнях: compile-time (Cargo-фича `io-uring`,
> off by default — без неё `io/uring.rs` не компилируется) и рантайм
> (`Config::io_backend = IoBackend::Uring { sqpoll_idle_ms }`). Без фичи или вне
> Linux `Uring` падает в `Pwrite` с однократным `warn!`. Причина дефолта — CPU-шум
> выделенных SQPOLL-поллеров (по одному на шард): см. `docs/research/sqpoll-noise.md`.

### Инициализация

```rust,ignore
let ring = IoUring::builder()
    .setup_sqpoll(2000)           // kernel polling, idle timeout 2s
    .setup_sqpoll_cpu(cpu_id)     // привязка к ядру
    .build(256)?;                 // 256 entries в SQ

// Регистрация буферов (zero-copy writes)
let buffers: Vec<Vec<u8>> = (0..64)
    .map(|_| vec![0u8; BUFFER_SIZE])
    .collect();
ring.register_buffers(&buffers)?;

// Регистрация файлов (избежать fd lookup)
let fds: Vec<RawFd> = shard_files.iter().map(|f| f.as_raw_fd()).collect();
ring.register_files(&fds)?;
```

### Использование

- **Write path**: batch submit нескольких write операций из ring buffer
- **Compaction**: параллельное чтение старых файлов + запись нового
- **Read path**: НЕ используем io_uring, используем `pread` (меньше overhead для единичных операций)

---

## Публичное API

Каждое дерево — самостоятельная точка входа. Для управления несколькими коллекциями есть `Db` struct (feature `armour`, `src/armour/db.rs`) — оркестратор с persistent-метаданными, sequence-генерацией и фоновыми воркерами (compaction, flush); обе модели сосуществуют.
Одно дерево = одна директория на диске.

```rust,ignore
/// Конфигурация базы данных
pub struct Config {
    pub path: PathBuf,
    pub shard_count: usize,        // default: num_cpus * 2
    pub max_file_size: u64,        // default: 256MB
    pub compaction_threshold: f64,  // default: 0.3 (30%)
    pub enable_fsync: bool,        // default: false
    pub write_buffer_size: usize,  // default: 1MB
    pub cache: CacheConfig,        // настройки Block Cache
    pub shard_prefix_bits: usize,  // default: 0 (hash full key via key.as_bytes())
    pub reversed: bool,            // default: false (descending iteration when true)
    pub direct_io: bool,           // default: false (O_DIRECT on Linux hot path; no effect off Linux)
}

pub struct CacheConfig {
    /// Максимальный размер кэша в байтах. 0 = отключён.
    pub max_size: u64,             // default: 0
    /// Примерное количество блоков (для преаллокации hash table).
    pub estimated_items: usize,    // default: 100_000
}

/// Дерево с фиксированной длиной значений — всегда в памяти
/// K: FromBytes + IntoBytes + Immutable + Copy + 'static
pub struct ConstTree<K, const V: usize, H: WriteHook<K> = NoHook> { .. }

impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static, const V: usize> ConstTree<K, V> {
    pub fn open(config: Config) -> DbResult<Self>;
}

impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static, const V: usize, H: WriteHook<K>> ConstTree<K, V, H> {
    pub fn open_hooked(config: Config, hook: H) -> DbResult<Self>;
    pub fn close(self) -> DbResult<()>;     // hint files + flush + fsync
    pub fn flush_buffers(&self) -> DbResult<()>;
    pub fn config(&self) -> &Config;

    pub fn get(&self, key: &K) -> Option<[u8; V]>;
    pub fn put(&self, key: &K, value: &[u8; V]) -> DbResult<Option<[u8; V]>>;
    pub fn delete(&self, key: &K) -> DbResult<Option<[u8; V]>>;
    pub fn cas(&self, key: &K, expected: &[u8; V], new: &[u8; V]) -> DbResult<()>;
    pub fn contains(&self, key: &K) -> bool;
    pub fn iter(&self) -> ConstIter<K, V>;
    pub fn range(&self, start: &K, end: &K) -> ConstIter<K, V>;
    pub fn prefix_iter(&self, prefix: &[u8]) -> ConstIter<K, V>;
    pub fn len(&self) -> usize;
}

/// Итератор по записям ConstTree. impl Iterator<Item = (K, [u8; V])>.
/// Возвращается методами iter(), range(), prefix_iter().
pub struct ConstIter<K, const V: usize> { .. }

/// Дерево с переменной длиной значений — ByteView + Cache
/// K: FromBytes + IntoBytes + Immutable + Copy + 'static
pub struct VarTree<K, H: WriteHook<K> = NoHook> { .. }

impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static> VarTree<K> {
    pub fn open(config: Config) -> DbResult<Self>;
}

impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static, H: WriteHook<K>> VarTree<K, H> {
    pub fn open_hooked(config: Config, hook: H) -> DbResult<Self>;
    pub fn close(self) -> DbResult<()>;
    pub fn flush_buffers(&self) -> DbResult<()>;
    pub fn config(&self) -> &Config;

    pub fn get(&self, key: &K) -> Option<ByteView>;
    pub fn put(&self, key: &K, value: &[u8]) -> DbResult<()>;
    pub fn delete(&self, key: &K) -> DbResult<bool>;
    pub fn cas(&self, key: &K, expected: &[u8], new: &[u8]) -> DbResult<()>;
    pub fn contains(&self, key: &K) -> bool;
    pub fn iter(&self) -> VarIter<K, H>;
    pub fn range(&self, start: &K, end: &K) -> VarIter<K, H>;
    pub fn prefix_iter(&self, prefix: &[u8]) -> VarIter<K, H>;
    pub fn len(&self) -> usize;
}

/// Итератор по записям VarTree. impl Iterator<Item = (K, ByteView)>.
/// Lazy — каждый next() может читать с диска (через Block Cache).
pub struct VarIter<K, H: WriteHook<K> = NoHook> { .. }

/// Immutable byte view — inline до 20 байт, иначе heap с ref counting
pub struct ByteView { .. }
```

---

## Структура модулей

```text
armdb/src/
├── lib.rs                 // pub API: exports, MigrateAction
├── engine.rs              // Engine: pub(crate), owns Config + shards + cipher
├── config.rs              // Config, CacheConfig, валидация, defaults
├── entry.rs               // EntryHeader, GSN/tombstone helpers, сериализация/десериализация
├── byte_view.rs           // ByteView: inline/heap union, ref counting, Deref
├── skiplist/
│   ├── mod.rs             // SkipList<N>, итераторы
│   ├── node.rs            // ConstNode, VarNode, tower allocation
│   └── iter.rs            // Iter (lock-free через seize::Guard, Bound-based)
├── cache.rs               // BlockCache: кэш 4096-байтных блоков (quick_cache, S3-FIFO)
├── shard.rs               // Shard, ActiveFile, ImmutableFile, WriteBuffer
├── io/
│   ├── mod.rs
│   ├── uring.rs           // UringWriter: batch write, fsync
│   ├── direct.rs          // aligned pread; O_DIRECT (Linux, Config.direct_io); F_NOCACHE (macOS); bulk + fadvise
│   └── aligned_buf.rs     // AlignedBuf: буферы выровненные по 4096
├── compaction.rs           // Compactor: фоновый поток, merge файлов
├── recovery.rs             // Recovery: загрузка hint files, скан active files
├── hint.rs                 // Hint file generation
├── hook.rs                 // WriteHook trait, NoHook
├── sync.rs                 // Mutex wrapper (parking_lot)
├── disk_loc.rs             // DiskLoc struct
├── replication/            // (feature: replication) Bitcask: Leader/Follower, GSN log shipping per shard
│   ├── mod.rs             // ReplicationEntry, ReplicationRegistry
│   ├── server.rs          // ReplicationServer
│   ├── client.rs          // ReplicationClient
│   ├── protocol.rs        // Wire format
│   ├── apply.rs           // ReplicationTarget trait
│   ├── log_reader.rs      // ShardLogReader (catch-up)
│   └── cursor.rs          // ReplicationCursor
├── fixed_replication/      // (feature: replication) FixedStore: event-based replication
│   ├── mod.rs             // FixedReplicationTarget, exports
│   ├── server.rs          // FixedReplicationServer
│   ├── client.rs          // FixedReplicationClient
│   ├── protocol.rs        // Wire format
│   ├── apply.rs           // FixedReplicationTarget trait
│   ├── event.rs           // FixedReplicationEvent
│   ├── engine_access.rs   // ArcEngine, FixedEngineAccess
│   └── cursor.rs          // FixedReplicationCursor
├── crypto.rs               // (feature: encryption) PageCipher: AES-256-GCM
├── error.rs                // DbError, DbResult
├── const_tree.rs           // ConstTree<K,V,H> — open/close, inline values (K: zerocopy bounds)
├── var_tree.rs             // VarTree<K,H> — open/close, ByteView + cache (K: zerocopy bounds)
├── const_map.rs            // ConstMap<K,V,H> — open/close, HashMap + inline values (K: + Send + Sync + Hash + Eq)
└── var_map.rs              // VarMap<K,H> — open/close, HashMap + ByteView + cache (K: + Send + Sync + Hash + Eq)
```

---

## Порядок реализации

### Фаза 1 — Основа
1. `byte_view.rs` — ByteView: inline/heap, ref counting, Deref, Drop, Clone
2. `entry.rs` — формат записи, сериализация, CRC32
3. `skiplist/node.rs` — ConstNode, VarNode
4. `skiplist/mod.rs` — concurrent SkipList на `seize`: insert, get, remove
5. `skiplist/iter.rs` — RangeIter, PrefixIter

### Фаза 2 — Storage
6. `io/aligned_buf.rs` — выровненные буферы
7. `io/direct.rs` — aligned `pread`/`pwrite`; `O_DIRECT` (Linux, `Config.direct_io`); `F_NOCACHE` (macOS)
8. `config.rs` — конфигурация, включая `direct_io` + валидация page-aligned `write_buffer_size`
9. `shard.rs` — шард: active file, write buffer, `Mutex`
10. `const_tree.rs` — ConstTree: open, get (inline), put, delete
11. `var_tree.rs` — VarTree: open, get (disk), put, delete
12. `engine.rs` — Engine: open shards, маршрутизация
13. `recovery.rs` — полный скан файлов при старте

### Фаза 3 — Производительность
14. `cache.rs` — BlockCache: S3-FIFO кэш 4096-байтных блоков
15. `io/uring.rs` — batch write через io_uring
16. `shard.rs` — ring buffer + async flush
17. CAS операции в const_tree и var_tree
18. Hint files (в `recovery.rs` + `shard.rs`)
19. Prefix-based sharding — `shard_prefix_bits` в Config, побитовая точность
20. ~~`bloom.rs`~~ — не применимо (полный in-memory index делает negative lookup мгновенным)

### Фаза 4 — Compaction
21. `compaction.rs` — фоновый merge
22. `shard.rs` — garbage ratio tracking
23. File rotation

### Фаза 5 — Репликация
24. `replication.rs` — leader/follower, log shipping
25. GSN-based sync протокол

---

## Примечания

- **Тестирование на Linux**: `io_uring` — Linux-only; на macOS fallback на `pwrite`. `O_DIRECT` включается через `Config.direct_io` (default `false`); при `true` — probe в data dir, graceful fallback на tmpfs/overlayfs. На macOS hot path использует `F_NOCACHE`. При `direct_io` или `encryption`: `write_buffer_size` ≥ 8192 и кратен 4096. Bulk-пути (recovery, compaction) — buffered + `fadvise`.
- **Выравнивание**: все write буферы и read буферы выровнены по 4096 байт. Value в записи выровнен по 8 байт.
- **Concurrency**: `parking_lot::Mutex` per shard для write path. SkipList — lock-free на `seize` для read path.
- **Сериализация значений**: armdb работает с сырыми байтами. Типизированная обёртка через `rapira`/`zerocopy` — в `armour` crate.
- **Memory reclamation**: единственная система — `seize` (Hyaline algorithm). Используется и для SkipList узлов, и для любых lock-free структур. `scc`/`sdd` не используются.

---

## Encryption at Rest (feature `encryption`)

Шифрование данных на диске за feature flag `encryption` с использованием `ring` crate.

### Принцип

Plaintext в памяти (WriteBuffer, BlockCache, индексы). Шифрование только на границе память ↔ диск.

```text
 In-Memory (plaintext)                  On-Disk (encrypted)
┌─────────────────────┐                ┌────────────────────┐
│  WriteBuffer        │──encrypt───→   │  .data files       │
│  (append entries)   │   (page-level  │  (4096B pages,     │
│                     │    AES-256-GCM)│   AES-256-GCM)     │
│  BlockCache         │◀──decrypt────  │                    │
│  (4096B plaintext)  │                │  .tags files       │
│                     │                │  (16B GCM tags     │
│  SkipList / HashMap │                │   per page)        │
│  (index, inline     │                │                    │
│   values for Const) │                │  .hint files       │
└─────────────────────┘                │  (plaintext)       │
                                       └────────────────────┘
```

### Алгоритм

- **AES-256-GCM** — authenticated encryption (AEAD)
- **Гранулярность**: 4096-байтная страница в `.data` файлах
- **Nonce**: `file_id(4 bytes LE) || page_number(8 bytes LE)` = 12 байт. Уникален: файлы append-only, file_id монотонно растёт
- **Tag**: 16 байт GCM authentication tag на страницу, хранится в отдельном `.tags` файле
- **CRC**: остаётся над plaintext (encrypt после CRC на записи, decrypt перед CRC на чтении)

### Overhead

**Без feature flag `encryption`**: zero overhead. Весь encryption код исключён компилятором (`#[cfg(feature = "encryption")]`).

**С флагом, без ключа** (`encryption_key: None`): минимальный overhead — одна проверка `Option::is_some()` на flush/read.

**С флагом и ключом** (`encryption_key: Some([u8; 32])`):

| Операция | Overhead | Детали |
|----------|----------|--------|
| Write (flush) | ~160ns/page | AES-256-GCM encrypt 4096B (~120ns с AES-NI) + tag file write (~40ns) |
| Read (block cache miss) | ~160ns/page | Tag file read (~40ns) + AES-256-GCM decrypt 4096B (~120ns) |
| Read (block cache hit) | 0 | BlockCache хранит plaintext — без decrypt |
| Read (ConstTree/ConstMap) | 0 | Значения inline в памяти — без disk I/O |
| Compaction | ~320ns/page | Decrypt old page + encrypt new page |
| Recovery | ~160ns/page | Decrypt при full scan / hint-based recovery |
| Storage | +0.4% | `.tags` файл: 16B на 4096B страницу |

Для типичного entry (key 16B + value 100B = ~132B entry): ~31 entry на страницу → ~5ns overhead per entry на write, ~5ns per entry на read (cache miss).

### Файлы на диске

```text
shard_000/
├── 000001.data      # encrypted 4096-byte pages
├── 000001.tags      # 16-byte GCM tags (один на страницу)
├── 000001.hint      # plaintext (ключи + смещения, без значений)
├── 000002.data
├── 000002.tags
└── 000002.hint
```

Hint-файлы **не шифруются** — содержат ключи и смещения, но не значения.

### Ключ

32-байтный AES-256 ключ задаётся в `Config::encryption_key`. Key derivation — ответственность вызывающего кода. Хелпер `PageCipher::key_from_env("ARMDB_KEY")` читает hex-encoded ключ из переменной окружения.

### db.meta

Файл `db.meta` (16 байт, version 2, magic "ARMD"; источник истины — `src/meta.rs`) в корне БД хранит backend, shard_count, shard_prefix_bits и flags; для Bitcask бит 0 во flags = `encrypted`. При открытии:
- Есть флаг `encrypted=true`, но нет ключа → `DbError::Config`
- Нет флага, но есть ключ → `DbError::Config`
- Первое открытие → создаётся `db.meta` с текущим состоянием

### Реализация

| Файл | Назначение |
|------|-----------|
| `crypto.rs` | `PageCipher`: encrypt_page, decrypt_page, key_from_env |
| `io/tags.rs` | `TagFile`: read/write GCM tags по page_number |
| `io/direct.rs` | `pread_value_encrypted`: decrypt при чтении |
| `shard.rs` | Encrypted flush, decrypt on read_block, tag file management |
| `hint.rs` | `generate_hint_data_dyn_encrypted`: чтение из encrypted data files |
| `recovery.rs` | `make_reader` / `encrypted_reader`: decrypt при recovery |
| `compaction.rs` | Decrypt old → encrypt new, tag file lifecycle |
| `engine.rs` | Cipher threading, db.meta validation |

---

## Migrate API

Метод `migrate(callback)` на каждом дереве — обход всех записей при старте с возможностью мутации. Применение: миграции (изменение/удаление структуры записей), построение пользовательских in-memory индексов.

### API

```rust,ignore
pub enum MigrateAction<V> {
    Keep,       // оставить без изменений
    Update(V),  // заменить значение (запись в active file)
    Delete,     // удалить (tombstone в active file)
}

// ConstTree / ConstMap — type-safe [u8; V], zero allocation
tree.migrate(|key: &K, value: &[u8; V]| -> MigrateAction<[u8; V]>)

// VarTree / VarMap — ByteView (inline ≤20 bytes, heap для больших)
tree.migrate(|key: &K, value: &[u8]| -> MigrateAction<ByteView>)
```

Возвращает `DbResult<usize>` — количество мутированных записей.

### Алгоритм

**SkipList-деревья (ConstTree, VarTree) — O(1) доп. память:**

Inline apply во время обхода level 0. Безопасно потому что:
- `current = node.tower(0).load(Acquire)` — указатель на следующий узел сохраняется ДО обработки
- `put` на существующий ключ → RCU swap данных, узел остаётся в списке
- `delete` → узел помечен (marked), итератор его пропустит
- `put`/`delete` берут свой seize guard + write_lock внутри, не конфликтуют с read-only обходом

**HashMap-деревья (ConstMap, VarMap) — O(K × N/shards) доп. память:**

Per-shard: собрать только ключи под lock, drop lock, затем для каждого ключа: `get()` → callback → `put()`/`delete()`. Значения не буферизуются.

### Потребление памяти (50M записей × 128 байт, K=16, 8 шардов)

| Дерево | Доп. память |
|--------|-------------|
| ConstTree | 0 |
| VarTree | 0 |
| ConstMap | ~100 MB (ключи одного шарда) |
| VarMap | ~100 MB (ключи одного шарда) |

### Особенности

- ConstTree/ConstMap: zero I/O для чтения значений (всё в памяти)
- VarTree/VarMap: disk I/O через block cache. `migrate()` заполняет кеш автоматически — отдельный `warmup()` не нужен
- Мутации через `put`/`delete` — RCU, dead_bytes, encryption обрабатываются автоматически
- `Fn` callback (не `FnMut`) — для мутабельного состояния использовать `Cell`/`RefCell`

---

## WriteHook — generic parameter для write notifications

Нативная поддержка secondary indexes на уровне storage engine. Hook получает key, old value, new value синхронно при каждой мутации.

### Дизайн

Generic parameter `H: WriteHook<K>` с default `NoHook` — compile-time monomorphization, zero overhead при отсутствии hook.

```rust,ignore
pub trait WriteHook<K: FromBytes + IntoBytes + Immutable + Copy + 'static>: Send + Sync {
    /// true → дерево читает old value перед записью.
    /// false → old = None всегда (нет disk read для VarTree/VarMap).
    const NEEDS_OLD_VALUE: bool;

    fn on_write(&self, key: &K, old: Option<&[u8]>, new: Option<&[u8]>);
}

pub struct NoHook; // пустая inline fn → вырезается полностью
```

### Типы с hook parameter

```text
ConstTree<K, V, H = NoHook>    ConstMap<K, V, H = NoHook>
VarTree<K, H = NoHook>         VarMap<K, H = NoHook>
```

Ассоциированные типы (`ConstShard`, `VarShard`, `ConstMapShard`, `VarMapShard`, `*PrefixIter`) также параметризованы `H`.

### Zero overhead при NoHook

- `NoHook::NEEDS_OLD_VALUE = false` → ветка чтения old value вырезается компилятором
- `NoHook::on_write()` = пустая `#[inline(always)]` fn → вырезается полностью
- Существующий код (`ConstTree<[u8; 16], 64>` = `ConstTree<[u8; 16], 64, NoHook>`) не меняется

### Hook call sites

| Метод | old value | new value | Hook |
|-------|-----------|-----------|------|
| `put(key, value)` | Если `NEEDS_OLD_VALUE` | `Some(value)` | Да |
| `insert(key, value)` | `None` (ключа не было) | `Some(value)` | Да |
| `delete(key)` | Если `NEEDS_OLD_VALUE` | `None` | Да, если ключ существовал |
| `cas(key, expected, new)` | `Some(expected)` | `Some(new)` | Да |
| `update(key, fn)` | Да (уже читается) | `Some(new)` | Да |
| `atomic(...)` | — | — | Нет (пользователь решает сам) |

Для **ConstTree/ConstMap** old value бесплатен — значения inline в памяти.
Для **VarTree/VarMap** old value = disk read, выполняется только при `H::NEEDS_OLD_VALUE == true`.

### Open methods

```text
// Без hook (H = NoHook):
ConstTree::<[u8; 16], 64>::open("data/col", Config::balanced().build())
VarTree::<[u8; 16]>::open("data/col", Config::large_values().build())
ConstMap::<[u8; 16], 64>::open("data/col", Config::balanced().build())
VarMap::<[u8; 16]>::open("data/col", Config::large_values().build())

// С hook:
ConstTree::<[u8; 16], 64, H>::open_hooked("data/col", Config::balanced().build(), hook)
VarTree::<[u8; 16], H>::open_hooked("data/col", Config::large_values().build(), hook)
ConstMap::<[u8; 16], 64, H>::open_hooked("data/col", Config::balanced().build(), hook)
VarMap::<[u8; 16], H>::open_hooked("data/col", Config::large_values().build(), hook)

// С typed key:
VarTree::<PostKey>::open("data/col", Config::large_values().build())
ConstTree::<PostKey, 64>::open("data/col", Config::balanced().build())
```

`shard_prefix_bits` задаётся в `Config`. Recovery происходит внутри `open_inner()` — recovery не знает о `H`.

### Пример: secondary index по email

```rust,ignore
// Пример с [u8; 16] ключом:
struct EmailIndex {
    by_email: Mutex<HashMap<String, [u8; 16]>>,
}

impl WriteHook<[u8; 16]> for EmailIndex {
    const NEEDS_OLD_VALUE: bool = true;

    fn on_write(&self, key: &[u8; 16], old: Option<&[u8]>, new: Option<&[u8]>) {
        let mut idx = self.by_email.lock();
        if let Some(old_val) = old {
            if let Ok(email) = std::str::from_utf8(&old_val[0..32]) {
                idx.remove(email.trim_end());
            }
        }
        if let Some(new_val) = new {
            if let Ok(email) = std::str::from_utf8(&new_val[0..32]) {
                idx.insert(email.trim_end().to_string(), *key);
            }
        }
    }
}

let index = EmailIndex { by_email: Mutex::new(HashMap::new()) };
let tree = ConstTree::<[u8; 16], 64, EmailIndex>::open_hooked(config, index)?;
```

```rust,ignore
// Пример с typed key:
#[derive(FromBytes, IntoBytes, Immutable, Copy, Clone)]
#[repr(C)]
struct UserId([u8; 16]);

struct UserActivityIndex {
    active_users: Mutex<HashSet<UserId>>,
}

impl WriteHook<UserId> for UserActivityIndex {
    const NEEDS_OLD_VALUE: bool = false;

    fn on_write(&self, key: &UserId, _old: Option<&[u8]>, new: Option<&[u8]>) {
        if new.is_some() {
            self.active_users.lock().insert(*key);
        }
    }
}

let hook = UserActivityIndex { active_users: Mutex::new(HashSet::new()) };
let tree = VarTree::<UserId, UserActivityIndex>::open_hooked(config, hook)?;
```
