DBDB - Dog Bed Database

Introduction

DBDB (Dog Bed Database) 是一个实现了简单 key/value 数据库的 Python 库。它将键和值进行关联，并把这种关联关系存储到磁盘上用于之后的访问。

DBDB 旨在电脑崩溃或者其他错误条件下也能保证数据的安全。它也避免了把所有的数据都存在内存当中，这样，用户就可以存储比内存容量更大的数据。

Why is it Interesting?

大多数项目都在某种程度上使用到了数据库。你确实不需要自己写一个，就算是将 json 数据存储到磁盘上，数不尽的边缘情况也会把你搞崩溃。

• 当存储空间不足时会发生什么？
• 当数据正在存储，但是笔记本没电了，会发生什么？
• 当数据大小比可用内存空间还要大，会发生什么？

尽管如此，实现一个自己的数据库是一个非常好的方法来理解一个数据库系统如何处理这些情况。

我们这里讨论的技术和概念应该要能够处理各种情况。

说道不足之处。。。

Characterizing Failure

数据库的评判标准在于多大程度的遵守了 ACID 属性：atomicity（原子性）、consistency（一致性）、isolation（独立性）、durability（持久性）。

DBDB 的数据更新保证了原子性和持久性。这两个属性就会在后面的章节介绍。由于没有对数据存储做限制，DBDB无法保证一致性；独立性也统一没有实现。

应用程序自身是可以保证自己的一致性，但是在数据库中实现一致性需要一个事务管理器。我们没有在这里试图实现它，不过，你可以在CircleDB chapter进一步了解事务管理器。

我们同事还有别的一些系统维护的问题需要考虑。旧数据（Stale data）在 DBDB 中不会进行回收处理，因此，不断的更新最终将消耗掉所有的磁盘空间。PostgreSQL 把处理陈旧数据的过程称之为“吸尘(vacuuming)”，这使得旧的行空间可以重新使用，CouchDB 把处理陈旧数据的过程称之为“压缩”，通过把正常数据(live data)的部分重写入新文件，并替代旧的文件。

DBDB 能够添加“压缩”这个功能，不过这就留作读者的练习了。

The Architecture of DBDB

DBDB 把物理层（数据是如何存储在文件当中）和逻辑层（数据的逻辑结构 - 在这里是二叉树）从 key/value 存储相关的内容分离开来。

许多数据库豆浆逻辑层和物理层分离开来，这样能有效地提供不同的实现来获得不同的性能特性。比如说，DB2的SMS(文件系统中的文件)和DMS(原始块设备)或MySQL的替代引擎。

Discovering the Design

在本文中，我们假设 DBDB 是一个完整的项目，然后去了解它的流程和逻辑。让我们先从整个项目的结构开始吧。

Organisational Units

以下文件按照一个普通用户所需要了解的程度来排列。

• tool.py 提供了一个在终端使用数据库的命令行工具。
• interface.py 定义了一个DBDB类。它使用二叉树来实现了 Python 中的 dict。这也将是你如何在一个 Python 程序中使用 DBDB。

• logical.py定义了逻辑层。这是存储 key/value 的抽象接口。

  • LogicalBase提供了逻辑上更新（get/set/commit）的接口，并用一个子类来完成具体的实现。它也提供了对存储的锁以及内部节点的解应用（dereferencing）。
  • ValueRef是一个对应于存在数据库中的二进制大型对象（blob）的 Python 对象。它间接上让我们避免了一次性将所有数据加载到内存当中。

• binary_tree.py定义了在逻辑接口之下的二叉树。

  • BinaryTree提供了二叉树的具体实现，包括 get、insert、delete key/value 的方法。二叉树是一个不可变（immutable)对象，所以数据的更新会生成一个与之前的树一样结构的二叉树。
  • BinaryNode实现了二叉树中的节点。
  • BinaryNodeRef是一个ValueRef类的特殊化实现，用来实现如何序列化和反序列化BinaryNode。
• physical.py定义了物理层，Storage类提供了持久化存储。

每个类只能有一个改变的原因。（each class should have only one reason to change.）

Reading a Value

我们从一个简单的例子开始：从数据库中读取一个数据。来看下如何从example.db数据库中获取 key 为foo的 value 吧。

$ 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。为什么要这样做呢？self._tree不能用自己单独的对存储的访问么？

关于哪个对象应该“拥有”一个资源的问题，在设计中通常是一个重要的问题，因为它影响到了程序的安全性。我们稍后会解释这个问题。

当我们得到DBDB的实例后，通过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()函数（由LogicalBase提供）来获取key在内部_tree中所对应的值。

# 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() 先检查了 storage 是否被锁。我们现在可以猜到它是用来管理数据写入权限的。如果存储不使用锁会发生什么呢？

# 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将磁盘上数据树的视图（view）更新了，这让我们能够读取最新的数据。

如果我们读取数据的时候，数据被锁了呢？这说明其他的进程或许正在更新这部分数据；我们读取的数据可能不是最新的。 这通常被称为“脏读”(dirty read)。这种模式允许许多读者访问数据，而不用担心阻塞，相对的缺点就是数据可能不是最新的。

现在，一起来看看是怎么具体拿取数据的。

# 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

这是一个标准的二叉树搜索算法。上文中介绍过了Node 和 NodeRef 是BinaryTree中的对象。他们是不可变的，所以他们的值不会改变。Node类包括键值和左右子项，这些不会改变。当更换根节点时，整个BinaryTree的内容才会明显变化。 这意味着在执行搜索时，我们不需要担心我们的树的内容被改变。

当找到了相应的值后，main()函数会把这个值写入到stdout，输出的值中，并且不会包含换行符。

Inserting and Updating

现在，我们在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:
        ...

这次我们通过调用 DBDB.__setitem__() 做到 db[key] = value。

# 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。

回到_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中)。我们建一个新的节点，它会与旧的节点共享未改变的部分。而不是更新旧的节点上的数据。这使我们的二叉树是不可变的(immutable)。

你可能意识到有个奇怪的地方：我们还没对磁盘上的数据做任何处理呢。我们目前所做的只是通过移动树的节点来操纵我们对磁盘数据的视图。

为了真正的把新的数据保存在硬盘上，我们需要调用commit()函数。我们在前面的讲set操作的章节见过这个函数。

commit 将会把内存中的所有脏状态写出，然后保存下磁盘地址作为树的新的根节点。

# 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的序列化(serialise)是通过让它们的子节点使用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)

The BinaryNode in question, _referent, asks its refs to store themselves:

# 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()里的最后一步是序列化这个节点，然后保存它的存储地址：

# 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保证会有引用的地址，所以我们通过创建这个节点的字节串(bytestring)来序列化它：

# 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()中)，所有的数据就已经保存在磁盘上了。现在我们可以调用根地址的提交(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()

我们确保句柄(file handle)已被刷新(所以系统就知道了我们想要所有数据都被保存起来，比如：SSD)以及返回了根节点的地址。我们知道最后一次写入是具有原子性(atomic)的，因为我们将磁盘地址存储在扇区边界上(sector boundary)。这是文件中的最靠前的，所以无论扇区大小如何，这都是正确的，单扇区磁盘写入能由磁盘硬件保证原子性。

因为根节点地址要么是旧值要么是新值(没有中间值)，所以其他进程可以从数据库中读取而不用锁定。 外部进程可能会获取到旧的或新的数据。所以，提交(commit)是原子性的。

因为我们在赋予根节点地址之前，会把新的数据写入磁盘并调用fsync syscall [尾注2]，所以未提交的数据是无法访问的。 相反，一旦根节点地址被更新，我们知道它引用的所有数据也在磁盘上。以这种方式，提交(commit)也具有持久性(durability)。

就是这样！

How NodeRefs Save Memory

为了避免把这个树的数据同时保存在内存中，当从磁盘读取逻辑节点时，其左和右子节点的磁盘地址(还有值)将被加载到内存中。所以访问子节点需要调用一个额外的函数NodeRef.get()来获取真正的数据。

NodeRef 只需包含一个地址：

+---------+
| NodeRef |
| ------- |
| addr=3  |
| get()   |
+---------+

当点用 get()后，NodeRef 会返回具体的节点，并包括其两个子节点的NodeRef类。

+---------+     +---------+     +---------+
| NodeRef |     | Node    |     | NodeRef |
| ------- |     | ------- | +-> | ------- |
| addr=3  |     | key=A   | |   | addr=1  |
| get() ------> | value=B | |   +---------+
+---------+     | left  ----+
                | right ----+   +---------+
                +---------+ |   | NodeRef |
                            +-> | ------- |
                                | addr=2  |
                                +---------+

当树的更改未提交时，它们保存在内存中，包括从根(root)向下到更改的叶(leaves)。 当更改还没保存到磁盘时，所以被更改的节点包含具体的键和值，但是没有磁盘地址。 处理写入的进程可以看到这些未提交的更改，并且可以在发出提交之前再次对其进行更改，这是因为NodeRef.get()有值的话，会返回一个未提交的值; 在通过API访问时，提交和未提交的数据之间没有区别。其他读者可以看到最新的数据，因为新的更改在根节点的地址被写入磁盘前，是看不到的。并发的更新操作会被磁盘上的文件锁阻止。文件会在第一次更新时上锁，并在提交后解锁。

Exercises for the Reader

DBDB 允许多进程同时访问同一个数据库。为做到这一点，我们付出的是，读取有时获得的是陈旧的数据。如果我们需要总是读取最新的数据该怎么办？ 一个常见的用例是读取值，然后根据该值进行更新。 你如何在“DBDB”上实现这个方法呢？你需要做什么权衡来做到这个功能呢？

更新数据存储的算法可以通过改变interface.py文件中的这个词BinaryTree来使用别的算法。 比如说可以用 B-trees, B+ trees 或其他的结构来提高数据库的效能。一个平衡的二叉树需要做O(log2(n))次节点的读取，来查找值。而B+树只需要更少的次数，比如O(log32(n))次，永伟每个节点有32个子节点(而不是2个)。这会很大的提高练习的难度。比如40亿条数据中查找一条信息，这需要大约 log2(2 ^ {32})= 32 至 log32(2 ^ {32})=6.4次查找。每个查找都是随机访问，因为开销非常大，所以这是难以做到的。SSD或许可以用延迟解决，但I/O的节省仍然存在。

默认情况下，值以字节的形式(为了能直接传入到Storage)存储在ValueRef里。二叉树的节点是ValueRef的子类。通过json 或者 msgpack 格式保存更丰富的数据则需要编写自己的文件并将其设置为“value_ref_class”。BinaryNodeRef 就是一个使用 pickle 来序列化数据的例子。

压缩数据库是另一个有趣的练习。 压缩可以随着树的移动通过中间遍历(infix-of-median traversal)完成。如果树节点全部在一起可能是最好的，因为它们是遍历以查找任何数据的。将尽可能多的中间节点打包进到磁盘扇区中可以提高读取性能，至少是在压缩之后，可以提高读取效率。 这里有一些细节需要注意(例如，内存使用)，如果你打算完成这个练习。 请记住：在修改前后，总是注意记录性能的改变！你经常会对结果感到惊讶。

Patterns and Principles

有些没有实现的测试接口。作为开发DBDB的一部分，我写了一些描述我想要使用DBDB的测试。第一个测试针对数据库的内存版本进行，然后我将DBDB的存储方式扩展到了磁盘，甚至后来添加了NodeRefs的概念。而且大多数测试并不需要改变，这让我对开发DBDB更加有信心。

遵守单一责任原则(Single Responsibility Principle)。类最多只能有一个改变的原因。这不是严格按照DBDB的情况，但也多种拓展途径与只需要局部的变化。Refactoring as I added features was a pleasure!

Summary

DBDB 是一个实现了简单功能的数据库，但是它也可以变的很复杂。我为了管理它的复杂性，做的最重要的事情就是用不可变数据结构实现一个表面上可变的对象(implement an ostensibly mutable object with an immutable data structure.)。 我鼓励你以后遇到某些棘手问题(非常多的边际情况)的时候，考虑使用这种方法。

1. 额外的功能：您能保证压实的树结构是平衡的吗？ 这有助于保持性能。

2. 在文件描述符(file descriptor)上调用fsync请求会让操作系统和硬盘驱动器(或SSD)立即写入所有缓冲的数据。操作系统和驱动器通常为保证性能，不会立即写入所有内容。