Improving Storage Efficiency of Magic Pocket's Immutable Blob Store

Magic Pocket is Dropbox's exabyte-scale blob storage, and because of its immutable structure, deletions and updates don't immediately translate into space reclamation. Once a blob is written, it isn't modified, and unneeded data must be marked via garbage collection and then actually relocated through compaction before the space can be returned.

The problem is that fragmentation increased sharply after new placement paths were recently introduced. In particular, some volumes created via the Live Coder path were left with live data at levels below 5%, producing a long tail that occupied raw capacity excessively. Steady-state compaction alone couldn't keep up with this distribution, causing storage overhead to spike again.

The existing baseline, L1, worked by filling in live bytes from a donor volume while the host volume was already nearly full. This approach is stable, but since a single run typically produces just one new volume, it wasn't fast enough to reclaim space in a situation with many extremely sparsely filled volumes.

To address this, Dropbox added two additional strategies.

• L2: This groups multiple moderately empty volumes together and frames the problem as bounded packing, aiming to nearly fill a new destination volume. It uses dynamic programming, while limiting computation and memory through a cap on the number of source volumes and byte granularity coarsening.
• L3: This targets the most sparsely filled tail, using Live Coder like a streaming pipeline to continuously re-encode live blobs. It drains the least-filled volumes quickly to speed up reclamation, though this comes with the tradeoff of increased blob rewrites and metadata updates.

On the operational side, compaction is rate-limited so it doesn't compete with user traffic, and is handled only within a cell, avoiding movement between data centers. Additionally, the host eligibility threshold was changed from a fixed value into a dynamic control loop that adjusts based on fleet signals, reclaiming more aggressively when overhead rises and easing off once it stabilizes.

As a result, L2 lowered overhead 2 to 3 times faster than L1 in production, and cells with L2 enabled achieved 30-50% lower compaction overhead on a weekly basis. By shifting to a layered strategy where L1 maintains the steady state, L2 cleans up the middle tier, and L3 drains the sparsest tail, Dropbox brought the storage efficiency of its immutable blob store back into a stable range.