Improving storage efficiency in Magic Pocket, our immutable blob store (opens in new tab)

Magic Pocket’s immutable design protects data integrity but makes storage efficiency dependent on continuous reclamation. A new Live Coder service reduced write amplification while unintentionally creating severely under-filled volumes, driving fragmentation and storage overhead sharply upward. Dropbox responded by rethinking compaction, since its existing steady-state strategy was too slow to recover space from the resulting long tail of sparse volumes.

The Cost of Immutability

• Magic Pocket stores user files as immutable blobs distributed across its storage fleet.
• Updates and deletions never modify data in place; obsolete blobs remain until compaction.
• Garbage collection identifies unreferenced blobs, while compaction physically moves live blobs into new volumes and retires old ones.
• Because closed volumes cannot be reopened, deleted data creates unused space unless it is actively consolidated.
• Durability also increases storage requirements:
  • Replication stores multiple complete copies.
  • Erasure coding splits data into fragments and adds parity, providing fault tolerance with less overhead.
• Fragmentation determines how efficiently that redundant capacity is used:
  • A volume with 50% live data effectively doubles required storage.
  • A volume with 10% live data uses roughly ten times the necessary space.

The Live Coder Incident

• A new on-the-fly erasure-coding service created severely under-filled volumes as it rolled out to new regions.
• In the worst cases, less than 5% of a volume’s capacity contained live data.
• Since volumes have fixed allocations, many mostly empty volumes consumed nearly as much raw capacity as full volumes.
• Dropbox detected rising effective replication-factor signals, indicating more raw storage was being used per live byte.
• The existing compaction system continued reclaiming space but was not designed for a long tail of extremely sparse volumes.
• The incident demonstrated that compaction must adapt when the distribution of live data changes substantially.

Steady-State L1 Compaction

• Dropbox’s baseline strategy, L1, treats compaction as a packing problem.
• It selects:
  • A highly filled host volume with available space.
  • Donor volumes whose live data fits into that space.
• Live blobs from the donors are written into a new volume, eventually leaving the donors empty and removable.
• L1 is simple, fast, and limits placement risk and metadata changes.
• However, each run can read tens of GiB while typically producing only one densely packed volume.
• Fewer than one complete volume is reclaimed on average because only donor volumes are fully drained.
• This works well when volumes are already near full, but performs poorly when storage overhead is concentrated in many severely under-filled volumes.