钻头
PDF钻头 (#5)
使原始 NoSQL 键值存储免受崩溃影响
Terence Kelly
本期《钻头》揭示了一种新的崩溃容错机制，该机制将久负盛名的 gdbm 数据库提升到事务型 NoSQL 数据存储的行列。我们将通过追溯 gdbm 的历史来阐述这一升级的动机。我们将考察崩溃防护的微妙科学，在为粗心大意者布满陷阱的雷区中穿行。我们将得出一个紧凑而坚固的设计，该设计利用了现代文件系统的特性，并且我们将浏览此设计的生产就绪实现及其符合人体工程学的界面。
持久数据的持久模式
Ken Thompson 在一个充满传奇色彩的黄金时代编写了原始的 dbm。在 Unix 的推动下，20 世纪 70 年代贝尔实验室的软件创造力蓬勃发展，产生了一个生态系统10，几十年后仍然充满活力。母公司的环境技术可能激发了员工重新构想数据组织，这带来了深远的影响
IBM 操作系统构建者在数据存在于单元记录设备（80 列卡片、132 列打印机等）的地方工作，并构建了一个看起来像这样的文件系统。Ken 和 Dennis 在一家电话公司工作，那里的数据以流的形式通过电线传输，并构建了一个文件看起来像这样的系统。3
来自文件和管道的非结构化字节流迫使应用程序施加结构。许多人选择了随意的键值范例——如果关系数据库显得大材小用，而固定布局又过于僵化，这通常是一个不错的选择。早期持久的键值模式包括自描述文本格式2 以及 AWK 及其后代内置的关联数组。
Thompson 的 dbm 库提供了一种持久键值抽象。16 客户端程序通过 store()/fetch() 接口操作键值对字符串；在底层，dbm 管理着嵌入在文件中的可扩展哈希表。
Philip Nelson 于 1990 年实现了 GNU gdbm。此后，维护者 Justin Downs 和 Sergey Poznyakoff 更新了 gdbm 以利用新的 Unix 功能，例如 writev() 和 mmap()。1.20 版本（2021 年 7 月）通过完全重写哈希表 bucket 缓存来提高性能。用户和客户端软件维护人员经常帮助进行测试。
由于其成熟度和易用性，gdbm 已成为不可或缺的主力。在某些 Linux 发行版上，六分之一的软件包直接或间接地依赖于 libgdbm；突出的例子包括 man-db（手册页）、几个 Apache 模块以及 Python 和 Perl 的流行接口。一项对近 20 万个 Debian 系统的调查发现，60% 的系统定期使用 libgdbm。4
不幸的是，自 20 世纪 90 年代以来，崩溃漏洞一直是 dbm 家族的阿喀琉斯之踵，它一直在将一些潜在用户推向替代数据存储。意外的电源故障、操作系统内核崩溃或进程崩溃可能会损坏 gdbm 数据库。因此，必须容忍崩溃的应用程序使用了“事务型” NoSQL 数据存储，例如 Berkeley DB11 或 LevelDB5，或者支持 ACID 事务的成熟的关系数据库。然而，现在，您可以拥有您的 gdbm 并且也可以使其崩溃了。
在失败中取得成功
容忍崩溃意味着将持久数据恢复到一致状态，该状态在所有软件层（包括应用程序）中都满足所有相关的正确性标准。一致性不仅仅意味着较低层中不存在损坏：考虑一个不谨慎实现的银行应用程序，该应用程序旨在将一个帐户余额减少相同的金额并增加另一个帐户余额。在这两个步骤之间发生崩溃，并且偶然地，它与有序（尽管时机不当）的关闭具有相同的效果。数据完整性在存储、文件系统和数据库层是无可挑剔的，但应用程序级别的“货币守恒”不变量被违反了。
应用程序通过使用事务来防止崩溃引起的不一致，即使在出现故障的情况下，事务也能原子地执行多次更改。应用程序必须确保崩溃前和崩溃后的状态都是一致的；事务机制保证在崩溃后可以恢复其中一种状态。不幸的是，可靠的实现是难以捉摸的：成熟、广泛使用的事务型数据存储并不总是能容忍崩溃。17
难怪。在类 Unix 操作系统之上可移植地实现故障原子更新非常困难：12 文件系统提供模糊且通常较弱的崩溃后保证，此外，这些保证还取决于配置细节。修改文件并同步地将更改持久化到持久介质的 Posix 系统调用——write()/fsync() 和 mmap()/msync()——不是原子的。例如，尝试进行两字节的 write() 可能会返回 1，这意味着第一个字节可能随时变为持久的，但我们必须再次尝试 write() 第二个字节；与此同时，当然，可能会发生崩溃。陷阱列表还在继续：如果没有来自 fsync() 或 msync() 的显式排序约束，操作系统可能会随时以任何顺序将文件修改从主内存缓冲区推送到持久存储。崩溃可能会使文件损坏，但并不明显。这只是冰山一角；Pillai 等人描述了进一步的挑战。13
除了技术难题之外，相互冲突的优先级也破坏了可靠性。许多数据存储提供丰富的功能，这需要复杂的代码，而复杂代码又会隐藏错误。更糟糕的是，许多数据库为了追求性能而牺牲了崩溃容错能力——这是事务的主要动机。对于数据库来说，就像降落伞一样，过快的速度会危及安全性。
崩溃容错协议
gdbm 中的崩溃容错始于一个幼稚的协议，该协议显然很慢且存在细微缺陷。修复缺陷表明崩溃防护很棘手，但不必深奥。解决性能问题利用了针对不相关问题的现有解决方案。
gdbm 数据库驻留在数据文件中。传统上，应用程序调用 gdbm_sync() 将数据库从易失性内存持久化到通过文件系统到持久存储介质。只有当数据库一致时，这种缓慢的操作才有意义。因此，现有的 gdbm_sync() 函数在启用崩溃容错时还具有额外的用途：它告诉 gdbm 数据库是一致的并且适合崩溃恢复。
我们首次尝试（不正确）崩溃容错只是在 gdbm_sync() 之后立即复制数据文件，然后 fsync() 副本；崩溃后恢复使用最新的副本。这种方法在两个微妙方面存在缺陷：首先，副本可能会在崩溃中丢失，因为它们的目录条目未持久化。其次，崩溃后，不确定最新的复制和 fsync() 是否成功完成；副本可能已损坏。
为了解决第一个问题，我们通过在副本本身和副本与根之间的 realpath() 上的每个目录上调用 fsync() 来确保副本在崩溃后在文件系统中可见。为了解决第二个问题，我们使用副本的权限位标记包含一致数据的副本。为了创建副本，我们：以写模式 open() 它；用 gdbm 数据文件的内容填充它；fsync() 它；然后将其权限位更改为只读；最后再次 fsync() 副本以持久化其权限位。至关重要的是，文件系统确保最后一步中的元数据操作是故障原子的，并且两个 fsync() 调用按程序顺序持久化数据。崩溃后恢复使用最新的可读副本，该副本肯定是一致且持久的，因为它在成功填充了一致的数据库并 fsync() 后才变为可读的。
虽然正确，但上面概述的协议是不切实际的，因为它会在每次 gdbm_sync() 时物理复制整个数据文件。复制大型数据文件以提交一些小的更改将是浪费的。性能成本不应受整个数据库大小（“O(数据)”）的限制，而应受连续 gdbm_sync() 调用之间更改大小（“O(delta)”）的限制。
幸运的是，现代文件系统支持高效的复制操作：Reflink 克隆的动机是虚拟机，虚拟机使用驻留在虚拟机监控程序文件系统中的文件中的虚拟磁盘。克隆减少了包含几乎相同的虚拟磁盘副本的多个文件的开销。当进行逻辑复制时，克隆不会物理复制存储块。相反，新克隆与原始文件共享数据块。写时复制机制确保随后对任一文件的更改都不会影响另一个文件。时间和存储的总成本随着克隆后两个文件的更改而增长：O(delta)，而不是 O(data)。
图 1 说明了创建然后更改克隆。在具有 4 KiB 文件系统块的 Linux 系统上，我用随机字节填充了一个 100 块的文件，然后使用以下命令克隆了它
dd if=/dev/urandom bs=4096 count=100 > random
cp --reflink=always random random.copy
图 1a 显示了文件如何将逻辑块映射到物理块，这要归功于 filefrag 实用程序。每个文件都包含一个 100 块的区段（块范围），并且两个文件都将相同的逻辑区段映射到相同的物理区段（即，它们共享存储）。接下来，我修改了克隆的逻辑块 7 和 47，为此，写时复制分配了两个新的物理块（图 1b）。现在，两个文件都有五个区段：三个大的共享区段和两个私有的单块区段；每个文件的 98% 由共享物理块支持。
克隆目前在三个文件系统上可用：OCFS2（Oracle 集群文件系统版本 2）、Btrfs 和 XFS。为了方便起见，我们可以将这些支持 reflink 的文件系统之一安装在不同文件系统（如 ext4）上的普通文件中；gdbm 崩溃容错文档解释了如何操作。15 克隆和 fsync() 等关键操作的可靠性将与直接安装在专用存储上的支持 reflink 的文件系统一样可靠。6
通过克隆进行崩溃防护提供了与基于预写日志的事务不同的性能权衡。Reflink 写时复制跟踪对块的更改，这些块通常为 4 KiB，而许多事务系统以更精细的粒度跟踪更改。工作负载以不同的方式影响这些方法中的性能。
实现细节
为了原型化崩溃容错的 gdbm，我更改了 1.20 版本中的四个源文件，总共添加了不到 200 行代码。我针对注入的崩溃测试了我的原型；早期实现的相同基本协议在数万次电源故障中幸存下来。9 原始 gdbm 作者 Phil Nelson 和维护者 Sergey Poznyakoff 审查了我的协议设计。Poznyakoff 审查了我的代码，重复了我的测试，并将我的原型合并到 1.21 版本中。
应用程序通过将 gdbm_failure_atomic() 指向 gdbm 数据库和将保存主数据文件克隆的两个快照文件的名称来“选择加入”崩溃容错；所有三个文件必须驻留在同一个支持 reflink 的文件系统上。gdbm_failure_atomic() 调用使用给定的名称创建两个空的只写快照文件，并 fsync() 它们及其封闭目录到根目录。在 gdbm_failure_atomic() 返回后，后续对 gdbm_sync() 的调用使用 ioctl(FICLONE) 根据先前描述的协议将主数据库文件的克隆存放到一个或另一个快照文件中，在两者之间交替。
崩溃后，应用程序通过调用 gdbm_latest_snapshot() 来识别最近修改的快照文件。此文件包含反映最近一次成功 gdbm_sync() 调用的 consistent 数据库，只需替换主 gdbm 数据文件即可。
由于 gdbm 不使用预写日志，因此无需“垃圾回收”在无故障运行期间堆积的日志，也无需重放日志以在崩溃后恢复期间重建数据库。
崩溃容错取决于系统调用以及文件和存储系统的正常运行；如果例如，存储设备在电源故障后发生故障，则一切都无法保证。18 此外，gdbm 库无法保护应用程序免受损坏其自身数据库的影响——对于 C/C++ 程序来说风险很大，但对于许多使用 gdbm 的 Python 和 Perl 程序来说风险很小。
很容易理解崩溃容错的 gdbm 并正确使用它，因为它只是加强了熟悉接口的语义：gdbm_sync() 一直意味着“持久化数据库”；崩溃容错添加了，“并且故障原子地克隆它”。连续 gdbm_sync() 调用之间对 gdbm 数据库的所有更改都构成一个事务。相比之下，begin()- 和 end()-transaction 接口更容易出错：诸如 malloc()/free()、lock()/unlock() 和 open()/close() 之类的书挡很容易不匹配。
深入挖掘
就像自己打包降落伞一样，在没有适当的培训和监督的情况下推出自己的崩溃容错机制是鲁莽的。现成的事务系统通常更好——如果它适合用途。17 为了成为精明的购买者和精明的用户，请研究故障原子更新机制的设计和实现。学习如何审计和破坏它们。了解它们如何依赖于操作系统、文件系统和存储。12,13,18 如果您依赖事务，请像战斗一样训练：针对它必须在生产中幸存下来的故障测试您的整个硬件-软件堆栈。9
位
从 https://ftp.gnu.org/gnu/gdbm/gdbm-1.21.tar.gz 获取 gdbm 1.21 版本。在文件 gdbmsync.c 中，查看用户可见函数 gdbm_failure_atomic() 和内部函数 _gdbm_snapshot() 的实现，该函数在 gdbm_sync() 完成其传统工作后调用。如果您需要崩溃容错的键值存储，请在阅读所有相关文档后考虑新的 gdbm。14, 15
练习
1. 数据库的标准性能测试比比皆是；示例包括 TPC 基准测试。尝试查找崩溃容错测试。
2. 找到一个已经使用 gdbm 的应用程序。修改它以利用崩溃容错。
3. 找到使用其他事务型键值存储的软件，并修改它以使用崩溃容错的 gdbm。针对实际故障测试两者。9 如果两者都通过，则比较性能。构建工作负载，使每个都比另一个更快。测量可持续的长期稳态；不要让预写日志堆积起来。
4. 如果一位远方的客户要求银行将钱从储蓄账户转移到支票账户，那么余额转移交易与银行告知客户钱款已转移的回复之间有什么关系？如果回复和交易没有正确协调，会发生什么情况？
5. 可靠性和安全性密切相关。计算机安全经济学1 中的哪些原则适用于可靠性？例如，谁应该评估崩溃容错声明：数据库供应商、独立研究人员还是最终用户？
6. 使用 raise(SIGKILL) 在 gdbm 中“中止事务”的优缺点是什么？
7. 构建持久哈希表的一种方法是从内存哈希表（例如，C++ STL <map>）开始，并使其持久化。8 如前所述添加崩溃容错并不困难。7 将该方法与事务型键值存储（例如 gdbm）进行比较。哪种方法支持更自然的编程风格？
致谢
GDBM 作者 Phil Nelson、GDBM 维护者 Sergey Poznyakoff 和编程珠玑作者 Jon Bentley 对本专栏草稿提供了宝贵的反馈。Lionel Debroux 回答了有关键值存储的问题。XFS 开发人员 Christoph Hellwig 回答了有关 reflink 克隆的问题。
参考文献
1. Anderson, R. 2001. 为什么信息安全很难——经济学视角。在年度计算机安全应用会议 (ACSAC)，十二月； https://www.acsac.org/2001/papers/110.pdf。
2. Bentley, J. 1987. 编程珠玑：自描述数据。《 通讯》30(6), 479–483； https://doi.org/10.1145/214762.315733。（《更多编程珠玑》，Addison-Wesley，1988 年，第 4 章）。
3. Bentley, J. 2019 年 8 月。给同事的电子邮件。Ken Thompson 和 Dennis Ritchie 编写了第一个 UNIX 操作系统。
4. Debian 流行度竞赛。2021 年 7 月； https://popcon.debian.org/。
5. Ghemawat, S., Dean, J. 2021. LevelDB； https://github.com/google/leveldb。
6. Hellwig, C. 2021 年 7 月。个人交流。块设备和文件系统语义的要求保证了文件系统内安装的正常运行。
7. Kelly, T. 2019. 传统持久内存。《Usenix ;login:》44(4), 29-34； https://www.usenix.org/system/files/login/articles/login_winter19_08_kelly.pdf。
8. Kelly, T. 2019. 传统硬件上的持久内存编程。《acmqueue》17(4)； https://queue.org.cn/detail.cfm?id=3358957。
9. Kelly, T. 2020. 持久内存是持久的吗？《 通讯》，63(9), 48-54； https://dl.acm.org/doi/10.1145/3397882。为了避免付费墙：《acmqueue》18(2)； https://queue.org.cn/detail.cfm?id=3400902。
10. Kernighan, B. W., Pike, R. 1984. 《UNIX 编程环境》。Prentice Hall。
11. Oracle Berkeley DB。2021 年 7 月； https://www.oracle.com/database/berkeley-db/。
12. Pillai, T. S., et al. 2014. 并非所有文件系统都是一样的：论制作崩溃一致性应用程序的复杂性。在第 11 届 Usenix 操作系统设计与实现研讨会 (OSDI) 会议论文集中； https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-pillai.pdf。
13. Pillai, T. S., et al. 2015. 崩溃一致性。《acmqueue》13(7)； https://dl.acm.org/doi/pdf/10.1145/2800695.2801719。
14. Poznyakoff, S. 2021. 崩溃容错 gdbm（九月）。1.21 版本（2021 年 9 月）。源代码 tarball：https://ftp.gnu.org/gnu/gdbm/gdbm-1.21.tar.gz。与 1.20 的差异：https://git.gnu.org.ua/gdbm.git/rawdiff/?id=v1.21&id2=v1.20
15. Poznyakoff, S. 2021. 崩溃容错。gdbm 手册（七月）； https://gnu.ac.cn.ua/software/gdbm/current/Crash-Tolerance.html。
16. Unix dbm 手册； http://man.cat-v.org/unix_7th/3/dbm。
17. Zheng, M., Tucek, J., Huang, D., Qin, F., Lillibridge, M., Yang, E. S., Zhao, B. W., Singh, S. 2014. 为了乐趣和利益折磨数据库。在第 11 届 Usenix 操作系统设计与实现研讨会 (OSDI) 会议论文集中； https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-zheng_mai.pdf。（请注意，单独提供勘误表。）
18. Zheng, M., Tucek, J., Qin, F., Lillibridge, M. 2013. 了解 SSD 在电源故障下的稳健性。在第 11 届 Usenix 文件和存储技术会议 (FAST) 会议论文集中； https://www.usenix.org/system/files/conference/fast13/fast13-final80.pdf。
在前空降兵Terence Kelly ([email protected]) 的空降区，绰号是“Crash”。
版权所有 © 2021 归所有者/作者所有。出版权已授权给 。
最初发表于 Queue vol. 19, no. 4—
在 数字图书馆 中评论本文
© 保留所有权利。