500行代码构建自己的数据库 DBDB
介绍
DBDB（狗床数据库）是一个 Python 库，它实现了一个简单的键值数据库。它允许你将一个键与一个值关联起来，并将这种关联存储在磁盘上以便以后检索。
DBDB 旨在计算机崩溃和错误情况下保存数据。它还避免一次性将所有数据都加载到 RAM 中，因此您可以存储比 RAM 容量更多的数据。
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 对象，它指向数据库中存储的二进制数据块。这种间接方式使我们能够避免一次性将整个数据存储加载到内存中。
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 OK
connect() 函数打开数据库文件（可能会创建该文件，但绝不会覆盖它），并返回一个 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 共享该引用。
在设计中，确定哪些对象“拥有”某个资源通常是一个重要的问题，因为它能提示我们哪些更改可能存在安全隐患。
一旦我们有了 DBDB 实例，获取 key 的值是通过字典查找 ( db[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 通过调用 LogicalBase 提供的 _tree.get() 方法来检索与内部 _tree 上的 key 关联的值：
# 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)
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
这是一个标准的二叉树搜索，通过节点引用进行查找。我们从 BinaryTree 文档中得知， Node ）和 NodeRef ）都是值对象：它们不可变，其内容永远不会改变。 Node 创建时会关联一个键和一个值，以及左子节点和右子节点。这些关联也永远不会改变。只有当根节点被替换时，整个 BinaryTree 的内容才会发生可见的变化。这意味着在执行搜索时，我们无需担心树的内容会发生变化。
一旦找到关联的值， main() 函数会将其写入 stdout ，而不添加任何额外的换行符，以完全保留用户的数据。
插入和更新
现在我们将 example.db 中键为 foo 的值设置为 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() 将 key 到 value 关联存储在内部 _tree 中。
_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
这里有两点需要注意：
- 我们的锁是由名为 portalocker 的第三方文件锁定库提供的。
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()
# dbdb/logical.py
class LogicalBase(object)
# ...
def commit(self):
self._tree_ref.store(self._storage)
self._storage.commit_root_address(self._tree_ref.address)
# 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))
# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
def prepare_to_store(self, storage):
if self._referent:
self._referent.store_refs(storage)
_tree.commit() 的实现来自 LogicalBase ：
所有 NodeRef 都知道如何通过首先请求其子节点使用 prepare_to_store() 进行序列化来将自身序列化到磁盘：
在这种情况下， LogicalBase 中的 self._tree_ref 实际上是一个 BinaryNodeRef （ ValueRef 的子类），因此 prepare_to_store() 的具体实现如上边代码所示：
相关 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)
这会一直递归下去，直到找到任何有未写入更改的 NodeRef （例如 _address ）。
现在我们又回到了 ValueRef 的 store 方法中，调用栈的上一级函数。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()
我们确保文件句柄被刷新（以便操作系统知道我们希望将所有数据保存到像固态硬盘这样的稳定存储设备上），并写入根节点的地址。我们知道最后一次写入是原子性的，因为我们将磁盘地址存储在扇区边界上。它是文件中的第一个元素，因此无论扇区大小如何，这个结论都成立，并且磁盘硬件保证单扇区磁盘写入是原子性的。
由于根节点地址要么是旧值，要么是新值（绝不会同时包含一部分旧值和一部分新值），其他进程无需加锁即可从数据库读取数据。外部进程可能看到旧树或新树，但绝不会同时看到两者。这样，提交操作就具有原子性。
由于我们在写入根节点地址之前就将新数据写入磁盘并调用了 fsync 系统调用 ，因此未提交的数据是无法访问的。相反，一旦根节点地址更新，我们就知道它引用的所有数据也都已在磁盘上。这样，提交操作也具有持久性。
NodeRefs 如何节省内存
为了避免同时将整个树结构保存在内存中，当从磁盘读取一个逻辑节点时，其左右子节点的磁盘地址（以及该子节点的值）会被加载到内存中。访问子节点及其值需要额外调用一次 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(log2N) 随机节点读取即可找到一个值，而 B+ 树所需的读取次数要少得多。 因为每个节点会分成 32 个分支，而不是只有 2 个，查找复杂度为O(log32n)。这在实践中会产生巨大的差异，因为遍历 40 亿个条目将需要从log 2 (232) =32到 log32(232)≈6.4 次查找。每次查找都是一次随机访问，这对使用旋转盘片的硬盘来说开销极大。固态硬盘 (SSD) 有助于降低延迟，但 I/O 方面的开销优势依然存在。
默认情况下，值由 ValueRef 存储，ValueRef 接受字节作为值（直接传递给 Storage ）。二叉树节点本身只是 ValueRef 的一个子类。要通过 JSON 或 msgpack 存储更丰富的数据，只需编写自定义的 ValueRef BinaryNodeRef 并将其设置为 value_ref_class 即可。BinaryNodeRef 是使用 pickle 序列化数据的一个示例。
数据库压缩是另一个有趣的练习。压缩可以通过对树进行中值遍历来实现，边遍历边写入数据。最好将所有树节点放在一起，因为查找任何数据都需要遍历这些节点。将尽可能多的中间节点打包到一个磁盘扇区中应该可以提高读取性能，至少在压缩后是如此。如果您尝试自己实现，这里会有一些细节（例如内存使用情况）。记住：务必在压缩前后进行性能基准测试！结果往往会让您感到惊讶。
模式与原则
测试的是接口，而不是实现。在开发 DBDB 的过程中，我编写了许多测试用例，描述了我希望如何使用它。最初的测试用例是针对数据库的内存版本运行的，后来我扩展了 DBDB 的功能，使其能够持久化到磁盘，甚至后来还添加了 NodeRef 的概念。大多数测试用例都不需要修改，这让我确信系统仍然运行良好。
遵循单一职责原则。类最多只能有一个修改的理由。虽然数据库数据库（DBDB）并非完全如此，但它有很多扩展途径，只需要进行局部修改。在添加新功能的同时进行重构，真是令人愉悦！
总结
DBDB 是一个简单的数据库，它提供的保证也很简单，但即便如此，问题还是很快变得复杂起来。为了应对这种复杂性，我做的最重要的事情就是用一个不可变的数据结构来实现一个表面上可变的对象。下次当你遇到棘手的问题，觉得各种边界情况多到难以处理时，建议你考虑一下这种方法。
- 附加功能：您能保证压缩后的树状结构保持平衡吗？这有助于长期维持性能 。↩
2. 对文件描述符调用 fsync 函数会请求操作系统和硬盘（或固态硬盘）立即写入所有缓冲数据。为了提高性能，操作系统和硬盘通常不会立即写入所有数据 。