## Статус реализации
| 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 захвачен
#### Сравнение
| `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()`.