## Статус реализации

| # | Идея | Статус |
|---|------|--------|
| 1 | Формат записи на диске | **DONE** — `entry.rs`: CRC32, tombstone flag, фиксированный ключ K байт |
| 2 | Hint Files | **DONE** — `hint.rs`: генерация при ротации/compaction, быстрый recovery |
| 3 | In-Memory Index | **DONE** — собственный concurrent SkipList на `seize` (не scc::TreeIndex) |
| 4 | io_uring | **ЧАСТИЧНО** — `io/uring.rs` для batch write (Linux), `pread` для чтения |
| 5 | Write Batching / Ring Buffer | **DONE** — `WriteBuffer` per shard, memcpy write path, `Db::flush_buffers()` |
| 6 | Compaction | **DONE** — dead_bytes tracking, threshold-based compact, batched index updates |
| 7 | Репликация / GSN | **DONE** — `GLOBAL_GSN`, Leader/Follower, SPSC + TCP log shipping, CompactionGuard. Feature `replication` |
| 8 | Структура модулей | **DONE** — реализована близко к предложению |
| 9 | Чего стоит избегать | Рекомендации, не требуют реализации |
| 10 | Block Cache | **DONE** — `cache.rs`: S3-FIFO (quick_cache), 4096-byte блоки, invalidation при compaction |
| 11 | Возврат старых данных / RMW | **DONE** — `cas()`, `update(key, fn)`, ConstTree `put`/`delete` возвращают old value |
| 12 | Prefix-based sharding | **DONE** — `shard_prefix_bits` per tree, побитовая точность, `const_tree_with()`/`var_tree_with()` |
| 13 | HashMap-based trees | **DONE** — `ConstMap<K,V>`, `VarMap<K>` — per-shard `Mutex<HashMap>`, O(1) lookup, без ordered iteration |
| 14 | Encryption at rest | **DONE** — `PageCipher` (AES-256-GCM via `ring`), per-page encryption, `.tags` files, feature `encryption` |

---

## Дополнительные идеи и предложения

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

```
┌─────────┬───────────┬──────────┬───────────┬─────────┬─────────┬─────────┐
│ CRC32   │ Timestamp │ Key      │ ValueLen  │ Flags   │ Value   │ Padding │
│ 4 bytes │ 8 bytes   │ K bytes  │ 4 bytes   │ 1 byte  │ N bytes │ 0-7 b   │
└─────────┴───────────┴──────────┴───────────┴─────────┴─────────┴─────────┘
```

- **Flags**: `TOMBSTONE`, `COMPRESSED`, тип значения (fixed/variable)
- **CRC32** считается от всего остального — для проверки целостности при recovery
- **Timestamp** — монотонный `u64` (не системное время, а atomic counter per shard) — нужен для compaction и replication
- Ключ фиксированной длины `K` — не нужно хранить `KeyLen`, экономим 4 байта на запись

### 2. Hint Files — мгновенный старт

Без WAL при рестарте придется сканировать все файлы всех шардов, чтобы восстановить индекс. Для базы в 100GB это может занять минуты.

Решение (из оригинального Bitcask):
- При ротации активного файла (или при graceful shutdown) — записываем "hint file":
  ```
  [Key][Offset][ValueLen][Timestamp] — без самих значений
  ```
- При старте загружаем hint files вместо сканирования data files
- Только последний (активный) файл сканируется полностью
- Это превращает холодный старт из минут в секунды

### 3. In-Memory Index — выбор структуры

`scc::TreeIndex` — хороший выбор для старта, но есть альтернативы:

- **ART (Adaptive Radix Tree)** — лучше для prefix search, O(k) lookup вместо O(k * log n), лучшая cache locality. Можно написать свой на `seize`.
- **SkipList** — проще реализовать lock-free (с `seize`), хороший concurrent write throughput. `crossbeam-skiplist` как референс.
- Для ключей `[u8; N]` фиксированной длины `scc::TreeIndex` подходит для старта. Оптимизировать можно позже.

Оптимизация — inline values: для маленьких значений (до 64 байт) хранить значение прямо в индексном узле, избегая disk read:

```rust
enum IndexEntry {
    Inline { data: [u8; 64], len: u8 },
    OnDisk { shard_id: u8, offset: u64, len: u32 },
}
```

### 4. io_uring — конкретные оптимизации для NVMe

- **Registered buffers** (`IORING_REGISTER_BUFFERS`) — предаллоцировать пул буферов, чтобы ядро не делало `copy_from_user` каждый раз. Для write path это существенно.
- **Registered files** (`IORING_REGISTER_FILES`) — зарегистрировать fd шардов один раз, избежать lookup в fd table ядра.
- **`O_DIRECT`** — обязательно для NVMe. Иначе page cache дублирует данные, которые уже кэшируются в RAM. Требует выравнивание буферов по 4096 (или 512 на некоторых NVMe).
- **Для чтения** — `pread` через `rustix` быстрее io_uring для единичных мелких read (меньше overhead). `io_uring` выигрывает при batch read.

```rust
// Read path: простой pread
fn get(&self, key: &[u8; K]) -> Option<Value> {
    let entry = self.index.get(key)?;
    match entry {
        IndexEntry::Inline { data, len } => Some(data[..len].into()),
        IndexEntry::OnDisk { shard_id, offset, len } => {
            let mut buf = AlignedBuf::new(len); // aligned to 4096 for O_DIRECT
            rustix::fs::pread(self.shards[shard_id].fd, &mut buf, offset)?;
            Some(buf.into())
        }
    }
}
```

### 5. Write Batching — Group Commit

```
Writer Thread (per shard):
1. Копируем данные в Ring Buffer (под Mutex — наносекунды)
2. Обновляем Index (тоже под Mutex)
3. Отпускаем Mutex — клиент может читать новое значение
4. Когда buffer полон OR прошло N микросекунд:
   → submit io_uring write для всего batch
   → опционально fsync (если нужна durability)
```

Ключевое: клиент не ждет записи на диск. Он ждет только копирования в буфер. Это даёт "memory speed" latency при чтении/записи.

### 6. Compaction — дополнения

- **Garbage ratio tracking**: для каждого immutable файла хранить счётчик `dead_bytes`. При каждом обновлении ключа, чей старый вариант лежит в файле X, инкрементировать `X.dead_bytes`. Когда `dead_bytes / total_bytes > threshold` — файл кандидат на compaction.
- ~~**Bloom filters**~~: не применимо — в Bitcask архитектуре полный in-memory index (SkipList) содержит все ключи. Negative lookup (`get` для несуществующего ключа) возвращает None мгновенно без disk I/O. Bloom filters полезны в LSM-tree или при partial index, но не здесь.
- **Compaction не должен блокировать чтение**: держать `Arc<File>` на каждый файл, компактор может удалить файл только когда все читатели отпустят `Arc`.

### 7. Репликация — Global Sequence Number

Log shipping per shard — отличная идея. Но нужен GSN для consistent snapshot:

```rust
// При записи в любой шард
let gsn = GLOBAL_SEQ.fetch_add(1, Ordering::Relaxed);
entry.header.gsn = gsn;
```

Follower может запросить: "дай мне все записи с GSN > X" — и получить консистентный срез по всем шардам. Без GSN невозможно сделать consistent backup или point-in-time recovery.

### 8. Предлагаемая структура модулей

```
armdb/src/
├── lib.rs              // публичное API: Db, Tree, Config
├── config.rs           // конфигурация (shard count, file size, etc.)
├── entry.rs            // формат записи: EntryHeader, Entry, сериализация
├── shard.rs            // Shard: active file, write buffer, mutex
├── index.rs            // обёртка над scc::TreeIndex + IndexEntry
├── io/
│   ├── mod.rs
│   ├── uring.rs        // io_uring writer (batch submit)
│   └── direct.rs       // O_DIRECT pread для чтения
├── compaction.rs       // фоновый compaction thread
├── recovery.rs         // startup: загрузка hint files + scan active
├── replication.rs      // log shipping (отдельный этап)
└── tree.rs             // VarTree<K>, ConstTree<K,V> — типизированные обёртки
```

### 9. Чего стоит избегать

- **mmap** — на NVMe с `O_DIRECT` + `io_uring` будет быстрее
- **LSM** — слишком сложно, Bitcask-подход проще и достаточен
- **Сложная concurrency для начала** — начать с `Mutex` per shard, оптимизировать до lock-free позже если будет bottleneck

### 10. Block Cache вместо Value Cache

Текущий подход: value-level кеш (`DiskLoc → ByteView`). Кешируется каждое значение отдельно.

Предложение: кешировать 4096-байтные блоки — естественную единицу чтения O_DIRECT.

#### Текущий read path (Value Cache)

```
get(key) → index → DiskLoc → cache[DiskLoc]?
  miss → pread(aligned 4096 block) → extract value → ByteView → cache
```

Aligned block, прочитанный с диска, **выбрасывается** после извлечения value.

#### Предлагаемый read path (Block Cache)

```
get(key) → index → DiskLoc → block_key = (file_id, offset / 4096)
  miss → pread(4096 block) → cache block
  hit  → extract value bytes from cached block
```

#### Преимущества

1. **Пространственная локальность** — bitcask пишет записи последовательно. Рядом лежащие ключи попадают в один блок. Закешировав блок, получаем бесплатные чтения соседних записей.

2. **Один read = много value** — при key=8, value=8, entry=32 байта → ~128 записей в одном блоке. Один промах кеширует данные для 128 ключей.

3. **Убирает double-alloc** — сейчас `pread` аллоцирует `AlignedBuf`, потом `ByteView::from_vec` аллоцирует ещё раз. С block cache: блок кешируется, value — slice из него.

4. **Естественно для O_DIRECT** — диск читает блоками 4096, кешируем блоками 4096.

#### Недостатки

1. **Waste для больших значений** — value 3KB в блоке 4KB = 75% блока занято одним value. Value cache эффективнее по памяти.

2. **Spanning** — value может пересекать границу блоков. Нужно читать/кешировать два блока и склеивать.

3. **Invalidation при compaction** — когда файл удаляется, все его блоки в кеше stale. Нужен batch remove по file_id.

4. **Доп. memcpy** — из кешированного блока нужно скопировать value bytes. Value cache отдаёт ByteView напрямую (refcount increment).

#### Вывод

Для armdb block cache **предпочтительнее**: append-only layout даёт высокую пространственную локальность, типичные value маленькие (id, status, session), O_DIRECT и так читает блоками. Value cache выигрывает только при больших value (KB+) и полностью рандомном доступе.

Реализация: `quick_cache` с ключом `(u32 file_id, u64 block_offset)` и weight = 4096 на запись. При compaction — batch invalidate по file_id.

### 11. Возврат старых данных и read-modify-write

Текущий API: `put` возвращает `DbResult<()>`, `delete` возвращает `DbResult<bool>`. Старое значение не возвращается ни в одном случае. CAS не реализован (только `CasError` в error.rs).

Проблема: для read-modify-write (инкремент счётчика, обновление статуса) нужно атомарно прочитать старое и записать новое. Без специального API — race condition между `get` и `put`.

#### Текущее состояние кода

**ConstTree::put** — при update `old_data = existing.swap_data(new_data)`. Старое значение `old_data.value: [u8; V]` **уже в руках** (inline в SkipList node), но уходит в `retire`. Вернуть его — zero cost.

**VarTree::put** — при update `old_disk = *old_disk_ptr`. Старый `DiskLoc` доступен, но сами байты — на диске. Перед `cache.remove(&old_disk)` можно попробовать `cache.get(&old_disk)`, но кеш-попадание не гарантировано. В worst case нужен disk read.

**delete** — аналогично. ConstTree: старое значение в узле (бесплатно). VarTree: нужен disk read.

#### Три подхода

##### Подход 1: Возврат старого значения из put/delete

```rust
// ConstTree — бесплатно, value в памяти:
pub fn put(&self, key: &[u8; K], value: &[u8; V]) -> DbResult<Option<[u8; V]>>
pub fn delete(&self, key: &[u8; K]) -> DbResult<Option<[u8; V]>>

// VarTree — старое значение может потребовать disk read:
pub fn put(&self, key: &[u8; K], value: &[u8]) -> DbResult<Option<ByteView>>
pub fn delete(&self, key: &[u8; K]) -> DbResult<Option<ByteView>>
```

- ConstTree: `old_data.value` доступен при swap — zero cost, zero I/O
- VarTree: DiskLoc есть, но значение нужно читать с диска. Добавлять disk read в каждый `put` дорого для случаев, когда старое значение не нужно
- Не решает read-modify-write: caller получает старое значение, но между get и следующим put может быть concurrent write

##### Подход 2: CAS (compare-and-swap)

```rust
pub fn cas(&self, key: &[u8; K], expected: &[u8], new: &[u8]) -> Result<(), CasError>
```

Работает под shard Mutex: read + compare + write атомарны внутри шарда. Caller должен делать retry loop:

```rust
loop {
    let old = tree.get(key)?;
    let new = modify(&old);
    match tree.cas(key, &old, &new) {
        Ok(()) => break,
        Err(CasError::ValueMismatch) => continue,
    }
}
```

- Caller делает retry при contention
- Для VarTree: CAS читает текущее значение с диска (один disk read per attempt)
- Стандартный паттерн, знакомый всем

##### Подход 3: Update с замыканием

```rust
// ConstTree — замыкание получает inline value, zero I/O:
pub fn update(&self, key: &[u8; K], f: impl FnOnce([u8; V]) -> [u8; V]) -> DbResult<bool>

// VarTree — один disk read под lock:
pub fn update(&self, key: &[u8; K], f: impl FnOnce(&[u8]) -> Vec<u8>) -> DbResult<bool>
```

Под shard Mutex: read → вызов замыкания → write. Атомарно, без retry.

- ConstTree: замыкание получает `[u8; V]` из памяти — zero I/O
- VarTree: один disk read (или cache hit) под lock
- Самый эргономичный для caller'а: нет retry loop, нет race condition
- Замыкание не должно быть тяжёлым — shard lock захвачен

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

| Подход | ConstTree cost | VarTree cost | Retry? | Эргономика |
|--------|---------------|-------------|--------|------------|
| `put → Option<old>` | бесплатно | disk read на каждый put | нет | простая, но не решает RMW |
| CAS | ok | disk read per attempt | да | стандартная, retry loop |
| `update(key, fn)` | zero I/O | один disk read | нет | лучшая для RMW |

#### Рекомендация

- **ConstTree:** `put` возвращает `Option<[u8; V]>` — zero overhead. `update(key, fn)` как удобная обёртка.
- **VarTree:** `put` остаётся `-> DbResult<()>` без старого значения (не платим за disk read когда не нужно). `update(key, fn)` — один read под lock + write для RMW.
- **CAS** — имеет смысл как альтернатива, когда caller уже знает expected value (закешировал на своей стороне). Дешевле `update` в этом случае — нет лишнего disk read.

### 12. Prefix-based sharding для составных ключей

Текущая маршрутизация хеширует **полный ключ**: `xxh3_64(key) % shard_count`. Для составных ключей (например `post_id:comment_id`) это значит, что комментарии одного поста разбросаны по разным шардам.

Предложение: хешировать только **префикс** ключа, чтобы связанные записи попадали в один шард.

#### Текущее поведение

```rust
fn shard_for(&self, key: &[u8; K]) -> usize {
    xxh3_64(key) % shard_count  // полный ключ
}
```

`post_1:comment_1` и `post_1:comment_2` → разные шарды (с высокой вероятностью).

#### Предлагаемое поведение

```rust
fn shard_for(&self, key: &[u8; K]) -> usize {
    let prefix_bytes = (self.shard_key_prefix + 7) / 8; // биты → байты (округление вверх)
    let shard_bytes = if prefix_bytes > 0 && prefix_bytes < K {
        &key[..prefix_bytes]
    } else {
        key.as_slice()
    };
    (xxh3_64(shard_bytes) as usize) % self.shard_count
}
```

Все комментарии одного поста → один шард.

#### Преимущества

1. **Атомарность связанных ключей** — главный выигрыш. Если `post_id:data` и `post_id:comment_count` в одном шарде, можно обновить оба под одним shard Mutex. Лёгкие транзакции для связанных ключей без распределённого lock'а.

2. **Disk locality** — связанные записи в одних файлах → одних блоках. С block cache (идея 10) — один cache miss подтягивает соседние записи.

3. **Prefix iteration I/O** — SkipList один на дерево, так что prefix_iter уже ищет по одному индексу. Но значения VarTree на диске — с prefix sharding они в одном файле, sequential read вместо random I/O по разным шардам.

#### Недостатки

1. **Hot shard** — пост с миллионом комментариев → все записи через один Mutex. При uniform шардировании нагрузка распределена равномерно.

2. **Неравномерное распределение** — одни префиксы имеют 10 ключей, другие 10 миллионов. `xxh3` по полному ключу даёт идеальное распределение.

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

Минимальное изменение — runtime параметр при создании дерева:

```rust
// 0 = полный ключ (по умолчанию, текущее поведение)
// N = хешировать первые N бит ключа
let tree = db.const_tree_with::<8, 8>(TreeConfig {
    shard_key_prefix: 32,  // первые 32 бита = post_id
})?;
```

Хорошо ложится на `armour::Cid` / `KeyScheme` — там уже есть концепция составных ключей с разделением на части. `shard_key_prefix` может выводиться автоматически из `KeyScheme::prefix_len()`.
