简介

Memory

I remember the first time I was really stuck on a bug. When I finished typing in my BASIC program and ran it, weird sparkly pixels （奇怪的闪闪发光的像素）showed up on the screen, and the program aborted（中止） early. When I went back to look at the code, the last few lines of the program were gone.
One of my mom’s friends knew how to program, so we set up a call. Within a few minutes of speaking with her, I found the problem: the program was too big, and had encroached onto（侵犯到） video memory（显存）. Clearing the screen truncated the program, and the sparkles were artifacts of Applesoft BASIC’s behaviour of storing program state in RAM just beyond the end of the program.
From that moment onwards, I cared about memory allocation（分配）. I learned about pointers and how to allocate memory with malloc. I learned how my data structures were laid out（布局） in memory. And I learned to be very, very careful about how I changed them.
Some years later, while reading about a process-oriented（面向进程） language called Erlang, I learned that it didn’t actually have to copy data to send messages between processes, because everything was immutable（一成不变）. I then discovered immutable data structures in Clojure, and it really began to sink in.
When I read about CouchDB in 2013, I just smiled and nodded, recognising the structures and mechanisms for managing complex data as it changes.
I learned that you can design systems built around immutable data.
Then I agreed to write a book chapter.
I thought that describing the core data storage concepts of CouchDB (as I understood them) would be fun.
While trying to write a binary tree algorithm that mutated the tree in place, I got frustrated with how complicated things were getting. The number of edge cases and trying to reason about how changes in one part of the tree affected others was making my head hurt. I had no idea how I was going to explain all of this.
Remembering lessons learned, I took a peek at a recursive（递归） algorithm for updating immutable binary trees and it turned out to be relatively straightforward.
I learned, once again, that it’s easier to reason about things that don’t change.
So starts the story.

Why Is it Interesting?

Most projects require a database of some kind. You really shouldn’t write your own; there are many edge cases that will bite you, even if you’re just writing JSON to disk:
What happens if your filesystem runs out of space?
What happens if your laptop battery dies while saving?
What if your data size exceeds（超过） available memory? (Unlikely for most applications on modern desktop computers… but not unlikely for a mobile device or server-side web application.)
However, if you want to understand how a database handles all of these problems, writing one for yourself can be a good idea.
The techniques and concepts we discuss here should be applicable to any problem that needs to have rational（合理的）, predictable behaviour when faced with failure.
Speaking of failure…

检定失败

数据库一般通过他们坚持ACID性能来表现他们的特征：atomicity（原子性）, consistency（一致性）, isolation（隔离性）, and durability（持久性）
DBDB的更新是原子的并且是可持久的。DBDB不提供一致性保证，因为数据存储没有限制，隔离性也没有实现。
应用层代码可以加上他自己的一致性保证，但是合适的隔离需要有一个事务管理器。
另外，我们还有其他的系统维护问题需要考虑。在本设计中，陈旧的数据没有回收，所以重复的更新最终会完全消耗掉磁盘空间。(You will shortly discover why this is the case.)PostgreSQL calls this reclamation “vacuuming” (which makes old row space available for re-use), and CouchDB calls it “compaction” (by rewriting the “live” parts of the data store into a new file, and atomically moving it over the old one).
DBDB could be enhanced to add a compaction feature（压缩功能）, but it is left as an exercise for the reader1.

DBDB结构

Discovering the Design

组织单元

tool.py：命令行工具，从终端窗口来操作数据库

interface.py：使用二叉树实现方式定义了DBDB类->实现Python的字典接口。因此才能在Python程序中使用DBDB

logical.py：逻辑层，键值存储的抽象接口

LogicalBase：逻辑层更新的接口（get、set、commit） ValueRef：指向存储在数据库中的二进制数据的Python类（间接引用->避免一次性全将数据存到内存中） 

binary_tree.py：逻辑接口之下的实体二叉树算法

讯享网BinaryTree：实现二叉树（get、insert、delete、key/value对），一成不变的 -- > 更新 -->返回一新的树。 BinaryNode：二叉树的一个点 BinaryNodeRef：实例化的ValueRef，可以 serialise and deserialise（连载和丢弃）一二叉树节点（BinaryNode） 

physical.py：实体层，Storage类提供持久性（大多是只可加的）

读取值

$ python -m dbdb.tool example.db get foo

运行dbdb.tool.py中的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

（1）

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)

（2）

一旦有了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实例的直接引用：这样他才能执行先决条件判断。

（3）

DBDB之后通过调用_tree.get()函数查找_tree中跟键key关联的值，_tree.get()由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()首先检查我们该存储是否被锁着。

• 【3.1】

如果该存储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’，这样我们可以实现一个完全更新过的读取。

• 【3.2】

如果storage被锁着，说明有其他进程可能正在改变我们正想去读的这个数据；我们读到的可能就不是最新的数据。这个叫做“dirty read”。这样的模式允许读者读取数据时可以不用担心阻塞问题，代价就是数据不是最新的。

讯享网

（4）

现在，我们看看如何真正读到该数据的：

讯享网# 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

插入和更新

设置键foo的值为bar in example.db:

$ 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: ...

（1）

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__确保数据库仍然处于打开状态。

（2）

通过调用_tree.set()存储key、value关系到_tree中：

讯享网# 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))

# 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 

【2.2】
回到_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中）。我们建立一个新的节点，该节点共享未改变的子树部分，而不是更新该节点到一个新的子树。这样，我们的二叉树是一个永久不变的数据结构。

（3）

你可能已经注意到了奇怪的地方：我们没有在磁盘上做任何的改变，我们之前做的是通过来回移动树节点来操纵我们看磁盘上的数据的视角。
为了真正的在磁盘上写入这些改变值，我们需要明确地调用commit()，，tool.py中set操作的第二部分：
提交包括将内存中的dirty stat写出，保存树的新的根节点的磁盘地址。
由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)

讯享网# 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))

【3.2】
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)

【3.3】

讯享网# 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的。

# 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对于他自己的refs都有可用的地址，所以我们通过创建一个字节串来代表这个节点，实现连载它：

讯享网# 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, })

（4）

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

NodeRefs如何保存到内存中的

为了避免一下把整个树结构放到内存中，当读磁盘上的一个逻辑节点时，他的左和右子叶的磁盘地址也被加载到了内存中。为了得到子叶和他们的值需要另一个额外的函数：NodeRef.get()来从新引用这个数据。
NodeRef结构：

讯享网+---------+ | NodeRef | | ------- | | addr=3 | | get() | +---------+

调用get()会返回具体的节点，同时还有节点的引用：

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