# CPU Time: Read Path & Write Path

Приблизительные затраты по времени на каждом этапе для 2 GHz CPU.
Ключ 16 байт, значение 100 байт (entry ~132 байт с header и padding).

---

## Write Path: ConstTree::put

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

| Категория | Время | % от total |
|-----------|-------|------------|
| 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).

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

| Этап | Bitcask | FixedStore |
|------|:-------:|:---------:|
| 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

```text
TOTAL (new key):             ~1200ns  ≈ 1.2 us
TOTAL (update):              ~1350ns  ≈ 1.35 us
```

---

## Read Path: ConstTree::get

```text
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 (быстрый путь)

```text
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 (диск)

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

---

## Сводная таблица

| Операция | CPU время | Disk I/O | Итого |
|----------|----------|----------|-------|
| 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

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

### Влияние на операции

| Операция | Без шифрования | С шифрованием | Overhead |
|----------|---------------|---------------|----------|
| 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 страниц):

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

```text
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 в памяти).
