提高 Magic Pocket 不可变 Blob 存储的空间效率-未完纪

Magic Pocket 是 Dropbox 的核心存储系统：一个定制构建、达到 EB 级规模的 Blob 存储系统，围绕持久性、可用性、规模和效率设计。它保存用户内容，因此必须安全、快速，并能以合理成本随公司扩展。存储效率对 Dropbox 非常重要；我们通过比较使用的总磁盘空间与实际保存的用户数据量来衡量它。

去年，我们上线了一项新服务，改变了 Magic Pocket 中数据的放置方式。这减少了后台写入的写放大，使每次写入触发的后端存储操作更少。但它也产生了意外副作用：碎片增加，存储开销上升。增长大多来自少量填充率极低的卷，它们占用了不成比例的原始容量，而现有压实策略无法足够快地回收空间。在 EB 级规模下，即使开销小幅增长，也意味着显著的基础设施和容量成本，因此尽快降低这一数值成为优先事项。

本文介绍为什么不可变 Blob 存储的开销特别难控制、Magic Pocket 如何进行压实，以及我们如何部署多策略方案，将开销降回此前水平，甚至低于原先基线。

不可变性的成本

用户向 Dropbox 上传文件时，Magic Pocket 将文件拆成更小的片段，称为 Blob，并存入存储集群。Blob 就是写入磁盘的一块二进制数据，可以是用户文件的一部分或全部。Magic Pocket 是不可变 Blob 存储，意味着 Blob 一旦写入，就永远不会原地修改。文件更新或删除时，写入新数据，旧数据则保留到压实过程将它回收为止。

在 Dropbox 的规模下，Magic Pocket 保存数万亿个 Blob，每天处理数百万次删除；删除指的是文件被删除或更新时，请求移除对应 Blob。由于数据不可变，删除不会立即释放磁盘空间。旧数据仍保存在卷中，卷一旦关闭，就永远不会重新打开。代价是删除留下未使用空间，如果不主动回收，浪费会不断增长。

没有回收时，卷会逐渐变成部分填满的状态，存活数据分散到比实际需要更多的磁盘上。缺少回收导致的碎片，对存储开销有很大影响。

我们分两步处理。垃圾回收识别不再被引用的 Blob，并标记为可以安全移除，但它本身不释放空间。压实执行物理回收。卷关闭后不能再修改，因此我们收集卷中的存活 Blob，把它们写入新卷，并退役旧卷。删除最终就是这样转化为可复用空间的。

卷 1 与一个供体卷（卷 2）一起进行压实的生命周期。随后，卷 1 可被重新使用。

读图提示：原图使用四副本布局演示垃圾回收与压实过程；正文另有说明，Magic Pocket 的绝大多数数据采用纠删码。图示不代表所有生产数据都使用四副本。

压实控制删除产生的浪费，但碎片并非影响存储开销的唯一因素，持久性也有影响。为抵御硬件故障，我们通过完整副本或分布到不同机器上的编码片段冗余保存数据，使磁盘或服务器故障后仍能恢复。复制会保留每个 Blob 的多个完整副本，并相应增加存储用量。在 Magic Pocket 中，几乎所有数据都使用纠删码。纠删码把数据拆成片段，并添加少量校验片段；即使部分片段丢失，这些额外片段也能帮助重建原始数据。它提供与复制相同级别的容错，却需要明显更少的额外存储。

冗余影响开销，而碎片决定这些空间使用得是否高效。可以用卷中活跃数据所占比例来理解：如果一个卷只有一半是存活数据，实际上就使用了所需空间的两倍；如果仅有 10% 存活，约使用所需空间的十倍。即使数据冗余方案不变，没有持续压实，磁盘容量最终也会耗尽。因此，要让不可变系统的存储开销保持较低，既需要高效冗余，也需要持续整合碎片空间。

促使我们重新思考的事件

今年早些时候，我们发现一项实时执行纠删码的新服务存在问题，下文称它为 Live Coder。它用了几个月逐步部署到新区域。问题持续数周未被发现：经由这条路径创建的卷填充率极低。最严重时，存活数据不到已分配容量的 5%。

实际结果是，存活数据散布在远多于预期的卷上。我们没有将 Blob 密集装在一起，而是创建了大量几乎空的卷。因为卷的大小固定，一个欠填充卷与满卷占用相同的磁盘分配量。这导致碎片大幅增加，存储开销相应上升。

我们早期看到有效复制因子受到影响，这表明每个存活字节消耗的原始存储比预期更多。但定位根因需要深入调查。理解情况之后，还必须设计能有效降低开销的恢复机制。现有压实策略仍在取得进展，但它并不是为如此大规模、严重欠填充的长尾卷设计的。

这次事件暴露了稳态方案的局限。它迫使我们重新思考存活数据分布变化时应该如何压实，并开发能够更快、更有效回收空间的新策略。

稳态压实是什么样的

事件发生之前，正常运行中各卷的数据分布相对稳定。大多数卷已经高度填满，删除逐渐积累。在这种稳态下，压实的任务是不断整合少量碎片，使存储开销保持有界。

多年来，我们称为 L1 的基线压实策略在这种环境中表现良好。它把压实视为装箱问题：把一个或多个部分填满的供体卷中的存活数据，移入有足够空闲空间的宿主卷。随着供体卷的存活数据被逐渐搬空，它们变为空卷，就能移除。

L1 选择一个填充率已很高的宿主卷，再选择存活字节数能放入其空闲空间的供体卷，最后将数据写入一个新卷。选择逻辑简单快速，数据放置风险和元数据更新量也保持有界。但每次压实运行成本较高，可能要从宿主与供体读取数十 GiB 数据，通常却只产生一个新的高密度卷。由于只有供体被完全搬空，平均每次运行回收的空间少于一个完整卷。

大多数卷接近满载时，这种方法很有效。但事件改变了这一分布：开销集中在严重欠填充的长尾卷上。L1 继续有进展，却无法足够快地压实这些卷。它的核心假设——大多数卷高度填满——已经不再成立。因此，我们引入 L2 和 L3 两种新策略，分别处理卷填充率分布的不同部分。

更有效的空间回收方式

分布变化后，L1 的局限变得明显。它用于补满已经密集的卷，而不是快速回收大量严重欠填充卷。我们需要把多个稀疏卷合成一个接近满载的目标卷，以更快回收空间。

检查存活数据分布后，我们发现多数浪费集中在填充率不足一半的特定卷集合。L1 不适合这一模式；它补满已有高密度卷，而不是积极合并稀疏卷。L2 不再逐步将供体装入宿主，而是将欠填充卷分组，选择其存活数据能几乎填满一个新目标卷的组合。一次回收多个稀疏卷，让系统能够更快恢复空间。

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.

算法范围：这段原文伪代码说明候选选择思路，不是完整可执行程序；没有展开容量粗粒度化时的取整方向、边界状态和异常处理。具体实现仍需确保映射回原始字节数后不超出目标容量。

底层上，L2 用动态规划解决有界装箱问题。每次运行选择有限数量的卷，使其存活字节总量尽量接近目标容量而不超出。为了在生产规模下实际可行，我们限制单次使用的源卷数量，并将字节数粗粒度化，以缩小搜索空间。这使计算与内存使用保持有界，同时仍然得到紧密装箱。

实际部署中，我们调节粒度、批大小和规划器并发度，在装箱质量与计算、内存成本之间取得平衡。这些设置让 L2 能够高效运行，同时得到紧密的装箱结果。

测试结果很好。使用形状接近生产分布的数据，L2 稳定地产生接近满载的卷。在生产环境中，它降低压实开销的速度为 L1 的两到三倍。启用 L2 的 cell，其开销在数天内降回可持续水平；一周后，与只运行 L1 的 cell 相比，压实开销降低 30% 到 50%。这里的 cell 指独立管理自身数据的存储系统单元。

清理最稀疏的卷

L2 有效处理分布中间部分：这些卷欠填充，但仍有足够密度进行高效合并。然而，对于只剩很少存活数据的最稀疏卷，它无法同样快速地回收。这些卷构成分布的极端长尾，需要不同方案。

迭代压实策略时，我们重新考虑了 Live Coder。它原本用于直接将数据写入纠删码卷，跳过初始的复制写入路径。虽然不适合对延迟敏感的流量，但非常适合吞吐量比即时性更重要的后台流程。

压实实际上是一种受约束的重新编码：从一组卷提取存活数据，并产生新的持久卷。L3 以此为基础，把 Live Coder 用作流式流水线。它不在有界批次中装箱，而是持续把严重欠填充卷中的剩余存活 Blob 送入 Live Coder，让它随时间积累并编码为新卷。源卷中的存活数据一旦搬空，就能立即回收。

这种策略关注不适合 L1 或 L2 的卷。供体部分搬空时，自然会产生欠填充卷；在前述事件这样的故障模式下，它们也可能快速积累。优先处理最稀疏卷，使 L3 将每回收一个卷需要重写的数据量降至最低，加速碎片空间恢复。

L3 也带来权衡。因为把存活数据写入全新的卷，每个移动的 Blob 都必须重写，意味着新标识符和额外元数据更新。这些记账工作增加了存储和元数据系统的负载。按稳态观察到的欠填充卷数量，这项额外负载可以承受；我们也设置了限制，避免这些系统不堪重负。

运行调优与保护措施

为避免压实与用户流量竞争，我们对流水线限速，并将流量保持在各 cell 内，而不是跨数据中心发送。L1、L2、L3 共同构成分层策略：L1 维持稳态，L2 合并中度欠填充卷，L3 搬空最稀疏长尾，以快速回收空间，同时避免破坏整个集群的稳定性。

部署 L2 和 L3 不只是提高装箱效率，还必须确保系统能承受额外工作，不产生新瓶颈。压实涉及存储、计算、元数据系统和网络带宽，因此提高处理强度需要谨慎控制。

最敏感的调节参数之一，是决定卷何时有资格压实的宿主资格阈值。阈值过高时，合格卷太少，开销上升；过低时，计算和 I/O 被用于回收很少的空间。我们将静态调节换为根据集群信号调整阈值的动态控制循环。开销上升时，系统提高阈值，优先执行收益更高的压实；开销稳定时，降低阈值，继续响应删除而不过度压实。

阈值说明：原文没有给出该阈值的精确定义、单位或控制器公式，同时保留了“阈值过高会减少合格卷”和“开销升高时提高阈值”两种描述。不能只凭这段文字推出可通用于其他系统的阈值调整方向；实现时应先明确所度量的指标、资格条件与反馈关系。

候选排序是另一项重要参数。选择先压实哪些卷，可能加速空间回收，也可能因重写更多 Blob 而增加元数据工作。我们针对每种策略调整排序。L1 保持保守，限制接触的供体数量，以降低放置风险和元数据负载；L2 适合更积极的分组，因为更密集的装箱使每次压实回收更多空间；L3 优先处理最稀疏卷，因为搬空它们通常只需为每个卷重写较少数据。

最后一步是让 L1、L2、L3 并发运行而互不干扰。每种策略处理分布的不同部分：L1 在高度填满的卷之间维持稳态，L2 把中度欠填充卷合并为高密度目标卷，L3 搬空最稀疏卷。我们在策略间强制明确资格边界，并对每条路径限速，保护下游服务。我们也约束流量局部性，让压实留在 cell 内，避免给跨集群带宽施压。

这些保护措施共同让系统适应工作负载变化，同时使元数据压力、网络流量和计算利用率保持在安全范围内。

我们学到了什么

这个项目再次说明，压实不能依赖单一启发式方法。L1 在稳态下有效，是因为多数卷接近满载，任意时刻只有少量卷部分填满。分布变化、大量极度稀疏卷积累后，L1 无法足够快地降低开销。将问题分给多种策略，覆盖了完整的填充率范围：L1 维持大部分满载卷的稳态，L2 合并中度欠填充卷，L3 关注最稀疏卷。

我们还发现，手动调节无法扩展。宿主资格阈值过于敏感，难以人工管理，特别是在 EB 级规模下。转向与集群信号绑定的动态控制循环，使开销更稳定，也减少了持续干预的需要。候选排序和限速同样必须考虑下游系统，尤其是元数据服务。

运行中，元数据容量成为最大的约束之一。不是每次压实移动都有相同的元数据成本。在 L1 和 L2 中，许多 Blob 可以保持相同的卷身份，因此仅供体 Blob 需要重写位置；在 L3 中，Blob 被写入全新卷，因此大部分 Blob 需要新的位置条目。所以，仅仅高效装箱还不够，还必须控制触发的重写量。通过限制 L2 的单次工作量、让最稀疏卷走 L3、将流量保持在各 cell 内，我们回收了空间，又没有让元数据、存储和网络系统过载。

最后，这项工作表明，我们需要更好地观察压实表现。我们增加指标，跟踪 Live Coder 产出的数据量、集群各卷的填充情况，以及存储开销逐周如何变化。我们也加入监控，在压实开始落后时提前告警。目标是在开销涨得过高之前发现数据分布变化，主动响应，而不是事后匆忙恢复。

存储开销直接决定了保存相同存活用户数据需要多少原始容量。即使开销小幅变化，也会明显影响硬件采购和集群增长。通过把压实变成分层、自适应的流水线，并加强监控与控制，我们让 Magic Pocket 更能应对工作负载变化，也更有能力让长期存储增长保持可预测。

致谢：Tommy Dean（对 L2 策略的贡献）和 Lisa Kosiachenko（对自动化的贡献）。

~ ~ ~

如果构建创新产品、体验和基础设施让你感到兴奋，欢迎与我们一起创造未来！访问 jobs.dropbox.com 查看开放岗位。