Skip to content

PATTERN Cited by 1 source

Multi-strategy compaction

Pattern

Instead of a single compaction heuristic, run N strategies concurrently over disjoint segments of the volume (or run/SSTable/fragment) fill-level distribution. Each strategy embeds a different distributional assumption and a different reclamation mechanism; an explicit eligibility boundary between strategies prevents interference.

Why

Any single compaction heuristic bakes in an assumption about the shape of the fill-level distribution it's operating on. As long as the live-data distribution matches that assumption, the heuristic works; when a workload change shifts the distribution — fragmentation spike, a new write path that produces under-filled volumes, a traffic-pattern shift — the heuristic's reclamation rate decouples from the overhead-production rate and storage overhead drifts upward.

Splitting the problem by fill-level segment lets each segment have its own mechanism tuned to its own data shape, while the whole pipeline stays adaptive across distribution shifts.

Canonical realization — Magic Pocket (Dropbox, 2026-04)

After the Live Coder rollout produced a long tail of volumes with <5% live data (Magic Pocket's fragmentation incident), Dropbox deployed three strategies over disjoint fill ranges:

Layer Target fill range Mechanism Destination shape
L1 Highly-filled donors Topping-off packing: one host volume + donor volumes fitting its free space Reused host (donor blobs rewritten)
L2 Moderately under-filled Dynamic-programming bounded packing — scale live bytes by granularity, DP over (volume-index, count, capacity), backtrack for max packing New near-full destination volume
L3 Sparse tail (e.g. <10% live) Streaming feed into the Live Coder erasure-coder — patterns/streaming-re-encoding-reclamation New volumes produced by Live Coder

Concurrency discipline: disjoint eligibility boundaries between strategies + per-strategy rate limits + cell-local traffic (no cross-DC compaction). Each strategy's candidate ordering is tailored to its shape — L1 conservative (placement-risk / metadata load kept low), L2 aggressive (denser packings → more reclaim per run), L3 sparsest-first (minimize per-volume rewrite cost).

Reported impact (Magic Pocket, 2026-04):

  • L2 (vs L1-only cells): 30–50% lower compaction overhead over a week; 2–3× faster overhead reduction.
  • Final fleet overhead driven below the pre-incident baseline.

Structural ingredients

  1. Classify volumes by fill level (or more generally: by the distributional axis your single-strategy heuristic is failing on).
  2. One mechanism per segment — each tuned to its segment's data shape, not averaged across the whole distribution.
  3. Disjoint eligibility boundaries enforced in the strategy selector — no volume is a candidate for two strategies at once.
  4. Per-strategy candidate ordering (conservative vs aggressive vs tail-first) expressing each strategy's cost profile.
  5. Per-strategy rate limits protecting shared downstream systems (storage / compute / metadata / network).
  6. Strategies share the same reclaim substrate (same garbage-collection, same metadata system, same cell), differing only in the rewrite / re-encode shape.

When it applies

The pattern is a response to distribution shift in an append-only / immutable substrate where reclamation must be compact-and-rewrite rather than in-place edit. Preconditions:

  • Reclaimable units exist at a bounded granularity (volumes, SSTables, Parquet fragments, blob batches).
  • Live-data content of each unit is measurable / observable.
  • A single-mechanism heuristic is known to be optimal for some subset of the distribution but not all.
  • Metadata / downstream-system cost of reclamation varies with mechanism (e.g. rewriting vs repackaging), so choosing the right mechanism per segment is a real cost lever.

Relationship to other compaction families

  • LSM compaction already mixes strategies (size-tiered at small scales, leveled at larger scales — Husky's "hybrid" shape). That is multi-strategy compaction over the run-size axis — a sibling instance of the pattern, with a different distributional axis and different mechanisms than Magic Pocket.
  • Copy-on-write merge (Amazon BDT's compactor) is a single mechanism but applied over partitioned buckets; the multi-strategy shape would be a BDT variant where different bucket classes get different merge algorithms.
  • Generic garbage collection in managed-memory runtimes (Young / Old generation, G1, ZGC regions) is the classical instance — the generational hypothesis is exactly the "embed one distributional assumption per strategy" move.

Failure modes

  • Boundary drift: the eligibility threshold that separates strategies becomes stale as the workload shifts, so the "wrong" strategy is applied to a segment. Mitigation: dynamic control loop on the threshold itself.
  • Downstream starvation: one strategy's work budget crowds out another's (L3's metadata writes can starve L1/L2's). Mitigation: per-strategy rate limits sized against the shared downstream capacity.
  • Silent regression on a segment: a strategy degrades on its own segment (say L2's DP packing quality drops when volumes are more homogeneous). Mitigation: per-strategy observability (reclamation rate, destination-volume fill quality, metadata writes / reclaimed volume).

Seen in

Last updated · 200 distilled / 1,178 read