# R1/R2 (RAM-индекс) — разведка кода и выбор размера DiskLoc

> **Статус:** временная рабочая записка для ревью вторым агентом. Не спека.
> Контекст: `armdb/docs/space-optimization.md`, дорожка RAM, пункты **R1** и **R2**.
> Цель записки — (1) зафиксировать факты из кода, (2) обосновать развилку
> представления `DiskLoc` (12 байт vs 8 байт), (3) перечислить, на что ещё это
> повлияет, и (4) собрать открытые вопросы. Реализация не начата.
> Все ссылки — `file:line` на момент разведки (ветка `main`).

## 0. Что такое R1 и R2 (из space-optimization.md)

- **R1** — инлайнить `DiskLoc` в узел индекса через SeqLock (как в `ConstNode`),
  убрать `Box`. Выигрыш ~8–16 Б/запись + убирает отдельную аллокацию и
  cache-miss на чтении. Документ оценивает риск как низкий.
- **R2** — ужать `DiskLoc` 16 → 12 Б, убрав `shard_id`+pad (шард известен из
  контекста узла). Ещё ~4–8 Б/запись. Риск низкий.

## 1. Текущее состояние кода (факты)

### 1.1 DiskLoc — 16 байт (`armdb/src/disk_loc.rs`)

```rust
#[repr(C)]
pub struct DiskLoc {
    pub offset: u32,    // байтовый offset значения внутри файла
    pub len: u32,       // длина значения (== value_len в EntryHeader)
    pub file_id: u32,   // монотонный id файла, ПЕР-ШАРД
    pub shard_id: u8,   // <-- кандидат на удаление в R2
    _pad: [u8; 3],      // <-- паддинг, уходит вместе с shard_id
}
// test disk_loc_size_is_16, align == 4
```

### 1.2 Два разных индекса под Bitcask

| Коллекция | Индекс | Хранение DiskLoc |
|---|---|---|
| **VarMap** | `[Mutex<HashMap<K, DiskLoc>>]` (per-shard) — `var_map.rs:693` | **уже inline, by-value** |
| **VarTree** | lock-free skiplist из `VarNode<K>` — `skiplist/node.rs` | **`AtomicPtr<DiskLoc>` + `Box`** |
| **ConstTree** | skiplist из `ConstNode<K,V,L>` | **inline `UnsafeCell<L>` + SeqLock** |
| **TypedTree** | skiplist из `TypedNode<K,T>` | `AtomicPtr<TypedData{disk,value}>` + `Box` |

Вывод: **R1 (убрать Box) актуален только для `VarNode`** (skiplist у `VarTree`).
У `VarMap` (HashMap) `DiskLoc` уже лежит по значению — там R1 нечего убирать,
работает только R2 (ужатие самой структуры).

### 1.3 ConstNode уже реализует целевой паттерн R1+R2

`skiplist/node.rs:95-237`. `ConstNode<K, const V, L: Location = DiskLoc>`:
- `seq: AtomicU64` + `loc: UnsafeCell<L>` + `value: UnsafeCell<[u8;V]>` — SeqLock.
- Читатели: `read_loc()` / `read_value()` спинят на чётности `seq`, читают по
  значению (без захода в кучу).
- Писатели: `write_loc()` / `write_data()` под shard-mutex (single writer),
  bump `seq` нечёт→чёт.
- Нет per-loc аллокации, нет seize-retire для данных.

Трейт `Location` (`key.rs:39-53`) **уже декларирует «DiskLoc 12 байт»**, и
`ConstNode` уже generic over `L` (`DiskLoc` для Bitcask, `u32` slot_id для
FixedStore). То есть скелет R2 заложен в типах, но сам `DiskLoc` ещё 16 Б.

### 1.4 VarNode — боксированный AtomicPtr (`skiplist/node.rs:295-376`)

```rust
pub struct VarNode<K: Key> {
    pub key: K,
    pub disk: AtomicPtr<DiskLoc>,   // указывает на Box<DiskLoc>
    mark: AtomicBool,
    height: u8,
    tower_ptr: *const AtomicPtr<Self>,
}
```

- `alloc`: `Box::into_raw(Box::new(disk))` — отдельная куча-аллокация на запись.
- `load_disk() -> &DiskLoc` — читатель идёт по указателю в кучу (cache-miss).
- `swap_disk` / `compare_exchange_disk` — RCU-указатель + seize-retire старого Box.

## 2. R1 — анализ (де-боксинг VarNode)

### 2.1 Модель конкуренции уже совпадает с ConstNode

Оба писателя в `VarNode.disk` сериализованы **shard-mutex**:
- `put_locked(&self, …, inner: &mut ShardInner, …)` получает уже залоченный шард
  (`var_tree.rs:396`) и делает `swap_disk` под этим локом.
- Компакция держит `shard.lock()` вокруг `update_if_match`
  (`compaction.rs:451` берёт лок, `:473` зовёт `update_if_match`).

Значит CAS (`compare_exchange_disk`) у `VarNode` **дублирует** блокировку — он
ловит рассинхрон между снимком `old_loc` (снятым ДО входа в критическую секцию
при построении batch) и текущим состоянием. Это «match-проверка», а не защита
writer-vs-writer.

`ConstTree::update_if_match` (`const_tree.rs:180-189`) делает ровно то же без CAS:
```rust
if node.read_loc() == old_loc {  // match-проверка
    node.write_loc(new_loc);     // запись под shard-lock
    return true;
}
```
`VarTree::update_if_match` (`var_tree.rs:167-195`) — то же, но через
`compare_exchange_disk` поверх Box.

### 2.2 Что меняет R1

`VarNode` становится зеркалом `ConstNode` (без `value`):
```rust
pub struct VarNode<K: Key> {
    pub key: K,
    seq: AtomicU64,            // +8 Б — SeqLock
    loc: UnsafeCell<DiskLoc>,  // inline (12 Б после R2), без Box
    mark: AtomicBool,
    height: u8,
    tower_ptr: *const AtomicPtr<Self>,
}
```
- Читатели: `load_disk() -> &DiskLoc` → `read_loc() -> DiskLoc` (по значению).
  ~30 call-сайтов в `var_tree.rs` уже разыменовывают в значение
  (`let disk = *node.load_disk();`) — правка механическая.
- Компакция: `compare_exchange_disk` → `read_loc()==old` + `write_loc()` под
  shard-lock (как Const). CAS уходит вместе с Box.
- Уходит: per-put Box-аллокация + seize-retire `DiskLoc`. Это плюс и к памяти,
  и к скорости записи, и к латентности чтения (нет cache-miss в кучу).

### 2.3 Память (ключ 8 Б)

| | Сейчас | После R1 (loc 16Б) | После R1+R2 (loc 12Б) |
|---|---|---|---|
| VarNode | ~32 Б | key8+seq8+loc16+mark/height+tower8 ≈ 48 Б | …+loc12 ≈ 40 Б |
| Box\<DiskLoc\> | ~24–32 Б (16 payload + накладные аллокатора) | — | — |
| **Итого/запись** | **~56–64 Б** | **~48 Б** | **~40 Б** |

(Документ оценивал ~67–75 Б — он включал также башню указателей ~11 Б; здесь
показан только узел+loc. Порядок экономии тот же: де-боксинг снимает ~16–24 Б,
R2 ещё ~8 Б за счёт меньшего `loc` и выравнивания.)

### 2.4 Риск R1 — низкий, но с одной проверкой

Прецедент (`ConstNode`) уже в проде, есть loom/miri-обвязка для SeqLock.
Единственное, что обязан подтвердить implementer: **все** пути записи в
`VarNode.disk` идут под shard-mutex (put fast/slow, atomic-блок, миграция,
репликация catch-up). Если найдётся путь без лока — там SeqLock сломается
(SeqLock допускает ровно одного писателя). Проверял put — под локом; нужно
прозвонить atomic()/replication/recovery.

## 3. R2 — анализ (ужатие DiskLoc, удаление shard_id)

### 3.1 shard_id — чистый in-memory дубликат

- `DiskLoc.shard_id` присваивается в `append_entry(shard_id, …)`, где
  `shard_id = shard_for(key)` (`var_map.rs:705`, `var_tree.rs` put).
- На чтении он используется только чтобы достать `engine.shards()[disk.shard_id]`.
  Но вызывающий **уже знает** шард: он только что взял `indexes[shard_id]` или
  посчитал `shard_for(key)`.
- **На диске shard_id отсутствует.** Hint-entry = `GSN(8)+Key+Offset(8)+Len(4)+CRC(4)`
  (`hint.rs:13`), без shard_id и без file_id — они неявны из пути файла
  (`<shard_dir>/NNN.hint`). При recovery `DiskLoc` пересобирается:
  shard_id ← из директории шарда, file_id ← из имени файла, offset/len ← из hint.

Вывод: **R2 не меняет on-disk формат вообще.** Это чисто in-memory правка
структуры + проброс `shard_id` из контекста в read-path.

### 3.2 Blast radius — ~21 callsite

`disk.shard_id` / `snap.shard_id` читается из снимка `DiskLoc` в:
- `var_tree.rs`: ~11 мест (885, 907, 2007, 2164, 2481, 2516, 2539, 2563, 2918,
  2997, …)
- `var_map.rs`: ~10 мест (773, 793, 1480, 1531, 1793, 1821, 1842, 1863, 2103,
  2165)

Все — в read-path/iterator/snapshot, где шард доступен из контекста. Правка
механическая (передать `shard_id`/`i` аргументом вместо чтения из `disk`), но
это ~21 точка, не «6 строк». `warmup` (`var_map.rs:491-520`) нужно перевести с
`for index in indexes` на `enumerate()`, чтобы взять `i as u8` вместо
`disk.shard_id`.

### 3.3 Риск R2 — низкий

Нет изменения диска, нет нового failure-mode, диапазоны u32 сохраняются.
Единственная цена — аккуратность на ~21 callsite + одно требование инварианта:
«shard, в чьём индексе лежит ключ, == shard, в чьих файлах лежит значение». Это
выполняется по построению (per-shard append), но стоит закрепить debug_assert.

## 4. РАЗВИЛКА: размер DiskLoc — 12 байт vs 8 байт

Любое представление > 8 Б нельзя прочитать одной атомарной операцией на ARM/x86
портабельно, поэтому **>8 Б ⇒ нужен SeqLock** (или боксированный RCU). Ровно 8 Б
⇒ помещается в `AtomicU64` ⇒ **SeqLock не нужен вовсе**. Поэтому осмысленных
вариантов два: **12 Б (SeqLock)** и **8 Б (AtomicU64)**. Промежуточные 10/14 Б
доминируются: всё ещё SeqLock, кривое выравнивание, частичная потеря диапазонов.

### 4.1 Текущие диапазоны (u32 каждый)

| Поле | Диапазон сейчас | Реальная граница |
|---|---|---|
| offset | 0..4 GiB | ≤ `max_file_size` ≤ u32::MAX (config.rs:156). Дефолт 256 MiB |
| len | 0..4 GiB | rapira `VEC_MAX_SIZE_OF` = 2 GiB |
| file_id | 0..4.29e9 | монотонный, **пер-шард**, растёт с ингестом+компакцией |

### 4.2 Вариант 12 Б (R2 как в документе)

`DiskLoc { offset:u32, len:u32, file_id:u32 }` = 12 Б, align 4. Просто убираем
`shard_id`+pad.

- **Плюсы:** полные диапазоны u32 сохранены; ноль новых лимитов; ноль изменений
  диска; помогает ВСЕМ Bitcask-коллекциям (VarMap+VarTree+ConstTree); риск
  низкий.
- **Минусы:** в `VarNode` всё ещё нужен `seq: AtomicU64` (+8 Б) и SeqLock-спин на
  чтении; узел ~40 Б.

### 4.3 Вариант 8 Б (бит-паковка в u64)

`PackedLoc(u64)` — `offset/len/file_id` упакованы битовыми полями. `VarNode.loc`
становится `AtomicU64`: **нет SeqLock, нет `seq`-счётчика (−8 Б), узел ~32 Б**,
читатель = одна атомарная загрузка + распаковка (нет спина, нет окна рваного
чтения), компакция = снова естественный lock-free `compare_exchange` на u64.

64 бита — это zero-sum split на 3 поля. Примеры (бит → лимит):

| Сплит | offset | len | file_id | файл ≤ | значение ≤ | файлов/шард | ингест/шард до wrap |
|---|---|---|---|---|---|---|---|
| **A** msgr-tight | 28 | 16 | 20 | 256 MiB | 64 KiB | 1.05M | 256 TiB |
| **B** balanced | 30 | 18 | 16 | 1 GiB | 256 KiB | 65.5K | 64 TiB |
| **C** value-room | 26 | 24 | 14 | 64 MiB | 16 MiB | 16.4K | 1 TiB |
| **D** big-id | 28 | 12 | 24 | 256 MiB | 4 KiB | 16.7M | 4 PiB |

(«ингест/шард до wrap» = файлов/шард × файл; компакция переписывает живое в новые
файлы, потребляя id сверх сырого ингеста — при insert-once space-amp ~1.1, так
что это близко к бюджету ингеста. **file_id пер-шард**, поэтому агрегатный потолок
= число шардов × значение в таблице, напр. 256 шардов × сплит A = 64 PiB.)

Для мессенджера (значения десятки–сотни байт, insert-once) комфортны A или D:
много бит на file_id (долгий lifetime) ценой `len`.

### 4.4 На что ещё повлияет 8-байтная паковка (важно для ревью)

1. **Конфиг ужесточается:** верхняя граница `max_file_size` падает с u32::MAX до
   `1<<offset_bits`. Пресет 1 GiB требует offset ≥ 30 бит; пресеты >1 GiB
   становятся невалидными. Нужна правка валидации + миграция пресетов.
2. **Новый runtime failure-mode:** put значения больше `1<<len_bits` обязан
   возвращать ошибку (`ValueTooLarge`). Сейчас принимается до 2–4 GiB. Меняется
   контракт put.
3. **Потолок file_id (САМЫЙ острый риск):** монотонный file_id когда-нибудь
   упрётся в `1<<file_id_bits`. Молчаливый wrap = порча адресации. Нужна жёсткая
   политика: (a) задокументировать потолок как недостижимый на целевом масштабе +
   hard-guard, который отказывает в записи у границы; (b) перенумерация файлов при
   компакции; (c) reset при полной компакции шарда. Минимум — guard, не молчать.
4. **VarNode → generic over `L`:** сейчас он жёстко на `DiskLoc`. Чтобы дать
   PackedLoc как opt-in (а 12 Б оставить дефолтом), `VarNode`/`VarTree` нужно
   сделать generic, как `ConstNode`/`ConstTree`. Это удваивает матрицу тестов/loom.
   Альтернатива — PackedLoc заменяет DiskLoc целиком (тогда лимиты у ВСЕХ
   коллекций, что для general-engine спорно).
5. **Распаковка на горячем пути:** мелкие бит-операции на каждом get (unpack) и
   put (pack). Дешевле, чем SeqLock-спин; по сути убирает спин с чтения.
6. **Диска по-прежнему не касается:** `DiskLoc` in-memory, recovery собирает
   индекс из hint(offset/len)+контекста(shard/file). Даже 8 Б — чистая
   in-RAM перепаковка; единственное условие — реальный file_id из hint должен
   влезать в `file_id_bits` (иначе старый каталог не откроется → нужна проверка
   при recovery).
7. **Бонус concurrency:** AtomicU64 возвращает компакции честный lock-free CAS
   без shard-lock-зависимости — это даже чище текущей боксированной модели и
   модели ConstNode SeqLock-под-локом.

### 4.5 Третий путь (гибрид)

12 Б `DiskLoc` как дефолт для всех + opt-in `PackedLoc(u64)` через generic
`VarNode`/`VarTree` (трейт `Location` уже это допускает). Мессенджер берёт
`VarTree<MsgKey, PackedLoc>` (8 Б, максимум экономии и лимиты ок для его данных),
general-коллекции — `VarTree<K, DiskLoc>` (12 Б, полные диапазоны). Цена —
generic-VarNode + удвоение тестовой матрицы (как у Const).

### 4.6 ВЫНОС file_id в таблицу слотов (ключевая идея ревью)

8-байтная паковка §4.3 «одни компромиссы» в основном из-за `file_id`: 32-битный
монотонный id — **lifetime-bound** ресурс (растёт с ингестом+компакцией → wrap).
Развитие принципа R2 («не хранить per-value то, что выводится из группировки»):

- `shard_id` вынесен в **раздел индекса** (`indexes[i]`) — бесплатно, группировка
  уже есть.
- `file_id` можно вынести в **per-shard таблицу слотов**: значение хранит
  маленький `slot`, а таблица `slot -> FileMeta(real file_id, fd, …)` — одна
  запись на *живой* файл, не на value.

**Почему это снимает главный риск.** `slot` индексирует только живой набор файлов
шарда (`active` + `immutable: Vec`, shard.rs:106-138). Файл удалён компакцией →
слот свободен → переиспользован. Это **live-bound**, а не lifetime-bound: wrap
невозможен (живых файлов не больше, чем влезает на диск). 14 бит = 16384 живых
файла/шард.

**Бонус — быстрее на чтении.** Сейчас `resolve_block_refs(file_id)` —
**линейный** `immutable.iter().find(|f| f.file_id == id)` (shard.rs:1222-1239).
Прямой индекс по слоту делает это O(1). Плюс существующий guard
`next_file_id == u32::MAX` (shard.rs:1119) перестаёт быть проблемой.

Бит-бюджет со slot (slot — LIVE-bound, не lifetime):

| Сплит | offset | len | slot | файл ≤ | значение ≤ | живых файлов/шард | live/шард |
|---|---|---|---|---|---|---|---|
| offset-full | 32 | 18 | 14 | 4 GiB | 256 KiB | 16384 | 64 TiB |
| **balanced** | 30 | 20 | 14 | 1 GiB | **1 MiB** | 16384 | 16 TiB |
| value-room | 28 | 22 | 14 | 256 MiB | 4 MiB | 16384 | 4 TiB |

Строго доминирует §4.3 (сырой file_id): и лимит значения больше, и wrap-риска нет.

**Новые издержки слот-таблицы:**
1. Стабильный аллокатор слотов per-shard (`Vec<Option<FileMeta>>` + free-list);
   slot стабилен, не позиция в `immutable`. Мутации под shard-lock (писатели там).
2. Инвариант переиспользования: слот освобождается только когда у файла 0 живых
   ссылок в индексе — ровно текущее поведение компакции (переносит живые записи
   через `update_if_match` до удаления старого файла). Сохранить + debug_assert.
3. Кэш блоков ключуется на **реальный file_id**, не на slot (slot
   переиспользуется → алиасинг). На get резолвим slot→real_file_id (O(1) read)
   для `BlockKey`. Сейчас кэш уже инвалидируется per-file при компакции
   (`invalidate_blocks(shard_id, file_id, …)`).
4. Recovery раздаёт слоты файлам в отсортированном порядке при открытии. On-disk
   формат не меняется (file_id в hint и так нет).
5. Guard на >2^slot_bits живых файлов.

### 4.7 Можно ли вынести и `len`?

`len` — единственное реально per-value поле кроме `offset`, но оно есть на диске
(`EntryHeader.value_len`, entry.rs:30). Можно убрать из индекса и читать заголовок
по `offset`. Для мелких значений (< 1 блока) заголовок в том же блоке → без
лишнего I/O. Цена: учёт dead-bytes на overwrite/delete
(`entry_size(K, old.len)`) потребует чтения старого заголовка — для insert-once
дёшево, для general — лишние reads. **Не в первый заход.** Если убрать и file_id,
и len → DiskLoc = только `offset` (≤4 GiB = u32 = **4 байта**), теоретический пол
Bitcask, но read-path-цена не окупается.

### 4.8 Иерархия выноса полей (сводно)

| Поле | Куда выносится | Цена | Статус |
|---|---|---|---|
| shard_id | раздел индекса `indexes[i]` | бесплатно | R2 baseline |
| file_id | per-shard слот-таблица | O(1) индирекция, быстрее read, аллокатор+инвариант | **сильный кандидат** |
| len | on-disk EntryHeader | reads на overwrite/delete | пропустить 1-й заход |
| offset | (несжимаемо) | — | остаётся |

## 5. Сводка вариантов

| | 12 Б SeqLock | 8 Б AtomicU64 | 12 Б + opt-in 8 Б |
|---|---|---|---|
| Экономия RAM/запись (VarTree) | де-Box + ~8 Б | де-Box + ~16 Б (нет seq) | по выбору коллекции |
| Новые лимиты | нет | да (файл/значение/file_id) | только у opt-in коллекций |
| Изменение диска | нет | нет | нет |
| Concurrency | SeqLock-под-локом | atomic store/CAS (проще) | оба |
| Объём работы | R1+R2, ~21 callsite | + конфиг/ошибки/guard file_id | + generic VarNode, ×2 тесты |
| Риск | низкий | средний (file_id wrap, контракт put) | средний (объём) |
| Помогает | всем Bitcask | VarTree (или всем, если замена) | всем + макс. для opt-in |

## 6. Открытые вопросы к ревьюеру

1. armdb — general-purpose движок или допустимо «заточить» под мессенджер?
   От этого зависит, приемлемы ли жёсткие лимиты 8-байтного варианта глобально.
2. Какой реальный потолок по: размеру файла, размеру значения, объёму ингеста на
   шард за жизнь БД? Это напрямую задаёт, проходит ли какой-либо 64-битный сплит.
3. Терпим ли новый failure-mode «значение слишком большое» на put?
4. file_id-wrap: какую политику у границы считаем приемлемой (guard-отказ vs
   перенумерация при компакции)?
5. Стоит ли сразу делать `VarNode` generic over `Location` (гибрид), или это
   преждевременно (YAGNI) и берём один из крайних вариантов?
5b. Слот-таблица (§4.6): согласны ли с выносом file_id? Какую ширину slot брать
   (14/16 бит) и какой потолок живых файлов/шард считать безопасным? Готовы ли на
   инвариант «слот свободен ⇔ 0 живых ссылок» как формальный контракт компакции?
6. Микро: `tower_ptr` (8 Б/узел) хранится ради provenance под Stacked Borrows —
   документ отмечает, что его можно пересчитывать из базы аллокации и снять ещё
   8 Б. Класть в этот же заход или отдельно?

## 7. Предварительная рекомендация автора разведки

- **R1 — делать безусловно**, это явный выигрыш по RAM, скорости записи и
  латентности чтения при низком риске; модель уже доказана `ConstNode`.
- **R2 — делать в варианте 12 Б как baseline** (полные диапазоны, ноль изменений
  диска, помогает всем коллекциям, риск низкий). ~21 callsite — терпимо.
- **8 Б через слот-таблицу (§4.6) — целевой дизайн, но крупнее.** Сырая паковка
  file_id (§4.3) — «одни компромиссы» и wrap-риск; вынос file_id в per-shard
  слот-таблицу убирает wrap (slot — live-bound), даёт лимиты вровень с пресетами
  (1 MiB значение / 1 GiB файл), убирает SeqLock (AtomicU64) и **ускоряет read**
  (O(1) вместо линейного `find`). Цена — слот-аллокатор + инвариант
  переиспособления + recovery-раздача слотов. Это разумная вторая фаза.
- **Возможный порядок:** Фаза 1 = R1 + R2(12 Б) — дёшево, низкий риск, помогает
  всем. Фаза 2 = вынос file_id в слот-таблицу + opt-in `PackedLoc(u64)` 8 Б через
  generic `VarNode` (трейт `Location` уже готов). `len`-вынос (§4.7) — не делать.
- Принимать 8 Б желательно после замера R0 (VarTree vs Const на реальных данных) и
  ответов на вопросы 1–5.

— подготовлено агентом Claude (Opus 4.8, 1M), разведка по ветке `main`.
