# armdb: анализ производительности
## Lookup (get)
Каждый шаг в SkipList — `AtomicPtr::load(Acquire)` + сравнение ключа.
Стоимость шага зависит от уровня кеша:
| L1 (64KB) | ~1 ns | hot path, маленькое дерево |
| L2 (256KB-1MB) | ~4 ns | ~10K-100K entries |
| L3 (8-32MB) | ~12 ns | ~100K-1M entries |
| DRAM | ~60-80 ns | >1M entries (не помещается в L3) |
### SkipList (Tree-типы)
MAX_HEIGHT = 16, p = 0.25. Максимум ~4.3B entries.
| 1M | ~20 | ~200-400 ns | ~600 ns |
| 10M | ~23 | ~1-2 μs | ~3 μs |
| 1B | ~30 | ~2-3 μs | ~5-6 μs |
Основная стоимость — pointer chasing (каждый узел на разной cache line).
### HashMap (Map-типы)
| Любой | ~50-100 ns | ~200 ns (hash collision chain) |
O(1) с shard mutex lock/unlock (~20-50 ns uncontended).
### ART (гипотетическая замена SkipList)
Для 8-байтных ключей — максимум 8 уровней вместо 20-30.
| 1M | 4-8 | ~300-600 ns |
| 10M | 6-8 | ~500-700 ns |
| 1B | 8 | ~600-800 ns |
Выигрыш ~2.5× на point lookup при >10M entries. При <1M — разница незаметна.
## Put (write)
### Путь записи
```
1. shard_for(key) — hash + mod ~5 ns
2. shard.lock() — mutex acquire ~20-50 ns (uncontended)
3. codec.encode_to() — serialize value ~50-500 ns (зависит от T)
4. append_entry() — memcpy в write buf ~20-100 ns
5. SkipList::get() — найти узел ~60 ns - 3 μs (зависит от размера)
6. [ConstTree] SeqLock write_data() — inline update ~10-30 ns (no heap alloc)
[TypedTree] Box::new(TypedData) — heap alloc ~20-50 ns
[VarTree] Box::new(DiskLoc) — heap alloc ~20-50 ns
7. [TypedTree/VarTree] AtomicPtr::swap() — pointer swap ~5 ns
8. [TypedTree/VarTree] seize::retire() — schedule dealloc ~10 ns
9. hook.on_write() — callback ~0-??? ns
10. shard.unlock() — mutex release ~10 ns
```
Итого на 1 put (uncontended, 1M entries): **~300-800 ns**
### Shard mutex contention
Вся запись проходит через per-shard mutex.
Default: `shard_count = available_parallelism() * 2`.
На 16 cores / 32 threads → shard_count = 32 → ~1 writer/shard (идеально).
| Сценарий | Writers/shard | Latency per put |
|----------|:------------:|:---------------:|
| 32 shards, равномерное распределение | ~1 | ~500 ns |
| 32 shards, 80% в 3 шарда (skew) | ~8-10 | ~3-5 μs |
| 32 shards, 1 hot shard | ~32 | ~15-25 μs |
### Throughput (32 threads, AMD 16-core)
| Потоки | Throughput (равномерно) | Throughput (skewed keys) |
|:------:|:----------------------:|:-----------------------:|
| 1 | ~2M ops/sec | ~2M ops/sec |
| 8 | ~16M ops/sec | ~5-8M ops/sec |
| 32 | ~50-60M ops/sec | ~8-15M ops/sec |
### Put latency по размеру дерева
| Entries per shard | Put latency (p99) |
|------------------:|:-----------------:|
| 100K | ~400 ns |
| 1M | ~800 ns |
| 10M | ~2 μs |
| 100M | ~4-6 μs |
| 1B per shard | ~8-10 μs |
## FixedStore backend
FixedStore заменяет Bitcask (append-only log) на fixed-slot pwrite (in-place updates) для коллекций с `[u8; V]` inline-значениями (ConstTree, ConstMap, ZeroTree, ZeroMap).
### Put latency: FixedStore vs Bitcask
| Percentile | Bitcask | FixedStore | Причина разницы |
|:----------:|:-------:|:----------:|:----------------|
| p50 | ~500 ns | ~500 ns | CPU-bound, сравнимо |
| p99 | ~2-5 μs | ~1-3 μs | нет compaction contention |
| p99.9 | **~1-5 ms** | **~10-50 μs** | нет write buffer flush под lock |
### Что убирает FixedStore
1. **Write buffer flush contention** — Bitcask flush 1MB под shard lock = ~1-5 ms spike. FixedStore: pwrite каждой записи в page cache (~200ns), fdatasync батчами после release lock.
2. **Compaction** — Bitcask compaction переписывает data files, конкурирует за shard lock и disk I/O. FixedStore: in-place overwrite, нет мёртвых записей, compaction не нужна.
3. **Space amplification** — Bitcask: 1.3-2x (мёртвые записи до compaction). FixedStore: 1x.
### Что остаётся
- **SkipList traversal** — O(log n) pointer chasing, одинаково для обоих backend'ов
- **Shard mutex contention** — per-shard Mutex, одинаково
- **Alloc pressure** — ConstNode alloc при insert, одинаково
### Recovery
| Записей | Bitcask | FixedStore (dirty) | FixedStore (clean) |
|--------:|:-------:|:------------------:|:------------------:|
| 1M | ~0.1-1 s | ~30 ms | ~10-20 ms |
| 10M | ~1-10 s | ~300 ms | ~100-200 ms |
| 100M | ~10-100 s | ~3 s | ~1-2 s |
FixedStore: один sequential scan vs множество файлов. Clean shutdown с bitmap sidecar пропускает свободные слоты.
### Потребление памяти
FixedStore экономит 8 байт на запись (slot_id `u32` 4B вместо DiskLoc 12B):
| Записей | Bitcask | FixedStore | Экономия |
|--------:|:-------:|:----------:|:--------:|
| 1M | ~72 MB* | ~64 MB* | 8 MB |
| 10M | ~720 MB | ~640 MB | 80 MB |
| 100M | ~7.2 GB | ~6.4 GB | 800 MB |
\* Для ConstTree с ключом 8B, значением 64B. SkipList node ~60B + V + location.
---
## Пороги проблем
### 1. Write buffer flush (~1-5 ms задержка) — только Bitcask
> **FixedStore:** эта проблема отсутствует. pwrite каждой записи в page cache, fdatasync батчами после release lock.
Каждый шард имеет write buffer (default 1MB). Когда буфер полон — flush на диск **под shard lock**:
```
write_buffer_size = 1MB
entry_size ≈ 50 bytes (key 8 + header 16 + value 26)
entries_per_buffer ≈ 20,000
```
При 2M puts/sec на шард → flush каждые ~10ms.
Сам flush: ~0.5-2 ms (NVMe), +1-5 ms если fsync включён.
Во время flush весь шард заблокирован.
**Порог:** sustained write >1M ops/sec на шард (~32M ops/sec суммарно при 32 шардах).
### 2. Alloc pressure при >10M entries
Каждый put аллоцирует:
- При новом ключе: один alloc для VLA node (inline data) — ~60-120 bytes
- [TypedTree/VarTree] При update: `Box<TypedData<T>>` или `Box<DiskLoc>` — ~40-80 bytes
- [ConstTree/ZeroTree] При update: **без heap-аллокации** (SeqLock inline write). Alloc pressure снижена.
Для TypedTree/VarTree при 10M puts/sec → ~0.5-1 GB/sec аллокаций. seize retire накапливает garbage → периодические bulk deallocation pauses.
Каждый put для ConstTree не аллоцирует TypedData (inline SeqLock). Alloc pressure снижена.
**Порог:** >50M entries при >5M inserts/sec (актуально для TypedTree/VarTree).
### 3. SkipList degradation при >100M per shard
Lookup деградирует из-за cache misses. Put = lookup + alloc + append, всё дороже.
**Порог:** >100M entries per shard, mean put latency >4 μs.
### 4. Hot shard contention
Неравномерное распределение ключей по шардам. >8 writers на 1 shard — throughput cap ~3-5M ops/sec на этот шард.
**Митигация:** `shard_prefix_bits` для контроля распределения, увеличение shard_count.
### 5. Compaction contention — только Bitcask
> **FixedStore:** compaction не нужна. In-place overwrite, space amplification 1x.
Compaction перечитывает data files и обновляет DiskLoc через `update_if_match` — конкурирует с writers за shard lock.
**Порог:** >100GB data on disk, compaction и writes на одном шарде одновременно.
## Сводная таблица
| Масштаб | Проблема | Симптом | FixedStore? |
|---------|----------|--------|:-----------:|
| >30M ops/sec sustained writes | write buffer flush contention | p99 spikes ~1-5 ms | **нет** |
| >50M entries + high insert rate | alloc/seize GC pressure | periodic latency spikes | да (одинаково) |
| >100M entries per shard | SkipList lookup деградация | mean latency >4 μs | да (одинаково) |
| hot shard (>8 writers) | mutex contention | throughput cap ~3-5M/sec на shard | да (одинаково) |
| >100GB disk | compaction + write contention | periodic throughput drops | **нет** |
## Контекст
Для сравнения — latency других операций:
| Операция | Latency |
|----------|:-------:|
| L1 cache hit | ~1 ns |
| L3 cache hit | ~12 ns |
| DRAM access | ~60-80 ns |
| NVMe random read (4KB) | ~10-20 μs |
| NVMe write (buffered) | ~5-10 μs |
| TCP loopback | ~10-30 μs |
| Network (datacenter) | ~50-500 μs |
Даже worst case SkipList lookup на 1B entries (~5-6 μs) быстрее одного NVMe read.
## Сравнение с PostgreSQL
Условия: AMD 16-core / 32 threads, NVMe SSD, 64GB RAM.
PostgreSQL 16 с настроенным shared_buffers, таблица с B-tree индексом по primary key.
### Point lookup (SELECT by PK)
| Entries | armdb (Tree, in-memory) | armdb (Map, in-memory) | PostgreSQL (buffer cache hit) | PostgreSQL (disk) |
|--------:|:-----------------------:|:----------------------:|:-----------------------------:|:-----------------:|
| 1M | ~200-400 ns | ~50-100 ns | ~5-15 μs | ~100-300 μs |
| 10M | ~1-2 μs | ~50-100 ns | ~10-20 μs | ~100-500 μs |
| 1B | ~2-3 μs | ~50-100 ns | ~20-50 μs | ~200-1000 μs |
PostgreSQL overhead на каждый запрос даже при cache hit:
- SQL parse/plan (prepared stmt): ~2-5 μs
- Buffer manager latch: ~1-3 μs
- B-tree traversal: ~2-10 μs (зависит от глубины, ~4 уровня для 1B rows)
- Tuple visibility check (MVCC): ~0.5-1 μs
- Итого: **~5-20 μs при cache hit**
armdb: прямой вызов функции, никакого SQL/parse/plan/MVCC. Разница ~10-100×.
### Point insert (INSERT single row)
| Entries | armdb (Tree) | armdb (Map) | PostgreSQL |
|--------:|:------------:|:-----------:|:----------:|
| 1M | ~500-800 ns | ~300-500 ns | ~20-80 μs |
| 10M | ~1-2 μs | ~300-500 ns | ~30-100 μs |
| 100M | ~3-5 μs | ~300-500 ns | ~50-200 μs |
PostgreSQL overhead на insert:
- SQL parse/plan: ~2-5 μs
- Heap insert + WAL: ~10-30 μs
- B-tree index insert + WAL: ~10-30 μs
- Buffer pin/unpin, lock manager: ~5-10 μs
- fsync (при commit, batched): amortized ~1-10 μs
armdb: append в write buffer (no fsync по умолчанию), index update.
PostgreSQL: WAL + heap + index + MVCC + lock manager.
### Throughput (32 threads)
| Операция | armdb | PostgreSQL (tuned) |
|----------|:-----:|:------------------:|
| Point reads/sec | ~50-60M | ~1-3M |
| Point writes/sec | ~30-50M | ~200K-500K |
| Mixed 80/20 read/write | ~40-50M | ~500K-1M |
PostgreSQL throughput ограничен:
- WAL serialization (один WAL writer)
- Lock manager contention
- Buffer pool latch contention
- Process-per-connection model (context switches)
### Latency distribution
| Percentile | armdb put (Bitcask) | armdb put (FixedStore) | PostgreSQL INSERT |
|:----------:|:-------------------:|:---------------------:|:-----------------:|
| p50 | ~500 ns | ~500 ns | ~30 μs |
| p99 | ~2-5 μs | ~1-3 μs | ~200-500 μs |
| p99.9 | ~1-5 ms (write buf flush) | **~10-50 μs** (fdatasync) | ~5-50 ms (checkpoint, vacuum) |
### Что PostgreSQL даёт взамен
| Возможность | armdb | PostgreSQL |
|-------------|:-----:|:----------:|
| SQL | нет | да |
| Транзакции (ACID, multi-key) | нет | да |
| MVCC (snapshot isolation) | нет | да |
| Вторичные индексы | hooks (manual) | встроенные |
| JOIN, агрегации | нет | да |
| Репликация | базовая | streaming, logical |
| Конкурентный DDL | нет | да |
| Point-in-time recovery | нет | да |
| Constraints, FK | нет | да |
### Когда armdb vs PostgreSQL
| Сценарий | Выбор |
|----------|-------|
| KV store, embedded, <10 μs latency | armdb |
| Высокий write throughput (>1M ops/sec) | armdb |
| Нужен SQL, JOIN, транзакции | PostgreSQL |
| Данные >RAM, complex queries | PostgreSQL |
| Embedded в Rust приложение, без сети | armdb |
| Микросервис с простым CRUD по PK | armdb может быть достаточно |
| Аналитика, reporting | PostgreSQL |
armdb — это embedded KV engine уровня RocksDB/sled/fjall, не замена реляционной БД. Сравнение корректно только для KV workloads (point lookup/insert by key).