# 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 Б значения)
| 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 (ранжировано: выигрыш / цена / риск)
| **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-бюджет.