Improving storage efficiency in Magic Pocket, our immutable blob store

Why overhead creeps up in an immutable store

Magic Pocket, Dropbox's exabyte-scale blob storage system, stores user content as immutable blobs. Once written, a blob is never modified in place. When users update or delete files, new data is written and the old data simply remains on disk until a separate reclamation process removes it. This design guarantees durability and simplifies consistency, but it also means deleted data doesn't immediately free up capacity.

At Dropbox scale, the system processes millions of deletes per day. Because volumes are never reopened after being closed, those deletes leave behind unused space that gradually accumulates. Without intervention, volumes become partially filled, spreading live data across more disks than necessary. That fragmentation directly inflates storage overhead, a metric Dropbox tracks closely since even modest increases at exabyte scale translate into meaningful infrastructure costs.

Two processes keep this waste in check. Garbage collection identifies blobs no longer referenced and marks them safe to remove. Compaction performs the physical reclamation: it gathers live blobs from existing volumes, writes them into new volumes, and retires the old ones. This is how deletes eventually become reusable storage.

Compaction manages the waste created by deletes, but redundancy also affects overhead. Magic Pocket uses erasure coding for nearly all data, splitting blobs into fragments and adding parity fragments for fault tolerance. This provides the same protection as full replication, but with significantly less extra storage. Fragmentation, however, determines how efficiently that redundant space is actually used. A volume half-filled with live data effectively uses twice the storage needed; one only ten percent live uses about ten times the space required. Without continuous compaction, disk capacity would eventually be exhausted regardless of the redundancy scheme in place.

An incident that broke the steady state

Earlier this year, a new service that performs on-the-fly erasure coding, referred to internally as the Live Coder service, rolled out gradually to new regions. Over several weeks, it silently caused a problem: volumes created through this path were severely under-filled. In the worst cases, less than five percent of allocated capacity contained live data.

Because volumes are fixed in size, each under-filled volume consumed the same disk allocation as a full one. That meant live data was spread across far more volumes than intended, producing a sharp increase in fragmentation and a corresponding rise in storage overhead. The system's effective replication factor began signaling that more raw storage was being consumed per live byte than expected.

Once the root cause was identified, the team needed recovery mechanisms capable of bringing overhead back down efficiently. The existing compaction strategy continued to make progress, but it was not designed to handle a long tail of severely under-filled volumes at this scale. The incident exposed a fundamental limitation in the steady-state approach and forced a rethink of how compaction should behave when the distribution of live data shifts dramatically.

The limits of traditional compaction

Before the incident, the distribution of data across volumes was relatively stable. Most volumes were already highly filled, and deletes accumulated gradually. In that environment, compaction needed only to continuously consolidate small amounts of fragmentation and keep overhead bounded.

For years, the baseline strategy, called L1, worked well under these conditions. L1 treats compaction as a packing problem: it selects a host volume that is already highly filled, chooses donor volumes whose live bytes fit into the host's available space, and writes them into a new volume. Over time, donors are drained of live data, become empty, and can be removed.

L1's selection logic is simple and fast, keeping placement risk and metadata updates bounded. But each run is relatively expensive: it may read tens of GiB across host and donors yet typically produces only a single new densely packed volume. On average, fewer than one full volume is reclaimed per run. That tradeoff works fine when most volumes are close to full. The incident changed the distribution, though, and L1 could no longer compact the long tail of sparse volumes quickly enough.

Combining sparse volumes efficiently

Faced with a large population of severely under-filled volumes, the team needed a strategy that could reclaim space faster by combining multiple sparse volumes into a single near-full destination. That became L2.

Instead of incrementally packing donors into a host, L2 groups under-filled volumes together and selects combinations whose live data can nearly fill a new destination volume. Reclaiming several sparse volumes at once allows the system to recover space far more quickly than topping off already dense volumes.

Inputs:
volumes[] with LiveBytes
  maxVolBytes (destination volume capacity)
  maxVolumesToUse (count cap)
  granularity (scaling factor)
1) Scale live bytes and capacity by granularity to shrink the DP table.
2) DP over (i = volume index, k = count, c = capacity), keeping max packed bytes.
3) Track choices in a parallel “choice” table for reconstruction.
4) Backtrack from the best (k, capacity) to recover the selected volumes.

Under the hood, L2 is a bounded packing problem solved with dynamic programming. Each run selects a limited set of source volumes whose combined live bytes come as close as possible to the destination capacity without exceeding it. The implementation caps the number of source volumes per run and coarsens byte counts to keep the search space manageable at production scale. Granularity, batch size, and planner concurrency were tuned to balance packing quality against compute and memory cost.

Testing against data shaped to resemble production distributions, L2 consistently produced near-full volumes. In production, it reduced compaction overhead two to three times faster than L1. In cells where L2 was enabled, overhead returned to sustainable levels within days; over the course of a week, overhead was thirty to fifty percent lower compared to cells running L1 alone. Cells refer to independent units of the storage system that manage their own data.

Streaming reclamation for the sparsest volumes

L2 effectively targeted the middle of the distribution, where volumes were under-filled but still dense enough to combine efficiently. It was less effective, however, at quickly reclaiming the sparsest volumes, those with only a small fraction of live data remaining. That extreme tail required a different approach.

Returning to the Live Coder service, the team found a useful connection. The service was originally designed to write data directly into erasure-coded volumes, bypassing the initial replicated write path. It isn't ideal for latency-sensitive traffic, but it's well suited for background workflows where throughput matters more than immediacy.

Compaction is, in effect, a constrained form of re-encoding: take live data from one set of volumes and produce a new durable volume. L3 builds on that idea by using Live Coder as a streaming pipeline. Rather than packing volumes together in a bounded batch, L3 continuously feeds the remaining live blobs from severely under-filled volumes into Live Coder, which accumulates and encodes them into new volumes over time. Once a source volume's live data has been drained, it can be reclaimed immediately.

This strategy deliberately prioritizes volumes that aren't good candidates for L1 or L2. Severely under-filled volumes occur naturally as donors are partially drained and can accumulate quickly during failure modes like the one described earlier. By prioritizing the sparsest volumes first, L3 minimizes the amount of data rewritten per reclaimed volume, accelerating recovery of fragmented space.

L3 does introduce tradeoffs. Because every blob it moves must be rewritten into entirely new volumes, each migration creates new identifiers and requires additional metadata updates. That extra bookkeeping creates load on storage and metadata systems. With the volume of under-filled volumes observed during steady state, that additional load remains tolerable, and limits are in place to prevent overwhelming those systems.

Keeping compaction from competing with user traffic

To stop compaction work from interfering with live user traffic, Dropbox rate-limits the pipeline and confines all related data movement to the local cell rather than shipping it across data centers. The three tiers form a layered defense: L1 holds the steady state, L2 consolidates moderately under-filled volumes, and L3 drains the sparsest tail, letting the system reclaim space on a fast cadence without destabilizing the wider fleet.

Rolling out L2 and L3 demanded more than just improvements to packing density. Compaction touches storage, compute, metadata systems, and network bandwidth, so any increase in aggressiveness needs tight controls.

Dynamic thresholds replace static tuning

The most sensitive lever is the host eligibility threshold, the bar that decides when a volume is worth compacting. Too high a threshold leaves too few volumes eligible and overhead climbs; too low a threshold spends compute and I/O reclaiming barely any space. Dropbox swapped static tuning for a dynamic control loop that adjusts the threshold from fleet signals. When overhead rises, the system raises the threshold to prioritize higher-yield compactions; when overhead stabilizes, it lowers the threshold so it stays responsive to deletes without over-compacting.

Candidate ordering is a second lever. Which volume gets compacted first can speed up space reclamation, but it can also raise metadata work because more blobs may need rewriting. Each strategy gets a tailored ordering. L1 stays conservative and limits the number of donor volumes it touches to cap placement risk and metadata load. L2 groups volumes more aggressively since denser packings reclaim more space per run. L3 targets the sparsest volumes first; draining them typically means rewriting relatively little data per volume.

Running all three tiers concurrently

The final step was letting L1, L2, and L3 execute at the same time without tripping over each other. Each targets a different part of the volume distribution: L1 keeps mostly full volumes in steady state, L2 packs moderately under-filled volumes into dense destinations, and L3 empties the sparsest volumes. Clear eligibility boundaries keep the strategies from colliding, rate limits shield downstream services, and traffic locality rules keep compaction within a cell to avoid straining cross-cluster bandwidth.

Those safeguards let the system adapt as workloads shift while holding metadata pressure, network traffic, and compute use inside safe limits.

Lessons from the rollout

This work drove home that compaction cannot lean on a single heuristic. L1 performed fine in steady state because most volumes sat close to full and only a few were partially filled at any moment. When the distribution changed and a large batch of very sparse volumes accumulated, L1 could not recover overhead quickly enough. Splitting the problem across three strategies gives coverage over the full range of volume fill levels: L1 for mostly full volumes, L2 for moderately under-filled ones, and L3 for the sparsest.

Manual tuning also does not scale. The host eligibility threshold is far too sensitive to manage by hand at exabyte scale. Moving to a control loop driven by fleet signals made overhead more stable and cut the need for constant intervention. Candidate ordering and rate limits likewise need to be set with an eye on downstream systems, and metadata services in particular.

Metadata is the binding constraint

Metadata capacity turned out to be one of the biggest operational constraints, and not every compaction move carries the same metadata cost. In L1 and L2, many blobs can stay under their current volume identity, so only donor blobs need location rewrites. In L3, blobs land in brand-new volumes, so most of them need fresh location entries. Efficient packing alone was not enough; the team also had to control how much rewriting each run triggered. Limiting L2's work per run, routing the sparsest volumes through L3, and keeping traffic local to each cell allowed space reclamation without overwhelming metadata, storage, or network systems.

Finally, the project exposed the need for better visibility into compaction performance. Dropbox added metrics for how much data Live Coder produces, how full volumes are across the fleet, and how storage overhead trends week over week. Monitoring now gives early warning if compaction starts to fall behind, with the goal of catching distribution shifts before overhead rises too far so the team can respond proactively rather than scramble to recover later.

Storage overhead directly dictates how much raw capacity must be bought to hold the same amount of live user data; even small overhead changes materially affect hardware purchases and fleet growth. Turning compaction into a layered, adaptive pipeline with stronger monitoring and controls makes Magic Pocket more resilient to workload changes and keeps storage growth more predictable over time.