# 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`, `O_DIRECT`, fd management) |
| `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.
---
## Архитектура
### Общая схема
```
┌──────────────────────────┐
│ 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
/// 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
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>;
/// Вставка нового узла. Сериализуется через 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);
/// Удаление: логическое (mark) + retire через seize. Сериализуется через 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: write_lock vs CAS-based linking
Текущая реализация линкует новые узлы в tower через plain `store` (не CAS). Это не thread-safe для concurrent insert: два потока с общим predecessor перезаписывают один tower slot, теряя узел.
Для корректности добавлен `write_lock: Mutex<()>` — сериализует `insert`/`remove`. Читатели (`get`, итераторы) остаются lock-free.
**Почему не CAS:** CAS-based linking (как в `crossbeam-skiplist`) требует retry loop при конфликте и значительно усложняет код. Текущий `write_lock` добавляет ~20ns overhead (uncontended) и ~100ns при контенции между шардами. Это <10% от disk I/O на write path.
**Идеальное решение (future):** заменить plain `store` на CAS loop для tower linking. Это уберёт `write_lock`, сделает insert полностью lock-free, и вернёт параллельность insert'ов из разных шардов.
### Референс реализации
- `crossbeam-skiplist` — архитектура, layout узлов, **CAS-based алгоритм вставки/удаления** (target для lock-free insert)
- Herlihy & Shavit "The Art of Multiprocessor Programming", Chapter 14 — lock-free SkipList
- Заменить `crossbeam-epoch` на `seize` (API похож: `Guard`, `retire`)
---
## Типы данных
### Ключ
Генерик `K` с zerocopy trait bounds:
```rust
K: FromBytes + IntoBytes + Immutable + Copy + 'static
```
Длина ключа известна на этапе компиляции через `size_of::<K>()`. Не нужно хранить `key_len` в заголовке записи.
`[u8; N]` работает как fallback — самый простой вариант ключа:
```rust
let tree = ConstTree::<[u8; 16], 64>::open(config)?;
```
Для составных ключей — любой `repr(C)` zerocopy struct:
```rust
#[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(config)?;
```
Для `ConstMap`/`VarMap` ключ дополнительно требует `+ Send + Sync + Hash + Eq`.
### Значение
Два типа деревьев с разными стратегиями хранения значений:
```rust
/// Значения фиксированной длины — всегда 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
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
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`. Кешируется естественная единица чтения O_DIRECT — aligned disk block. Отделён от индекса, чтобы:
- Можно было 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 | 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) — это непрерывный блок байтов:
```
┌──────────────────── 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. Bit 63 = tombstone flag, bits 0-62 = 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 байтам |
### Tombstone encoding в GSN
Отдельного поля `flags` нет. Признак удаления закодирован в старшем бите GSN:
```rust
const TOMBSTONE_BIT: u64 = 1 << 63;
fn is_tombstone(gsn: u64) -> bool { gsn & TOMBSTONE_BIT != 0 }
fn sequence(gsn: u64) -> u64 { gsn & !TOMBSTONE_BIT }
fn make_tombstone(gsn: u64) -> u64 { gsn | TOMBSTONE_BIT }
```
63 бита на sequence = 9.2 * 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 — всегда из памяти
```
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
```
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
- 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 ОС, данные идут напрямую в userspace buffer
```rust
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
```
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:**
```
Условие: 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
impl<K: FromBytes + IntoBytes + Immutable + Copy + 'static> VarTree<K> {
pub fn cas(
&self,
key: &K,
expected: &[u8],
new_value: &[u8],
) -> Result<(), CasError> {
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(CasError::ValueMismatch),
None => return Err(CasError::KeyNotFound),
}
// 3. Пишем новое значение (под тем же lock)
self.put_under_lock(key, new_value, shard)?;
Ok(())
}
}
```
CAS безопасен, потому что все операции над одним ключом маршрутизируются в один шард, а запись в шард сериализована через `Mutex`.
---
## Шардирование
### Маршрутизация
По умолчанию — хеш полного ключа. С prefix-based sharding — хеш первых N бит:
```rust
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
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
}
```
---
## Файловая структура на диске
```
{db_path}/
├── db.meta # метаданные (4 bytes): 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 байта, фиксированный размер.
```
[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 содержит только метаданные записей без значений:
```
┌──────────────── 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 (при старте)
```
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
// старая запись была в файле old_file_id
shard.dead_bytes[old_file_id] += old_entry_size;
```
### Алгоритм
```
Фоновый поток (один на базу или один на 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
// Все три метода возвращают один тип:
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
let mut config = Config::new("data/posts");
config.reversed = true; // forward = descending
let tree = VarTree::<[u8; 16]>::open(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`
### Архитектура
```
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 |
---
## io_uring конфигурация
### Инициализация
```rust
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 удалён.
Одно дерево = одна директория на диске.
```rust
/// Конфигурация базы данных
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 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 { .. }
```
---
## Структура модулей
```
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_read: O_DIRECT pread
│ └── 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) Leader/Follower, 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
├── 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` — `pread` с `O_DIRECT`
8. `config.rs` — конфигурация
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` и `O_DIRECT` — Linux-only. Для разработки на macOS использовать fallback на обычный `pread`/`write` без `O_DIRECT`.
- **Выравнивание**: все 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, индексы). Шифрование только на границе память ↔ диск.
```
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).
### Файлы на диске
```
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` (1 байт) в корне БД хранит флаг `encrypted: bool`. При открытии:
- Есть флаг `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
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
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
```
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
```rust
// Без hook (H = NoHook):
ConstTree::<[u8; 16], 64>::open(config)
VarTree::<[u8; 16]>::open(config)
ConstMap::<[u8; 16], 64>::open(config)
VarMap::<[u8; 16]>::open(config)
// С hook:
ConstTree::<[u8; 16], 64, H>::open_hooked(config, hook)
VarTree::<[u8; 16], H>::open_hooked(config, hook)
ConstMap::<[u8; 16], 64, H>::open_hooked(config, hook)
VarMap::<[u8; 16], H>::open_hooked(config, hook)
// С typed key:
VarTree::<PostKey>::open(config)
ConstTree::<PostKey, 64>::open(config)
```
`shard_prefix_bits` задаётся в `Config`. Recovery происходит внутри `open_inner()` — recovery не знает о `H`.
### Пример: secondary index по email
```rust
// Пример с [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
// Пример с 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)?;
```