作为 Countermeasure 最新的贝斯手（有时也担任男高音），Taavi 努力打破传统……有时仅仅是无视传统的存在。这在他的职业生涯中所经历的多样工作场所中得到了充分体现：IBM（从事 C 和 Perl 语言开发）、FreshBooks（负责所有事务）、Points.com（从事 Python 语言开发），以及现在的 PagerDuty（从事 Scala 语言开发）。除此之外——当他不骑着他的 Brompton 折叠自行车时——你可能会发现他在和儿子一起玩 Minecraft 或者和妻子一起参加跑酷（或者攀岩，或者其他冒险活动）。他使用大陆式针法编织。
DBDB（狗狗床数据库）是一个 Python 库，它实现了一个简单的键值数据库。它允许你将一个键与一个值关联起来，并将该关联存储在磁盘上以备日后检索。
DBDB 的目标是在计算机崩溃和错误情况下保护数据。它还避免一次将所有数据加载到内存中，这样你就可以存储比 RAM 容量更大的数据。
我记得第一次遇到一个真正让我卡住的 bug 的时候。当我完成 BASIC 程序的输入并运行它时，屏幕上出现了奇怪的闪闪发光的像素，程序提前中止了。当我回去查看代码时，程序的最后几行不见了。
我妈妈的一个朋友懂编程，所以我们给她打了电话。和她通话几分钟后，我找到了问题所在：程序太大了，侵占了视频内存。清除屏幕截断了程序，闪光点是 Applesoft BASIC 将程序状态存储在程序末尾后的 RAM 中的行为所产生的伪像。
从那一刻起，我开始关注内存分配。我学习了指针以及如何使用 malloc 分配内存。我了解了数据结构在内存中的布局。我学会了在修改数据结构时要非常小心。
几年后，在阅读关于一种叫做 Erlang 的面向过程的语言时，我了解到它实际上并不需要复制数据来在进程之间传递消息，因为所有东西都是不可变的。然后，我在 Clojure 中发现了不可变数据结构，这真的让我开始理解了。
当我 2013 年读到 CouchDB 时，我只是微笑点头，因为我认识到用于管理复杂数据的结构和机制。
我了解到你可以在不可变数据的基础上设计系统。
然后，我答应写一个章节。
我认为描述 CouchDB 的核心数据存储概念（正如我理解的那样）会很有趣。
在尝试编写一个原地修改树的二叉树算法时，我因为事情变得太复杂而感到沮丧。边角情况的数量以及试图推断树的一个部分的变化如何影响其他部分让我头疼。我不知道该怎么解释这一切。
牢记以往的经验教训，我查看了更新不可变二叉树的递归算法，发现它相对简单。
我再次认识到，对于不改变的事物来说，推断起来更容易。
故事由此开始。
大多数项目都需要某种数据库。你真的不应该自己编写数据库；即使你只是将 JSON 写入磁盘，也会有很多边角情况会让你措手不及。
但是，如果你想了解数据库如何处理所有这些问题，自己编写一个数据库可能是一个好主意。
我们在本文中讨论的技术和概念应该适用于任何需要在遇到故障时表现出合理、可预测的行为的问题。
说到故障……
数据库通常以它们对 ACID 属性的遵守程度来区分：原子性、一致性、隔离性和持久性。
DBDB 中的更新是原子性和持久的，这两个属性将在本章后面进行描述。DBDB 不提供任何一致性保证，因为对存储的数据没有限制。隔离同样没有实现。
当然，应用程序代码可以自己实施一致性保证，但适当的隔离需要事务管理器。我们这里不会尝试这样做；但是，你可以在 CircleDB 章节 中了解有关事务管理的更多信息。
我们还需要考虑其他系统维护问题。在这个实现中，过时的数据不会被回收，因此重复更新（即使是针对同一个键的更新）最终会消耗掉所有磁盘空间。（你很快就会发现这是为什么。）PostgreSQL 将此回收称为“vacuuming”（使旧的行空间可供重用），而 CouchDB 将其称为“compaction”（通过将数据的“活动”部分重写到一个新文件中，并原子地将其移到旧文件上）。
DBDB 可以通过添加一个压缩功能来进行增强，但这留给读者作为练习1。
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/tool.py
def main(argv):
if not (4 <= len(argv) <= 5):
usage()
return BAD_ARGS
dbname, verb, key, value = (argv[1:] + [None])[:4]
if verb not in {'get', 'set', 'delete'}:
usage()
return BAD_VERB
db = dbdb.connect(dbname) # CONNECT
try:
if verb == 'get':
sys.stdout.write(db[key]) # GET VALUE
elif verb == 'set':
db[key] = value
db.commit()
else:
del db[key]
db.commit()
except KeyError:
print("Key not found", file=sys.stderr)
return BAD_KEY
return OKconnect() 函数打开数据库文件（可能创建它，但从不覆盖它）并返回一个 DBDB 实例。
# dbdb/__init__.py
def connect(dbname):
try:
f = open(dbname, 'r+b')
except IOError:
fd = os.open(dbname, os.O_RDWR | os.O_CREAT)
f = os.fdopen(fd, 'r+b')
return DBDB(f)# dbdb/interface.py
class DBDB(object):
def __init__(self, f):
self._storage = Storage(f)
self._tree = BinaryTree(self._storage)我们立即看到 DBDB 引用了一个 Storage 实例，但它也与 self._tree 共享该引用。为什么？self._tree 不能自己管理对存储的访问吗？
哪个对象“拥有”资源的问题在设计中通常是一个重要问题，因为它为我们提供了一些关于哪些更改可能不安全的提示。让我们在继续之前牢记这个问题。
一旦我们有了 DBDB 实例，就可以通过字典查找（db[key]）在 key 上获取关联的值，这将导致 Python 解释器调用 DBDB.__getitem__()。
# dbdb/interface.py
class DBDB(object):
# ...
def __getitem__(self, key):
self._assert_not_closed()
return self._tree.get(key)
def _assert_not_closed(self):
if self._storage.closed:
raise ValueError('Database closed.')__getitem__() 通过调用 _assert_not_closed 来确保数据库仍然处于打开状态。啊哈！这里我们至少看到 DBDB 需要直接访问 Storage 实例的一个原因：这样它就可以强制执行先决条件。（你同意这种设计吗？你能想到另一种方法吗？）
DBDB 然后通过调用 _tree.get() 在内部 _tree 上检索与 key 关联的值，该方法由 LogicalBase 提供。
# dbdb/logical.py
class LogicalBase(object):
# ...
def get(self, key):
if not self._storage.locked:
self._refresh_tree_ref()
return self._get(self._follow(self._tree_ref), key)get() 检查我们是否锁定了存储。我们不确定为什么这里可能存在锁，但我们可以猜测它可能存在是为了允许写入者序列化对数据的访问。如果存储没有被锁定会发生什么？
# dbdb/logical.py
class LogicalBase(object):
# ...
def _refresh_tree_ref(self):
self._tree_ref = self.node_ref_class(
address=self._storage.get_root_address())_refresh_tree_ref 使用当前磁盘上的内容重置树的“数据视图”，使我们能够执行完全最新的读取。
如果我们在尝试读取时存储被锁定了会发生什么？这意味着其他某个进程可能正在修改我们现在要读取的数据；我们的读取可能不会与数据的当前状态保持一致。这通常被称为“脏读”。这种模式允许许多读者访问数据，而无需担心阻塞，但代价是它们可能略微过时。
现在，让我们看看我们实际上是如何检索数据的。
# dbdb/binary_tree.py
class BinaryTree(LogicalBase):
# ...
def _get(self, node, key):
while node is not None:
if key < node.key:
node = self._follow(node.left_ref)
elif node.key < key:
node = self._follow(node.right_ref)
else:
return self._follow(node.value_ref)
raise KeyError这是一个标准的二叉树搜索，按照 ref 到它们的节点进行。我们从阅读 BinaryTree 文档中知道 Node 和 NodeRef 是值对象：它们是不可变的，它们的内容从不改变。Node 是使用关联的键和值以及左孩子和右孩子创建的。这些关联也永远不会改变。整个 BinaryTree 的内容只有在根节点被替换时才会发生可见变化。这意味着我们无需担心在执行搜索时树的内容会被更改。
找到关联的值后，main() 将其写入 stdout，而不添加任何额外的换行符，以精确保留用户的数据。
现在，我们将键 foo 设置为 example.db 中的值 bar。
$ python -m dbdb.tool example.db set foo bar再次，这运行了来自模块 dbdb.tool 的 main() 函数。由于我们之前已经看过这段代码，所以我们只突出显示重要的部分。
# dbdb/tool.py
def main(argv):
...
db = dbdb.connect(dbname) # CONNECT
try:
...
elif verb == 'set':
db[key] = value # SET VALUE
db.commit() # COMMIT
...
except KeyError:
...这次我们使用 db[key] = value 设置值，这会调用 DBDB.__setitem__()。
# dbdb/interface.py
class DBDB(object):
# ...
def __setitem__(self, key, value):
self._assert_not_closed()
return self._tree.set(key, value)__setitem__ 确保数据库仍然处于打开状态，然后通过调用 _tree.set() 在内部的 _tree 上存储从 key 到 value 的关联。
_tree.set() 由 LogicalBase 提供。
# dbdb/logical.py
class LogicalBase(object):
# ...
def set(self, key, value):
if self._storage.lock():
self._refresh_tree_ref()
self._tree_ref = self._insert(
self._follow(self._tree_ref), key, self.value_ref_class(value))set() 首先检查存储锁。
# dbdb/storage.py
class Storage(object):
...
def lock(self):
if not self.locked:
portalocker.lock(self._f, portalocker.LOCK_EX)
self.locked = True
return True
else:
return False这里有两点需要注意：
lock() 返回 False，否则返回 True。回到 _tree.set()，我们现在可以理解它为什么首先检查 lock() 的返回值：它让我们可以为最新的根节点引用调用 _refresh_tree_ref，这样我们不会丢失自上次从磁盘刷新树后其他进程可能做出的更新。然后它用包含插入（或更新）的键值的新树替换根树节点。
插入或更新树不会改变任何节点，因为 _insert() 返回一个新的树。新的树与之前的树共享未更改的部分，以节省内存和执行时间。递归地实现这一点很自然。
# dbdb/binary_tree.py
class BinaryTree(LogicalBase):
# ...
def _insert(self, node, key, value_ref):
if node is None:
new_node = BinaryNode(
self.node_ref_class(), key, value_ref, self.node_ref_class(), 1)
elif key < node.key:
new_node = BinaryNode.from_node(
node,
left_ref=self._insert(
self._follow(node.left_ref), key, value_ref))
elif node.key < key:
new_node = BinaryNode.from_node(
node,
right_ref=self._insert(
self._follow(node.right_ref), key, value_ref))
else:
new_node = BinaryNode.from_node(node, value_ref=value_ref)
return self.node_ref_class(referent=new_node)注意我们始终返回一个新节点（包装在 NodeRef 中）。我们不是更新一个节点以指向一个新的子树，而是创建一个新的节点，该节点共享未更改的子树。这就是使这棵二叉树成为不可变数据结构的原因。
您可能已经注意到这里有一些奇怪的地方：我们还没有对磁盘上的任何东西进行任何更改。我们所做的只是通过移动树节点来操作我们对磁盘上数据的视图。
为了真正将这些更改写入磁盘，我们需要显式调用 commit()，我们在一节开头在 tool.py 中看到了 set 操作的第二部分。
提交涉及写出内存中所有脏状态，然后保存树新根节点的磁盘地址。
从 API 开始
# dbdb/interface.py
class DBDB(object):
# ...
def commit(self):
self._assert_not_closed()
self._tree.commit()_tree.commit() 的实现来自 LogicalBase。
# dbdb/logical.py
class LogicalBase(object)
# ...
def commit(self):
self._tree_ref.store(self._storage)
self._storage.commit_root_address(self._tree_ref.address)所有 NodeRef 都知道如何通过首先让他们的子节点通过 prepare_to_store() 进行序列化来将自己序列化到磁盘。
# dbdb/logical.py
class ValueRef(object):
# ...
def store(self, storage):
if self._referent is not None and not self._address:
self.prepare_to_store(storage)
self._address = storage.write(self.referent_to_string(self._referent))在这种情况下，LogicalBase 中的 self._tree_ref 实际上是一个 BinaryNodeRef（ValueRef 的子类），因此 prepare_to_store() 的具体实现是
# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
def prepare_to_store(self, storage):
if self._referent:
self._referent.store_refs(storage)相关的 BinaryNode，_referent，要求它的引用存储自己。
# dbdb/binary_tree.py
class BinaryNode(object):
# ...
def store_refs(self, storage):
self.value_ref.store(storage)
self.left_ref.store(storage)
self.right_ref.store(storage)这对任何具有未写入更改（即没有 _address）的 NodeRef 都递归到底层。
现在我们回到了 ValueRef 的 store 方法的堆栈中。store() 的最后一步是序列化此节点并保存其存储地址。
# dbdb/logical.py
class ValueRef(object):
# ...
def store(self, storage):
if self._referent is not None and not self._address:
self.prepare_to_store(storage)
self._address = storage.write(self.referent_to_string(self._referent))此时，NodeRef 的 _referent 保证其所有引用都有可用的地址，因此我们通过创建一个表示此节点的字节串来序列化它。
# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
# ...
@staticmethod
def referent_to_string(referent):
return pickle.dumps({
'left': referent.left_ref.address,
'key': referent.key,
'value': referent.value_ref.address,
'right': referent.right_ref.address,
'length': referent.length,
})更新 store() 方法中的地址在技术上是对 ValueRef 的修改。因为它对用户可见的值没有影响，所以我们可以将其视为不可变。
一旦根 _tree_ref 上的 store() 完成（在 LogicalBase.commit() 中），我们就知道所有数据都已写入磁盘。现在我们可以通过调用以下方法提交根地址：
# dbdb/physical.py
class Storage(object):
# ...
def commit_root_address(self, root_address):
self.lock()
self._f.flush()
self._seek_superblock()
self._write_integer(root_address)
self._f.flush()
self.unlock()我们确保文件句柄被刷新（以便操作系统知道我们想要将所有数据保存到稳定的存储设备，例如 SSD）并写出根节点的地址。我们知道最后一次写入是原子性的，因为我们存储在扇区边界上的磁盘地址。它是文件中的第一个内容，因此无论扇区大小如何，这都是正确的，并且磁盘硬件保证单扇区磁盘写入是原子性的。
因为根节点地址要么是旧值要么是新值（绝不会是新旧值的混合），所以其他进程可以在没有获取锁的情况下从数据库中读取数据。外部进程可能会看到旧树或新树，但绝不会看到两者的混合。这样，提交是原子性的。
因为我们在写入新数据到磁盘并调用 fsync 系统调用2 之后才写入根节点地址，所以未提交的数据是不可访问的。相反，一旦根节点地址更新，我们就知道它引用的所有数据也都在磁盘上。这样，提交也是持久的。
我们完成了！
为了避免同时将整个树结构保存在内存中，当从磁盘读取逻辑节点时，其左右子节点的磁盘地址（以及其值）将加载到内存中。访问子节点及其值需要额外调用 NodeRef.get() 来取消引用（真正获取）数据。
我们只需要一个地址就可以构造一个 NodeRef。
+---------+
| NodeRef |
| ------- |
| addr=3 |
| get() |
+---------+对它调用 get() 将返回具体的节点，以及该节点的引用作为 NodeRef。
+---------+ +---------+ +---------+
| NodeRef | | Node | | NodeRef |
| ------- | | ------- | +-> | ------- |
| addr=3 | | key=A | | | addr=1 |
| get() ------> | value=B | | +---------+
+---------+ | left ----+
| right ----+ +---------+
+---------+ | | NodeRef |
+-> | ------- |
| addr=2 |
+---------+当对树的更改未提交时，它们存在于内存中，从根到更改的叶子的引用。更改尚未保存到磁盘，因此更改后的节点包含具体的键和值，没有磁盘地址。进行写入的进程可以看到未提交的更改，并且可以在发出提交之前进行更多更改，因为 NodeRef.get() 将返回未提交的值（如果有）；通过 API 访问已提交和未提交的数据之间没有区别。所有更新将对其他读取器原子地显示，因为更改在新的根节点地址写入磁盘之前是不可见的。并发更新被磁盘上的锁定文件阻止。在首次更新时获取锁，并在提交后释放锁。
DBDB 允许许多进程同时读取同一个数据库，而不会阻塞；权衡是读取器有时会检索到过时的数据。如果我们需要一致地读取一些数据怎么办？一个常见的用例是读取一个值，然后根据该值更新它。您将如何在 DBDB 上编写一个方法来执行此操作？为了提供此功能，您需要付出哪些权衡？
用于更新数据存储的算法可以通过替换 interface.py 中的字符串 BinaryTree 来完全更改。数据存储往往使用更复杂类型的搜索树，例如 B 树、B+ 树等等，以提高性能。虽然平衡二叉树（这个不是）需要进行 \(O(log_2(n))\) 次随机节点读取才能找到一个值，但 B+ 树需要的次数要少得多，例如 \(O(log_{32}(n))\)，因为每个节点分叉 32 次而不是只有 2 次。这在实践中产生了巨大的差异，因为遍历 40 亿个条目将从 \(log_2(2^{32}) = 32\) 变为 \(log_{32}(2^{32}) \approx 6.4\) 次查找。每次查找都是随机访问，对于具有旋转磁盘的硬盘来说非常昂贵。SSD 有助于减少延迟，但 I/O 节省仍然存在。
默认情况下，值由 ValueRef 存储，ValueRef 期待字节作为值（直接传递给 Storage）。二叉树节点本身只是 ValueRef 的一个子类。通过 json 或 msgpack 存储更丰富的数据，只需编写您自己的数据并将其设置为 value_ref_class 即可。BinaryNodeRef 是使用 pickle 序列化数据的示例。
数据库压缩是另一个有趣的练习。压缩可以通过对树进行中序中值遍历来完成，在遍历时将内容写入磁盘。如果树节点都放在一起，这可能是最好的，因为它们是查找任何数据的遍历对象。将尽可能多的中间节点打包到一个磁盘扇区中应该可以提高读取性能，至少在压缩之后就是这样。如果您尝试自己实现这一点，这里有一些微妙之处（例如，内存使用情况）。请记住：在进行性能增强之前和之后始终进行基准测试！您经常会对结果感到惊讶。
测试接口，而不是实现。在开发 DBDB 的过程中，我编写了许多测试，这些测试描述了我想如何使用它。第一个测试针对数据库的内存版本运行，然后我扩展了 DBDB 以持久化到磁盘，甚至后来添加了 NodeRefs 的概念。大多数测试不需要更改，这让我确信一切仍然正常工作。
遵守单一职责原则。类最多应该只有一个变化原因。DBDB 不是严格意义上的这种情况，但有多种扩展途径，只需要进行本地化更改。在我添加功能时进行重构真是太令人愉悦了！
DBDB 是一个简单的数据库，它提供简单的保证，但事情仍然很快变得复杂起来。我管理这种复杂性的最重要的措施是使用不可变数据结构实现一个看似可变的对象。我鼓励您在下次遇到棘手的难题时，考虑使用这种技术，因为这种难题似乎有太多您无法跟踪的边缘情况。