# Bug: VarTree concurrent compaction causes transient read corruption

**Status**: исправлен
**Severity**: средний — данные на диске корректны, corruption только in-memory при concurrent reads
**Затронуты**: `VarTree`, `VarMap` (типы, читающие значения с диска)
**Не затронуты**: `ConstTree`, `ConstMap`, `ZeroTree`, `ZeroMap`, `TypedTree`, `TypedMap` — значения inline в памяти

## Симптомы

`VarTree::get()` возвращает zeros или значение от другого ключа **во время**
concurrent compaction. После close + reopen все данные корректны.

Corruption **transient** — только в in-memory read path, не персистентный.

```
key=130 → stored=0   (все нули)
key=93  → stored=490 (чужое значение)
key=42  → stored=4138414780148875264 (мусор)
```

## Воспроизведение

```sh
# В stress_concurrent_var включить compaction + flush threads (сейчас отключены):
cargo test -p armdb --test stress_tests stress_concurrent_var -- --ignored --nocapture
```

Конфигурация: 6 threads × 100K ops, zipfian 10K keyspace, shard_count=8,
max_file_size=64KB, cache=16MB, compaction_threshold=0.2.

## Что проверено (НЕ причина)

| Гипотеза | Результат |
|----------|-----------|
| Block cache cross-shard (shard_id в BlockKey) | Исправлено — отдельный баг, single-thread corruption ушёл |
| `quick_cache` concurrent bug | НЕТ — corruption воспроизводится с `cache.max_size = 0` |
| macOS F_NOCACHE | НЕТ — corruption без F_NOCACHE тоже |
| TOCTOU в `update_if_match` | НЕТ — shard lock сериализует `put` и `update_if_match` |

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

- **Single-thread** + compaction: OK (proptest + `stress_compaction_pressure`)
- **Multi-thread** без compaction: OK (`stress_concurrent_var` с отключённым compaction)
- **Multi-thread** + compaction: **CORRUPT** (transient)
- **Post-reopen verification**: всегда OK — данные на диске корректны

## Гипотезы

### 1. `read_block` отпускает shard lock перед pread

`Shard::read_block()` берёт shard lock кратко (чтобы получить file handle),
потом отпускает и делает `pread_block` без lock. Concurrent flush (`write_all_at`)
или rotation может менять файл пока `pread_block` читает.

```
read_block:                         flush thread:
  lock shard
  get read_file handle
  unlock shard
                                      lock shard
                                      write_all_at(data, offset)
                                      reset buffer
                                      unlock shard
  pread_block(read_file, offset)
  → reads partially-written or
    stale data?
```

### 2. Окно между `update_if_match` и добавлением нового файла

Compaction обновляет DiskLoc на `new_file_id` в batch processing, но добавляет
новый файл в immutable list только после обработки ВСЕХ записей. В этом окне:

- DiskLoc → {new_file_id, offset}
- `read_block(new_file_id, ...)` → NOT FOUND (файла нет в immutable list)
- Но это должно возвращать `None`, а не wrong data

### 3. `write_all_at` не атомарна

`write_all_at` вызывает `pwrite` в цикле. Между итерациями concurrent `pread`
видит partially-written data. Это объясняет "got 0" (zeros в ещё не записанной
части файла).

## Обходное решение

Compaction thread отключён в `stress_concurrent_var`. VarTree compaction
работает корректно в single-threaded режиме (proptest, `stress_compaction_pressure`).

## Файлы для исследования

| Файл | Что смотреть |
|------|-------------|
| `armdb/src/shard.rs:365` | `read_block` — отпускает lock перед pread |
| `armdb/src/shard.rs:596` | `flush_write_buf_plain` — write_all_at под shard lock |
| `armdb/src/compaction.rs:239` | Batch processing — update_if_match под shard lock |
| `armdb/src/compaction.rs:330` | Добавление нового файла в immutable list |
| `armdb/src/var_tree.rs:598` | `read_value_cached` — 3-step read path |
| `armdb/tests/stress_tests.rs` | `stress_concurrent_var` — воспроизводящий тест |

## Причина и Решение (Исправлено)

### Причина бага
Окно гонки (race condition) происходило из-за того, что компакция **переиспользовала ID старого файла** для нового файла (`let new_file_id = files_to_compact.last().unwrap().file_id;`) и обновляла индексы порциями (batches) еще до того, как новый файл был готов и добавлен в `inner.immutable`.

Когда `update_if_match` обновлял индекс `DiskLoc`, чтобы указывать на `new_file_id` с новыми смещениями (offset) из файла `.data.tmp`, любой конкурирующий читающий поток делал следующее:
1. Запрашивал этот `file_id` из списка `inner.immutable`.
2. Находил **СТАРЫЙ** файл, так как подмена на новый файл происходила только в самом конце компакции.
3. Пытался прочитать данные из старого файла по смещению, взятому из нового файла.

Если новое смещение выходило за границы старого файла, `pread_block` получал `EOF`, заполнял буфер нулями, и база возвращала `stored=0`. Если смещение попадало внутрь старого файла, база читала данные от другого ключа (чужое значение) или просто мусор.

### Исправление
1. **Новый генератор ID**: В `ShardInner` добавлено поле `next_file_id`, чтобы файлы, создаваемые при ротации и компакции, всегда получали уникальный, инкрементальный идентификатор.
2. **Безопасная подмена**: В `compact_shard_inner` `update_if_match` теперь не выполняется в процессе сканирования.
3. Сначала генерируется `00000X.data.tmp`.
4. Затем этот файл переименовывается в `00000X.data` и атомарно добавляется в `inner.immutable` как полностью готовый к чтению (с новым, уникальным `new_file_id`).
5. **Только после этого** происходит итерация по `batch` и обновление in-memory индекса через `update_if_match`. Читающие потоки, увидевшие новый `DiskLoc`, идут в `inner.immutable`, находят там новый файл и безопасно читают данные из него.
6. В самом конце старые файлы удаляются из памяти (`inner.immutable`) и с диска.

Стресс-тест `stress_concurrent_var` с включенной компакцией теперь успешно проходит 600 000 параллельных операций без transient data corruption.

### Влияние на производительность (Memory & Resource Trade-off)
Изменения **не влияют** на скорость основных операций чтения и записи. Lock contention шарды также остался прежним (обновление индекса всё ещё происходит батчами по 256 элементов с перезахватом лока).

Однако, для обеспечения корректности данных, были внесены следующие компромиссы:

1.  **Потребление памяти при компакции (Background RAM):**
    *   Раньше вектор `batch` очищался каждые 256 записей. Теперь мы аккумулируем адреса **всех** переносимых записей (включая tombstone-ы) в `batch` до тех пор, пока полностью не запишем новый `.data` файл.
    *   При размере `BatchEntry` около 56 байт (для 16-байтного ключа), компакция 4 файлов по 256 МБ (~4 млн записей по 256 байт) может дополнительно потреблять **~224 МБ оперативной памяти** на протяжении одной операции.
    *   Включение tombstone-ов в `batch` дополнительно увеличивает расход RAM в базах с большим количеством удалений.

2.  **Потребление памяти при восстановлении (Recovery RAM):**
    *   Для `VarTree` восстановление теперь использует `HashMap<Vec<u8>, u64>` для отслеживания актуального GSN каждого ключа.
    *   Это создает временную нагрузку на память (примерно **40–60 байт на каждый уникальный ключ**) во время выполнения `open()`. Память освобождается сразу после загрузки индекса.

3.  **Дисковое пространство:**
    *   Tombstone-ы теперь сохраняются в компактированных файлах до тех пор, пока они не будут гарантированно перекрыты живой записью в памяти или не попадут в компакцию вместе с самыми старыми файлами базы. Это может временно увеличить размер файлов данных на диске.

Для систем с NVMe и гигабайтами RAM эти накладные расходы пренебрежимо малы по сравнению с гарантированной защитой от потери данных и транзитных ошибок чтения.

---

## Сопутствующий баг: Recovery ordering + tombstone loss after compaction

**Status**: исправлен (полностью)
**Severity**: высокий — **persistent** data corruption (ключи воскресают после close/reopen)
**Обнаружен**: proptest `var_tree_model_test` (~2 из 3 запусков фейлит)

### Симптомы

После `Compact → CloseReopen` (или `Compact → Delete → CloseReopen`) дерево содержит
**лишние ключи**, которые должны были быть удалены. Модель (BTreeMap) ожидает N записей,
дерево возвращает N+k (обычно k=1..3).

```
assertion: len mismatch after reopen at op 165
  left: 40    (дерево)
  right: 37   (модель)
```

### Воспроизведение

```sh
cargo test -p armdb --test proptest_model var_tree_model_test
# Фейлит ~2/3 запусков. const_tree_model_test проходит (inline values).
```

### Две причины

#### 1. Recovery ordering (частично исправлено)

`next_file_id` даёт компактированному файлу ID **выше** active file. Recovery
обрабатывает файлы по возрастанию file_id. Компактированный файл обрабатывается
**последним** и `recover_var_hint` / `recover_var_full_scan` безусловно перезаписывали
DiskLoc при `InsertResult::Exists`, не проверяя GSN. Старые entries из компактированного
файла затирали свежие entries из active file.

**Частичный fix**: в `recover_var_hint` и `recover_var_full_scan` добавлен
`HashMap<Vec<u8>, u64>` (key_bytes → max_gsn). Swap выполняется только если GSN
нового entry выше. Tombstone'ы также записывают свой GSN в map, предотвращая
воскрешение удалённых ключей из компактированных файлов.

#### 2. Tombstone loss при compaction (НЕ исправлено)

Compaction **drop'ает tombstone'ы** (`if !header.is_tombstone() { ... }`).
Если tombstone и старый Put для одного ключа находятся в **разных** файлах,
и compaction обрабатывает ТОЛЬКО файл с tombstone:

1. Файл A (не компактируется): содержит старый `Put(key_X)` с GSN=50
2. Файл B (компактируется): содержит `Delete(key_X)` с GSN=100
3. Compaction: файл B → tombstone drop'ается, `update_if_match` → false (key не в индексе)
4. Файл B удаляется, tombstone потерян
5. Recovery: файл A загружается → `Put(key_X)` с GSN=50 → key_X **воскрешает**

`key_gsn` map не помогает: tombstone из файла B больше не существует ни в каком файле.

### Варианты решения tombstone loss

| Подход | Сложность | Описание |
|--------|-----------|----------|
| **Tombstone retention (Реализован)** | Средняя | Компакция сохраняет tombstone'ы в компактированном файле, если в in-memory индексе нет живой (`Put`) записи для этого ключа. Удаляет tombstone только когда он гарантированно перекрыт более новой записью в индексе. |
| **Compaction scope** | Низкая | Компактировать ТОЛЬКО файлы с file_id ≤ min(компактируемых), гарантируя что все более старые Put уже включены |
| **Persistent tombstone log** | Высокая | Отдельный файл с активными tombstone'ами, переживающий compaction |
| **Full keyspace scan** | Высокая | При compaction проверять ВСЕ файлы на наличие Put для удаляемых ключей |

### Как было исправлено (Tombstone Retention + GSN Check)

1. **Исправление `recovery.rs`**: В `recover_var_hint` и `recover_var_full_scan` при обработке tombstone мы теперь проверяем `key_gsn`. Если встреченный tombstone имеет `GSN` меньше, чем уже известный (например, из-за нарушения хронологического порядка `file_id` у компактированных файлов), мы его игнорируем и **не вызываем** `index.remove(key)`. Это предотвращает удаление свежих данных старыми tombstone-ами.
2. **Интерфейс `CompactionIndex`**: Добавлен метод `contains_key(&self, key: &K) -> bool`, который позволяет проверить наличие живой записи в индексе для всех типов деревьев.
3. **Исправление `compaction.rs`**: Цикл сканирования больше не отбрасывает tombstone-ы слепо (`if !header.is_tombstone()`). Tombstone-ы теперь собираются в батчи вместе с обычными записями.
4. В процессе итерации батча:
   - Если это tombstone и `index.contains_key()` возвращает `true` (есть более свежая живая запись), tombstone **отбрасывается**.
   - Если `index.contains_key()` возвращает `false` (запись реально удалена), tombstone **сохраняется** в новом компактированном файле и `.hint` файле, чтобы "перекрывать" старые записи из более старых файлов при следующих восстановлениях базы.

Все тесты (`cargo test` и `proptest_model`) успешно проходят. Баг полностью устранён.

### Файлы затронутые fix'ом

| Файл | Изменение |
|------|-----------|
| `armdb/src/compaction.rs` | Добавлен `contains_key`, tombstone'ы переносятся, если не перекрыты |
| `armdb/src/recovery.rs:452` | `recover_var_hint` — GSN check для tombstone |
| `armdb/src/recovery.rs:660` | `recover_var_full_scan` — GSN check для tombstone |
| `armdb/src/recovery.rs:207` | `recover_var_tree` — `HashMap<Vec<u8>, u64>` per shard |
| Все `*_tree.rs`, `*_map.rs` | Реализован метод `contains_key` для `CompactionIndex` |
