armdb 0.1.13

sharded bitcask key-value storage optimized for NVMe
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

# Fixed Store for armdb

Для фиксированного размера записей с частыми обновлениями на NVMe оптимальна архитектура **slotted page / direct-mapped file** с in-place updates.

## Почему Bitcask плохо подходит

- Каждый update = новая запись → write amplification
- Нужна compaction для освобождения места
- Растущий лог при частых обновлениях (например, счётчики)

## Идеальная архитектура: Page-aligned fixed-slot store

### Суть

Записи фиксированного размера → смещение вычисляется арифметически:

```
offset = slot_id * record_size
```

Обновление = seek + overwrite на месте. Никакого append, никакой compaction.

### Ключевые свойства

| Свойство | Решение |
|----------|---------|
| **I/O alignment** | Записи выравниваются по 4KB страницам NVMe. Несколько записей пакуются в одну страницу |
| **O_DIRECT** | Обход page cache — прямая работа с NVMe, предсказуемая латентность |
| **io_uring** | Батчинг операций, полное использование параллелизма NVMe (multiple submission queues, deep queue depth) |
| **In-place update** | Нет write amplification — запись ровно того что изменилось |
| **Crash safety** | Мини-WAL или copy-on-write на уровне страницы (запись в shadow page → atomic rename/pointer swap) |
| **Конкурентность** | Lock per page или lock-free CAS для отдельных слотов |

### Структура файла

```
┌─────────────────────────────────────┐
│ Header (4KB page 0)                 │
│   magic, version, record_size,      │
│   record_count, free_list_ptr       │
├─────────────────────────────────────┤
│ Page 1:  [rec0][rec1]...[recN]      │  ← records_per_page = 4096 / record_size
│ Page 2:  [rec N+1]...[rec 2N]       │
│ ...                                 │
│ Page K:  [rec ...]...[rec ...]      │
└─────────────────────────────────────┘
```

### Почему это идеально для NVMe

1. **Random read/write ≈ sequential** на NVMe — нет штрафа за seek, в отличие от HDD
2. **4KB atomic write** — NVMe гарантирует атомарность записи одной страницы (512B-4KB), поэтому обновление записи внутри одной страницы может быть crash-safe без WAL
3. **Queue depth** — io_uring позволяет отправлять десятки/сотни операций одновременно, NVMe обрабатывает их параллельно через внутренние каналы
4. **Нет compaction** — CPU и bandwidth не тратятся на перезапись данных

### Сравнение

| | Bitcask (текущее) | LSM-tree | B+tree (LMDB) | **Fixed-slot** |
|---|---|---|---|---|
| Write amplification | Высокий (append + compaction) | Высокий (compaction levels) | Средний (page splits) | **1x** |
| Read amplification | 1 (через index) | N (levels) | O(log n) | **1** |
| Space amplification | Высокий (мёртвые записи) | Средний | Низкий | **Нулевой** |
| Compaction нужна | Да | Да | Нет | **Нет** |
| NVMe parallelism | Слабо | Хорошо | Средне (mmap) | **Отлично (O_DIRECT + io_uring)** |
| Фиксированный размер | Не использует | Не использует | Не использует | **Полностью оптимизирован** |

### Crash recovery

Два варианта:

1. **Без WAL** — если NVMe гарантирует atomic page write (большинство современных NVMe), и запись ≤ размера страницы, то crash-safe "бесплатно"
2. **Lightweight WAL** — для записей, которые пересекают границу страницы: записать intent в WAL → обновить страницы → truncate WAL. WAL будет крошечным и почти всегда пустым

### Для armdb

У вас уже есть io_uring в armdb. Новый storage engine можно добавить как альтернативный backend рядом с bitcask — за feature flag (например `fixed_store`). Индексы (SkipList/HashMap) остаются как есть, просто вместо offset в лог-файле хранят slot_id.