开源应用程序架构（第一卷）
Berkeley DB

4.1. 起源

Berkeley DB 可以追溯到 Unix 操作系统专属于 AT&T 并且有数百个实用程序和库的时代，这些库的谱系具有严格的许可约束。Margo Seltzer 是加州大学伯克利分校的研究生，Keith Bostic 是伯克利计算机系统研究小组的成员。当时，Keith 正在努力从伯克利软件发行版中移除 AT&T 的专有软件。

Berkeley DB 项目始于一个适度的目标，即用一个新的改进的哈希实现来替换内存中的 hsearch 哈希包和磁盘上的 dbm/ndbm 哈希包，该实现能够在内存中和磁盘上运行，并且可以自由地重新分发而无需专有许可证。Margo Seltzer 编写的 hash 库 [SY91] 基于 Litwin 的可扩展线性哈希研究。它拥有一个巧妙的方案，允许在哈希值和页面地址之间进行恒定时间映射，以及处理大型数据的能力——大于底层哈希桶或文件系统页面大小的数据项，通常为 4 到 8 千字节。

如果哈希表很好，那么 B 树和哈希表会更好。Mike Olson 也是加州大学伯克利分校的研究生，他编写了许多 B 树实现，并同意再编写一个。我们三个人将 Margo 的哈希软件和 Mike 的 B 树软件转换为一个与访问方法无关的 API，其中应用程序通过数据库句柄引用哈希表或 B 树，这些句柄具有用于读取和修改数据的句柄方法。

基于这两种访问方法，Mike Olson 和 Margo Seltzer 撰写了一篇研究论文 ([SO92])，描述了 LIBTP，一个在应用程序地址空间中运行的程序化事务库。

哈希和 B 树库已合并到最终的 4BSD 版本中，名称为 Berkeley DB 1.85。从技术上讲，B 树访问方法实现了一个 B+link 树，但是，在本节的其余部分，我们将使用 B 树这个术语，因为这就是访问方法的名称。Berkeley DB 1.85 的结构和 API 对于任何使用过任何基于 Linux 或 BSD 的系统的人来说都可能很熟悉。

Berkeley DB 1.85 库沉寂了几年，直到 1996 年 Netscape 与 Margo Seltzer 和 Keith Bostic 签订合同，以构建 LIBTP 论文中描述的完整事务设计，并创建软件的生产级版本。这项工作产生了 Berkeley DB 的第一个事务版本，即 2.0 版。

Berkeley DB 随后的历史是一个更简单、更传统的的时间线：Berkeley DB 2.0（1997 年）为 Berkeley DB 引入了事务；Berkeley DB 3.0（1999 年）是一个重新设计的版本，增加了更多抽象级别和间接级别以适应不断增长的功能。Berkeley DB 4.0（2001 年）引入了复制和高可用性，而 Oracle Berkeley DB 5.0（2010 年）增加了 SQL 支持。

在撰写本文时，Berkeley DB 是世界上使用最广泛的数据库工具包，数以亿计的已部署副本运行在从路由器和浏览器到邮件程序和操作系统的各种设备中。尽管已有二十多年的历史，但 Berkeley DB 基于工具和面向对象的的方法使其能够逐步改进和重新设计自身，以满足使用它的软件的要求。

4.2. 架构概述

在本节中，我们将回顾 Berkeley DB 库的架构，从 LIBTP 开始，并重点介绍其演变的关键方面。

图 4.1（取自 Seltzer 和 Olson 的原始论文）说明了原始 LIBTP 架构，而 图 4.2 则展示了 Berkeley DB 2.0 的设计架构。

图 4.1：LIBTP 原型系统的架构

图 4.2：Berkeley DB-2.0 的预期架构。

LIBTP 实现和 Berkeley DB 2.0 设计之间唯一的重大区别是去除了进程管理器。LIBTP 要求每个控制线程向库注册自身，然后同步各个线程/进程，而不是提供子系统级同步。如 第 4.4 节 所述，最初的设计可能对我们更有帮助。

图 4.3：实际的 Berkeley DB 2.0.6 架构。

设计和实际发布的 db-2.0.6 架构（如图 图 4.3 所示）之间的差异说明了实现健壮恢复管理器的现实情况。恢复子系统以灰色显示。恢复包括驱动程序基础架构（在恢复框中描述），以及一组恢复重做和撤消例程，这些例程恢复访问方法执行的操作。这些由标记为“访问方法恢复例程”的圆圈表示。Berkeley DB 2.0 中的恢复处理方式具有一致的设计，而不是 LIBTP 中特定于特定访问方法的手工编码日志记录和恢复例程。这种通用设计还在各个模块之间产生了更丰富的接口。

图 4.4 说明了 Berkeley DB-5.0.21 架构。图中的数字引用了 表 4.1 中表格中列出的 API。虽然原始架构仍然可见，但当前架构显示了其随着新模块的添加、旧模块的分解（例如，log 已成为 log 和 dbreg）以及模块间 API 数量的显着增加而逐渐老化的状态。

经过十多年的发展、数十个商业版本和数百个新功能的发布，我们发现架构比其祖先复杂得多。需要注意的关键事项是：首先，复制为系统添加了全新的层，但它以干净的方式执行此操作，通过与历史代码相同的 API 与系统的其余部分交互。其次，log 模块被拆分为 log 和 dbreg（数据库注册）。这将在 第 4.8 节 中详细讨论。第三，我们将所有模块间调用都放置到以下划线开头的命名空间中，这样应用程序就不会与我们的函数名称发生冲突。我们将在设计教训 6 中进一步讨论这一点。

第四，日志记录子系统的 API 现在基于游标（没有 log_get API；它被 log_cursor API 替换）。从历史上看，Berkeley DB 在任何时间点都从未有过多个控制线程读取或写入日志，因此库对日志中的当前查找指针有一个单一的概念。这从来不是一个好的抽象，但在复制中，它变得无法使用。就像应用程序 API 使用游标支持迭代一样，日志现在也使用游标支持迭代。第五，访问方法内的 fileop 模块提供了对事务性保护的数据库创建、删除和重命名操作的支持。我们尝试了多次才能使实现变得可接受（它仍然不像我们希望的那样干净），并且在多次重新设计之后，我们将其提取到自己的模块中。

图 4.4：Berkeley DB-5.0.21 架构

为什么将事务库设计成由多个组件构成，而不是针对单一预期用途进行优化？这个问题有三个答案。首先，它迫使设计更加规范。其次，如果没有代码中的严格边界，复杂的软件包不可避免地会退化为难以维护的混乱代码。第三，您永远无法预测客户将如何使用您的软件；如果您通过向用户提供访问软件组件的权限来赋予他们权力，他们将以您从未考虑过的方式使用它们。

在后续章节中，我们将分别考虑 Berkeley DB 的每个组件，了解其功能以及它如何在更大的框架中发挥作用。

4.3. 访问方法：Btree、Hash、Recno、Queue

Berkeley DB 访问方法提供了可变和固定长度字节字符串的键查找和迭代功能。Btree 和 Hash 支持可变长度的键/值对。Recno 和 Queue 支持记录号/值对（其中 Recno 支持可变长度的值，而 Queue 仅支持固定长度的值）。

Btree 和 Hash 访问方法之间的主要区别在于，Btree 为键提供了局部性引用，而 Hash 没有。这意味着 Btree 几乎适用于所有数据集；但是，对于数据量如此之大以至于连 Btree 索引结构都无法容纳在内存中的数据集，Hash 访问方法是合适的。在那种情况下，最好将内存用于数据而不是索引结构。这种权衡在 1990 年更有意义，当时主内存通常比现在小得多。

Recno 和 Queue 之间的区别在于，Queue 支持记录级锁定，但代价是需要固定长度的值。Recno 支持可变长度的对象，但与 Btree 和 Hash 一样，仅支持页面级锁定。

我们最初设计 Berkeley DB 时，CRUD 功能（创建、读取、更新和删除）是基于键的，并且是应用程序的主要接口。后来我们添加了游标来支持迭代。这种顺序导致库内部出现了混乱且浪费的大量重复代码路径。随着时间的推移，这变得难以维护，我们把所有基于键的操作都转换为游标操作（基于键的操作现在分配一个缓存的游标，执行操作，然后将游标返回到游标池）。这是软件开发中一个不断重复的规则的应用：除非您知道这样做是必要的，否则不要以任何损害清晰度和简单性的方式优化代码路径。

我们省略了对 Berkeley DB 访问方法内部的详细讨论；它们实现了相当知名的 Btree 和哈希算法（Recno 是 Btree 代码之上的一个层，而 Queue 是一个文件块查找函数，尽管由于添加了记录级锁定而变得复杂）。

4.4. 库接口层

随着时间的推移，随着我们添加了更多功能，我们发现应用程序和内部代码都需要相同的高级功能（例如，表连接操作使用多个游标来迭代行，就像应用程序可能使用游标来迭代这些相同的行一样）。

因此，我们将访问方法 API 分解成明确定义的层。这些接口例程层执行所有必要的通用错误检查、特定于函数的错误检查、接口跟踪以及其他任务，例如自动事务管理。当应用程序调用 Berkeley DB 时，它们会根据对象句柄中的方法调用第一级接口例程。（例如，__dbc_put_pp 是 Berkeley DB 游标“put”方法的接口调用，用于更新数据项。"_pp" 是我们用于标识应用程序可以调用的所有函数的后缀。）

Berkeley DB 在接口层执行的任务之一是跟踪哪些线程正在 Berkeley DB 库内部运行。这是必要的，因为某些内部 Berkeley DB 操作只能在没有线程在库内部运行时执行。Berkeley DB 通过在每个库 API 的开头标记线程正在库内部执行，并在 API 调用返回时清除该标志来跟踪库中的线程。这种进入/退出检查始终在接口层执行，类似地，还会检查调用是否在复制环境中执行。

显而易见的问题是“为什么不将线程标识符传递到库中，那样不是更容易吗？”答案是，是的，这会容易得多，我们当然希望我们能这样做。但是，这种更改将修改每个 Berkeley DB 应用程序，修改应用程序中大多数对 Berkeley DB 的调用，并且在许多情况下需要重新构建应用程序。

接口层执行的另一项任务是事务生成。Berkeley DB 库支持一种模式，其中每个操作都在自动生成的事务中发生（这节省了应用程序创建和提交自己的显式事务）。支持此模式需要每次应用程序在不指定其自身事务的情况下通过 API 调用时，自动创建一个事务。

最后，所有 Berkeley DB API 都需要参数检查。在 Berkeley DB 中，有两种类型的错误检查——通用检查以确定我们的数据库在之前的操作期间是否已损坏，或者我们是否处于复制状态更改（例如，更改哪个副本允许写入）。还有一些特定于 API 的检查：正确的标志用法、正确的参数用法、正确的选项组合以及在实际执行请求的操作之前我们可以检查的任何其他类型的错误。

所有这些特定于 API 的检查都封装在以 _arg 结尾的函数中。因此，游标 put 方法的特定错误检查位于函数 __dbc_put_arg 中，该函数由 __dbc_put_pp 函数调用。

最后，当所有参数验证和事务生成完成后，我们调用实际执行操作的工作方法（在我们的示例中，它将是 __dbc_put），这是我们在内部调用游标 put 功能时使用的相同函数。

这种分解是在一个活动密集的时期演变而来的，当时我们正在确定在复制环境中工作时需要采取哪些具体措施。在对代码库进行了多次非平凡的迭代后，我们将所有这些序言检查拆分出来，以便在下一次我们发现其问题时更容易更改。

4.5. 底层组件

访问方法的底层有四个组件：缓冲区管理器、锁管理器、日志管理器和事务管理器。我们将分别讨论它们，但它们都有一些共同的架构特征。

首先，所有子系统都有自己的 API，最初每个子系统都有自己的对象句柄，所有该子系统的方法都基于该句柄。例如，您可以使用 Berkeley DB 的锁管理器来处理您自己的锁或编写您自己的远程锁管理器，或者您可以使用 Berkeley DB 的缓冲区管理器来处理共享内存中的您自己的文件页面。随着时间的推移，为了简化 Berkeley DB 应用程序，子系统特定的句柄已从 API 中删除。尽管子系统仍然是独立的组件，可以独立于其他子系统使用，但它们现在共享一个公共对象句柄，即 DB_ENV “环境”句柄。此架构特性强制执行分层和泛化。即使层会不时移动，并且仍然有一些地方一个子系统会跨越到另一个子系统，但程序员将系统的各个部分视为独立的软件产品本身也是一个好的习惯。

其次，所有子系统（实际上，所有 Berkeley DB 函数）都会将错误代码返回到调用堆栈。作为库，Berkeley DB 无法通过声明全局变量来占用应用程序的名称空间，更不用说强制错误通过调用堆栈中的单一路径返回可以强制执行良好的程序员纪律。

最后，所有子系统都支持共享内存。由于 Berkeley DB 支持在多个运行进程之间共享数据库，所有有趣的数据结构都必须驻留在共享内存中。这种选择最重要的影响是，内存中的数据结构必须使用基地址和偏移量对而不是指针，以便基于指针的数据结构在多个进程的上下文中工作。换句话说，不是通过指针间接访问，Berkeley DB 库必须从基地址（共享内存段映射到内存的地址）加上偏移量（该映射段中特定数据结构的偏移量）创建一个指针。为了支持此功能，我们编写了一个 Berkeley 软件发行版queue包的版本，该版本实现了各种各样的链表。

4.6. 缓冲区管理器：Mpool

Berkeley DB Mpool 子系统是一个内存中的文件页面缓冲池，它隐藏了主内存是有限资源的事实，要求库在处理大于内存的数据库时将数据库页面移入和移出磁盘。将数据库页面缓存到内存中是最初的哈希库能够显著优于历史hsearch和ndbm实现的原因。

虽然 Berkeley DB Btree 访问方法是相当传统的 B+树实现，但树节点之间的指针表示为页号，而不是实际的内存指针，因为库的实现也使用磁盘上的格式作为其内存中的格式。这种表示的优点是可以将页面从缓存中刷新而无需格式转换；缺点是遍历索引结构需要（更昂贵的）重复缓冲池查找，而不是（更便宜的）内存间接寻址。

从底层假设 Berkeley DB 索引的内存表示实际上是磁盘持久数据的一个缓存，还会产生其他性能影响。例如，每当 Berkeley DB 访问缓存页面时，它首先将页面固定在内存中。此固定操作可以防止任何其他线程或进程将其从缓冲池中逐出。即使索引结构完全适合缓存并且永远不需要刷新到磁盘，Berkeley DB 仍然在每次访问时获取和释放这些固定操作，因为 Mpool 提供的底层模型是缓存，而不是持久存储。

4.7. 锁管理器：Lock

与 Mpool 一样，锁管理器被设计为一个通用组件：一个分层锁管理器（参见[GLPT76]），旨在支持可以锁定的对象层次结构（例如单个数据项）、数据项所在的页面、数据项所在的以及文件，甚至是一组文件。当我们描述锁管理器的功能时，我们还将解释 Berkeley DB 如何使用它们。但是，与 Mpool 一样，重要的是要记住其他应用程序可以以完全不同的方式使用锁管理器，这没关系——它被设计为灵活并支持许多不同的用途。

锁管理器具有三个关键抽象：一个“锁具”，用于识别代表谁获取锁，一个“锁对象”，用于识别被锁定的项，以及一个“冲突矩阵”。

锁具是 32 位无符号整数。Berkeley DB 将此 32 位命名空间划分为事务锁具和非事务锁具（尽管这种区分对锁管理器是透明的）。当 Berkeley DB 使用锁管理器时，它将范围 0 到 0x7fffffff 内的锁具 ID 分配给非事务锁具，将范围 0x80000000 到 0xffffffff 分配给事务。例如，当应用程序打开数据库时，Berkeley DB 会获取该数据库的长期读取锁，以确保在使用过程中没有其他控制线程删除或重命名它。由于这是一个长期锁，它不属于任何事务，并且持有此锁的锁具是非事务性的。

任何使用锁管理器的应用程序都需要分配锁具 ID，因此锁管理器 API 提供了DB_ENV->lock_id和DB_ENV->lock_id_free调用来分配和释放锁具。因此，应用程序不需要实现自己的锁具 ID 分配器，尽管它们当然可以。

4.8. 日志管理器：日志

日志管理器提供了结构化、仅追加文件的抽象。与其他模块一样，我们打算设计一个通用的日志记录功能，但是日志记录子系统可能是我们最不成功的地方。

日志在概念上非常简单：它获取不透明的字节字符串并将它们顺序写入文件，并为每个字符串分配一个唯一的标识符，称为日志序列号 (LSN)。此外，日志必须提供通过 LSN 进行高效的前向和后向遍历和检索。有两个棘手的地方：首先，日志必须保证在任何可能的故障后都处于一致状态（其中一致意味着它包含一系列连续的未损坏的日志记录）；其次，由于必须将日志记录写入稳定存储以使事务提交，因此日志的性能通常是限制任何事务应用程序性能的因素。

由于日志是仅追加数据结构，因此它可以无限增长。我们将日志实现为一系列按顺序编号的文件，因此可以通过简单地删除旧日志文件来回收日志空间。鉴于日志的多文件架构，我们将 LSN 形成文件号和文件内偏移量的对。因此，给定一个 LSN，日志管理器可以轻松地找到该记录：它跳转到给定日志文件的给定偏移量并返回写入该位置的记录。但是日志管理器如何知道从该位置返回多少字节呢？

4.9. 事务管理器：Txn

我们的最后一个模块是事务管理器，它将各个组件联系在一起，以提供事务的ACID特性，即原子性、一致性、隔离性和持久性。事务管理器负责开始和完成（提交或中止）事务，协调日志和缓冲区管理器进行事务检查点，并协调恢复。我们将按顺序访问这些领域。

Jim Gray 发明了 ACID 首字母缩略词来描述事务提供的关键属性 [Gra81]。原子性意味着在事务中执行的所有操作都以单个单元的形式出现在数据库中——它们要么都存在于数据库中，要么都不存在。一致性意味着事务将数据库从一个逻辑一致的状态转移到另一个逻辑一致的状态。例如，如果应用程序指定所有员工都必须分配到数据库中描述的部门，则一致性属性会强制执行此操作（使用正确编写的交易）。隔离性意味着从事务的角度来看，事务似乎是顺序运行的，没有任何并发事务运行。最后，持久性意味着一旦事务提交，它就会保持提交状态——任何故障都不能导致已提交的事务消失。

事务子系统在其他子系统的协助下强制执行 ACID 属性。它使用传统的事务开始、提交和中止操作来限定事务的开始和结束点。它还提供了一个准备调用，该调用有助于两阶段提交，这是一种跨分布式事务提供事务属性的技术，本章不讨论此技术。事务开始分配一个新的事务标识符，并向应用程序返回一个事务句柄DB_TXN。事务提交写入提交日志记录，然后强制将日志写入磁盘（除非应用程序指示它愿意放弃持久性以换取更快的提交处理），确保即使在发生故障的情况下，事务也将被提交。事务中止向后读取属于指定事务的日志记录，撤消事务执行的每个操作，将数据库恢复到事务前的状态。

ckp_record = read (cached_ckp_lsn)
ckp_lsn = ckp_record.checkpoint_lsn
cur_lsn = ckp_record.my_lsn
while (cur_lsn > ckp_lsn) {
    ckp_record = read (ckp_record.prev_ckp)
    cur_lsn = ckp_record.my_lsn
}

4.10. 总结

Berkeley DB 现在已经超过 20 年历史了。它可以说是第一个通用的事务性键值存储，也是 NoSQL 运动的鼻祖。Berkeley DB 继续作为数百种商业产品和数千种开源应用程序（包括 SQL、XML 和 NoSQL 引擎）的基础存储系统，并在全球范围内拥有数百万次部署。我们在其开发和维护过程中学到的经验教训都体现在代码中，并在上面概述的设计技巧中进行了总结。我们希望这些技巧对其他软件设计师和架构师有所帮助。