# FixedStore — Design Document

Альтернативный durability backend для коллекций с фиксированным размером значений (`FixedTree<K, V>`, `FixedMap<K, V>`), оптимизированный для частых обновлений на NVMe.

Архитектура: **pwrite через page cache + batched fdatasync + fixed-slot файл с ростом по требованию**.

---

## Цели и применение

### Цели

- Предсказуемая write latency без tail spikes от compaction
- Нулевой write amplification (1x)
- Константное disk usage (нет мёртвых записей)
- Простая и быстрая recovery

### Что заменяет

`ShardInner::append_entry()` — вместо append в Bitcask log, pwrite в фиксированный слот.

### Что НЕ меняется

- Read path (inline values в SkipList/HashMap — zero I/O)
- Index structures (SkipList, HashMap)
- Shard routing (`shard_for()`)
- WriteHook API
- Public API (`put`, `get`, `delete`, `cas`)

### Применение

- Счётчики, rate limiters (частые инкременты)
- Сессии, статусы (частые обновления одного поля)
- Метрики, агрегаты
- Любые данные с фиксированным key+value размером и высоким update ratio

### Feature flag

Без feature flag в первой версии. Код добавляется напрямую. Feature flag при необходимости — позже.

---

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

### Принцип

pwrite через page cache + batched fdatasync. Файл с фиксированными слотами, прямая адресация по slot_id. Файл растёт по требованию (нет pre-allocation).

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

```
                    ┌──────────────────────────┐
                    │      Public API           │
                    │  get / put / cas / delete │
                    └────────────┬─────────────┘
                                 │
                    ┌────────────▼─────────────┐
                    │  FixedTree / FixedMap     │
                    │   index: SkipList/HashMap │
                    │   (inline values, как и   │
                    │    сейчас — zero I/O read) │
                    └────────────┬─────────────┘
                                 │ put/delete
                    ┌────────────▼─────────────┐
                    │     FixedStore Engine     │
                    │  slot_id = index lookup   │
                    │  или alloc from free list │
                    └────────────┬─────────────┘
                                 │
              hash(key) % N  маршрутизация
                                 │
        ┌───────────────────┬────┴────┬───────────────────┐
        │                   │         │                   │
  ┌─────▼──────┐     ┌─────▼──────┐  │  ┌──────────────┐
  │  Shard #0  │     │  Shard #1  │ ... │  Shard #N    │
  │  Mutex     │     │  Mutex     │     │  Mutex       │
  │  SlotFile  │     │  SlotFile  │     │  SlotFile    │
  │  Bitmap    │     │  Bitmap    │     │  Bitmap      │
  │ (in-memory)│     │ (in-memory)│     │ (in-memory)  │
  └─────┬──────┘     └─────┬──────┘     └──────┬───────┘
        │ pwrite           │ pwrite            │ pwrite
        ▼                  ▼                   ▼
  [ NVMe file ]      [ NVMe file ]       [ NVMe file ]
```

### Durability

- pwrite идёт через page cache (kernel buffer) — fast return
- fdatasync вызывается батчами: каждые N ms или N операций (настраиваемо)
- Data loss window = fdatasync interval (аналогичен текущему write buffer в Bitcask)

---

## Формат файла на диске

Один файл на шард: `shard_NNN/fixed.data`. Bitmap — sidecar файл `shard_NNN/fixed.bitmap` (только при clean shutdown).

### Layout

```
┌─────────────────────────────────────┐
│ Header (4KB, page 0)                │
│   magic: [u8; 4]     = b"FIXD"     │
│   version: u16       = 1           │
│   slot_size: u16                    │
│   slot_count: u32    (текущее)      │
│   key_len: u16       = size_of::<K>│
│   value_len: u16     = V           │
│   shard_id: u8                      │
│   clean_shutdown: u8  (0 or 1)      │
│   _reserved: [u8; 4062]            │
├─────────────────────────────────────┤
│ [Slot 0] [Slot 1] ... [Slot N-1]   │
└─────────────────────────────────────┘
```

Bitmap на диске отсутствует — хранится только в памяти. Source of truth — status байт каждого слота. При clean shutdown bitmap сбрасывается в sidecar файл `fixed.bitmap`.

### Offset арифметика

```
HEADER_SIZE = 4096
slot_offset(slot_id) = HEADER_SIZE + slot_id * slot_size
```

### Рост файла

Файл растёт на `grow_step` слотов когда bitmap заполнен:

```
1. ftruncate(fd, HEADER_SIZE + new_count * slot_size)
   → extends with zeros, новые слоты status=0x00=FREE
2. bitmap.grow(new_count)           — extend in-memory bitmap
3. pwrite header.slot_count = new_count
4. fdatasync(fd)
```

Существующие offset'ы не меняются. Per-shard Mutex сериализует grow с write.

Recovery при crash во время grow: `slot_count = (file_size - HEADER_SIZE) / slot_size`.

---

## Формат слота

```
┌──────────────────────────────────────┐
│ status: u8          (1 byte)         │  0x00=free, 0x01=occupied, 0x02=deleted
│ _pad: [u8; 3]      (3 bytes)        │  alignment до 4 bytes
│ crc32: u32          (4 bytes)        │  CRC32 over (key + value)
│ key: [u8; K]        (K bytes)        │  e.g. 8 bytes для Fuid/Id64
│ value: [u8; V]      (V bytes)        │  e.g. 32-64 bytes
│ _pad_tail: [u8; P]  (0-7 bytes)     │  padding до 8-byte boundary
└──────────────────────────────────────┘

slot_size = align_up(8 + size_of::<K>() + V, 8)
```

### Примеры размеров

| Key | Value | Header | Total slot_size |
|-----|-------|--------|-----------------|
| 8B (Fuid) | 32B | 8B | 48B |
| 8B (Fuid) | 64B | 8B | 80B |
| 16B (Uuid) | 32B | 8B | 56B |
| 16B (Uuid) | 64B | 8B | 88B |

### Почему 8-byte aligned header

- Key начинается на выровненном offset → zerocopy/bytemuck работают без `repr(packed)`
- Совместимо с alignment паттерном существующего `EntryHeader`
- `_pad_tail` гарантирует что следующий слот тоже выровнен

### Почему без GSN

- Нет append-only лога → GSN-based log shipping невозможен
- Экономия 8 байт на слот
- CRC32 достаточен для crash detection

### Почему key хранится в слоте

- Recovery: без ключа невозможно восстановить индекс
- CRC integrity: ключ включён в checksum

---

## Read/Write paths

### Read path (без изменений)

```
tree.get(&key)
  → index.get(key)         // SkipList or HashMap lookup
  → node.read_value()      // SeqLock read, inline [u8; V]
  → return Some(value)     // Zero I/O
```

### Write path: put

```
1. shard_for(key)                         ~5 ns
2. shard.lock()                           ~20-50 ns
3. index.get(key)?
   ├─ EXISTS: slot_id = node.slot_id()    ~60-400 ns
   └─ NEW:    slot_id = bitmap.alloc()    ~50-200 ns
4. serialize slot → buf                   ~20-50 ns
5. pwrite(fd, buf, slot_offset(slot_id))  ~200-500 ns (page cache)
6. index update (SeqLock inline write)    ~10-30 ns
7. hook.on_write()                        ~0 ns
8. shard.unlock()                         ~10 ns
9. maybe_sync()                           amortized ~0.1-1μs
───────────────────────────────────────
   Total: ~300-800 ns (uncontended)
```

### Write path: delete

```
1. index.get(key) → slot_id
2. pwrite status=DELETED + crc=0 в слот
3. bitmap.clear(slot_id)
4. index.remove(key)
```

### Batched fdatasync

```
trigger:
  pending_writes >= sync_batch_size      (e.g. 1000)
  OR last_sync.elapsed() >= sync_interval (e.g. 50ms)

action (ПОСЛЕ unlock шарда — не блокирует writers):
  1. fdatasync(fd)
  2. reset counters

bitmap sidecar НЕ пишется при batched fdatasync — только при clean shutdown.
При dirty recovery bitmap восстанавливается из scan слотов.
```

fdatasync после release mutex — безопасно: pwrite уже в page cache (visible), fdatasync только гарантирует durability.

---

## Concurrency

**Per-shard Mutex** — как в текущем Bitcask, без изменений.

- ConstNode SeqLock: один writer (shard mutex) + concurrent lock-free readers
- Mutex scope: serialize + pwrite + index update ≈ 300-800ns — короткий critical section
- Per-page locking — overengineering: при 32 шардах contention минимальна (~1 writer/shard)

---

## Crash safety и recovery

### Гарантии

После recovery все данные консистентны. Возможна потеря writes за последний fdatasync interval (аналогично текущему write buffer).

### Сценарии отказа

**Crash во время pwrite слота:**
- Слот частично записан → CRC mismatch → при recovery пропускается
- UPDATE: потеря ключа (старое значение перезаписано, новое битое)
- INSERT: слот не попадает в индекс (потеря одного insert)
- Для use cases FixedStore (счётчики, метрики) — допустимо

**Crash во время grow:**
- file_size > header.slot_count → recovery определяет slot_count из file_size

**Crash между pwrite и fdatasync:**
- Данные в page cache, не на диске → потеря N writes

### Recovery алгоритм

```
1. Прочитать header: slot_size, key_len, value_len, clean_shutdown
2. Определить slot_count:
   actual = (file_size - HEADER_SIZE) / slot_size
3. Если clean_shutdown == 1:
   → прочитать bitmap из fixed.bitmap sidecar
   → scan только occupied слотов (CRC verify)
4. Если clean_shutdown == 0 (dirty):
   → sequential scan всех слотов
   → для каждого: проверить status + CRC
   → валидные → insert в index + set bitmap bit
5. Очистить clean_shutdown flag в header
```

### Время recovery

| Записей | Файл (80B slots) | Dirty recovery (scan all, ~3GB/s) | Clean recovery (bitmap + verify) |
|--------:|------------------:|----------------------------------:|---------------------------------:|
| 1M | ~80 MB | ~30ms | ~10-20ms |
| 10M | ~800 MB | ~300ms | ~100-200ms |
| 100M | ~8 GB | ~3s | ~1-2s |

### Clean shutdown

```
1. fdatasync всех шардов
2. pwrite bitmap → fixed.bitmap sidecar для каждого шарда
3. fdatasync sidecar
4. set clean_shutdown = 1 в header
5. fdatasync header
```

---

## API и интеграция

### Новые типы (compile-time backend)

```rust
// FixedStore backend
pub struct FixedTree<K: Key, const V: usize, H: WriteHook<K> = NoHook> {
    index: SkipList<ConstNode<K, V, u32>>,   // u32 = slot_id (4 bytes)
    engine: FixedEngine,
    shard_prefix_bits: usize,
    reversed: bool,
    hook: H,
}

pub struct FixedMap<K: Key, const V: usize, H: WriteHook<K> = NoHook> {
    index: HashMap<K, V, u32>,
    engine: FixedEngine,
    hook: H,
}
```

Public API идентичен ConstTree/ConstMap: `put`, `get`, `delete`, `cas`, `contains`, `iter`.

### ConstNode: generic Location

```rust
pub trait Location: Copy + 'static {
    const SIZE: usize;
}

impl Location for DiskLoc { const SIZE: usize = 12; }  // Bitcask
impl Location for u32 { const SIZE: usize = 4; }        // FixedStore (slot_id)

pub struct ConstNode<K: Key, const V: usize, L: Location = DiskLoc> {
    pub key: K,
    seq: AtomicU64,
    loc: UnsafeCell<L>,            // 4 bytes для FixedStore вместо 12
    value: UnsafeCell<[u8; V]>,
    height: u8,
    tower_ptr: *const AtomicPtr<Self>,
}
```

Экономия 8 байт на запись:

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

### db.meta v2

```rust
#[repr(C)]
struct DbMeta {
    magic: [u8; 4],          // b"ARMD"
    version: u8,             // 2
    backend: u8,             // 0 = Bitcask, 1 = FixedStore
    shard_count: u8,
    shard_prefix_bits: u8,
    flags: u8,               // bit 0 = encryption
    _reserved: [u8; 7],
}
// 16 bytes total
```

---

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

```rust
pub struct FixedConfig {
    // Immutable (в db.meta)
    pub shard_count: usize,            // default: available_parallelism()
    pub shard_prefix_bits: usize,      // default: 0

    // Tunable
    pub grow_step: u32,                // slots per grow, default: 1_000_000
    pub sync_interval: Duration,       // fdatasync interval, default: 50ms
    pub sync_batch_size: u32,          // fdatasync every N writes, default: 1000
    pub enable_fsync: bool,            // sync every write, default: false
}
```

Размер файла на диске (при slot_size = 80B):

| Записей | Файл |
|--------:|-----:|
| 1M | ~80 MB |
| 10M | ~800 MB |
| 100M | ~8 GB |

---

## Сравнение с Bitcask

### Latency

| Операция | Bitcask (ConstTree) | FixedTree |
|----------|:-------------------:|:---------:|
| Read (get) | ~50-400ns | ~50-400ns |
| Write (put) | ~300-800ns | ~300-800ns |
| Write p99 | ~2-5μs | ~1-3μs |
| Write p99.9 | ~1-5ms (write buf flush) | ~10-50μs (fdatasync) |
| Delete | ~300-800ns | ~300-700ns |

### Throughput (32 threads)

| Метрика | Bitcask | FixedTree |
|---------|:-------:|:---------:|
| Reads/sec | ~50-60M | ~50-60M |
| Writes/sec | ~30-50M | ~30-50M |
| Mixed 80/20 | ~40-50M | ~40-50M |

### Disk и operational

| Метрика | Bitcask | FixedTree |
|---------|:-------:|:---------:|
| Space amplification | 1.3-2x | **1x** |
| Write amplification | Высокий | **1x** |
| Compaction | Да | **Нет** |
| Background I/O storms | Да | **Нет** |
| Recovery (10M entries) | ~1-10s | **~300ms** |
| Файлы на шард | Множество .data + .hint | **1 файл + 1 sidecar** |
| Disk usage предсказуем | Нет | **Да** |

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

| Сценарий | Выбор |
|----------|-------|
| Фиксированные значения, частые updates | **FixedTree** |
| Счётчики, rate limiters, метрики | **FixedTree** |
| Variable-size values | ConstTree (Bitcask) |
| Append-mostly workload (логи) | ConstTree (Bitcask) |
| Нужна репликация (log shipping) | ConstTree (Bitcask), FixedTree (v2 replication) |

---

## Ограничения

1. **Только фиксированный размер** — key и value const generic
2. **Лимитированная репликация v2** — передается состояние слотов, а не лог изменений (см. ниже)
3. **Потеря ключа при crash mid-update** — частично записанный слот → CRC mismatch → ключ потерян
4. **Нет ordered iteration по времени записи** — слоты не упорядочены хронологически
5. **Фрагментация bitmap** при частых insert/delete
6. **Нет encryption** в первой версии

---

## Репликация (v2)

В версии 2 добавлена поддержка репликации для FixedStore (передача состояния слотов).

### Архитектура и ограничения репликации FixedStore:
1. **Один стримящий follower на шард** — поддерживается только один активный получатель стриминга на шард. Подключение второго concurrent follower отклоняется с ошибкой `shard already streaming`.
2. **Нет multi-follower broadcast fanout** — трансляция событий идет строго по схеме 1-to-1 для каждого шарда.
3. **Восстановление при переполнении SPSC (SPSC overflow)** — в случае переполнения очереди SPSC или обрыва соединения, follower переподключается, выполняет Phase-1 catch-up (полное сканирование непустых слотов) и возвращается к Phase-2 streaming.
4. **Сходимость при dirty recovery (CRC validation)** — в случае повреждения данных лидера, Phase-1 catch-up выполняет CRC-валидацию и отправляет FREE/reset события для очистки неконсистентного состояния на стороне follower.
5. **Нет follower-side truncate** — если у follower размерность по слотам (slot count) больше, чем у лидера, усечение не производится (лишние слоты игнорируются).

---

## Ключевые файлы для реализации

| Файл | Что создаём / меняем |
|------|---------------------|
| `armdb/src/fixed_tree.rs` | **Новый.** FixedTree struct + put/get/delete/cas |
| `armdb/src/fixed_map.rs` | **Новый.** FixedMap struct |
| `armdb/src/fixed_engine.rs` | **Новый.** FixedEngine, FixedShardInner, Bitmap, slot I/O |
| `armdb/src/fixed_config.rs` | **Новый.** FixedConfig |
| `armdb/src/skiplist/node.rs` | **Изменение.** ConstNode generic по Location (L = DiskLoc / u32) |
| `armdb/src/key.rs` | **Изменение.** Location trait |
| `armdb/src/config.rs` | **Изменение.** db.meta v2 (16 bytes) |
| `armdb/src/lib.rs` | **Изменение.** re-export FixedTree/FixedMap за feature flag |

