DreamDB Specification — 0021: Compaction

Status: Normative (v0.1), 2026-05-22. Implemented in the reference impl (dreamdb-dataset Dataset::compact; dreamdb-cli compact) and gated by conformance at 0009 §8.7: the behavioral compact.correctness + compact.idempotence properties are asserted in dreamdb-conformance (behavioral.rs::dag_compaction_preserves_results_and_is_idempotent) and dreamdb-dataset compact.rs tests (anchor-conflict/lineage refusal, rerank-VS alignment), and the consolidated SpatialBucket byte format rides the 0009 §5.4 spatial-bucket vectors. Sharded compaction (§6) remains optional/draft. Builds on 0001, 0006, 0007 §6.6, 0008 §6.

1. Purpose

After the LSM retrofit (0007 §6.6), Dataset::append writes one new SpatialBucket per touched cell with only the records from this batch. The Track Object's object_index accumulates F SpatialBucketEntry entries per <spatial-key> over time. Reads union all entries for a cell, so query latency scales linearly with F.

This document defines the compaction protocol: how an operator consolidates a cell to the fewest Buckets its capacity allows (F → K), the safety properties readers and writers rely on during compaction, and the conformance requirements compactors MUST satisfy.

2. When compaction runs

Compaction is operator-driven. DreamDB SDKs MUST NOT auto-trigger compaction. Operator-driven means:

• Triggered by an explicit CLI invocation (dreamdb-cli compact) or external orchestration (k8s CronJob, monitoring-based trigger).
• The SDK never spawns background threads, daemons, or implicit compaction workers as part of normal append/iter operations.

Rationale: in-SDK background compaction adds failure modes (resource contention with the application, partial-flush races, debugging difficulty) that are inappropriate for a v1 protocol. Operator-driven compaction matches the model already established by ada-ivf-step (per 0008 §6 + project_rebuild_concurrency_rules).

Recommended operator cadences:

3. Compaction operations

A conformant compactor MUST perform the following steps atomically (one Manifest published at the end, single Ref CAS):

3.1 Identify candidate cells

1. Read the Ref to obtain the current Manifest hash + ETag.
2. Read the Manifest; find the target modality's TrackEntry.
3. Walk the Track Object's object_index:
   • Inline SpatialBucket index: enumerate SpatialBucketEntry directly.
   • Paged SpatialBucket index: walk the B-tree (per 0007 §7.3.2).
4. Group entries by (table_id, spatial_key). That pair is the cell's identity: 0007 §6.4 splits independently per table and a Bucket address does not encode the table, so grouping on the spatial key alone would union records from different tables into one Bucket and strand the rewritten entry with no table_id. Per-cell fragment count F = entries_for_cell.len().
5. Compute the cell's capacity floor. With payload cap B (0007 §6.4) and record width R, one Bucket holds C = floor(B / R) records; C = 0 MUST be refused before any write, because no compliant Bucket exists. For N distinct records in the cell, the minimum legal Bucket count is K = ceil(N / C).
6. Fragment debt is max(F - K, 0), not bare F. Select a cell when debt >= threshold (operator-supplied, default 1). A cell already at K has zero debt however many Buckets it holds: two 60 MiB Buckets under a 100 MiB cap are already the fewest possible, and rewriting them into 100 + 20 is churn, not progress.
7. Regardless of debt or threshold, select any cell holding a Bucket whose payload exceeds B. Such an Object violates 0007 §6.4 and MUST be repaired; gating that on an optimisation threshold would make a historically oversized Bucket permanently unrepairable.
8. threshold = 0 MUST be refused for Bucket-splitting (embedding) compaction, before any write. Every cell has debt >= 0, so it selects the entire Track on every pass and no pass is a no-op, contradicting §7. Reading it as 1 is not an acceptable substitute: the caller asked for something the format cannot express and would be told it succeeded.
9. max_cells caps the cells a pass rewrites, not the cells it examines. Counting cells that a coarse pre-filter admitted and the capacity test then found complete would let a batch of legitimately split cells hold the quota indefinitely and starve the cells carrying real debt.

3.2 Per-cell merge

For each selected cell:

1. Read and validate every fragment header. Record payloads MUST be consumed through bounded windows or an external/spill merge; a compactor MUST NOT retain the whole cell merely because its output will later be sliced.
2. Validate compatible headers. All fragments MUST share modality, record_size, spatial_index_hash, and vector_compressor_hash. If any differ, compaction MUST fail loudly with a clear error identifying the affected cell. Mismatched headers indicate the operator must use a feature-branch reindex (per 0008 §6) rather than a compaction.
3. Union records by time_anchor within a bounded working set. An implementation MAY make repeated selection passes, perform an external sort, or use another deterministic bounded merge. When two fragments contain the same time_anchor:
   • If the record bytes match exactly → keep one (deduplication).
   • If the record bytes differ → compaction MUST fail loudly. Different vectors at the same anchor indicate two writers ingested the same logical Item (slice-assignment bug per 0008 §5); compaction MUST NOT silently choose one.
   • For compressed records with exact sidecars on both sides, deduplication additionally requires byte-identical original vectors. Equal lossy codes do not prove equal logical values; conflicting sidecar records MUST refuse before publication, not select the first value.
4. Sort the merged records by time_anchor.
5. Cut the merged records into K = ceil(N / C) contiguous slices of at most C records, in time_anchor order, and encode + PUT one content-addressed SpatialBucket Object per slice. K is the cell's capacity floor from §3.1; a compactor MUST NOT emit a single Object when the records do not fit under the cap. Every input and every output plan MUST be validated before the first output PUT. An implementation MAY regenerate a planned slice at commit time, but the regenerated bytes MUST hash to the address computed during planning before they reach the Connector.
6. Emit one replacement SpatialBucketEntry per slice, whose t_start = min(slice records), t_end = max(slice records) + 1, byte_size and bucket_address are that slice's own, and whose table_id is the cell's. Set rerank_storage_hash to that slice's rerank VS (§5) — never carry over a single fragment's hash, and never a VS cut at a different boundary.

3.2.1 Retained-payload bound

Peak retained Bucket-record plus exact-vector payload for one cell MUST be bounded by an implementation-declared working bound and MUST NOT grow with the cell's total record payload. The reference implementation uses fixed 1 MiB input scan windows, retains at most one capacity-bounded output slice per cell plan, and materializes deferred output slices serially at commit.

This is a payload-memory guarantee, not a claim that every byte of compaction state is constant-size. The K replacement-entry descriptors required by the Track Object, fragment header metadata, and backend/client bookkeeping may grow with the number of input or output Objects. No implementation may count those small descriptors as permission to retain the records or exact vectors they describe.

3.3 Publish

1. Build the new Track Object: a cell that was compacted is replaced wholesale by its K replacement entries, every other cell is carried over unchanged, and the result is sorted by (spatial_key, table_id, t_start) per 0002 §7.3.1. Entries MUST be matched by cell identity, never by bucket_address: Bucket bytes carry no spatial key or table id, so one content hash can appear in more than one logical cell and removing "every entry with this address" deletes another cell's reference.
2. PUT the new Track Object.
3. PUT a new Manifest with the updated Track address; registry unchanged (SI/VC unchanged).
4. CAS-advance the Ref using the ETag captured in §3.1 step 1.

3.4 CAS conflict handling

If the Ref CAS fails (a concurrent writer landed during the compaction):

• Compaction MUST fail loudly with an error directing the operator to use a feature branch (per 0008 §6) or to retry.
• The Manifest + new Bucket Objects from this compaction remain on S3 (orphaned, GC-reclaimable via dreamdb-cli gc).
• The Ref still points at the prior consolidated state OR the writer's new tip.

4. Read-online property (mandatory)

During compaction:

• Queries MUST continue to hit the old Manifest (the one pinned by the Ref) until the atomic CAS advances. No window where queries slow down.
• After the CAS, new queries see the new Manifest immediately. Buckets reference content hashes; the new Bucket Objects are addressable as soon as their PUTs complete.
• The old Bucket Objects remain addressable on S3 (immutable, content-addressed). They become unreferenced once the new Manifest is the Ref's target, but content-addressing means in-flight queries against the OLD Manifest still resolve correctly until those queries complete.

This is the same property as the rebuild-concurrency rules pinned in 0008 §6 — "read-online, write-needs-branch."

5. Rerank VectorStorage consolidation

For modalities with rerank=true, each SpatialBucketEntry carries a rerank_storage_hash pointing at a parallel VectorStorage Object holding raw f32 vectors mirroring the bucket's record order (per 0010 §8). When compacting fragments:

• Validate every per-fragment VectorStorage header and scan its records in bounded ordinal-aligned windows with the parallel Bucket.
• Union only the exact records selected for the current output slice, in the same order as the merged bucket records. A missing or conflicting exact record refuses before publication.
• Cut that union at exactly the slice boundaries of §3.2 step 5, and encode + PUT one VectorStorage Object per slice.
• Each replacement SpatialBucketEntry.rerank_storage_hash MUST point at the VS of its own slice.

Invariant. Record index i in a Bucket MUST map to record index i in its rerank_storage VS, in identical order — before AND after compaction. The index is per Object: slice k's Bucket record i is slice k's VS record i, which is why the two are cut at one boundary and not independently. Rerank reads address the VS by candidate record index (0010 §5), so a misaligned or short VS yields out-of-bounds or wrong-vector exact distances.

Carrying over a single fragment's rerank_storage_hash is FORBIDDEN: a rewritten Bucket holds records drawn from all F fragments, so one fragment's VS covers only a prefix and violates the invariant — this is silent corruption of the exact-distance path, not "inaccuracy." An implementation that does not consolidate the VS MUST instead set rerank_storage_hash = null on the replacement entry (degrading that cell to compressed-only, which is safe), never a stale partial hash.

6. Sharded compaction (optional)

A conformant compactor MAY split work across multiple workers for billion-scale compaction:

• Worker phase (--shard N --of M): each worker handles cells where hash(spatial_key) % M == N. Each worker writes a per-shard JSON output listing its compacted entries.
• Orchestrator phase (--orchestrate --job-id ID): one orchestrator reads all M shard outputs, builds the new Track + Manifest from the union, CAS-advances the Ref.

Worker outputs MUST be content-addressed (idempotent re-runs are safe). Failed workers MUST be re-runnable without corrupting other workers' state.

7. Idempotence

A compactor running on an already-consolidated dataset MUST be a no-op. A cell is consolidated when F == K and every one of its Buckets is within the payload cap — not when F == 1. The completion test is the Bucket count and the cap, never a particular chunk boundary: a cell split as 60 + 60 is complete under a 100 MiB cap, and a compactor MUST NOT rewrite it merely because some other split would also have been legal.

When every selected cell turns out to be complete:

• No new Bucket Objects, no new Track Object, no new Manifest.
• The Ref MUST remain at its current state.
• Exit code MUST indicate success (no-op is success, not failure).

A pre-filter MAY admit more cells than the capacity test will keep — F is cheap to read and K is not knowable until the records are merged and deduplicated. Admitting a cell is not a decision to rewrite it, and a pass that admits cells and rewrites none MUST still be a no-op by the rule above.

This allows operators to run compaction defensively — e.g., before a snapshot, after a rebuild — without worrying about wasted work.

7.1. Read-only observation (OQ-96)

Dataset::observe_fragments(field, mode) observes one bucketed embedding field on the handle's immutable Manifest, not a refreshed Ref. Its report names that Manifest and the exact binding (including Track address), normalizes cell/table identity using the compactor's rules, and orders cells by the canonical index key. Unsupported Track families explicitly refuse. Observation MUST NOT PUT, CAS, delete, repair data, or automatically invoke compaction.

The caller explicitly selects the cost:

• Metadata reads the Track and any index pages, but not bucket payloads. It reports F and summed declared Object bytes (headers included). A declared Object size greater than the payload cap is only a possible oversize signal, not confirmed oversize. K, debt, and actual oversize MUST remain unknown.
• Exact scans all cells of the selected field, validating and deduplicating through the compactor's read-only planning path, including sidecar reads where required. It reports K, max(F-K,0), and actual payload oversize separately. This may require repeated payload scans; it is not a cheap metadata query.

F alone MUST NOT be presented as actionable debt: F=K>1 is complete. Reports are ephemeral SDK values, not new persistent Objects, and do not promise a latency bound or that a future execution will still see the same Ref.

8. Conformance requirements (catalogued in 0009)

The conformance categories for compaction are catalogued at 0009 §8.7:

1. Multi-bucket reads — append N batches into k cells, query, verify top-K matches brute force.
2. Compact idempotence — compact a consolidated dataset, assert no-op, including a dataset consolidated to K > 1 by the payload cap.
3. Compact correctness — compact a fragmented dataset, assert queries return the same anchors as pre-compact.
4. Lineage refusal — compact across an SI hash change, assert compaction fails with the documented error.
5. Anchor conflict refusal — compact two fragments with the same time_anchor but different vectors, assert compaction fails with the documented error.
6. Read-online property — start a query against the OLD Manifest while compaction runs, assert it completes correctly.
7. Bounded retained payload — compact one cell whose multiple Buckets and exact sidecars exceed the implementation's working bound; observe peak live merge payload below that bound while preserving query results and ordinal alignment.

9. Open questions

OQ-94, OQ-95 and OQ-96 are resolved above.