# armdb: память и диск для множества мелких значений

Аналитическая записка. Контекст: коллекции armdb занимают много места — и в RAM,
и на диске. Нагрузка-ориентир — **поток мелких значений, как сообщения
мессенджера** (значения в десятки–сотни байт, ключ ~8 Б, в основном insert-once).
Цель — разобрать и проранжировать рычаги оптимизации по двум независимым
дорожкам (RAM-индекс и диск), с ожидаемым выигрышем, ценой и риском. Это разбор
осуществимости, **без обязательства реализовывать**.

Бенчмарк-источник: `rust-storage-bench`, профиль `time-series`
(value-size 128 Б, упорядоченные значения). Смежный разбор сжатия Var-коллекций —
в [qa.md](./qa.md) («Рекомендации для VarTree/VarMap…»).

Допущения нагрузки, под которые заточена записка (заданы при постановке):

- значения сериализованы **rapira** (компактный бинарь, плохо сжимается);
- масштаб на узел заранее не фиксирован — пороги переключения даны явно;
- смена модели хранилища в выводах **допустима**, где она честно лучше Bitcask.

---

## 1. Замеры и разбор overhead

### Что показал бенчмарк (`time-series`, 128 Б значения)

| Движок | Диск | RAM | Чем определяется RAM |
|---|---:|---:|---|
| armdb **VarTree** | 8.5 ГБ | **6.6 ГБ** | в RAM только `ключ + DiskLoc` |
| armdb **TypedTree** | 9.2 ГБ | **13.4 ГБ** | в RAM ещё и десериализованное `T` |
| armdb **ConstTree** | 11.4 ГБ | **13.0 ГБ** | в RAM ещё и значение целиком (`[u8; V]`) |
| **fjall 3** (LSM) | 7.1 ГБ | **1.0 ГБ** | индекс на диске + bloom + блок-кэш |

Главный факт: **перерасход — в RAM-индексе, а не на диске.** Диск у VarTree
сопоставим с LSM (8.5 против 7.1 ГБ); RAM выше в ~6 раз (6.6 против 1.0 ГБ), а у
Const/Typed — в ~13 раз. Это не дефект, а свойство модели: armdb — Bitcask, весь
keydir держится в RAM по построению.

### Overhead на одну запись (по коду)

**RAM, VarTree, ключ 8 Б** (`skiplist/node.rs`, `VarNode<K>`):

| Компонент | Байт |
|---|---:|
| `VarNode` базовая структура (`key` 8 + `disk: AtomicPtr` 8 + `mark` 1 + `height` 1 + `tower_ptr` 8, выровнено) | ~32 |
| `DiskLoc` в отдельном `Box` (16 Б payload + метаданные аллокатора) | ~24–32 |
| башня указателей (в среднем 1.33 уровня × 8 Б при p=0.25) | ~11 |
| **итого** | **~67–75 Б/запись** |

Ключевое: эта величина **не зависит от размера значения** — она платится за
каждый ключ. Боксированный `DiskLoc` — отдельная аллокация на каждую запись
(фрагментация + cache-miss на чтении, т.к. чтение `get` идёт через указатель в
кучу).

> Поправка к qa.md: `DiskLoc` сейчас **16 Б**, не 12 (см. `disk_loc.rs`,
> тест `disk_loc_size_is_16`): `offset` u32 + `len` u32 + `file_id` u32 +
> `shard_id` u8 + 3 Б паддинга.

**RAM, Const/Typed** — сверх вышеуказанного держат в RAM *само значение*:
`ConstNode` инлайнит `[u8; V]` (плюс `seq` для SeqLock), `TypedNode` боксирует
`TypedData { disk, value: T }`. Отсюда 13 ГБ — линейно по размеру значения ×
число записей. Для мессенджера это прямой антипаттерн.

**Диск, на запись** (`entry.rs`, `EntryHeader` = 16 Б):

```
[ gsn u64=8 | crc32 u32=4 | value_len u32=4 ] + key + value + паддинг до 8 Б
```

Фиксированный overhead = 16 Б заголовок + ключ. Для значения rapira в 64 Б +
ключ 8 Б это 24 Б ≈ **27%**; для 128 Б ≈ **16%**. Дополнительно Bitcask —
append-лог: устаревшие версии живут до compaction (для insert-once сообщений
space-amp низкий, ~1.1; правки/удаления его поднимают).

---

## 2. Дорожка RAM (ранжировано: выигрыш / цена / риск)

| # | Вариант | Выигрыш RAM | Цена | Риск |
|---|---|---|---|---|
| **R0** | **Брать VarTree, не Const/Typed** для сообщений (не держать значение в RAM) | 13 → 6.6 ГБ (≈2×) | нулевая — выбор типа коллекции | нет |
| **R1** | **Инлайнить `DiskLoc` через SeqLock** (как в `ConstNode`), убрать `Box` | ~8–16 Б/запись + убирает аллокацию и cache-miss на чтении | низкая, локально в `node.rs` + Var-коллекции | низкий — паттерн SeqLock уже есть |
| **R2** | **Ужать `DiskLoc`** 16 → 12 Б (убрать `shard_id`+pad: шард известен из контекста узла) | ещё ~4–8 Б/запись (с учётом выравнивания узла) | низкая | низкий |
| **R3** | **Insert-once / immutable-режим**: `loc` пишется один раз → убрать `seq` (8 Б) и SeqLock на чтении | ещё ~8 Б/запись | средняя — новый режим коллекции и контракт «значение неизменяемо» | средний |
| **R4** | **ART / компактный индекс** вместо SkipList (амортизация указателей на узел, path-compression на кластеризованных Fuid-ключах) | 2–4× на индексе | высокая — отдельный проект, перенос loom/miri-обвязки | высокий |
| **R5** | **Ленивый/on-disk keydir холодных шардов** (hint-файлы уже пишутся; в RAM держать только горячие шарды) | до ×N: в RAM лишь горячий набор | высокая — lifecycle файлов, recovery, reopen | высокий |

**Дешёвая дорожка R1+R2** даёт VarTree ~51 Б/запись против ~67–75 (≈ **−25…30%
RAM**) при низком риске, плюс ускоряет чтение (нет похода в кучу за `DiskLoc`).
R3 добавляет ещё ~15% для чисто append-only данных. R4/R5 — структурные, для
сотен млн–млрд записей.

Микро-замечание: `tower_ptr` (8 Б/узел) хранится ради provenance под Stacked
Borrows; его можно пересчитывать из базы аллокации с аккуратной работой с
provenance и сэкономить ещё 8 Б — складывается в R1/R2 как мелочь.

Почему R0 первый: он бесплатен и закрывает самый большой разрыв (13 → 6.6 ГБ).
Const/Typed оправданы там, где нужно lock-free-чтение значения из RAM (горячие
мелкие словари, счётчики), а не для холодного потока сообщений.

---

## 3. Дорожка диск (значения rapira → сжатие слабое)

| # | Вариант | Выигрыш | Цена | Риск |
|---|---|---|---|---|
| **D0** | **Замер реального ratio** клиентским zstd (rapira → zstd → put) до любых правок движка | диагностика, 0 строк в armdb | нулевая | нет |
| **D1** | **VarTree вместо ConstTree** и по диску: фикс-размер `V` паддит каждое значение до максимума | ConstTree 11.4 → VarTree 8.5 ГБ | нулевая — выбор типа | нет |
| **D2** | **Ужать заголовок 16 Б**: varint `value_len`, delta-GSN внутри блока, опц. CRC под блочной контрольной суммой | ~10–25% при значениях в десятки байт | высокая — ломает zerocopy-`EntryHeader` и recovery-скан | высокий |
| **D3** | **Блочное фреймирование + prefix-compression ключей при compaction** (zstd опционально) | средне; для rapira — в осн. за счёт общих префиксов ключей и амортизации заголовков | высокая — `DiskLoc` → блочная адресация, hint-формат, catch-up репликации | высокий |

**Честный вывод по диску.** При rapira-значениях сжатие тела даёт ~1.2–1.5× и не
окупает инвазивность D2/D3 (это же зафиксировано в qa.md). Дешёвые и безопасные
рычаги — **D0** (проверить ratio данных) и **D1** (не платить за фикс-слоты
Const). Заголовок 16 Б + ключ — главный «жир» именно для очень мелких значений,
но трогать его (D2) дорого: формат заголовка `zerocopy`-fixed и его сканирует
recovery. D3 разумно лишь если D0 покажет компрессируемость или если профиль
сместится в крошечные значения, где доминирует заголовок.

---

## 4. Потолок модели (раз «можно шире»)

Bitcask держит весь keydir в RAM **по определению**. Дешёвые правки R1–R3
снимают 25–45% константного overhead на запись, но не меняют класс: RAM растёт
линейно с числом ключей. На **миллиардах** мелких записей никакая
внутри-индексная оптимизация не победит индекс, живущий на диске. Честные выводы
на этом масштабе:

- **R4 (ART)** — остаётся в модели armdb, но это полноценный проект.
- **R5 (ленивый keydir)** — компромисс: горячие шарды в RAM, холодные читаются
  через hint-файлы; естественно ложится на time-partitioned сообщения.
- **Взять fjall для коллекции сообщений** — 1 ГБ против 6.6 ГБ RAM при том же
  диске. Если коллекция сообщений — самая большая и холодная, это самый честный
  ответ; armdb остаётся для горячих/мелких/fixed-коллекций.

Co-location нескольких коллекций в одном логе (из qa.md) экономит **fd и
директории, но не RAM индекса** — это ортогональная проблема и здесь не помогает.

---

## 5. Рекомендации по масштабу

| Масштаб на узел | Что делать |
|---|---|
| **Миллионы – десятки млн** | R0 + R1 + R2 (+ D0/D1). Дёшево, низкий риск, закрывает вопрос: VarTree ~51 Б/запись, индекс в единицах ГБ. |
| **Сотни млн** | То же + всерьёз оценить R3 (insert-once) и R5 (ленивый keydir). Индекс уже десятки ГБ — пора думать структурно. |
| **Миллиарды** | R4 (ART) как отдельный проект **либо** fjall для коллекции сообщений. Внутри-Bitcask правок недостаточно. |

**Порядок действий, независимо от масштаба:** сначала R0/D0/D1 (бесплатно и сразу
меряет реальность), затем R1+R2 (дешёвая RAM-дорожка с понятным риском), и только
по результатам профилировки на реальных данных — структурные R3–R5 или смена
движка.

---

## Приложение: ссылки на код

- `armdb/src/skiplist/node.rs` — `VarNode` / `ConstNode` / `TypedNode`, layout и SeqLock/RCU.
- `armdb/src/disk_loc.rs` — `DiskLoc` (16 Б).
- `armdb/src/entry.rs` — `EntryHeader` (16 Б), `entry_size`, формат записи.
- [qa.md](./qa.md) — разбор сжатия Var-коллекций, co-location, fd-бюджет.
