Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

LayerFS

临时工作区,持久共享历史。

LayerFS 为每个 Agent 提供隔离、可随时丢弃的文件系统分支,而无需复制共享基础。值得保留的状态会成为持久、去重的检查点,并携带工作区级工具调用历史,可随时派生、回溯或复用于并行开发、环境实验与 MCTS 式 rollout。

01 · LayerStack 存储模型

核心存储机制

CAS、CDC 和 COW 通过复用未变化的对象、文件区域与文件系统结构,让 LayerStack 历史保持存储高效。

01 · 身份

内容寻址存储

根据规范字节为不可变对象命名,校验读取,并在文件、LayerStack 和 Agent 之间复用完全相同的内容。

02 · 字节局部性

内容定义分块

让局部修改附近的分块边界保持稳定,避免因一小处变化而重新存储整个大文件。

03 · 结构局部性

写时复制

将变更发布到新层时,只重建发生变化的文件及目录路径,父层中未变化的子树继续共享。

从任意层检出 Agent 临时文件系统

LayerStack 记录完整的文件系统检查点。Agent A 可以从 L1 开始,Agent B 则可独立从 L3 开始。每个 Agent 都拥有私有工作空间,而所选择的历史仍然共享。

一个包含 L0 到 L4 的 LayerStack。Agent A 从 L1 检出临时文件系统,Agent B 从 L3 检出另一个独立的临时文件系统。
一个 LayerStack、两个检出点,以及两个可供 Agent 独立工作的临时文件系统。

02 · 系统边界

LayerFS 组件

存储引擎已经实现;SDK 和文件系统投影是围绕它规划的接口。

已实现核心

存储引擎

负责身份、规范对象、CDC、文件清单、结构级 COW、pack、不可变 CAS 准入、生命周期协调和校验读取。

规划中的接口

SDK

将提供稳定的文件系统、工作区、LayerStack 与发布操作,而不泄露私有 CAS 句柄或存储格式。

规划中的接口

文件系统投影

向 Agent 提供工作区,并捕获范围受限的文件系统变更;身份、CDC、COW 和准入仍由存储引擎负责。

03 · 阅读路线

从第一性原理开始构建

本书沿着存储模型的依赖顺序展开:先建立不可变内容身份,再把文件修改限制在局部范围,只重建发生变化的文件系统路径,最后把这些状态组织成 Agent 历史。

第 1 章 · 编写中 基础:CAS + CDC + COW 完全相同对象复用 → 文件区域复用 → 文件系统结构复用
第 2 章 · 规划中 优化存储核心 类型化对象、验证准入、身份、pack 与高效读取
第 3 章 · 规划中 LayerStack 与 Agent 工作区 历史、私有 head、检查点、派生、回滚与发布

04 · 生态

协作项目

LayerFS 提供存储机制;周边项目负责执行环境与版本控制工作流。

Ephemeral AI Lab 提供支持

第 1 章 · 基础

基础:CAS + CDC + COW

一个文件系统状态在逻辑上应该完整,在物理存储上应该增量。当多个 Agent 从同一环境并行探索时,这不是后续优化,而是基本要求。

为什么存储效率是设计约束

LayerFS 的目标,是让一个环境支撑许多彼此隔离的 Agent 工作区。每个工作区都必须表现为完整文件系统:工具可以修改、创建检查点、派生、恢复、比较或回滚。

最直接的实现,是在 Agent 派生或记录检查点时复制当前文件系统。这样确实实现了隔离,却采用了错误的成本模型:一个工作区中的少量修改,也可能要求再次存储整个工作区。

多 Agent 开发让这种不匹配从偶发问题变成基本矛盾:

  • 共同起点。 Agent 通常从同一个代码库、依赖与已生成环境开始。
  • 稀疏修改。 一次工具调用相对于共享状态,通常只改变少量文件。
  • 高分叉与长历史。 并行尝试、环境实验与 MCTS 式 rollout 会产生大量相关状态,检查点还会保留此前状态。

如果每个逻辑状态都独占自己的字节,存储量就会随着所有工作区的总大小增长。LayerFS 选择另一条不变量:新状态的物理成本应该取决于发生了什么变化,而不是该状态所呈现的完整文件系统有多大。

这个选择决定了文件系统模型。工作区从不可变根开始;读取复用该根可达的对象;写入创建新对象而不修改共享基础;检查点记录一个新根,同时继续引用所有未变化内容。隔离来自每个 Agent 各自演进的根,而不是复制全部字节。

CAS + CDC + COW 如何落实这一选择

结构共享可能在对象、文件或目录树三个层次失效。因此 LayerFS 在三个层次上都实现复用,第 1 章也按同样顺序构建它们:

1.1 · 已发布
CAS:内容寻址存储 对象复用 · CAS 只存储一份相同字节

内容寻址存储从字节导出身份。相同的不可变对象会收敛到同一身份与同一份存储副本。

仍未解决:只改变一个字节,也会让整个文件对象获得新身份。

1.2 · 已发布
CDC:分块与内容定义边界 文件区域复用 · CDC 把局部编辑限制在局部

内容定义分块让未变化区域保持稳定边界,因此少量插入或删除只替换附近数据块,而不是整个文件。

仍未解决:完整文件系统仍需生成新根,但不能复制每个文件与目录。

1.3 · 规划中
写时复制文件系统树 树结构复用 · COW 只重建发生变化的路径

写时复制只创建新的文件清单与已编辑路径上的目录记录,其他文件和子树继续共享。

最终结果:每个检查点都是完整的不可变根,但物理成本取决于修改量,而不是工作区大小。

CAS:内容寻址存储

大多数存储系统根据数据的存储位置为其命名,例如路径名、对象键、URL 或数据库行。内容寻址存储(Content-Addressed Storage,CAS)采用另一条规则:它根据对象的字节内容生成对象名称,再用这个名称存储、读取、复用和校验对象。

这条规则很简单,却改变了存储引用所表达的含义。/docs/report.txt 这样的路径明天可能指向不同的字节;内容地址则始终标识同一组字节。字节一旦改变,地址也随之改变。

本节从第一性原理出发构建一个朴素 CAS,介绍它的架构、核心算法、精确内容去重、实际应用,以及文件级对象为什么需要分块表示。本节暂不讨论内容定义边界算法、LayerFS 对象格式、类型化身份、对象图、准入、pack 或生产级发布。只有先明确 CAS 的基本契约,这些机制的设计动机才容易理解。

1. 地址就是内容

先看一个传统文件系统路径:

/docs/report.txt

路径告诉文件系统去哪里寻找数据,却不会永久标识在那里找到的字节。进程可以在保留路径的同时覆盖文件,也可以把同一个文件移动到其他路径。名称与内容之间的关系是可变的。

内容寻址存储从相反方向出发:

object address = hash(object bytes)

地址由内容生成,而不是脱离内容单独指定。只要内容不变,地址就不变;内容发生变化,地址也会变化。

两种系统的区别并不是一个有位置、另一个没有。任何物理存储最终都必须把字节放在某个位置。真正的区别是公开身份所表达的含义:

命名模型名称标识什么内容变化时内容移动时
位置寻址一个可变位置名称可以不变名称通常改变
内容寻址一组确定的字节序列地址改变地址可以不变

因此,CAS 为不可变数据提供了一套实用的表达方式。两个调用方引用同一个内容地址,就表示它们期待完全相同的字节,即使存储系统后来改变了对象的物理位置也不影响这一点。

查找方式也随之改变。CAS 不会在存储中搜索与请求“相似”的字节。调用方已经持有对象标识符,存储系统会像键值存储使用键一样,直接用该标识符定位对象。区别在于,CAS 的键由值本身生成。

2. 从字节生成身份

x 是对象的字节序列,H 是密码学哈希函数。最小的内容身份可以写成:

id(x) = H(x)

哈希函数处理任意长度的输入,并产生固定长度的摘要。CAS 依赖以下性质:

  • 确定性: 使用同一算法哈希相同字节,会得到相同摘要。
  • 变化敏感性: 输入发生变化时,应产生不相关的摘要。
  • 抗碰撞性: 对于选定算法,寻找两个摘要相同但内容不同的输入在计算上应不可行。
  • 流式计算: 无需把整个对象载入内存,也能增量计算摘要。

摘要并不是“碰撞绝不可能发生”的数学证明,而是一项安全假设:摘要足够大、算法足够强,使意外或恶意碰撞在系统的威胁模型下不可行。长期运行的系统还必须考虑哈希算法老化后的迁移方式;Git 的哈希函数迁移设计说明了为什么不能假设算法选择永远不变。

身份支持内容校验

假设调用方通过 expected_id 请求对象,存储返回 content。调用方或存储重新计算摘要,再与请求的 ID 比较:

actual_id = H(content)

if actual_id != expected_id:
    return integrity_error

如果二者不同,返回的字节就不是所请求的对象。这项检查可以发现数据损坏、截断、错误的定位器,或者存储返回了其他对象。

这是一项完整性检查,而不是完整的安全系统。它不能证明字节由谁创建、内容是否可信、是否经过加密,也不能保证存在另一个副本用于修复。

身份支持精确去重

如果地址为 d 的对象已经存在,再次写入相同对象时便可以直接复用,而不必写入另一份 payload。这就是发生在 CAS 对象边界上的精确内容去重

对象边界很重要。以整个文件为对象的 CAS 可以识别两个完全相同的文件,但一个字节的变化就会让编辑后的文件成为另一个完整对象。若要复用文件内部未变化的区域,系统必须把文件拆成更小的对象。分块是额外的设计选择,并不属于 CAS 的基本定义。

CAS、去重和增量备份之间的区别值得明确说明:

概念首要问题基本机制
内容寻址如何为对象命名?根据内容生成身份
去重哪些重复数据可以共享存储?只保存一个物理实例并复用它
增量备份相比上一次备份发生了什么变化?记录相对较早备份发生变化的数据或文件

这些技术经常一起出现,尤其是在备份产品中,但它们不是同义词。BlinkDisk 的 CAS 概览描述了一套分块备份系统;真正让编辑后文件中的未变化区域得以复用的是分块。其关于去重增量备份的独立介绍进一步说明了这些相关概念。朴素 CAS 即使没有实现分块或增量备份链,也能对完全相同的对象去重。

3. 架构:最小内容寻址存储

最小 CAS 只需承担一组边界清晰的职责:

  1. 接收一段字节序列;
  2. 生成对象标识符;
  3. 为该标识符保留一个不可变对象;
  4. 根据标识符定位对象;
  5. 可选地重新哈希返回的字节,对其进行校验。

组件职责不负责
哈希器根据对象的全部字节生成身份选择便于人类阅读的名称
定位器把对象 ID 解析到物理存储定义对象的含义
对象存储保留不可变的 payload 字节检查点、分支或目录
校验器确认返回字节与所请求 ID 一致修复损坏的对象
客户端或上层保存有意义的名称以及对象间关系修改已安装对象的字节

定位器不一定需要数据库。简单存储可以直接根据摘要生成路径;更大的存储可能因为对象被打包、远程保存、复制,或在不同存储层之间移动而使用索引。两种设计都保留相同的分离关系:

logical identity:  which exact bytes?
physical locator:  where are those bytes currently stored?

在 CAS 之上,应用通常还会维护用户关心的名称与关系。备份系统把快照和路径名映射到已存储对象;Git 把 tree 和 commit 映射到对象,再用可变的 branch 名选择 commit;容器 registry 把 tag 映射到 manifest,而 manifest 中的 descriptor 则通过 digest 标识 blob。上层结构赋予对象含义,朴素 CAS 只存储不透明字节。

这个边界是有意为之。当 CAS 的核心契约不再同时试图扮演文件系统、版本控制系统、备份目录或分布式可用性服务时,它会更容易理解和验证。

4. 核心算法:Put、Get 与 Verify

从概念上看,朴素 CAS 只有两个操作:

put(bytes) -> object_id
get(object_id) -> bytes

核心算法可以写成:

put(bytes):
    id = hash(bytes)

    if id is not already stored:
        publish bytes as the immutable object named by id

    return id

get(id):
    bytes = locate and read the object named by id

    if hash(bytes) != id:
        return integrity error

    return bytes

publish ... as immutable 这句话隐藏了真正的工程工作。生产实现必须正确处理崩溃、并发写入、目标已经存在、部分写入和存储错误,同时不能覆盖可信数据。第 2 章会回到这些机制。现在只需把握逻辑规则:对象一旦成功发布,与其 ID 关联的字节便永不改变。

Put 操作

两条路径都会返回同一个对象 ID,区别只在于是否执行发布工作。

相同输入会产生相同的候选 ID,因此完全重复的对象会汇聚到同一个名称。但可信实现不能仅仅因为预期路径已经存在对象,就盲目信任当前占用者。第 2 章会通过验证准入强化这条复用路径。

Get 操作

调用方提供自己所期待字节的 ID。存储系统解析 ID、读取字节并重新计算摘要。摘要匹配,说明该字节序列与请求的内容身份一致;摘要不匹配则必须报告错误,不能假装读取成功并返回字节。

校验可以发生在不同边界。本地存储可以在每次读取时校验,也可以在准入时校验并依赖可信的不可变介质,还可以让客户端校验远程响应。校验位置会改变成本与信任假设,但不会改变 H(bytes) = requested ID 这条等式。

一个具体例子

假设字符串以 UTF-8 字节存储:

写入输入对象 ID新增 payload 存储量
1helloH(hello)5 字节
2helloH(hello)0 字节
3hello!H(hello!)6 字节

应用总共提交了 16 个逻辑字节,但 CAS 只保留了 11 个唯一 payload 字节。第二次写入 hello 时仍需要识别内容——通常需要读取并哈希这 5 个字节——但不需要再保存一份 payload。

这个小例子同时体现了朴素 CAS 的优势与边界:

  • 完全重复的对象共享同一 ID,因此保留成本很低;
  • 任意字节发生变化,都会产生新的整对象身份;
  • 上层引用必须解释应用为何关心这些对象。

5. 真实系统中的内容寻址

CAS 很少独自构成完整产品。成熟系统把它作为稳定对象层,再增加用于表达对象含义、可达性、策略和高效物理表示的结构。

系统内容寻址提供什么周边系统增加什么
Git不可变对象的稳定身份Blob、tree、commit、branch、tag、历史遍历和 packfile
Venti由摘要命名的不可变归档数据块Root、tree、index、cache 和归档策略
备份系统文件或数据块的精确复用扫描、分块、快照目录、保留策略、加密和恢复工作流
OCI 镜像通过 digest 标识并校验 blob 与 manifestRegistry、tag、media type、分发和平台选择
Bazel 远程缓存内容寻址的构建输入与输出Action key、action result、执行策略和可复现性假设
IPFSBlock 与有向无环图(DAG)的内容标识符分块、codec、路由、传输、可变命名和 pinning

Git 是最常见的教学示例。正如 Git Objects所介绍的,其对象数据库保存内容寻址的 blob、tree、commit 和 tag。main 这样的 branch 本身并不是不可变内容地址,而是一个用于选择 commit 的可变引用。

这种分离让 Git 可以保留稳定的历史对象,同时允许 branch 名不断前进。Git 也说明了逻辑身份与物理编码可以分别演进:packfile可以用 delta 紧凑保存对象,而不改变 commit 与 tree 使用的身份。

Venti是较早且影响深远的网络存储系统,其核心就是由内容寻址的不可变数据块。客户端在块存储之上构建归档数据结构,再次体现了相同边界:CAS 提供稳定数据块,上层提供 root 和解释方式。

容器和构建系统使用内容寻址来支持分发与复用。OCI image specification 的 descriptor携带 digest,用于标识和校验被引用的内容。Bazel 远程缓存把存储文件的 CAS 与 action cache 分开,后者负责将 action 映射到结果。两个例子中,CAS 都只是更大协议中的一个组件。

分布式 CAS 还揭示了另一条边界。IPFS 内容标识符可以独立于具体主机标识内容,但知道 CID 并不保证当前有可达 peer 提供数据。内容身份与内容可用性是两种不同的性质。

备份系统通常会组合前面提到的三个概念:分块选择去重单位,内容寻址为其命名,快照或增量元数据记录可恢复状态。因此,存储节省量和恢复行为属于完整的备份设计,而不是只靠哈希就能获得的性质。

6. CAS 为什么需要分块表示

CAS 的去重单位是对象。如果整个文件是一个对象,两个完全相同的文件可以共享同一身份;但只要改变一个字节,整个文件的身份都会变化。若没有 delta 压缩之类的其他编码方式,编辑后的版本就会再增加一份完整文件 payload。

分块表示把 CAS 的去重单位从整个文件改为更小的字节区域。每个数据块拥有自己的内容身份,一份小型 manifest 记录它们的顺序。局部编辑后,未变化的数据块保留原有身份并继续复用;只有受边界影响的区域和 manifest 需要产生新对象。

变化整文件 CAS分块 CAS
完全复制复用一个整文件对象复用全部数据块,通常也复用同一 manifest
局部覆盖保留另一份整文件 payload只保留受影响的数据块和新 manifest
插入或删除保留另一份整文件 payload复用程度取决于分块边界能否重新同步
增量传输发送发生变化的整文件对象发送缺失的数据块和新 manifest

例如,如果一个 1 GiB 文件作为单个 CAS 对象存储,那么一次单字节修改可能新增 1 GiB payload。使用分块后,新增 payload 只与受影响的分块区域以及一份小型 manifest 成正比。实际大小取决于数据块尺寸和边界行为;分块改善的是复用机会,并不保证每次编辑只改变一个数据块。

CAS 提供身份与精确复用;分块决定 CAS 可以复用哪些更小的区域。

这就引出了下一个设计问题:边界应该落在哪里?固定大小的边界很简单,但一次插入可能让后续所有数据块发生偏移。下一节将介绍内容定义分块,它根据内容选择边界,使字节流能在局部编辑后重新同步。

CDC:分块与内容定义边界

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

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

版本 1 包含 abcdefghij,并映射到 H(file 1);版本 2 插入 X 后映射到不同的 H(file 2)。

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

1. 什么是数据块?

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

字节流 B 包含 abcdef,并被切分为三个连续数据块:C0 包含 ab,C1 包含 cd,C2 包含 ef。按顺序连接这些数据块即可重建 B。

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

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

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

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

文件 1 abcdef 与文件 2 abxyef 分别使用有序索引;两个文件共享 C1 与 C3,文件 2 只增加新的数据块 C4。

第二个文件不需要再存储一份完整副本。它的索引从 [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:移除离开的字节,加入新字节,并在不重新哈希整个窗口的情况下更新哈希状态。

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

GearHash:快速指纹

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

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

GearHash 更新动画:当前字节进入一个固定的 256 项表查询,此前指纹向左移位,两项在示例中按 16 位回绕相加,从而在不减去离开字节的情况下生成新指纹。

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

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 策略动画:最小长度之前只复制字节,不计算指纹或判断边界;最小长度到目标长度之间使用严格的 MaskS;目标长度之后使用宽松的 MaskL;如果此前没有匹配,则在最大长度处输出数据块。

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

下面三项具名改进解释了这些护栏为何能够协同工作。它们是一条连续策略,而不是三种独立算法。(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这些字节是否已经出现过?ChunkId 寻址的不可变字节
文件表示应该按什么顺序读回这些范围?有序的数据块引用与长度
结构级 COW哪些文件系统记录必须改变?复用所有未变化子树的新根

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

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

各部分职责如下:

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

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

7. 接下来做什么

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

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

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

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