BerkeleyDB 的架构

# 开源应用程序架构（卷1）Berkeley DB 来源：https://aosabook.org/en/v1/bdb.html 康威定律指出，设计反映了产生它的组织结构。稍微扩展一下，我们可以预期，由两个人设计和初始产生的软件工件，可能不仅反映了组织的结构，还反映了每个人带来的内在偏见和哲学。我们中的一人（Seltzer）在文件系统和数据库管理系统之间度过职业生涯。如果被问到，她会争辩说这两者本质上是一回事，而且操作系统和数据库管理系统本质上都是资源管理器和便捷抽象提供者。区别“仅仅”是实现细节。另一人（Bostic）信奉基于工具的软件工程方法，以及基于更简单的构建块来构建组件，因为这样的系统在关键的“能力”方面（可理解性、可扩展性、可维护性、可测试性和灵活性）总是优于单体架构。 当把这两种观点结合起来时，我们共同在过去二十年中大部分时间致力于开发 Berkeley DB——一个提供快速、灵活、可靠和可扩展数据管理的软件库，这并不令人惊讶。Berkeley DB 提供了人们从更传统系统（如关系数据库）中期望的许多相同功能，但其打包方式不同。例如，Berkeley DB 提供快速数据访问（包括键控和顺序访问），以及事务支持和故障恢复。然而，这些功能是通过一个直接链接到需要这些服务的应用程序的库来提供的，而不是通过一个独立的服务器应用程序提供的。 在本章中，我们将深入探讨 Berkeley DB，并看到它由一组模块组成，每个模块都体现了 Unix 的“做好一件事”哲学。嵌入 Berkeley DB 的应用程序可以直接使用这些组件，或者通过更熟悉的 get、put 和 delete 数据项操作来隐式使用它们。我们将聚焦于架构——我们是如何开始的，我们设计的是什么，我们最终走向何方以及为什么。设计（当然也会！）被迫适应和改变——关键是在时间中保持原则和一致的愿景。我们还将简要考虑长期软件项目的代码演进。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 (https://aosabook.org/en/v1/bib1.html#bib:seltzer:hash)] 基于 Litwin 的可扩展线性哈希研究。它采用了一种巧妙的方案，允许在哈希值和页地址之间进行常数时间映射，以及处理大数据——大于底层哈希桶或文件系统页大小的数据项，通常为4到8 KB。 如果哈希表是好的，那么 B树 和哈希表会更好。Mike Olson，也是加州大学伯克利分校的研究生，编写过多个 B树 实现，并同意再写一个。我们三人将 Margo 的哈希软件和 Mike 的 B树 软件转换为一个与访问方法无关的 API，其中应用程序通过数据库句柄引用哈希表或 B树，这些句柄具有用于读取和修改数据的句柄方法。 基于这两种访问方法，Mike Olson 和 Margo Seltzer 撰写了一篇研究论文 ([SO92 (https://aosabook.org/en/v1/bib1.html#bib:seltzer:libtp)])，描述了 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 3.0（1999 年）是一个重新设计的版本，增加了抽象和间接层次以容纳增长的功能。Berkeley DB 4.0（2001 年）引入了复制和高可用性，而 Oracle Berkeley DB 5.0（2010 年）增加了 SQL 支持。 撰写本文时，Berkeley DB 是世界上最广泛使用的数据库工具包，部署了数亿份副本，运行在从路由器和浏览器到邮件程序和操作系统的各种设备中。虽然已有二十多年历史，但 Berkeley DB 基于工具和面向对象的方法使其能够逐步改进和重新发明，以匹配使用它的软件的需求。 设计教训 1 对于任何复杂软件包的测试和维护来说，软件被设计并构建为一组协作的、具有明确定义 API 边界的模块是至关重要的。这些边界可以根据需求的变化（而且应该！）调整，但它们必须始终存在。这些边界的存在防止了软件变成一堆不可维护的意大利面条式代码。Butler Lampson 曾说过，计算机科学中的所有问题都可以通过另一层间接来解决。更确切地说，当被问及某物是面向对象意味着什么时，Lampson 说它意味着能够在一个 API 后面有多个实现。Berkeley DB 的设计和实现体现了这种在公共接口后允许多个实现的方法，提供了面向对象的外观和感觉，尽管该库是用 C 语言编写的。 ## 4.2. 架构概述 在本节中，我们将回顾 Berkeley DB 库的架构，从 LIBTP 开始，并强调其演进的关键方面。 图 4.1 (https://aosabook.org/en/v1/bdb.html#fig.bdb.libtp) 取自 Seltzer 和 Olson 的原始论文，展示了最初的 LIBTP 架构，而图 4.2 (https://aosabook.org/en/v1/bdb.html#fig.bdb.bdb20) 展示了 Berkeley DB 2.0 的设计架构。 ![[LIBTP 原型系统的架构]](https://aosabook.org/static/bdb/libtp.png) 图 4.1: LIBTP 原型系统的架构 ![[Berkeley DB-2.0 的预期架构]](https://aosabook.org/static/bdb/bdb20.png) 图 4.2: Berkeley DB-2.0 的预期架构 LIBTP 实现与 Berkeley DB 2.0 设计之间唯一显著的区别是进程管理器的移除。LIBTP 要求每个控制线程向库注册自己，然后同步各个线程/进程，而不是提供子系统级别的同步。正如在第 4.4 节 (https://aosabook.org/en/v1/bdb.html#sec.bdb.int) 中讨论的那样，原来的设计可能对我们更好。 ![[实际的 Berkeley DB 2.0.6 架构]](https://aosabook.org/static/bdb/bdb20-actual.png) 图 4.3: 实际的 Berkeley DB 2.0.6 架构。 设计与实际发布的 db-2.0.6 架构之间的差异（如图 4.3 (https://aosabook.org/en/v1/bdb.html#fig.bdb.bdbact) 所示）说明了实现健壮恢复管理器的现实。恢复子系统以灰色显示。恢复包括驱动基础设施（在恢复框中描绘），以及一组恢复重做和撤销例程，这些例程恢复访问方法执行的操作。这些由标记为“访问方法恢复例程”的圆圈表示。在 Berkeley DB 2.0 中，恢复的处理方式是一致的，而 LIBTP 中则是对特定访问方法手工编码的日志和恢复例程。这种通用设计也在各个模块之间提供了更丰富的接口。 图 4.4 (https://aosabook.org/en/v1/bdb.html#fig.bdb.bdb50) 展示了 Berkeley DB-5.0.21 的架构。图中的数字引用了表 4.1 (https://aosabook.org/en/v1/bdb.html#tbl.bdb.apitab) 中列出的 API。虽然原始架构仍然可见，但当前架构因其年龄而显现：添加了新模块，分解了旧模块（例如，`log` 已变成 `log` 和 `dbreg`），并且模块间 API 的数量显著增加。 经过十多年的演进，数十个商业版本以及数百个新功能之后，我们看到架构比其前辈复杂得多。需要注意的关键点是：首先，复制为系统添加了一个全新的层，但它以干净的方式实现，通过与历史代码相同的 API 与系统的其余部分交互。其次，`log` 模块被拆分为 `log` 和 `dbreg`（数据库注册）。这一点将在第 4.8 节 (https://aosabook.org/en/v1/bdb.html#sec.bdb.log) 中更详细地讨论。第三，我们将所有模块间调用放入一个以下划线开头的命名空间中，这样应用程序就不会与我们的函数名冲突。我们将在设计教训 6 中进一步讨论这一点。 第四，日志子系统的 API 现在基于游标（没有 `log_get` API；它被 `log_cursor` API 取代）。历史上，Berkeley DB 从未同时有多个控制线程读取或写入日志，因此库在日志中有一个单一当前查找指针的概念。这从来不是一个好的抽象，但在复制下变得不可行。就像应用程序 API 使用游标支持迭代一样，日志现在也使用游标支持迭代。第五，访问方法中的 `fileop` 模块为事务保护的数据库创建、删除和重命名操作提供支持。我们尝试了多次才使实现可接受（它仍然没有我们想要的那么干净），在多次重做后，我们将其拆分为一个独立的模块。 设计教训 2 软件设计仅仅是在尝试解决问题之前迫使你彻底思考问题的几种方法之一。有经验的程序员使用不同的技术来实现这一目的：有些人编写第一个版本然后丢弃，有些人编写详尽的手册页或设计文档，其他人填写代码模板，其中每个需求都被识别并分配给一个特定的函数或注释。例如，在 Berkeley DB 中，我们在编写任何代码之前为访问方法和底层组件创建了一套完整的 Unix 风格的手册页。无论使用何种技术，在代码调试开始后很难清晰地思考程序架构，更不用说大的架构更改通常会浪费先前的调试工作。软件架构需要与调试代码不同的思维方式，而你在开始调试时所拥有的架构通常就是你在该版本中交付的架构。 ![[Berkeley DB-5.0.21 架构]](https://aosabook.org/static/bdb/bdb50.png) 图 4.4: Berkeley DB-5.0.21 架构 应用程序 API --- 1. DBP 句柄操作2. DB_ENV 恢复3. 事务 APIopenopen(... DB_RECOVER ...)DB_ENV->txn_begingetDB_TXN->abortputDB_TXN->commitdelDB_TXN->prepare游标 --- 访问方法使用的 API --- 4. 进入 Lock5. 进入 Mpool6. 进入 Log7. 进入 Dbreg__lock_downgrade__memp_nameop__log_print_record__dbreg_setup__lock_vec__memp_fget__dbreg_net_id__lock_get__memp_fput__dbreg_revoke__lock_put__memp_fset__dbreg_teardown__memp_fsync__dbreg_close_id__memp_fopen__dbreg_log_id__memp_fclose__memp_ftruncate__memp_extend_freelist --- 恢复 API --- 8. 进入 Lock9. 进入 Mpool10. 进入 Log11. 进入 Dbreg12. 进入 Txn__lock_getlocker__memp_fget__log_compare__dbreg_close_files__txn_getckp__lock_get_list__memp_fput__log_open__dbreg_mark_restored__txn_checkpoint__memp_fset__log_earliest__dbreg_init_recover__txn_reset__memp_nameop__log_backup__txn_recycle_id__log_cursor__txn_findlastckp__log_vtruncate__txn_ckp_read --- 事务模块使用的 API --- 13. 进入 Lock14. 进入 Mpool15. 进入 Log16. 进入 Dbreg__lock_vec__memp_sync__log_cursor__dbreg_invalidate_files__lock_downgrade__memp_nameop__log_current_lsn__dbreg_close_files__dbreg_log_files --- 进入复制系统的 API --- 17. 从 Log18. 从 Txn__rep_send_message__rep_lease_check__rep_bulk_message__rep_txn_applied__rep_send_message --- 从复制系统出去的 API --- 19. 进入 Lock20. 进入 Mpool21. 进入 Log22. 进入 Dbreg23. 进入 Txn__lock_vec__memp_fclose__log_get_stable_lsn__dbreg_mark_restored__txn_recycle_id__lock_get__memp_fget__log_cursor__dbreg_invalidate_files__txn_begin__lock_id__memp_fput__log_newfile__dbreg_close_files__txn_recover__memp_fsync__log_flush__txn_getckp__log_rep_put__txn_updateckp__log_zero__log_vtruncate表 4.1: Berkeley DB 5.0.21 API 为什么要用组件构建事务库，而不是针对单一的预期用途进行调优？这个问题有三个答案。首先，它迫使设计更加规范。其次，如果没有代码中的强边界，复杂的软件包不可避免地会退化为不可维护的大杂烩。第三，你永远无法预料客户会以什么方式使用你的软件；如果你通过让用户访问软件组件来赋予他们权力，他们会以你从未考虑过的方式使用它们。 在接下来的几节中，我们将审视 Berkeley DB 的每个组件，了解它的作用以及如何融入更大的图景。 ## 4.3. 访问方法：B树、哈希、记录号、队列 Berkeley DB 的访问方法提供对可变长度和定长字节串的键控查找和迭代。B树和哈希支持可变长度的键/值对。记录号和队列支持记录号/值对（记录号支持可变长度值，队列仅支持定长值）。 B树和哈希访问方法之间的主要区别在于，B树为键提供引用局部性，而哈希则不提供。这意味着对于几乎所有的数据集，B树是正确的访问方法；然而，哈希访问方法适用于如此之大的数据集，以至于即使是 B树