DBDB: 一个简单的key/value数据库(三)

编译自:http://www.aosabook.org/en/500L/dbdb-dog-bed-database.html 作者:Taavi Burns 翻译:鸿 如有翻译问题或建议,请公众号留言

前文点击链接:DBDB: 一个简单的key/value数据库(一) 前文点击链接:DBDB: 一个简单的key/value数据库(二)

插入和更新数据 将key值foo对应的value值bar插入到example.db中:

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

同样的进入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__方法通过_assert_not_closed方法保证DB数据库是可以使用的,并且调用_tree方法更新key/value值。_tree.set()由LogicalBase提供:

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

值得注意的是: 1.这儿的锁是由portalocker模块提供 2.如果数据库锁上了返回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)

DBDB总是返回一个包装在一个NodeRef中的新节点,所以不用通过更新节点来指向新的子树,而是创建一个共享未改变的子树的新节点。 目前所做的只是通过移动树节点来控制磁盘数据。为了这些修改写入磁盘,我们需要对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)
store()方法来源于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的子类)类

# dbdb/binary_tree.py
class BinaryNodeRef(ValueRef):
    def prepare_to_store(self, storage):
        if self._referent:
            self._referent.store_refs(storage)

_referent实际上是BinaryNode,调用的store_refs

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

这里是递归的调用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确保已经递归结束,referent_to_string进行序列化:

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

到这里所有的节点都被写入磁盘了,回到commit()方法,commit_root_address解决所有剩下的事。

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

这里保证了文件句柄被成功刷新(操作系统可以将所有数据保存到稳定的存储器中)并给出根节点的地址。由于根节点地址同时拥有旧值或新值,其他进程可以从数据库中读取而不需要获得锁。外部进程可能会看到不同状态的二叉树树,但并不会混淆这两种树。所以commit具有原子性的。由于我们在写入根节点地址之前就将新数据写入磁盘并调用了fsync syscall2,因此未commit的数据是无法访问的。相反,一旦根节点地址被更新,它引用的所有数据也在磁盘上。所以,commit也具有持久性。NodeRefs如何存储数据:这是为了避免整个二叉树结构同一时间都保存在内存当中,当从磁盘读入逻辑节点时,其左右子节点的磁盘地址(及其值)也会被加载到内存中。一个NodeRef就是一个地址:

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

调用get()方法会不断遍历地址:

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

当对二叉树的更新没有commit时,它们会保存在内存中。 这些更新不会保存到磁盘中,因此更新的节点会包含具体的key和value,但是没有磁盘地址。在执行写入的过程可以看到没有commit的更新,并且在确认commit之前可以继续更新,因为NodeRef.get()会返回未commit的值(如果有的话);在通过API访问时,commit数据与未commit数据之间是没有区别的。 所有更新都是原子性的。并发更新则会被磁盘上的锁阻塞。锁是在第一次更新时获取并在commit后释放。

原文发布于微信公众号 - 鸿的学习笔记(shujuxuexizhilu)

原文发表时间:2018-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏维C果糖

史上最简单的 MySQL 教程(三十六)「数据备份与还原(中)」

数据备份与还原的方式有很多种,具体可以分为:数据表备份、单表数据备份、SQL备份和增量备份。

414110
来自专栏人工智能LeadAI

mongoDB的安装及基本使用

mongoDB简介 1、NoSQL数据库 数据库:进行高效的、有规则的进行数据持久化存储的软件 NoSQL数据库:Not only sql,指代非关系型数据库...

31080
来自专栏Albert陈凯

2018-05-03 Java高级面试题及答案各自的子类比较对比一:

20950
来自专栏chenssy

【死磕Sharding-jdbc】---基于 SSM 集成sharding-jdbc2.0.3

本篇文章讲解如何在ssm(spring、springmvc、mybatis)结构的程序上集成sharding-jdbc(版本为2.0.3)进行分库分表; 假设分...

10710
来自专栏黑泽君的专栏

c语言_文件操作_FILE结构体解释_涉及对操作系统文件FCB操作的解释_

  C将每个文件简单地作为顺序字节流(如下图)。每个文件用文件结束符结束,或者在特定字节数的地方结束,这个特定的字节数可以存储在系统维护的管理数据结构中。当打开...

15710
来自专栏抠抠空间

Django之ORM基础

ORM简介 ORM概念 对象关系映射(Object Relational Mapping,简称ORM)模式是一种为了解决面向对象与关系数据库存在的互不匹配的现象...

35570
来自专栏Golang语言社区

Golang语言--【基础知识】访问数据库

对许多Web应用程序而言,数据库都是其核心所在. 数据库几乎可以用来存储你想查询和修改的任何信息,比如用户信息、产品目录或者新闻列表等。 Go没有内置的驱动支持...

45360
来自专栏决胜机器学习

ModernPHP读书笔记(三)——PHP的良好实践

ModernPHP读书笔记(三)——PHP的良好实践 (原创内容,转载请注明来源,谢谢) 一、密码 1、密码不宜用明文存储,也不能用可以解密的...

32160
来自专栏用户2442861的专栏

游标--数据库

http://blog.csdn.net/liujiahan629629/article/details/18014051

20130
来自专栏JavaEdge

操作系统之文件管理

将文件属性从外存拷到内存中打开文件表的一表目中 将其编号返回给用户。 系统可利用该编号到打开文件表中去查找。

385100

扫码关注云+社区

领取腾讯云代金券