使用Prolly树的版本控制数据库

# 使用Prolly树实现版本控制的数据库 来源：https://lwn.net/Articles/1068864/ > **你知道吗……？** LWN.net 是一个由订阅用户支持的出版物；我们依赖订阅用户来维持整个运作。请通过[购买订阅](https://lwn.net/Promo/nst-nag4/subscribe)来帮助我们，让 LWN 持续在线。 现代数据库和文件系统广泛使用 **B 树**（[B-tree](https://en.wikipedia.org/wiki/B-tree)），这是一种针对在块设备上存储有序键值列表而优化的树结构。 [Dolt](https://github.com/dolthub/dolt#dolt-is-git-for-data) 是一个采用 Apache 2.0 许可证的项目，它巧妙利用 B 树的变体来支持整个数据库的高效版本控制。它使用的这种数据结构很可能对其他项目也有参考价值。 Dolt 背后的公司 [DoltHub](https://www.dolthub.com/) 通过销售三个 Apache 许可证开源项目的托管版本盈利：Dolt、[Doltgres](https://github.com/dolthub/doltgresql#doltgres-is-dolt-for-postgres) 和 [DoltLite](https://github.com/dolthub/doltlite/tree/master#doltlite)。这些项目旨在分别作为 MySQL、PostgreSQL 和 SQLite 的即插即用替代品。它们为不同的 SQL 方言提供了单独的前端，但共享同一个支持版本控制操作的通用存储后端。 在实际使用中，这允许这些项目将类似 Git 的操作暴露为自定义 SQL 函数： ```sql -- 修改数据库 INSERT INTO users VALUES (...); -- 将表的更改添加到暂存区 SELECT dolt_add('users'); -- 提交更改 SELECT dolt_commit('-m', 'Add Joe to users'); -- 查看产生的差异 SELECT * from dolt_diff_users('HEAD~1', 'HEAD'); ``` 在任何时刻，数据库都有一个当前 HEAD 提交、暂存区中的一些更改以及工作区中的一些更改，就像 Git 一样。这种刻意的相似性是这些项目的主要卖点——公司主页上写着：“你已经知道如何使用 Dolt 了。” 这或许有些夸张，但确实，具备 Git 和 SQL 的基本知识似乎就足以开始使用 Dolt。 可能不太清楚的是，人们会使用版本控制的数据库来做什么。仅仅进行提交本身并不会比现有的事务概念增加太多能力。Dolt 的真正实用之处在于能够恢复旧提交、分支历史数据库状态，以及在审查后合并更改。例如，程序员可能希望针对数据库的旧状态运行分析，以确定在某个特定日期会报告什么。他们可以创建一个指向历史提交的新分支，挑选分析所需的模式更改，然后运行它。另一个潜在用途是给自动化工具提供一个“真正的”数据库供其操作，而不让它们有能力完全破坏生产数据库；任何更改都可以单独调查，只有在明确不会造成破坏时才合并进来。 Dolt 与普通的 MySQL 客户端完全兼容；唯一的区别在于连接字符串，因此这些工具没有理由认为它们不是在和真正的生产数据库通信。 ```text -- 连接到普通数据库 mysql://db-server:3306/mydb -- 连接到命名分支 mysql://db-server:3306/mydb/branch-name -- 连接到只读的历史提交 mysql://db-server:3306/mydb/ia1ibijq8hq1llr7u85uivsi5lh3310p ``` 在这三个项目中，Dolt 最为成熟。Doltgres 最近进入了[测试版](https://www.dolthub.com/blog/2025-04-16-doltgres-goes-beta/)，而 DoltLite 则处于中间阶段——从 SQLite 改编而来的组件在其原始上下文中已经过充分测试，但该项目仍处于 0.8.1 版本。该公司对 Dolt 的性能测试[表明](https://docs.dolthub.com/sql-reference/benchmarks/latency)，其速度与 MySQL 相当，尽管关于精确基准测试难度的常规注意事项依然适用。这种具有竞争力的性能之所以可能，是因为 Dolt 只更改了数据库的存储层。查询计划器、索引维护等都重用了 MySQL、PostgreSQL 或 SQLite 的现有实现。所有这些数据库都使用 B 树；Dolt 则使用 B 树的一个微小变体，该变体允许高效进行差异比较，并在大部分相同的版本之间共享存储。 #### B 树 B 树与其更简单的表亲二叉查找树有很多共同点。在二叉查找树中，每个节点有一个键、一个值和两个（可能为空的）子树。键值较低的存储在左子树，键值较高的存储在右子树。只要采用某种方案来保持树的平衡（例如内核中使用的[红黑树](https://lwn.net/Articles/500355/)），就能实现相当高效的基于比较的搜索：每次比较大致排除掉剩余候选中的一半。查找键的时间与树中节点数的以 2 为底的对数成正比。 B 树接受了这一核心概念，并消除了大量指针间接引用。B 树中的每个节点都有一个键、值和指向子树的指针数组。通常，数组的大小被选择为使得一个节点恰好适合底层存储的一个扇区或页面。要在 B 树中查找一个项，计算机会扫描整个数组，要么直接找到键，要么找到目标键应该介于其间的两个键，然后继续查找对应的子树。这种结构大大减少了树的层级数和指针间接引用次数，从而使整个结构在实际访问中更快。例如，在一个每个节点包含 16 个键的 B 树中，搜索一个键涉及的节点数只有二叉树的四分之一。 > [](https://en.wikipedia.org/wiki/File:B-tree.svg) 这使得 B 树成为数据库的绝佳选择，因为数据库需要在高效搜索特定项、范围内有序扫描以及访问底层存储之间保持平衡。不同数据库使用的 B 树有少数几种变体，能提供小幅的速度提升。例如，将所有值移到叶节点，只在内部节点中存储键，这样每个内部节点可以容纳更多键，使树更宽更矮。这一思想的延伸是为每个叶节点添加一个“下一个”指针，使得有序遍历可以沿着叶节点进行，而无需加载任何内部节点。Dolt 的核心数据结构（如下所述）融合了这两种优化。 普通 B 树的问题，也是 Dolt 之所以有趣的原因，在于**比较**整个 B 树代价高昂。项的插入和删除顺序会影响 B 树内部节点的结构，这意味着比较两棵 B 树的唯一方法是完整地迭代遍历它们。这个缺点对传统数据库来说不太重要，但对版本控制系统来说却构成了实际问题。 基于快照的版本控制系统（如 Git）可以被视为存储了源树的许多快照。每个提交在逻辑上是独立的，理论上可以原样存储。但在实践中，大多数 Git 仓库在提交之间不会完全改变，因此存储后续快照之间的差异比存储快照本身更高效。Git 处理整个目录树，它依赖于能够快速检查某个特定子树是否发生了变化，从而生成仅包含实际更改的紧凑差异。B 树与这种算法不兼容，因为相同的键值逻辑列表可能由两种不同的 B 树表示。朴素地将差异算法应用于 B 树可能会在内部节点的表示之间产生大量低效的变动。 问题源于 B 树在添加和删除项时分裂和合并节点的方式。当一个 B 树节点已满时，它会被分裂成两个较小的节点，每个节点半满。当一个 B 树节点不够满时（阈值因实现而异，通常略低于半满），其子节点会被合并以产生一个更满的节点。如果正确实现，这能保持 B 树平衡，并防止节点浪费存储空间。但这也意味着分裂和合并决策取决于项插入树的顺序。 #### Prolly 树 [概率性 B 树](https://docs.dolthub.com/architecture/storage-engine/prolly-tree)（简称 Prolly 树）是 Dolt 针对这个问题的答案。它们与 B 树几乎相同，只是插入和删除项的逻辑得到了更新，使得任何包含相同项的两棵树都完全相同，无论项是如何插入的。相同的属性也适用于单个子树，因此比较两棵 Prolly 树就大大简化了：如果某个子树的哈希在两个版本之间没有变化（即使某个项被插入后又删除），它仍然具有相同的哈希值。 为了实现这一点，Prolly 树需要能够仅根据其内容（而不是树的任何内部状态）来确定每个节点“应该”有多大。起初，可能会让人认为每个节点应该尽可能满，以最大化存储空间的利用。但这有时需要在同一层的节点之间来回移动子节点，这会破坏 B 树的一些良好性质，并导致版本之间产生额外的变动。为了保持插入和删除的高效性，平均节点不应该那么满或那么空，以至于单个项的插入或删除就需要触发分裂或合并。 这个问题的解决方案是使用哈希函数来做出决策，该决策仅依赖于数据，而不依赖于某个特定节点恰好有多满。哈希本质上是一个确定性的伪随机数，可以与阈值进行比较以做出随机决策，这也是 Prolly 树中“概率性”部分的来源。 要向节点中插入一个新值，实现会将其放入数组中的正确位置（基于键），然后根据项的哈希值重新计算该节点与其兄弟节点之间的边界应该落在哪里。每个哈希值与一个选定的截止值（阈值）进行比较，以决定节点是否应该在该项处结束。由于哈希值是独立的，因此关于在何处放置节点边界的决策也是独立的。因此，在大多数情况下，添加一个项不会产生新的边界：它的哈希值会高于阈值，节点仍将在同一位置（一个具有低哈希值的预先存在的项）结束。偶尔，插入的项会有一个低哈希值，导致节点分裂为二，从而保持节点整体大小平衡。 考虑到性能因素，这一情况会稍微复杂一些；为了保持节点大小最优，实际使用的阈值是动态的，基于节点中给定键之前的项数量。但这仍然意味着关于节点边界放置位置的决策是独立于树的预先存在的结构的。边界的位置仅取决于树中存储的项的哈希值，而这些哈希值不依赖于项的插入顺序。 这种插入逻辑有点复杂，特别是如果实现进行了性能优化，但它仍然相当紧凑： ```python # 未优化的 Python 示例代码 # 此函数由某个内部节点调用，用于更新其一个子节点； # 返回值用于更新内部节点。 def insert_into_node(node, new_items): sibling = node.next_sibling new_items = sorted(new_items + node.items) collected = [] nodes = [] while new_items: next = new_items.pop(0) collected.append(next) if hash(next.key) < threshold(len(collected)) \ or len(collected) >= max_node_length: nodes.append(Node(items=collected)) collected = [] if collected: # while 循环没有在自然屏障处结束 if node.next_sibling is not None: new_nodes, sibling = insert_into_node(node.next_sibling, collected) nodes += new_nodes else: nodes.append(Node(items=collected)) for i in range(1, len(nodes)): nodes[i - 1].next_sibling = nodes[i] nodes[-1].next_sibling = sibling return nodes, nodes[0] ``` 通过适当选择的阈值，平均插入不会创建新节点，因此树的每一层只需要更新一个节点。理论上，添加一个项可能导致其后所有节点被不同地分裂，但这种情况的可能性微乎其微，因为项的哈希值在统计上是独立的。所有现有项的哈希值必须恰好勉强超过阈值，才会导致这种重新对齐，因此这不是一个实际的性能问题。 由于将项放入节点的决策仅依赖于数据，因此每次都会创建相同的节点。 使用 Prolly 树相对于 B 树有一些缺点。例如，节点需要存储子树的哈希值，这需要更多的存储空间，或者通过内容寻址的块存储进行额外的间接引用，以将哈希值转换为地址。内容寻址存储是许多版本控制系统用来去重数据的一种方案：特定差异或其他对象根据其内容的哈希值存储在某个位置。这确保了重复项将重用相同的存储空间。作为版本控制系统一部分实现的 Prolly 树可以重用现有的内容寻址对象存储来存储块，并通过哈希值引用块，从而产生更紧凑的内部节点。其他系统则需要自己的解决方案。 另一个问题是树的性能对分裂概率的调整高度敏感。使用恒定的概率会导致平均节点半满，但中位数节点只包含一两个条目。为了应对这一点，Prolly 树使用动态阈值，该阈值随着节点填充而增加，从而使节点的大小最终服从正态分布。当然，某些应用程序确实对最坏情况性能有要求，而不是平均情况性能，这与 Prolly 树的随机布局不兼容。 尽管存在这些缺陷，Prolly 树可能是一种有用的数据结构，适用于依赖于树快照比较能力，或者依赖于以内容可寻址方式存储树的能力的应用程序。 #### 历史与未来 Prolly 树由 Aaron Boodman 为现已停用的 [Noms 数据库](https://github.com/attic-labs/noms#warning---this-project-is-not-active)发明。之后，它们被 [InterPlanetary Linked Data](https://github.com/ipld/ipld#ipld) 项目和 DoltHub 采用。Dolt 中使用的存储后端是 Noms 的一个分支版本，尽管自那以后该项目经历了相当多的更改和优化。还有一些其他实现 Prolly 树的库，但没有一个将它们应用于数据库。 Dolt 提供了对传统数据库设计的一种引人注目的演进。然而，就我个人而言，我很期待看到这些想法如何应用于其他使用 B 树的程序中，例如文件系统。Prolly 树当然不适合 B 树的所有用途，但