1.实验简介

1.1 实验来源

本课程核心部分来自《500 lines or less》项目，作者是来自 Countermeasure 的合唱歌手 Taavi Burns，也曾在 IBM 以及多家创业公司任职 。项目代码使用 MIT 协议，项目文档使用http://creativecommons.org/licenses/by/3.0/legalcode协议。

课程截取了原文档的部分内容，以讲解代码与原理为主。

1.2 内容简介

本课程将通过理解一个操作类似于 Redis ，存储理念来自于 CouchDB 的键值数据库的源代码来学习如何做数据库的数据存储，体会使用不可变数据结构的优点。

1.3 实验知识点

本课程项目完成过程中，我们将学习：

1. 二叉树数据的持久化存储与读取
2. 分层对数据库进行设计
3. 使用Python的内置方法将数据结构的操作封装为键值操作

1.4 版本

• Xfce终端
• python3.5
• portalocker-1.2.1
• nose-1.3.7

2.实验环境

打开Xfce终端，进入/home/shiyanlou/Code目录，直接通过wget获取 DBDB 的源代码，同时为了避免本地环境的影响，我们在虚拟环境中操作本次实验：

$ cd /home/shiyanlou/Code
$ sudo pip3 install virtualenv
$ virtualenv --python=python3.5 env
$ source env/bin/activate
$ wget http://labfile.oss.aliyuncs.com/courses/614/dbdb-code.zip
$ unzip dbdb-code.zip
$ cd dbdb-code
$ pip3 install -r requirements.txt
$ cd ../
$ sudo env/bin/easy_install-3.5 dbdb-code #安装 DBDB

3.相关简介

键值数据库属于 NoSQL 数据库，Redis 是其中的典型代表。本课程所讲解的数据库，其存储数据的核心理念参照 CouchDB （沙发DB），大概也是出于这个原因，所以它叫狗床DB（Dog Bed Database），可能没沙发那么舒适，但也足够温暖。

狗床DB 针对电脑死机、崩溃、异常等状况下数据没有保存而造成的数据丢失，它同时也避免了在内存中存储过多数据，使得你的程序能够使用超出内存大小的数据。

之后皆以 DBDB 来简称狗床DB。

DBDB的诞生背景

Taavi Burns：还记得第一次写程序卡在一个 BUG 上时的情景，那时我正运行自己刚写好的 BASIC 程序，不知道为什么屏幕上有些像素点一闪一闪的，然后程序就中止了。我回过头来查看自己的代码，发现代码最后几行竟然消失了。

正巧我妈妈的一个朋友会编程，交流了一下后就找到问题出在哪了。程序太大以至于占了显存。一旦屏幕清空，我的程序就直接被截断了。

自此之后，我就非常注意内存分配的问题了，我学习了关于指针的知识，知道了如何使用 malloc 分配内存，还学习了数据结构是如何存储在内存上的，你必须非常小心地应对这些内存上的数据，一旦修改了不该修改的地方，你的程序会崩溃而且可能需要花很长时间来调 BUG 。

一些年过去了，我遇到了一门面向并发程序设计的语言 Erlang，原来进程间通信并不一定要复制数据，所有的数据结构都是不可变的。之后我又学习了 Clojure 中的不可变数据结构，渐渐沉迷于此道。

2013 年的时候我阅读了 CouchDB 的源代码，他的设计理念，对于复杂数据的管理机制都让我由衷的认同和欣赏。我认识到使用不可变的数据结构设计系统会是一个不错的主意，所以就有了 DBDB 和这篇文档（500L 上的原文档）。

当我实现可变的二叉树时遇到了不少麻烦，当你对数据的一部分做出改变时你不知道它会不会影响到其它部分，需要考虑的边界情况很多，但是更可怕的是有些情况你自己也想不到，简直是一团乱。但是当我改用不可变的数据结构后，麻烦几乎都消失了，程序不那么容易出 BUG 了。我再一次认识到使用不可变的数据结构会使开发和维护程序更加容易。

4.体验DBDB

DBDB 既可在代码中使用，也可在命令行中使用，这里介绍一下命令行下的使用方法。

用法如下：

python -m dbdb.tool DBNAME get KEY          
#获得键值
python -m dbdb.tool DBNAME set KEY VALUE    
#设置键值
python -m dbdb.tool DBNAME delete KEY       
#删除键值

使用效果：

$ python -m dbdb.tool example.db set foo 12345
$ python -m dbdb.tool example.db get foo
$ python -m dbdb.tool example.db get bar
$ python -m dbdb.tool example.db delete foo
$ python -m dbdb.tool example.db get foo

5.代码讲解

不同于之前的课程是一步一步实现的，本课程主要通过讲解源代码来达到学习的目的，这里给出源代码地址方便阅读：DBDB github 地址。

文件底层

这里列出的文件越靠后越接近底层。

• tool.py是数据库的命令行工具，我们可以通过命令行（即终端）对数据库进行操作。
• interface.py定义了DBDB类，它对底层的二叉树结构进行封装，开放词典接口以供键值操作。
• logical.py定义了逻辑层，它是键值操作的抽象接口。
  • LogicalBase类提供了逻辑更新（比如 get，set 以及 commit）的抽象接口，它同时负责管理存储对象的锁以及对内部节点的解引用。
  • ValueRef是指向数据库中二进制数据对象的Python对象，是对数据库中数据的引用。
• binary_tree.py定义了逻辑接口下具体的的二叉树算法。
  • BinaryTree实现二叉树及其基本操作。值得注意的是，我们实现的是一个数据不可变的二叉树，每次数据更新都会返回一棵新树，新树的大部分数据由于同旧树一致所以直接与旧树共享那部分数据。
  • BinaryNode实现二叉树中的节点。
  • BinaryNodeRef是ValueRef的子类，实现对二叉树节点的引用。
• physical.py定义物理层。
  • Storage类提供持久化的记录存储（也就是写到硬盘上）。

DBDB接口

用户在程序中使用 DBDB 数据库时只需了解它对外开放的接口即可，接口在interface.py中定义，主要包括读取、创建、删除、提交等基本操作。

使用数据库前需要先连接数据库。类似于 sqlite ，这里的数据库实质上就是一个存储数据的文件，连接操作如下：

import dbdb
db = dbdb.connect(dbname)

connect连接函数的实现如下：

# __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)

r+b说明该文件可读可追加新数据但是不允许覆盖已有的数据。记住我们的设计基于不可变的数据结构，不可变使得对数据的操作更加安全。
在DBDB类中实现__getitem__、__setitem__、__delitem__、__contains__等函数，就能像操作词典一样操作DBDB对象了。

class DBDB(object):
    ...
    def __getitem__(self, key):
        # 通过 db[key] 获取键值
        ...
    def __setitem__(self, key, value):
        # 通过 db[key] = value 设置键值
        ...
    def __delitem__(self, key):
        # 通过 del db[key] 删除键值
        ...
    def __contains__(self, key):
        #通过 key in db 来判断键在不在数据库中
        ...

DBDB有两个成员变量：_storage与_tree，_storage封装了数据库文件和对数据库文件的基本操作，_tree是二叉树数据结构对象，DBDB接口的实现主要是将二叉树的操作封装为Python词典的键值操作。
_storage在DBDB中只完成一个功能：检查文件有没有关闭。

def _assert_not_closed(self):
    if self._storage.closed:
        raise ValueError('Database closed.')

像其它数据库一样，在对数据进行操作后，只有提交了数据才算真正地更新到了数据库中。

    def commit(self):
        self._assert_not_closed()
        self._tree.commit()

物理层

物理层在physical.py中实现，它是对数据库文件操作的封装。数据库的文件结构如下

可以看到文件开头的部分划给了超级块，超级块是取自文件系统的术语，在这里由它保存整个数据库文件的一些基本信息，一般超级块的长度会设置为 1024 B 的整数倍，我们指定它为 4096 B。

class Storage(object):
    SUPERBLOCK_SIZE = 4096

由于采用二叉树结构，通过根节点就能遍历所有数据，所以只需要在开头记录根节点的地址就足够了。
新建的文件长度为零，这就需要我们调用_ensure_superblock来为超级块留出位置了。

def _ensure_superblock(self):
    # 文件上锁，防止其它进程写文件
    self.lock()
    # 到达文件末尾
    self._seek_end()
    # 得到文件读取的位置（这里同时也是文件大小）
    end_address = self._f.tell()
    # 如果文件大小小于超级块大小那么必须为超级块分配足够的空间
    if end_address < self.SUPERBLOCK_SIZE:
        # 写入一串二进制零
        self._f.write(b'\x00' * (self.SUPERBLOCK_SIZE - end_address))
    # 文件解锁
    self.unlock()

获取与更新根节点地址方法：

def get_root_address(self):
    # 定位到超级块的地址（也就是文件开头）
    self._seek_superblock()
    # 获取根节点地址
    root_address = self._read_integer()
    return root_address
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()

每一个数据块的开头会记录这段数据的大小，随后记录数据块的内容。因此写的时候会先写大小，随后写数据，同样读的时候会先读数据大小，接着读取相应大小的数据。

def write(self, data):
    self.lock()
    self._seek_end()
    object_address = self._f.tell()
    # 写数据大小
    self._write_integer(len(data))
    # 写数据
    self._f.write(data)
    # 返回数据块的地址
    return object_address
def read(self, address):
    self._f.seek(address)
    # 得到数据大小
    length = self._read_integer()
    # 读取数据
    data = self._f.read(length)
    # 返回数据
    return data

因为 Python 的整数类型不是固定长的，所以我们需要用到struct模块先将 Python 整数打包成 8 个字节，再写入到文件中去，关于struct的使用可以参考下面这篇博客或者官方文档：

• Python 中 struct 模块的用法
• struct — Interpret strings as packed binary data

Python 整数与二进制字节的转换实现如下：

# "Q" 表示无符号长整形，"!" 表示网络流的字节序，也就是大端字节序
INTEGER_FORMAT = "!Q"
INTEGER_LENGTH = 8
# 字节转换整数
def _bytes_to_integer(self, integer_bytes):
    return struct.unpack(self.INTEGER_FORMAT, integer_bytes)[0]
# 整数转换字节
def _integer_to_bytes(self, integer):
    return struct.pack(self.INTEGER_FORMAT, integer)

逻辑层

逻辑层接口在logical.py中实现，包括ValueRef与LogicalBase这两个类。回顾一下之前讲文件组成时提及的内容：

• LogicalBase类提供了逻辑更新（比如 get，set 以及 commit）的抽象接口，它同时负责管理存储对象的锁以及对内部节点的解引用。
• ValueRef是指向数据库中二进制数据对象的Python对象，是对数据库中数据的引用。

这里先来说说ValueRef是个什么东西，从它的名字应该能猜出它的功能是引用某个值。其实引用的就是“键值”中的“值”，它有两个成员变量_referent与_address：

def __init__(self, referent=None, address=0):
    self._referent = referent
    self._address = address

其中_referent就是它引用的值，而_address就是该值在文件中的位置。
_referent没必要随时出现在我们的内存中，只要它已经被保存了，我们就可以通过_address来获得它：

def get(self, storage):
    if self._referent is None and self._address:
        #将从文件中读取的字节串转换为Python中引用的对象
        self._referent = self.string_to_referent(storage.read(self._address))
    return self._referent

string_to_referent的实现：

@staticmethod
def string_to_referent(string):
    return string.decode('utf-8')

可以看到值的处理很简单，只要将utf-8格式的字节串解码就可以了。
但是数据库会用到的引用类其实有两个ValueRef与BinaryNodeRef：

class LogicalBase(object):
    # 对数据结构节点的引用，会在子类中赋值 BinaryNodeRef
    node_ref_class = None
    # 对值的引用
    value_ref_class = ValueRef

BinaryNodeRef会继承ValueRef并实现自己的string_to_referent方法。这会在之后再讨论。
store实现对引用对象的存储：

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的实现。
LogicalBase的对外开放的几个接口实现如下：

# 获取键值
def get(self, key):
    # 如果数据库文件没有上锁，则更新对树的引用
    if not self._storage.locked:
        self._refresh_tree_ref()
        # _get 方法将在子类中实现
    return self._get(self._follow(self._tree_ref), key)
# 设置键值
def set(self, key, value):
    if self._storage.lock():
        self._refresh_tree_ref()
    # _insert 方法将在子类中实现
    self._tree_ref = self._insert(
        self._follow(self._tree_ref), key, self.value_ref_class(value))
# 删除键值
def pop(self, key):
    if self._storage.lock():
        self._refresh_tree_ref()
    # _delete 方法将在子类中实现
    self._tree_ref = self._delete(
        self._follow(self._tree_ref), key)
# 提交数据
def commit(self):
    # 存储引用的树
    self._tree_ref.store(self._storage)
    # 更新树的根节点的地址
    self._storage.commit_root_address(self._tree_ref.address)

_follow的作用就是获取Ref所引用的具体对象。self._follow(self._tree_ref)就是获取二叉树的根节点。
_refresh_tree_ref会通过读取文件中的根节点地址来刷新树的根节点。新创建的文件是一串二进制零，那么最初得到的根地址也就是0了，C语言中全为零的指针就是空指针，在这里我们也可以理解成地址为0的引用是个空引用。

def _refresh_tree_ref(self):
    self._tree_ref = self.node_ref_class(
        address=self._storage.get_root_address())

对空引用调用get函数将返回None：

def get(self, storage):
    #_address为0则会直接返回_referent，而_referent为None
    if self._referent is None and self._address:
        self._referent = self.string_to_referent(storage.read(self._address))
    return self._referent

二叉树的实现

实现DBDB所使用的二叉树是最普通的那种，就是你在数据结构教材中第一次遇到的那棵二叉树，这里就不做介绍了。二叉树结构的实现在binary_tree.py文件中。

回顾一下文件组成：

• BinaryTree实现二叉树及其基本操作。值得注意的是，我们实现的是一个数据不可变的二叉树，每次数据更新都会返回一棵新树，新树的大部分数据由于同旧树一致所以直接与旧树共享那部分数据。
• BinaryNode实现二叉树中的节点。
• BinaryNodeRef是ValueRef的子类，实现对二叉树节点的引用。

一个BinaryNode由对左右节点的引用，键，对值的引用，以及长度组成，这里的长度是指该节点及其子节点组成的子树的节点数，在代码中这个值似乎没起到任何作用。如果有同学知道这个值的意义的话欢迎在课程下评论。

class BinaryNode(object):
    ...
    def __init__(self, left_ref, key, value_ref, right_ref, length):
        self.left_ref = left_ref
        self.key = key
        self.value_ref = value_ref
        self.right_ref = right_ref
        self.length = length

对节点进行存储（就是存储它的引用关系）：

    def store_refs(self, storage):
        self.value_ref.store(storage)
        self.left_ref.store(storage)
        self.right_ref.store(storage)

可以看出先序遍历的影子，这一步是整个递归遍历存储数据的一环。
BinaryNode还有一个工厂方法from_node，该函数会根据读入的节点与更新节点的参数生成一个新节点并返回（记住数据结构不可变）。

接着来介绍BinaryNodeRef，它继承自ValueRef并重写了prepare_to_store、referent_to_string与string_to_referent方法。

prepare_to_store是你在存储引用的对象前的勾子函数，在处理值的时候我们并不需要做预处理，但是在处理节点的时候这一步就有必要了。

def prepare_to_store(self, storage):
    if self._referent:
        self._referent.store_refs(storage)

没错，就是之前的store_refs。

    def store_refs(self, storage):
        self.value_ref.store(storage)
        self.left_ref.store(storage)
        self.right_ref.store(storage)

在存储BinaryNodeRef的时候会触发先序遍历，直到访问ValueRef（相当于叶子节点）时递归才会停止。
referent_to_string将引用对象转换为字节串：

return pickle.dumps({
    'left': referent.left_ref.address,
    'key': referent.key,
    'value': referent.value_ref.address,
    'right': referent.right_ref.address,
    'length': referent.length,
    })

在预处理时已经存储了左右节点与值的引用，存储的同时已得到了这三者的地址，现在我们只需要将描述节点之间关系的BinaryNode存入文件即可。
BinaryTree继承自LogicalBase，二叉树的所有操作在这个类中实现。

_get实现的逻辑很简单，因此这里我们只讲解_insert和_delete的实现。

_insert的代码实现：

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)
    # 返回对节点的引用，address为None说明该新节点还未被存储。
    return self.node_ref_class(referent=new_node)

新节点的生成可以看作是自下而上的”感染”，新插入的节点的父节点势必要更新它对子节点的引用，因此父节点也需要被克隆生成新节点。
可能有同学会对不可变的二叉树究竟是如何被存储到文件中而感到疑惑，下面用一张示例图予以说明。

可见这个实现方式会占用很多空间。本课程是对不可变数据结构存储的简单演示，在实际生产中会有更好的解决方案。

_delete的代码实现：

def _delete(self, node, key):
    if node is None:
        raise KeyError
    # 这一部分与 _insert 同理
    elif key < node.key:
        new_node = BinaryNode.from_node(
            node,
            left_ref=self._delete(
                self._follow(node.left_ref), key))
        elif node.key < key:
        new_node = BinaryNode.from_node(
            node,
            right_ref=self._delete(
                self._follow(node.right_ref), key))
    # 删除操作
    else:
        left = self._follow(node.left_ref)
        right = self._follow(node.right_ref)
        if left and right:
            # 使用左子树的最大节点作为新的节点，同时删除左子树中的最大节点
            replacement = self._find_max(left)
            left_ref = self._delete(
                self._follow(node.left_ref), replacement.key)
            new_node = BinaryNode(
                left_ref,
                replacement.key,
                replacement.value_ref,
                node.right_ref,
                left_ref.length + node.right_ref.length + 1,
            )
        如果存在左子节点则直接返回对左子节点的引用
        elif left:
            return node.left_ref
        else:
            return node.right_ref
    return self.node_ref_class(referent=new_node)

6.总结

DBDB 选择将可变的数据以不可变的数据结构的形式保存下来，使得管理复杂的数据变为可能且易于上手，也许当你有一天面对着棘手的代码会想起不可变数据的优点，或许问题就会引刃而解了呢。本课程的主要内容与原文档有较大差异，有些点限于篇幅就略去了，所以推荐阅读原文档，地址就在下面参考资料中。

7.参考资料

• DBDB: Dog Bed Database
• DBDB: Dog Bed Database 源代码
• Python 中 struct 模块的用法
• struct — Interpret strings as packed binary data