# Bitcask compaction does not reclaim dead bytes under overwrite churn

- **Status:** RESOLVED (2026-06-18). Two distinct issues, fixed in sequence:
  1. **Reclaim correctness** (commit `fa17afe`): the compaction scan copied
     **every** entry (live + dead) into the new file verbatim, so the output
     equaled the input in size and reclaim was ≈0. Fixed by skipping superseded
     entries during the scan. Regression test:
     `const_tree::tests::compaction_reclaims_dead_bytes_under_overwrite_churn`.
     See **Root cause (confirmed)** below.
  2. **Continuous-write throughput** (this branch): after `fa17afe` the benchmark
     still showed unbounded disk growth — but **not** because reclaim was broken.
     Root cause was a per-pass throttle (`truncate(4)`) plus a misread metric. See
     **⚠️ Continuous-write gap — RESOLVED** below.

## Root cause (confirmed)

`compact_shard_inner` (`armdb/src/compaction.rs`) had a two-phase structure:
phase 1 scanned the selected source files and **unconditionally copied every
entry** into the new output file (`direct::pwrite_at` in the scan loop); phase 2
(the batched index pass) then decided liveness and merely re-credited the
already-copied superseded entries as `dead_bytes` **on the new output file**.

Net effect under overwrite/delete churn:
- the output file was the same total size as the inputs (all versions copied),
- the dead bytes copied forward made the new file an immediate compaction
  candidate again → endless copy-forward, **zero reclaim**,
- on-disk size tracked total bytes written, never the live set.

Reproduced deterministically (ConstTree, 500 keys × 40 overwrites, 64 KB files):
all 27 immutable files were 88–100% dead and **correctly selected**, yet after 32
`compact()` calls `immutable` stayed at 27 and disk stayed at 1,804,000 bytes =
**41× the 44,000-byte live set**; bytes reclaimed = 0.

This **refutes both hypotheses below**: accounting was correct (dead_bytes
reached ~100%), selection was correct (files were picked), and the `truncate(4)`
throttle (H2) is only a secondary throughput limiter — the root cause is that the
copy phase ignored liveness. After the fix the same scenario converges to exactly
the 44,000-byte live set (1.0×).

## Fix

Add a read-only `CompactionIndex::is_live(key, loc)` (true iff the index maps
`key` to exactly `loc`) and gate the scan copy on it: skip non-tombstone entries
that are not the live version, and tombstones whose key is present again. A
superseded entry can never become live again, so skipping is safe even under
concurrent writers; the existing post-copy `update_if_match` CAS remains the
authoritative guard for the live-then-overwritten race. Implemented for all
CompactionIndex types (Const/Zero/Typed/Var tree+map, VarTyped tree+map).

CRC is verified for every scanned entry **before** the liveness decision, so a
corrupt key cannot be mis-parsed, classified as superseded, and silently dropped
(it aborts compaction with `CrcMismatch` and preserves the source file instead).

### Crash-consistency (review P1)

`append_entry` buffers the new value in memory without disk I/O, and the index is
updated immediately — so the live version of a just-overwritten key may not be
durable yet while its previous value is still durable in a source file. Skipping
the old version and then deleting the source would lose the key entirely on a
crash before the buffer flush (notably for `hints=false` collections, whose
recovery does a full `.data` scan). Fixed by **flushing + fsyncing the active file
before deleting compacted source files**, so every key the index points at has a
durable on-disk home before its old copy is removed. Regression test:
`const_tree::tests::compaction_preserves_durable_value_when_overwrite_unflushed`.

### Scope / known limitation (review P2)

The reclaim fix fully recovers space under **overwrite** churn and reclaims the
dead **values** of deleted keys. It does **not** garbage-collect redundant
**tombstones**: a tombstone for a currently-absent key is treated as live and
copied forward (it may still be masking an older value in a not-yet-compacted
file). Repeated insert/delete of the same key therefore still accumulates
tombstones. Proper tombstone GC needs GSN-ordered cross-file analysis and is left
as a separate follow-up; it is not a regression (the pre-fix code copied
tombstones forward too).

## Tests

- `compaction_reclaims_dead_bytes_under_overwrite_churn` (ConstTree, hints off)
- `var_compaction_reclaims_dead_bytes_under_overwrite_churn` (VarTree, hints on,
  disk-backed reads)
- `compaction_aborts_on_corrupt_key_of_live_entry` (CRC-before-liveness)
- `compaction_preserves_durable_value_when_overwrite_unflushed` (crash-consistency)

## ⚠️ Continuous-write gap — RESOLVED

After `fa17afe` the benchmark still showed unbounded disk growth under a
*continuous concurrent overwrite* workload (`armdb-const` `fixed-update`,
`compact()` every 30s). The original write-up (below, kept for history)
concluded reclaim was still broken. **That conclusion was wrong** — it rested on
two measurement errors. The reclaim path is correct; the real cause was
throughput, not correctness.

### Root cause (two compounding errors, both confirmed by experiment)

1. **Per-pass throttle vs. a continuous writer (the actual disk-growth cause).**
   `compaction.rs` caps each `compact()` call at `files_to_compact.truncate(4)` —
   **4 immutable files per shard per call**. The bench calls `compact()` once,
   then `sleep(30s)` (`rust-storage-bench/src/db/builder.rs`). At ~600–800 files
   created per second (1.4M writes/s ÷ ~2000 entries per 64 KB file) versus 4
   files retired per 30s, removal is ~5000× too slow → on-disk size tracks total
   bytes written. Not a reclaim bug — a rate limit plus too-coarse cadence.
   Confirmed deterministically: with 135 fully-dead immutable files, **one**
   `compact()` call retires exactly 4
   (`const_tree::tests::compaction_max_files_per_pass_controls_backlog_drain`).

2. **Misread return value (the source of every "reclaim 0").** `compact()`
   returns `compacted_entries` — the count of **live** entries copied forward,
   **not** bytes reclaimed (`compaction.rs` `Ok(compacted_entries)`). `truncate`
   keeps the lowest file_ids, i.e. the **oldest** files, which under pure
   overwrite are 100% dead → 0 live entries copied → return 0 **even though
   space was freed**. The ad-hoc bench instrumentation logged this as
   `[compact] reclaimed 0 bytes` and inferred compaction was broken.

The "telemetry stayed 0" evidence in the **original report** below is likewise
meaningless: `running_compactions` / `time_compacting_us` are hard-coded to `0`
for non-Fjall backends in the bench (`src/db/mod.rs` `_ => 0`), so they read 0
even when armdb compaction runs perfectly.

**Refuted hypotheses (all about flush/accounting):** dead-byte accounting needs
no flush — `write_update` calls `add_dead_bytes` immediately, so after pure
overwrite churn **every** rotated immutable file is ~100% dead and selectable
with no flush at all. Regression test:
`const_tree::tests::dead_bytes_credited_on_immutable_files_without_flush`
(without flush: all 27 immutable files at ~99.6% dead, all cross the 0.30
threshold).

### Fix

- **armdb (`B`):** the per-pass cap is now the tunable
  `Config::compaction_max_files_per_pass` (default 4, `0` = unlimited drain in
  one pass) instead of the hard-coded `truncate(4)`. Threaded `Config → engine →
  ShardInner`, read under the lock in `compact_shard_inner`. Tests:
  `compaction_max_files_per_pass_controls_backlog_drain`,
  `config::tests::compaction_max_files_per_pass_default_and_override`.
- **bench (`A`):** `resolve_bitcask` sets `compaction_max_files_per_pass = 0`
  (bench-invariant; overridable with `--armdb-compaction-max-files-per-pass`), so
  one `compact()` per cycle drains the full backlog.

### Verification (bench, with the fix)

Repro from the original report, 55 s run, disk sampled from the bench's own
timeseries (`armdb-const fixed-update`, 64 KB files, 1 shard, 500 keys):

```
t(s):    1   10   20   30   36   38 │ 39   45   50   55
disk MiB:63  656 1321 1961 2284 2338│462  859 1187 1514
```

The single compaction pass that fired at t≈30 s (it took ~8 s to scan and
rewrite the whole backlog under the unlimited cap) **dropped disk 2338 → 462 MiB
in one pass — ~1.9 GB reclaimed**. Disk is now a **bounded sawtooth** (grow for
one interval, drain in one pass) instead of monotonic growth to 41 GB. The
sawtooth floor sits above the live set because the writer keeps appending during
the multi-second compaction; tightening the compaction interval (or shrinking
files) reduces the amplitude. Pre-fix, the same pass would have retired 4×64 KB =
256 KB.

**Benchmark status:** disk axis is valid again for Bitcask under churn — a sweep
can resume. Report the sawtooth peak/steady-state, not a single late sample.

---

### Original write-up (continuous-write gap — superseded by the RESOLVED section above)

The fix is verified in isolation (unit tests pass), but it does **not** resolve
the disk growth under the benchmark's *continuous concurrent overwrite* workload.
Re-verified 2026-06-18 with the fix built into `rust-storage-bench` (armdb
recompiled, `Compiling armdb v0.5.1`):

`armdb-const` `fixed-update` (true overwrite of a bounded keyset), compact()
every 30s, instrumented to log reclaimed bytes — disk grows linearly, reclaim
stays ≈0 across every config tried:

| config | disk | reclaim |
|---|---|---|
| default (512 MB files, 16 shards) | → 41 GB | 0 |
| `--armdb-max-file-bytes 32M`, 16 shards | → 15 GB | 0 / 9 bytes |
| 32 MB, **`--armdb-compaction-threshold 0.01`**, **1 shard** | → 14 GB | 0 |
| **64 KB files, 1 shard, 500 keys** (≈ unit-test config) | → 2.3 GB / **36 528 files** | 0 |

The last row is the tell: 500 keys overwritten millions of times → ~100% dead in
36 k immutable files, yet `compact()` selects nothing (reclaim 0). This **rules
out** selection threshold, shard count, file size, scale, and key
non-determinism (`to_key32` is a deterministic left-pad → real overwrites).

> **Correction:** the "reclaim 0" reading was `compacted_entries` (live entries),
> not bytes — see the RESOLVED section. Selection *was* picking files; the
> per-pass `truncate(4)` cap plus the 30 s cadence simply couldn't keep up.

**The one axis not covered by the passing unit tests:** they compact a
**quiesced** tree — write all N×M, `flush_buffers()`, then `compact()` in a loop
to convergence. The benchmark compacts **under live concurrent write load**,
every 30s, with no preceding flush. So `compaction_reclaims_dead_bytes_*`
green ≠ reclaim works under continuous writes.

**Hypotheses for the continuous-write regime (all later REFUTED):**
- dead bytes credited against the **active** file (or the in-memory write
  buffer) rather than the immutable files, so `inner.immutable` files show ~0
  dead at selection time (`compaction.rs:163`);
- compaction vs. writer contention on the shard lock leaves immutable dead-byte
  bookkeeping stale while files keep rotating;
- buffered (not-yet-flushed) supersessions don't credit dead until flush, and
  the bench never flushes during the run.

---

### Original report (hypotheses H1/H2 below were refuted — kept for history)

- **Status (original):** open — symptom reproduced & quantified; root cause
  inside the engine not yet confirmed line-by-line.
- **Found:** 2026-06-18, via the `rust-storage-bench` fork (branch `v1`,
  commit `2eabd40`) benchmarking armdb at `armdb` HEAD `4b3fd96` (0.5.1).
- **Severity:** high for write/overwrite-heavy workloads — on-disk size grows
  **unbounded**, tracking total bytes written rather than the live set.
- **Affected:** all six Bitcask collection types — `VarTree`, `VarMap`,
  `TypedTree`, `TypedMap`, `ConstTree`, `ConstMap`. **Not** FixedStore
  (`FixedTree`/`FixedMap`): in-place pwrite, no compaction, disk stays flat.

## Symptom

Under an overwrite-heavy workload (a fixed key set updated repeatedly), the
background `compact()` reclaims ≈0 bytes every cycle even though almost all
older data is dead (superseded by newer versions). On-disk size grows linearly
with total bytes written, never plateauing at the live-set size.

## Evidence

All runs: 1M keys, `fixed-update` (pure overwrite), Bitcask, `shard_count=16`,
`cache 512MB`, `enable_fsync=false`, `io_backend=Pwrite`, background
`collection.compact()` every 30s.

### Run A — default file size (`max_file_size = 512 MB`, ConstMap)

Disk over ~120s (monotonic, no plateau):

```
t(s):    1    11    21    31    41    51    61    71    81    91   101   111   121
disk MB:256 4294  8121 11111 15416 16819 20032 24145 26340 30448 33942 39356 41626
```

`running_compactions` and `time_compacting_us` telemetry stayed 0 throughout.
Final disk ≈ 41 GB for a ~256 MB live set (1M × 256B). The same shape appears on
every Bitcask backend; `space_amp` was reported at 60–165× on update workloads.

### Run B — small file size (`--armdb-max-file-bytes 32000000`, ConstTree, instrumented)

`compact()` was instrumented to log its `DbResult<usize>` return:

- **35s:** disk 5.2 GB; one log line `[compact] reclaimed 0 bytes` (the t≈0
  empty-db call; the post-rotation compaction did not finish before exit).
- **100s:** disk samples `2388 → 4687 → 6226 → 7802 → 10023 → 12092 → 13000 MB`
  (linear, no plateau). `compact()` logged `reclaimed 0 bytes` then
  `reclaimed 11 bytes`. The second call spanned ~26s wall (slow scan) and
  reclaimed **11 bytes out of ~13 GB** of overwritten data.

At 32 MB × 16 shards the data rotated into ~400 files (~25/shard); under a pure
overwrite of a 1M working set nearly every older file should be ~100% dead — yet
selection + reclaim returned ≈0.

### Ruled out

- **"Active-file headroom" (`max_file_size × shard_count` too large, so nothing
  rotates).** Refuted by Run B: at 32 MB files rotated heavily and reclaim was
  still ≈0. Shrinking `max_file_size` changes only file granularity, not the
  reclaim failure.
- **Compaction interval too slow.** Was 60s in the bench; tightened to 30s — no
  effect. compact() *runs*; it just doesn't reclaim.
- **compact() erroring.** Returns `Ok(_)`, not `Err` — the work runs to
  completion, returning ~0.

## Code anchors (armdb @ 4b3fd96)

- `compact()` entrypoints (all iterate shards → `compact_shard(shard, self, compaction_threshold)`):
  `const_tree.rs:162`, `const_map.rs:157`, `var_tree.rs:189`, `var_map.rs:178`,
  `typed_tree.rs:279`, `typed_map.rs:262`.
- **Compaction core:** `compaction.rs:142` `compact_shard_inner`.
- **File selection (prime suspect):** `compaction.rs:163-173` —
  ```rust
  for file in &inner.immutable {
      let total = file.total_bytes;
      let dead  = inner.dead_bytes.get(&file.file_id).copied().unwrap_or(0);
      if total > 0 && (dead as f64 / total as f64) > threshold
         && !cooldown_ids.contains(&file.file_id) {
          files_to_compact.push(file.clone());
      }
  }
  if files_to_compact.is_empty() { return Ok(0); }
  ```
- **Per-call cap:** `compaction.rs:~196` `files_to_compact.truncate(4)` — at most
  4 files compacted per `compact()` call.
- **dead_bytes accounting on overwrite/delete:** `durability.rs:106-116`
  (`write_update` / `write_tombstone` → `add_dead_bytes(old_loc.file_id, entry_size(key.len(), old_loc.len))`).
  Note: Const/Var tree update paths route through this shared layer (they have no
  own `add_dead_bytes` call on the write path — confirm this).
- **dead_bytes storage:** `shard.rs:109` (`HashMap<u32 file_id, u64>`), increment
  `shard.rs:1104` (`add_dead_bytes`), recovery install `shard.rs:668`.
- **Compaction mutates dead_bytes too:** `compaction.rs:449,481` (add), `:496`
  (`dead_bytes.remove(fid)` for retired files).

## Hypotheses (for the separate investigation)

1. **Selection / accounting (primary).** Immutable files' `dead_bytes` never
   reach `threshold × total_bytes`, so they're filtered out at
   `compaction.rs:165`. Sub-cases to check:
   - dead bytes attributed to the wrong `file_id`;
   - `entry_size(key.len(), old_loc.len)` undercounts relative to
     `file.total_bytes`, so the ratio never crosses the threshold (0.2–0.3);
   - Const/Var tree updates don't actually hit `durability.rs:write_update`
     (and therefore never credit dead bytes) — **verify the call path**.
2. **Throughput throttle (secondary/compounding).** `truncate(4)` caps each
   compact() to 4 files/shard. At ~130 MB/s net growth and 32 MB files that's
   ~7–8 new files/shard per 30s interval — 4/shard/cycle can't catch up. But a
   working selection would still reclaim ~GB/cycle, inconsistent with the
   observed 11 bytes, so this *compounds* H1 rather than being the root cause.
3. **Slow scan.** compact() took ~26s for one cycle while reclaiming ~0 —
   consistent with scanning all shards / rewriting near-live files each call.

## Suggested next steps

1. **Failing regression test** in armdb: open a `ConstTree` (Bitcask) with a
   small `max_file_size` (1–4 MB), insert N keys, overwrite each M times so
   `M·N·entry ≫ max_file_size` (many rotations), then `compact()`. Assert
   (a) `compact()` returns > 0 and (b) on-disk size approaches the live-set
   size, not total bytes written. This should currently fail.
2. Right before `compaction.rs:163`, dump per-file `dead/total` for every
   immutable file under that test — confirm whether any file crosses `threshold`.
3. Assert `shard.dead_bytes` actually grows after overwrites (validates the
   `durability.rs:109` path for Const/Var trees).
4. Re-evaluate `truncate(4)` — compact until the backlog clears, or scale the cap.

## Reproduction (via the benchmark fork)

`rust-storage-bench` branch `v1`. Instrument the Bitcask `compact()` calls in
`src/db/builder.rs` to log the `DbResult<usize>` (was done ad-hoc; reverted), then:

```sh
# small files — rotates heavily, still ~0 reclaim, disk → ~13 GB in 100s
rust-storage-bench run --backend armdb-const --data-dir /tmp/x --seconds 100 \
  --armdb-max-file-bytes 32000000 --out /tmp/o.jsonl fixed-update --item-count 1000000

# default files — disk → ~41 GB
rust-storage-bench run --backend armdb-const-map --data-dir /tmp/y --seconds 120 \
  --out /tmp/o2.jsonl fixed-update --item-count 1000000
```

Disk via `du -sh`; reclaim via the instrumented `[compact] reclaimed N bytes` log.

## Cross-references

- Benchmark baseline tables (full 51-run sweep, big files):
  `rust-storage-bench/docs/benchmarks/2026-06-18-baseline-bigfile.md`.
- `rust-storage-bench/docs/armdb-config-matrix.md` "Tuning note" is **now
  incorrect** — it claims shrinking `max_file_size` engages compaction; Run B
  refutes that. Correct it when benchmark work resumes.

## Environment

- armdb `4b3fd96` (0.5.1), features `var-collections, typed-tree, rapira-codec`.
- 16 logical cores, Linux 6.8. 2026-06-18.
