用 Rust 和 Durable Objects 为智能体构建细粒度版本控制

# 使用 Rust 和 Durable Objects 构建面向智能体的细粒度版本控制 来源：https://delta.dev/blog/fine-grained-version-control-for-agents 2021 年，Nathan、Max 和我共同创立了 Zed Industries，目标有两个：构建一个非常快速的代码编辑器（https://zed.dev/blog/videogame），以及从根本上改变团队协作开发软件的方式（https://delta.dev/blog/introducing-deltadb）。如今有数百万人在使用 Zed，我为我们所构建的一切感到自豪（https://zed.dev/blog/zed-1-0）。 过去一年里，我们一直在致力于实现第二个目标。我相信，编写软件的过程就是在你自己的头脑中、或与团队成员一起，不断澄清一个问题，直到代码的产出变得顺理成章。清晰的思维带来清晰的代码；混乱的思维带来混乱的代码。智能体并没有改变这一点。我们只是在以快得多的速度生产代码，而且越来越多的澄清工作发生在与智能体的对话中。在最好的情况下，这些代码背后的上下文被锁在了当周的智能体框架里；在最坏的情况下，它永远丢失在 Slack 中，或者被压缩成一条智能体写的、你从未读过的提交信息。 DeltaDB（https://delta.dev/deltadb）就是我们的答案——一个面向智能体上下文的版本控制系统。你可以指向一段代码，找回其背后的推理过程，并询问编写它的人类或智能体为什么它长成现在这个样子。 在这篇文章中，我们将深入探讨我们如何构建一个系统：实时流转来自人类和智能体的每一次变更，将它们的编辑合并到一个单调增长的因果图中，并将每一次编辑与产生它的对话关联起来。与 Zed Industries 的一贯作风一样，我们从一个空仓库开始。 ## 架构（https://delta.dev/blog/fine-grained-version-control-for-agents#architecture） DeltaDB 是一组 CRDT（https://zed.dev/blog/crdts）的集合，全部存储在本地 SQLite 中，并通过有向无环图（DAG）相互链接。图中的每个节点称为一个 *delta*（增量），它是可表示的最小变更单元。 结合起来，这使我们能够建模一个智能体线程（https://delta.dev/docs/agents/threads）的核心状态：它的对话、它的文件，以及与之相关的一切。 使用 CRDT 让客户端可以自主推进，并对网络故障或分区保持弹性。我们最终会将所有状态同步到服务器，但我们不需要客户端始终保持连接：变更会立即在本地应用，尽可能地再进行同步。这使得实现从异步移交线程到与队友实时协作（https://delta.dev/docs/collaboration/collaborate-thread）的整个协作谱系都变得直截了当。 DAG 使得系统中每一个可能的中间状态都可以被表示出来。这带来了一些很好的特性。例如，我们可以轻松地在线程及其工作树的历史中来回穿梭。它还让我们能用一个非常紧凑的版本来表达系统的全部状态：位于图各顶端的 delta（也称为 *frontier*，前沿）。它的大小只取决于同时打开的分支数量，而不是取决于曾经有过多少个写入者。 我们的设计与 Gentle 和 Kleppmann 在 Eg-walker 论文（https://arxiv.org/abs/2409.14252）中开创的工作高度相似。 使用 DAG 的主要缺点是，我们需要遍历图来检测某个 delta 是否已经包含了另一个 delta 的影响。如果使用版本向量（https://en.wikipedia.org/wiki/Version_vector），我们可以通过比较计数器来回答这个问题。尽管那比遍历父链接更便宜，但版本向量假设参与者数量少且存活时间长。然而在线程中，人类和智能体不断来来去去，一旦某个参与者做过一些修改，向量就无法降低计数器。因此即使参与者已经离开，向量也只会不断增长。带点版本向量（https://arxiv.org/abs/1011.5808）也有类似的问题，如下图所示。 你的客户端在主时间线上写入 delta 1、2 和 3，每个都由客户端的单一时钟编号。只有一条时间线时，版本向量、带点版本向量和 DAG 前沿都能正确描述主时间线。然后一个子智能体在同一个客户端上分叉出一条时间线，于是它的 delta 5 和 7 取到了主时间线的 4、6 和 8 之间的编号。版本向量将主时间线描述为 `你: 8`，这覆盖了你截至 8 的所有 delta，包括子智能体的 5 和 7。带点版本向量保留 8 作为它的点（dot），但它的上下文仍然是计数器，所以它必须说 `你: 4` 加上一个 6 的例外，而且每一次进一步的交错都会增加一个例外。主时间线的 DAG 前沿就是 8，从 8 沿父链接回溯会访问 6、4、3、2 和 1，恰好就是主时间线。 接下来，三个 Cloud Runner 沙箱从 8 分叉出来。每个沙箱都打开自己的数据库，因此每个都是新的写入者。将它们的工作合并为 delta 9 会把四个顶端收拢为一个，但两个向量都会为每个沙箱增加一个计数器。当沙箱关闭后你写入 delta 10 时，向量仍然携带那些计数器，而前沿只是单个 delta 10。 前沿的代价是因果查询变成了对父链接的遍历，而 DeltaDB 无论如何都要存储这些链接。 > **动画说明（图示文本）：** 你的时钟 → 10。主时间线。子智能体。沙箱 A 已离开，沙箱 B 已离开，沙箱 C 已离开。A1 B1 C1 A2 B2 C2。1 2 3 4 5 6 7 8 9 10。主时间线的版本。 > > 版本向量：`你 10`、`A 2`、`B 2`、`C 2`，还声称包含 5、7。 > > 带点向量：`点 10`、`你 4 + 6 + 8 + 9`、`A 2`、`B 2`、`C 2`，3 个例外。 > > DAG 前沿：9、10，精确 8/8。 祖先查询对我们来说是一个很好的折衷，因为我们反正需要存储每一个版本。它们在实践中也很快速，因为我们将 delta 的祖先关系与其负载分开存储。祖先数据非常小，并且按因果顺序存储，因此这些查询可以充分利用局部性。 将每个 delta 作为 DAG 中的一个节点，还能让我们将其网络表示与 CRDT 在内部表达其影响的方式解耦。例如，这就是我们定义文本编辑的方式： ```rust struct EditTextDelta { parent: Version, offset: usize, text: String, } ``` 注意 `parent` 和 `offset` 足以唯一标识缓冲区中的一个位置，即使在并发编辑存在的情况下也是如此。大多数时候，缓冲区已经处于 `parent` 状态，编辑可以直接应用。当不是这样时（例如，其间发生了并发编辑），客户端会*具体化*（reify）`parent` 处的版本，重建该时刻的缓冲区。然后它将偏移量转换为内部表示（在我们的例子中是片段 ID，类似于我们在 Zed 中的做法），并在我们要应用编辑的目标版本的缓冲区中定位该片段 ID。 这使得 delta 在网络上传输非常廉价，同时也让我们可以更改内部片段表示，并将未使用的片段换出内存。 ## 强大的 B+ 树（https://delta.dev/blog/fine-grained-version-control-for-agents#the-mighty-b-tree） 我们将所有数据存储在 SQLite 中。这些数据大致可以分为两类：关系型数据和版本化数据。 关系型数据相当直截了当。例如，在客户端上我们存储你创建或打开的所有线程。这放在一个传统的表里，没有任何特别之处。 版本化数据才是有趣的地方。整个系统的关键在于快速具体化任意版本的能力。正如我们上面看到的，应用并发 delta 取决于此，而且我们也不想在浏览历史或将线程旧版本的工作树挂载到文件系统上时等待很长时间。 为了使其快速，我们为 DAG 中最近使用的节点缓存整个状态的快照（外加我们固定住的几个重要版本）。然后，从我们想要的版本开始，沿 DAG 回溯到最近的有缓存快照的祖先，并应用其间的每一个 delta。 为每个缓存的版本存储完整的 CRDT 副本成本过高。相反，我们将整个状态表达为写时复制（copy-on-write）的 B+ 树。这意味着我们可以复用先前快照中的大多数节点，只为重放的 delta 所触及的路径付出代价。 > **动画说明（图示文本）：** 一个 delta 的 DAG。到目前为止的历史已被折叠进 delta P。你的时间线写入 delta 1 到 4、6 和 8，一个子智能体在 3 之后分叉并写入 5 和 7，然后 delta 9 合并两者，在 10 之前再有 12 跟进。P 的快照被固定，版本 2 和 4 有缓存的快照。要具体化版本 9，一次回溯从 9 沿两个分支上的父链接进行。它到达 delta 4，它有一个覆盖了 4 所见一切的快照，因此沿子智能体分支的回溯在 delta 3 处停止。剩下 delta 5、6、7、8 和 9 需要重放。 > > DAG 向上移动，版本 4 的 B+ 树从其快照中展开：一个根节点、三个内部节点和九个文本片段叶子。它的根被克隆为版本 9 的根，与版本 4 共享每个节点。然后每个 delta 从新根向下走到它的叶子。delta 5 克隆其路径上的内部节点和叶子，原节点留给版本 4。delta 6 落到同一个叶子，发现其路径已被克隆，就地写入。delta 7 克隆下一个子树中的一条路径，delta 8 就地写入它。delta 9 复用 delta 7 克隆的内部节点，只克隆它自己的叶子。从左到右阅读，叶子按顺序持有 delta 1 到 9。版本 9 最终拥有六个自己的节点，另外七个与版本 4 共享。它的快照加入缓存，而版本 2 的快照——最近最少使用的——被淘汰。点击任何一个 delta，都会以同样的方式具体化其版本，从最近的缓存快照出发。 > > **图示标签：** 1 2 3 4 5 6 7 8 9 10 11 12 / 1 2 3 4 5 6 7 8 9 / 4 / 9 8/8。 我们的 B+ 树是 Zed 的 SumTree（https://zed.dev/blog/zed-decoded-rope-sumtree）的一个变体。Zed 中的 `SumTree` 是一个只追加的 B+ 树，其内部节点对子节点进行汇总。要编辑一个 `SumTree`，你必须从树的开头切出一个前缀直到插入点，推入新项并跳过你想删除的项，最后追加后缀，这会重建切口上的每个节点。 相比之下，DeltaDB 的 B+ 树通过一个可变游标就地编辑。它快得多，因为我们对树做的调整少得多（见下图动画）。就地修改还让我们能精确地跟踪哪些节点被分配、修改或释放。在提交时，新节点变成插入，被修改的节点在其现有行中重写，被释放的节点只减少其引用计数。所有节点都存储在一个通用的 `nodes` 表中。 > **动画说明（图示文本）：** 同一个 B+ 树的两份副本，在叶子中持有文本 "Hello, wld!"，叶子最多四个字符，每个内部节点统计其子节点下的字符数。快照 v1 是两者的克隆，因此共享每个节点。在偏移 8 处输入 "o"，每棵树都通过计数进行查找：根跳过前 7 个字符，游标落在第三个叶子。 > > 上方的树按照 Zed 的 SumTree 的方式编辑。它在偏移处切开树，因此切口上的三个节点中的每一个都分裂为前缀半部和后缀半部。它将 "o" 推入前缀并追加后缀，当两半重新汇合时，后缀的三个节点被丢弃。那就是一个字符构建了六个节点、丢弃了三个。 > > 下方的树按照 DeltaDB 的可变游标的方式编辑。它走过同样的三个节点，因为 v1 仍然共享每一个，它在写入前复制该节点。原节点留给 v1，v1 仍然读到 "Hello, wld!"，而编辑未触及的节点保持共享。 > > 接着输入 "r"，重建又构建六个节点并丢弃六个，而游标发现其整条路径已全部取消共享，就地修改那三个节点，什么也不构建。 > > **图示标签：** text → Hello, world! / v1 → Hello, wld! / Zed SumTree：slice, push, append，built 12，thrown away 9+6+6，7 4 2 2 wl 3 4 4 2 7 6 / Hello,␣world! / v1 → DeltaDB B+ tree：mutable cursor，built 3，thrown away 0+0+0，7 4 2 2 wl 3 4 4 2 7 6 / Hello,␣world! / v1。 ## 时间线与同步（https://delta.dev/blog/fine-grained-version-control-for-agents#timelines-and-synchronization） 客户端可以使用 *timelines*（时间线）在 DAG 中跟踪任意数量的前沿。例如，当启动一个子智能体时，我们创建一条停靠在父线程前沿处的新时间线，并开始并行做出更改。所有时间线共享同一个 DAG，因此它们可以在之后的任何时间点被合并回来。 这一切都不涉及 Git，而且关键的是，跨智能体协作不需要提交操作。 时间线也用于客户端之间的同步。当一个线程被共享时，客户端与服务器建立 WebSocket 连接，并订阅它感兴趣的时间线。对于每条时间线，我们执行一个同步步骤，交换自上次连接以来双方各自错过的所有 delta（如果是首次连接到服务器，则交换全部）。这是通过遍历 DAG 并发送一个对数间隔的版本列表来找到最近的公共祖先来实现的。然后每个新 delta 都通过 WebSocket 增量发送，由服务器保存，并推送给订阅该时间线的其他所有客户端。 > **动画说明（图示文本）：** 三行分别显示同一条时间线在你的客户端、服务器和你队友的客户端上，每个客户端与服务器之间各有一条 WebSocket。你开始时离线：你的三次编辑留在你的机器上，而你队友的两次编辑通过他们已打开的套接字到达服务器并被保存在那里。当你重新连接时，你的客户端为历史打开一个 WebSocket 并订阅该时间线。然后它从自己的时间线发送五个祖先版本，在顶端附近密集，在更远处稀疏。服务器从最新到最旧检查它们，不知道你最近的三次编辑，并在第一个共享版本——公共祖先处停止。它回复一个该祖先之后所有 delta 的列表，不带内容。你的客户端已经拥有第一个，因此它只通过同一个套接字获取你队友的两次编辑。然后它上传自己的三次编辑；服务器保存它们并推送给你的队友。现在每个人都有相同的历史，两个套接字都保持打开。从那时起，新的编辑在其写入处保存，通过套接字发送，由服务器保存，并推送给另一个已订阅的客户端，无需探测也无需获取。你队友的下一次编辑也以同样方式传回给你。在离线一段时间后重新连接，或错过一次更新，会再次运行追赶轮次。 > > **图示标签：** 你（离线）→ 服务器 → Durable Object → 队友（离线）→ WebSocket → WebSocket。 重新连接的处理方式也一样，这使得推理 delta 投递的正确性变得简单直接。 ## 每个线程一个 Durable Object（https://delta.dev/blog/fine-grained-version-control-for-agents#one-durable-object-per-thread） 我们设想这样一个世界：每个人类都创建并交互越来越多的智能体。在那样的未来，很难想象将所有线程状态保持在单一服务器上。 在 DeltaDB 中，每个线程都被同步到它自己的 Cloudflare Durable Object（https://developers.cloudflare.com/durable-objects/）。该对象在客户端首次连接时苏醒，创建线程在服务器上不产生任何成本。每个客户端为其感兴趣的每个线程建立一条 WebSocket 连接。除了建立连接时的身份验证之外，这本质上是一个无共享（share-nothing）架构。这意味着我们随线程数量水平扩展，只要 Cloudflare 能承载流量。 你创建一个线程，最初它只存在于你的机器上。当你的客户端连接时，该线程的 Durable Object 被唤醒。它以该线程的历史命名，将那段历史保存在自己的 SQLite 数据库中，并接收你离线时写的 delta。你的队友、一个本地智能体和一个 Cloud Runner 沙箱打开同一条线程，每个都向同一个对象建立一条 WebSocket 连接。当智能体写入一个 delta 时，对象保存它，然后推送给连接到该对象的其他所有人。