# armdb: анализ производительности

## Lookup (get)

Каждый шаг в SkipList — `AtomicPtr::load(Acquire)` + сравнение ключа.

Стоимость шага зависит от уровня кеша:

| Cache level | Latency | Когда |
|-------------|:-------:|-------|
| 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.

| Entries | Шагов (log₂n) | Типичный | Worst case (RAM, NUMA) |
|--------:|:--------------:|:--------:|:----------------------:|
| 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-типы)

| Entries | Типичный | Worst case |
|--------:|:--------:|:----------:|
| Любой | ~50-100 ns | ~200 ns (hash collision chain) |

O(1) с shard mutex lock/unlock (~20-50 ns uncontended).

### ART (гипотетическая замена SkipList)

Для 8-байтных ключей — максимум 8 уровней вместо 20-30.

| Entries | Шагов ART | Типичный (DRAM) |
|--------:|:---------:|:---------------:|
| 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)

### Путь записи

```text
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**:

```text
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).
