# CPU Time: Read Path & Write Path
Приблизительные затраты по времени на каждом этапе для 2 GHz CPU.
Ключ 16 байт, значение 100 байт (entry ~132 байт с header и padding).
---
## Write Path: ConstTree::put
```
shard_for(key) xxh3 + modulo ~50ns
shard.lock() parking_lot uncontended ~25ns
append_entry()
GLOBAL_GSN.fetch_add Relaxed atomic ~5ns
serialize_entry CRC32 + memcpy ~450ns
CRC32 (128 bytes) table-driven ~200ns ← самая дорогая часть
Vec alloc (132 bytes) malloc ~100ns
header + key + value memcpy ~150ns
WriteBuffer::append memcpy в pre-alloc буфер ~50ns
ConstNode::alloc 1x alloc (VLA node, inline) ~150ns
index.insert() write_lock + traversal ~350ns
write_lock uncontended ~10ns
search (avg 4 levels) pointer chase + key cmp ~300ns
link (avg 1.3 levels) atomic store ~5ns
len.fetch_add Relaxed atomic ~5ns
[if update: SeqLock write]
write_data() seq bump + memcpy ~30ns
add_dead_bytes HashMap update ~15ns
dealloc unused node free ~50ns
shard.unlock() ~5ns
─────────────────────────────────────────────────────────────
TOTAL (new key): ~1080ns ≈ 1.1 us
TOTAL (update): ~1125ns ≈ 1.1 us
```
### Breakdown by category
| CRC32 | ~200ns | 19% |
| Allocations (Vec + Node) | ~250ns | 23% |
| SkipList traversal | ~300ns | 28% |
| memcpy (serialize + buffer) | ~200ns | 19% |
| Locking (shard + skiplist) | ~40ns | 4% |
| Остальное (hash, atomics) | ~90ns | 8% |
**Bottleneck:** SkipList traversal (28%) и аллокации (23%). Аллокации снижены: один alloc (VLA node, inline data) вместо двух (Node + ConstData). CRC32 (19%) растёт с размером entry. SkipList traversal O(log n) растёт медленно — при 100M ключей ~10 уровней вместо 4.
---
## Write Path: ConstTree::put (FixedStore backend)
Ключ 16 байт, значение 100 байт, slot_size = 124 байта (8 header + 16 key + 100 value).
```
shard_for(key) xxh3 + modulo ~50ns
shard.lock() parking_lot uncontended ~25ns
index.get(key) lock-free traversal ~280ns ← проверяем ДО записи
[if update]:
write_slot(slot_id) pwrite через page cache ~200-500ns
serialize_slot CRC32 + memcpy ~350ns
CRC32 (116 bytes) table-driven ~180ns
memcpy header+data memcpy ~170ns
pwrite_at syscall → page cache ~200ns
SeqLock write_data() inline update ~30ns
[if new key]:
bitmap.alloc() scan for free bit ~50-200ns
write_slot(slot_id) pwrite через page cache ~200-500ns
ConstNode::alloc 1x alloc (VLA node, inline) ~150ns
index.insert() write_lock + traversal ~350ns
shard.unlock() ~5ns
[maybe_sync] fdatasync if batch ready amortized ~0.1-1μs
─────────────────────────────────────────────────────────────
TOTAL (update): ~940ns ≈ 0.9 us
TOTAL (new key): ~1110ns ≈ 1.1 us
```
### Отличия от Bitcask write path
| Index check | после append | **до записи** (экономит append при update) |
| Disk write | memcpy в write buffer (~50ns) | **pwrite syscall** (~200ns) |
| CRC32 | header + key + value (~200ns) | key + value (~180ns, без header) |
| Vec alloc | ~100ns (serialized entry) | **нет** (слот фиксированного размера) |
| Dead bytes tracking | ~15ns (HashMap update) | **нет** |
| Sync | write buffer flush (~1-5ms spike) | **fdatasync после unlock** (~10-50μs, не блокирует) |
**Итог:** CPU time сравним (~1 μs). Главный выигрыш — отсутствие tail latency spikes от write buffer flush и compaction.
---
## Write Path: VarTree::put
Идентичен ConstTree::put за исключением:
- `VarNode::alloc` вместо `ConstNode::alloc` — на ~50ns дешевле (нет inline value)
- При update: RCU swap на `AtomicPtr<DiskLoc>` (Box + swap + retire) вместо SeqLock write
```
TOTAL (new key): ~1200ns ≈ 1.2 us
TOTAL (update): ~1350ns ≈ 1.35 us
```
---
## Read Path: ConstTree::get
```
guard = collector.enter() thread-local ~8ns
index.get(key) lock-free traversal ~280ns
height.load Relaxed atomic ~3ns
per-level traversal avg 4 levels ~270ns
pointer load Acquire atomic ~5ns/level
key comparison memcmp 16 bytes ~50ns/level
node.seqlock_read() SeqLock read ~15ns
seq load (Acquire) first seq read ~3ns
copy value [u8; V] memcpy ~5ns
copy disk (DiskLoc) memcpy ~2ns
seq load (Acquire) second seq check ~3ns
fence atomic fence ~2ns
guard drop thread-local ~5ns
─────────────────────────────────────────────────────────────
TOTAL: ~320ns ≈ 0.32 us
```
**Zero disk I/O** — значения inline в SkipList node. Lock-free — SeqLock read (spin при коллизии с writer, без Mutex). Guard нужен только для traversal SkipList, не для чтения данных.
---
## Read Path: VarTree::get
### Cache hit (быстрый путь)
```
guard = collector.enter() thread-local ~8ns
index.get(key) lock-free traversal ~280ns
node.load_disk() Acquire atomic ptr ~5ns
read_value_cached()
block_key computation arithmetic ~2ns
cache.get(&block_key) quick_cache S3-FIFO ~10ns
extract value from block slice + ByteView::new ~15ns
guard drop ~5ns
─────────────────────────────────────────────────────────────
TOTAL: ~325ns ≈ 0.33 us
```
### Cache miss (диск)
```
guard + index.get + load_disk ~295ns
read_value_cached()
cache.get() miss ~10ns
write buffer check shard.lock + check ~30ns
pread syscall system call overhead ~100ns
──── I/O WAIT ──── NVMe: 10-100 us 10-100 us ← доминирует
──── I/O WAIT ──── SSD: 50-500 us 50-500 us
cache.insert() S3-FIFO insert ~25ns
extract value slice + ByteView ~15ns
guard drop ~5ns
─────────────────────────────────────────────────────────────
CPU TOTAL: ~480ns
I/O TOTAL: 10-500 us (100-1000x дороже CPU)
```
---
## Сводная таблица
| ConstTree::get | 0.32 us | нет | **0.32 us** |
| VarTree::get (cache hit) | 0.33 us | нет | **0.33 us** |
| VarTree::get (cache miss) | 0.48 us | 10-500 us | **10-500 us** |
| ConstTree::put Bitcask (new) | 1.1 us | нет* | **1.1 us** |
| ConstTree::put Bitcask (update) | 1.1 us | нет* | **1.1 us** |
| ConstTree::put Fixed (new) | 1.1 us | pwrite** | **1.1 us** |
| ConstTree::put Fixed (update) | 0.9 us | pwrite** | **0.9 us** |
| VarTree::put | 1.2 us | нет* | **1.2 us** |
| ConstTree::insert | 1.1 us | нет* | **1.1 us** |
| ConstTree::insert (KeyExists) | 0.35 us | нет | **0.35 us** |
\* Bitcask: WriteBuffer поглощает запись. Реальный disk I/O — при flush (background или при заполнении буфера). Tail latency: **~1-5 ms** (flush под lock).
\** FixedStore: pwrite через page cache (~200ns). fdatasync batched, после unlock. Tail latency: **~10-50 μs**.
---
## Что больше всего потребляет
### Write path
1. **Аллокации (23%)** — Vec для serialized entry, один alloc для VLA node (inline data, без отдельного Box для ConstData)
2. **CRC32 (15%)** — table-driven, ~1.5 cycles/byte. Оптимизация: Intel CRC32C instruction (~0.3 cycles/byte)
3. **SkipList traversal (23%)** — O(log n) pointer chasing, плохая cache locality
### Read path
1. **SkipList traversal (85%)** — доминирует. Lock-free, но O(log n) pointer chasing
2. **Block cache lookup (3%)** — quick_cache очень быстрый
3. **Disk I/O (при cache miss)** — 100-1000x дороже всего CPU вместе взятого
---
## Потенциальные оптимизации
| Object pool для Node | ~100ns/write | средняя |
| SIMD CRC32C (hardware) | ~150ns/write | низкая |
| Pre-allocated entry buffer (stack) | ~100ns/write | низкая |
| HashMap index (без ordered iter) | ~200ns/read, ~250ns/write | средняя |
| Inline small values в VarTree index | устранение disk read для мелких значений | высокая |
---
## Encryption Overhead (feature `encryption`)
AES-256-GCM шифрование на уровне 4096-байтных страниц. Overhead только при включённом шифровании с ключом.
### Per-page cost
```
AES-256-GCM encrypt (4096B) AES-NI hardware ~120ns
AES-256-GCM decrypt (4096B) AES-NI hardware ~120ns
tag file write (16B) pwrite_at ~40ns
tag file read (16B) pread (read_exact_at) ~40ns
─────────────────────────────────────────────────────────────
Encrypt + tag write: ~160ns / page
Decrypt + tag read: ~160ns / page
```
Без AES-NI (software fallback): ~800ns/page encrypt, ~800ns/page decrypt.
### Влияние на операции
| ConstTree::put (new) | 1.1 us | 1.1 us* | 0** |
| ConstTree::get | 0.32 us | 0.32 us | 0 |
| VarTree::get (cache hit) | 0.33 us | 0.33 us | 0 |
| VarTree::get (cache miss) | 0.48 us + I/O | 0.64 us + I/O | +160ns |
| Flush (1MB буфер) | ~pwrite | ~pwrite + 40 us | +40 us (256 pages × 160ns) |
\* put — memcpy в WriteBuffer, шифрование при flush.
\** Overhead размазан по flush: ~160ns на страницу × (buffer_size / 4096) страниц.
### Breakdown: encryption в write flush
Для 1 MB write buffer (256 страниц):
```
Encrypt 256 pages 256 × 120ns = ~31 us
Write 256 tags 256 × 16B = 4KB pwrite ~40ns
Write encrypted data pwrite 1MB (same as plain)
─────────────────────────────────────────────────────────────
TOTAL overhead: ~31 us per 1MB flush
= ~120ns per entry (entry ~132B, ~31 per page)
```
### Breakdown: encryption в read path
```
VarTree::get (cache miss):
pread_block (4096B) same as plain
tag file read (16B) pread_exact_at ~40ns
AES-256-GCM decrypt hardware ~120ns
cache.insert() plaintext — no overhead
────────────────────────────────────────────────────
Overhead: ~160ns per cache miss
VarTree::get (cache hit):
cache.get() plaintext, zero decrypt
────────────────────────────────────────────────────
Overhead: 0
ConstTree::get / ConstMap::get:
Inline value in memory no disk I/O, no decrypt
────────────────────────────────────────────────────
Overhead: 0
```
### Когда overhead заметен
- **Write-heavy workload**: flush каждые 1MB добавляет ~31 us. При 100K writes/sec и 1MB buffer → flush ~13 раз/sec → ~400 us/sec overhead (ничтожно).
- **Read-heavy с холодным кешем**: каждый cache miss +160ns. При 1M random reads/sec с 50% miss rate → ~80 ms/sec overhead (~8%).
- **Read-heavy с горячим кешем**: zero overhead.
- **ConstTree/ConstMap**: zero overhead (значения inline в памяти).