CDC：分块与内容定义边界

上一节确立了 CAS 的基本规则：对象的身份来自它的字节。本节继续回答一个问题：如何把大文件表示为更小、可复用的对象，同时完整保留原始字节序列？

CAS 只能复用交给它的完整对象。如果整个文件就是一个对象，那么即使只修改一个字节，修改后的文件也会获得新身份，尽管其中几乎所有字节都没有变化。

未修改区域依然存在，只是整文件 CAS 无法识别它们。我们需要更小的复用单位，这个单位就是数据块。

1. 什么是数据块？

分块，就是把一个字节流切分成若干连续片段。这些片段保留原始字节及其顺序；新的表示方式只是提供了更小的存储、比较、传输与复用单位。

这里的 || 表示连接：依次读取 C₀、C₁ 和 C₂：

B = C₀ || C₁ || C₂

数据块只是一段字节范围。它不是文件格式中的记录，不是段落，也不是密码学身份。数据块的顺序属于文件表示的一部分：同一组片段采用不同顺序，会描述出不同的字节序列。

因此，文件还需要一份小型有序清单，用来说明应该读取哪些数据块。数据块本身则可以存放在一个共享池中：

第二个文件不需要再存储一份完整副本。它的索引从 [C1, C2, C3] 变为 [C1, C4, C3]：两侧未变化的数据块继续复用，只有中间发生变化的数据块需要新增。

定义数据块并不困难。真正困难的问题是：数据块应该在哪里结束？

2. 为什么固定位置边界会失效

假设把 abcdefghij 按每三个字节切分。如果在 c 后插入 X，此后的每个范围都会向后移动一个字节：

修改前：abcdefghij       → [abc] [def] [ghi] [j]
修改后：abcXdefghij      → [abc] [Xde] [fgh] [ij]

第一个范围仍然可以复用，但后续范围包含的字节已经不同，其内容地址也随之改变。这就是边界偏移问题：一次局部修改使此后的所有固定位置边界都发生移动。

固定大小边界简单而快速，但它追随的是偏移量，而不是内容。我们需要一种规则，能够根据当前位置附近的字节判断这里是否适合作为边界。

3. 内容定义分块（CDC）

内容定义分块（Content-Defined Chunking，CDC）让边界成为内容的函数。扫描器不会只因为到达预定偏移量就切分，而是让当前位置附近的字节参与判断这里是否为合适边界。

相同字节在相同配置下扫描，会产生相同的边界判断。局部修改可能扰乱一次判断，但扫描器随后可以重新识别未变化内容，而不会永久失去对齐。

从高层看，CDC 不断重复一个很小的循环：

读取字节 → 生成内容信号 → 判断切分或继续

下一节解释这个内容信号，之后再说明 FastCDC 如何利用它控制数据块大小。

4. 滚动指纹与 GearHash

通用滚动哈希：移动窗口的直觉

扫描器每次前进一个字节，同时复用此前状态。下面的动画展示了通用滚动哈希的直觉：

窗口从 ABCD 移动到 BCDE：移除离开的 A，加入新进入的 E，新状态复用上一状态的计算结果。这里的重点不是具体算术，而是扫描器不需要在每个位置从头计算。

GearHash：快速指纹

GearHash 是一种特别简单的 CDC 滚动指纹。对每个输入字节 bᵢ，它通过一次移位和一次固定表查询更新此前指纹：

fpᵢ = ((fpᵢ₋₁ << 1) + G[bᵢ]) mod 2ʷ

w 是指纹宽度，通常为 64 位。G 是一张固定表，包含 256 个预先计算的 w 位常量，通常选择得近似随机。表与位宽都属于分块配置；不同实现必须保持一致。在代码中，无符号回绕运算等价于对结果取模 2ʷ。

FastCDC 论文与 Josh Lee 对 GearHash 的解释描述了这个递推式及其三项基本操作：一次移位、一次加法和一次表查询。

GearHash 不保留显式字节窗口，也不会减去离开的字节。它只保留当前的 w 位指纹。每次移位都会把较早的表项贡献推向状态中最终被丢弃的一端；经过大约 w 次更新，更早字节的贡献就不再影响指纹。因此，GearHash 的行为类似滚动窗口，但实现只需要移位、加法与数组查询。

动画使用 16 位示例值展示概念上的逐字节递推。当前的 LayerFS 扫描器在热循环中展开了连续两次更新；从代数上看：

fpᵢ₊₂ = ((fpᵢ << 2) + (G[bᵢ] << 1) + G[bᵢ₊₁]) mod 2ʷ

这仍然是同一个递推式连续应用两次，同时允许实现在任一字节之后测试边界。

这里必须区分两件事：通用滑动窗口动画用于建立直觉，而 GearHash 的精确状态转移由上面的递推式定义。GearHash 能够快速寻找边界，但它不是密码学哈希，不能作为数据块的不可变身份。

哈希判定：切分还是继续

扫描器得到指纹后，还需要一条独立规则判断是否结束当前数据块。FastCDC 与当前 LayerFS 配置采用零掩码形式：

(fp & mask) == 0

如果选中的指纹位全部为零，扫描器就在此切分；否则继续。早期 Gear 系方法通常把判断写成 fp mod D == r；FastCDC 使用经过填充、分散的掩码，以及更方便的零值测试。具体判断式属于分块配置的一部分。

如果选中的位近似均匀且彼此独立，那么 N 位零值测试在每个测试位置匹配的概率约为 1 / 2ᴺ。这个概率只会让数据块大小趋向某个尺度，并不能保证每个数据块都具有精确大小；最小与最大限制以及 FastCDC 的归一化策略也会影响最终分布。

至此，基本 CDC 循环已经完整：更新指纹、进行判定，然后输出数据块或继续扫描。最小与最大范围限制让这个循环在工程上可用。后续 CAS 层可以对完整数据块计算哈希，用于命名和验证；边界指纹只是快速信号。

5. FastCDC

GearHash 降低了指纹计算成本，但廉价指纹并不会自动产生理想的数据块大小分布。Josh Lee 在莎士比亚语料上进行的 8 KiB GearHash 示例中，38.49% 的数据块小于 4 KiB，13.76% 大于 16 KiB，还有两个数据块超过 80 KiB。这些数字只来自该示例，并非 GearHash 的普遍保证；但它们清楚说明：平均值接近目标，并不意味着每个数据块都分布合理。（GearHash 文章）

FastCDC 论文指出了普通 Gear 系 CDC 的两个相关问题：边界判断只能看到较短的近期历史；而 GearHash 降低指纹成本之后，在每个位置执行判断本身就成为明显开销。在论文的评测中，FastCDC 的速度约为论文所选最佳开源 Rabin 基线的 10 倍，约为 Gear 与 AE 系 CDC 的 3 倍，同时去重率与 Rabin 接近。这些数字来自论文使用的工作负载与硬件，并不保证所有实现都能获得相同结果。（FastCDC 论文）

FastCDC 保留 GearHash 的快速指纹更新，同时调整其外围边界策略。可以把它理解为三道护栏，再加一道保证进度的安全栏：

• 最小长度之前： 只复制字节，不计算指纹，也不判断边界，因为此时不允许切分。
• 从最小长度到目标长度： 更新 GearHash 并使用严格的 MaskS，让匹配较少发生，鼓励数据块继续增长。
• 从目标长度到最大长度： 更新 GearHash 并使用宽松的 MaskL，提高匹配概率，鼓励数据块尽快结束。
• 到达最大长度： 如果此前没有匹配，则直接输出。这是正常的大小上限，不是 FastCDC 的第四项技术。

动画使用一个便于在单屏展示的示例配置：最小长度 4、目标长度 10、最大长度 18。LayerFS 实际构造配置属于实现契约，并不是通用 CDC 设置。

核心思路：先复制；随后让早期匹配较少发生，让后期匹配更容易发生，并在最大长度处无条件保证进度。

下面三项具名改进解释了这些护栏为何能够协同工作。它们是一条连续策略，而不是三种独立算法。（FastCDC 文章）

1. 扩展边界测试——增强哈希判定。 FastCDC 用零位填充掩码，并把有效位分散到指纹中更宽的范围。GearHash 更新本身没有变化：有效位数量相同，能够维持大致相同的匹配概率，同时让判断反映更长的近期历史。FastCDC 还把传统的余数／阈值测试简化为零掩码形式 fp & mask == 0。掩码必须采用确定性方式生成；不同掩码会产生不同边界并破坏复用。

2. 跳过不可能的早期切分——最小长度前跳过切分点。 达到最小长度之前，LayerFS 会把字节复制到候选数据块，但不更新或判断 Gear 状态。候选块达到最小长度后，GearHash 扫描才开始。这样既能避免极小数据块，也能省去禁止切分区间中的无效工作。被跳过的位置原本可能成为有价值的内容定义边界，因此这种优化可能以部分去重效果换取速度。

3. 让结果趋向目标——归一化分块。 目标长度之前，MaskS 包含更多有效位，因此匹配更少，鼓励数据块增长；目标长度之后，MaskL 包含较少有效位，因此匹配更容易，鼓励数据块结束。概念上可写为 mask = if len < target { MaskS } else { MaskL }。到达最大长度时，扫描器直接切分以保证进度。目标并不是让数据块都具有精确的目标大小，而是在良好去重效果下形成实用的大小范围。

输入结束时，剩余范围会作为尾块输出，即使它短于最小长度。这是正常的尾块行为，并非边界检测错误。如果输入以未配对的单个字节结束，该字节会加入尾块；输入结束本身不会触发额外边界测试。

因此，FastCDC 为 LayerFS 生成一组可重复的有序字节范围。接下来的两节把这些范围放回 LayerFS 的整体设计中，并预览由它们构成的文件表示。

6. 为什么 LayerFS 选择 CAS + CDC + COW

CAS、CDC 与 COW 分别解决三种存储放大。保持它们的契约彼此独立，可以让完整 LayerFS 设计更容易推理：

这种分工解释了 LayerFS 为什么不把版本信息写入数据块。数据块只是拥有内容派生身份的不可变字节。FastCDC 选择其范围，CAS 负责存储和验证，有序文件表示则记录如何用这些范围重建文件。

结构级 COW 位于文件表示之上。当一个文件发生变化时，它只为该文件创建新清单，并只在该文件所在路径上创建新目录记录。其他文件与子树继续和此前的不可变根共享。

各部分职责如下：

1. FastCDC 寻找实用且可重复的边界，无需为每个候选位置重新扫描整个文件。
2. CAS 为每个完整数据块提供不可变身份，并复用相同字节。
3. 文件表示 保留数据块顺序、长度与精确重建所需的信息。
4. 结构级 COW 只重建受影响路径，并生成新的完整不可变根。

因此，FastCDC 是边界策略，而不是存储格式。改变物理 CAS 布局或 Layer 的持久化方式，不应该改变逻辑数据块范围、数据块身份或重建后的字节。

7. 接下来做什么

现在，我们已经能够解释完整的分块决策：从字节流开始，更新内容派生指纹，应用 FastCDC 策略，然后输出长度受限的范围。我们也知道这些范围为什么有用：局部修改之后，未变化范围仍可保留原来的 CAS 身份。

分块器之上还缺少一个组件：完整文件需要一份持久、有序的数据块清单。存储层可以通过以下步骤构建这种表示：

• 对每个完整数据块计算哈希，得到它的 ChunkId；
• 按顺序记录数据块 ID 与长度；
• 重建并验证原始文件字节；
• 测量局部修改能够复用多少既有数据块。

规划中的第 1.3 节会把文件表示带入文件系统树：一个已编辑文件、一条重建路径，以及一个新的不可变根。LayerStack 与 Agent 工作区历史将在此之后讨论，届时根模型已经建立。