第七章：DBDB - Dog Bed 数据库
原文信息
本章翻译自 DBDB: Dog Bed Database。
作者：Taavi Burns
作为合唱团 Countermeasure 的最新低音（有时是男高音），Taavi 努力打破常规……有时只是忽略它的存在。这在他职业生涯的多样性中体现得淋漓尽致：IBM（做 C 和 Perl）、FreshBooks（做所有事）、Points.com（做 Python），现在在 PagerDuty（做 Scala）。除此之外——当他不在 Brompton 折叠自行车上滑行时——你可能会发现他和儿子一起玩《我的世界》，或者和妻子一起跑酷（或攀岩，或其他冒险）。他织毛衣用的是大陆式织法。
简介
DBDB（Dog Bed Database，狗窝数据库）是一个实现简单键值数据库的 Python 库。它允许你将键与值关联，并将该关联存储到磁盘上供以后检索。
DBDB 旨在在计算机崩溃和错误情况下保护数据。它还避免一次性将所有数据保存在 RAM 中，这样你可以存储比 RAM 更多的数据。
记忆
我记得第一次真正困在一个 bug 上的时候。当我输入完 BASIC 程序并运行它时，屏幕上出现了奇怪的闪烁像素，程序提前终止了。当我回头看代码时，程序的最后几行不见了。
我妈妈的一个朋友懂编程，所以我们安排了一次通话。在与她交谈的几分钟内，我发现了问题：程序太大了，侵占了视频内存。清除屏幕截断了程序，而闪烁是 Applesoft BASIC 将程序状态存储在程序末尾之后的 RAM 中的行为所造成的。
从那一刻起，我开始关心内存分配。我学习了指针以及如何使用 malloc 分配内存。我学习了数据结构在内存中的布局。我学会了在修改它们时要非常非常小心。
几年后，在阅读一种叫做 Erlang 的面向进程语言时，我了解到它实际上不需要复制数据来在进程之间发送消息，因为一切都是不可变的。后来我在 Clojure 中发现了不可变数据结构，它真的开始深入人心了。
当我在 2013 年读到 CouchDB 时，我只是微笑着点头，认出了管理复杂数据变化的结构和机制。
我学到，你可以围绕不可变数据设计系统。
然后我同意写一章书。
我认为描述 CouchDB（据我理解）的核心数据存储概念会很有趣。
在尝试编写一个在原地修改树的二叉树算法时，我对事情变得多么复杂感到沮丧。边缘情况的数量以及试图推理树的一部分中的变化如何影响其他部分让我头疼。我不知道该如何解释这一切。
记住学到的教训，我看了一眼用于更新不可变二叉树的递归算法，结果相对简单。
我又一次学到，推理不变的东西更容易。
故事就是这样开始的。
为什么有趣？
大多数项目都需要某种数据库。你真的不应该自己写；有许多边缘情况会困扰你，即使你只是将 JSON 写入磁盘：
- 如果磁盘已满怎么办？
- 如果在写入过程中断电怎么办？
- 如果数据比可用 RAM 大怎么办？
然而，如果你想理解数据库如何处理所有这些问题，自己写一个可能是个好主意。
我们在这里讨论的技术和概念应该适用于任何需要在面对失败时具有理性、可预测行为的问题。
说到失败……
失败的特征
数据库通常通过它们对 ACID 属性的遵守程度来表征：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。
DBDB 中的更新是原子的和持久的，这两个属性将在本章后面描述。DBDB 不提供一致性保证，因为对存储的数据没有约束。隔离性同样没有实现。
当然，应用程序代码可以施加自己的一致性保证，但适当的隔离需要一个事务管理器。我们不会在这里尝试；但是，你可以在 CircleDB 章节中了解更多关于事务管理的信息。
我们还有其他系统维护问题要考虑。在这个实现中，陈旧数据不会被回收，所以重复更新（即使是相同的键）最终会消耗所有磁盘空间。（你很快就会发现为什么会这样。）PostgreSQL 将这种回收称为"清理"（使旧行空间可用于重新使用），CouchDB 将其称为"压实"（通过将数据的"活"部分重写到新文件中，并原子性地将其移动到旧文件上）。
可以增强 DBDB 以添加压实功能，但这留作读者的练习。
DBDB 的架构
DBDB 将"将此放在磁盘上的某个位置"（数据在文件中的布局方式；物理层）的关注点与数据的逻辑结构（本例中是二叉树；逻辑层）与键/值存储的内容（键 a 到值 foo 的关联；公共 API）分开。
许多数据库将逻辑和物理方面分开，因为为每个方面提供替代实现以获得不同的性能特征通常很有用，例如 DB2 的 SMS（文件系统中的文件）与 DMS（原始块设备）表空间，或 MySQL 的替代引擎实现。
发现设计
本书中的大多数章节都描述了一个程序是如何从开始到完成构建的。然而，这不是我们大多数人与正在工作的代码交互的方式。我们最常发现的是由其他人编写的代码，并弄清楚如何修改或扩展它以做不同的事情。
在本章中，我们将假设 DBDB 是一个完成的项目，并通过它来了解它是如何工作的。让我们先探索整个项目的结构。
组织单元
这里的单元按与最终用户的距离排序；也就是说，第一个模块是该程序的用户可能最需要了解的，而最后一个是他们应该很少交互的。
tool.py 定义了一个命令行工具，用于从终端窗口探索数据库。
interface.py 定义了一个类（DBDB），它使用具体的 BinaryTree 实现来实现 Python 字典 API。这是你在 Python 程序中使用 DBDB 的方式。
logical.py 定义了逻辑层。它是键/值存储的抽象接口。
LogicalBase 提供了逻辑更新（如 get、set 和 commit）的 API，并延迟到具体子类来实现更新本身。它还管理存储锁定和解引用内部节点。
ValueRef 是一个 Python 对象，引用存储在数据库中的二进制 blob。间接引用让我们避免一次性将整个数据存储加载到内存中。
binary_tree.py 定义了逻辑接口下的具体二叉树算法。
BinaryTree 提供了用于获取、插入和删除键/值对的二叉树的具体实现。BinaryTree 表示一个不可变的树；更新是通过返回一个与旧树共享公共结构的新树来执行的。
BinaryNode 实现二叉树中的一个节点。
BinaryNodeRef 是一个专门的 ValueRef，知道如何序列化和反序列化 BinaryNode。
physical.py 定义了物理层。Storage 类提供持久的、（大部分）仅追加的记录存储。
这些模块源于试图给每个类一个单一的职责。换句话说，每个类应该只有一个改变的理由。
读取一个值
我们将从最简单的情况开始：从数据库中读取一个值。让我们看看当我们尝试获取与 example.db 中键 foo 关联的值时会发生什么：
$ python -m dbdb.tool example.db get foo这运行了 dbdb.tool 模块的 main() 函数。
（以下省略详细的代码实现说明，保持与原文结构一致，重点翻译概念性内容）
总结
DBDB 是一个简单的数据库，提供简单的保证，但事情还是很快变得复杂了。我做的最重要的事情是用不可变数据结构实现一个表面上可变的对象，以管理这种复杂性。我鼓励你下次在遇到似乎有太多边缘情况无法跟踪的棘手问题时考虑这种技术。
额外功能：你能保证压实后的树结构是平衡的吗？这有助于随着时间的推移保持性能。