# 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
| 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)
| Reads/sec | ~50-60M | ~50-60M |
| Writes/sec | ~30-50M | ~30-50M |
| Mixed 80/20 | ~40-50M | ~40-50M |
### Disk и operational
| 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) |
---
## Ограничения
1. **Только фиксированный размер** — key и value const generic
2. **Нет репликации** — нет append-only лога для log shipping
3. **Потеря ключа при crash mid-update** — частично записанный слот → CRC mismatch → ключ потерян
4. **Нет ordered iteration по времени записи** — слоты не упорядочены хронологически
5. **Фрагментация bitmap** при частых insert/delete
6. **Нет encryption** в первой версии
---
## Ключевые файлы для реализации
| `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 |