一个非常简单的支持事务的NoSQL数据库的实现

目标:

  1. 每秒10万次以上的事务。
  2. 无死锁。
  3. 实现简单。
  4. 单进程,多线程。不搞分布式。
  5. 并发冲突的粒度小,至少是行级。

一个database由很多table组成,每个table都是Map\这样的接口。上下可以分为2层,上面是事务及Cache层,下面是Storage层。

我本来打算用 Berkeley DB 1.8做Storage,但是为了实现事务,就必须保证对文件的修改是原子的,那么就必须在现在的基础上加上日志的功能。此时不必对 Berkeley DB本身的存储引擎(Btree、Hash)做修改,只需要修改它的cache层,也就是mpool的代码就可以了。这里所需要的原子性,就是把事务层的脏数据,能够原子化的刷到硬盘上。而且,这个flush的操作,是由一个专门的线程来做,所以不可能两个并行做。假设这个flush操作的最高频率是每秒一次。实现方式是采用write-ahread logging的方式,在修改数据文件之前必须先写日志文件。

日志有两种实现方式: redo logging和undo logging。(虽然我说不出哪种更好一些,但是我现在倾向于做undo logging)

1、redo: 在执行整个原子操作的过程中,不能写硬盘。在全部执行完之后,检查脏页,把脏页先写日志文件,再写数据文件。也就是说,记录的是After Image。这是我们之前的做法。优点是很容易做replication,具体实现非常类似于Mysql。每个server有一个唯一的server-id,每个server要么是master,要么是slave。Master多监听一个端口,Slave来这个端口拉Log。master先把日志吐到硬盘上,然后 slave来master这里pull。拿到 的日志先写内存,然后做redo。slave要定期做全 备份。 假设master只能有一个,slave可以有多个。master得维护slave的状态。slave得 向master报告说它做到哪了 (redo做到什么时间点了)。master要根据这个信息来 调整现有的日志清理策略。 全备份可以统统放在slave上做,master别做了。

2、undo:日志文件不再按page size切成一块一块的。flush开始时,把当前时间点写入到日志文件中(精确到毫秒)。然后开始做各种更新操作,对每个页面的读写采用COW的方式保留前像,每个页面最多一个前像(最早的那个)。当一个脏页需要从cache中丢弃时,先把它的前像追加写入到日志文件中,然后写数据文件。flush结束的时候,写入一个结束标记。每次启动的时候,先从后往前扫描日志文件,如果最末尾的一条结束标记,那么可认为这个数据库是干净的,上次是正常关闭的。如果不是,则找到上一条结束标记,并把这条结束标记之后的内容全部刷回到数据文件中。(即undo)为了减小日志文件的大小,在写前像的时候,可以先diff再写入。在执行数据读取请求的时候,如果cache达上限,那么只丢干净的页面,不丢脏页。只有执行写入请求的时候,才会丢脏页。于是,任何事务在执行的时候都不会写硬盘

Storage层可以完全不考虑多线程的问题,为了flush线程和事务执行之间并发,最简单的方式就是使用表锁。虽然可以把这个表锁拆掉,但其实没有太大好处。因为多线程的访问一个文件,会把原本顺序IO变成随机IO,效率剧降。

然后是事务层。为了彻底避免死锁,所以Berkeley DB的那种直接更新、悲观并发控制的方式,而采用MVCC这样的乐观并发。一个基本原则是:每个事务是在一个版本上原子化的执行,提交时再拿锁检查冲突。于是,执行事务本身的应用逻辑的时候,是无锁的,好处很多,不说了。单说这里具体的实现。

每个table都是Map\这样的接口,多加一个限制,V不能为null。

K必须是常量,如果要修改key,必须拆成两步:delete、insert。

V有两种实现策略:

1、V是常量。这是最容易实现的策略。每次get返回的值是一个Copy。如果要修改,只能把修改后的值put回来。

2、V是不是常量。每次get返回的是引用。对这个引用的修改,会返回到数据库中。此时有个很难的问题就是如何把Object的更改最终反映到Table上?

我现在只想清楚了V是常量怎么做。

同时,实际存的时候,Map的每个value会多一个版本号,称为write version。这个都不用自己去重新实现HashMap,只需要把现有的数据结构稍微包装一下就行了。有一个全局变量,AtomicLong globalClock,来存储时钟。这个时钟是逻辑时钟,从0开始,每成功提交一个事务,会加1。

每个事务开始的时候,tx.readVersion=globalClock.get()。每次读一个value的时候,assert(value.writeVersion\<=tx.readVersion),断言失败则abort,retry。

提交的时候,看是哪种隔离度。如果是snapshot,那么很简单,对write set上锁,然后写回更改,然后增加每个被修改的value的版本号,globalClock.inc()即可。

如果是serializable,先对write set上锁,然后tx.writeVersion=globalClock.inc(),如果tx.writeVersion > tx.readVersion +1,那么Validate read-set ( assert (obj.version \<=tx.readVersion ) && obj未被上锁 ) ,后续和上面一样,写回更改,然后增加每个被修改的value的版本号。对于只读的事务,只有globalClock.inc()和validate readset两步。

一般来说,要snapshot隔离度就足够了。如果真的出现了write skew,那么就把逻辑代码当作BUG改一下。对游戏而言,就算真的有这样的BUG,想被利用太难了。serializable最后最后策略,对于关键敏感操作,或者发现BUG了不好改的时候,直接把这个事务的隔离度设置成serializable就瞬间解决了。可作为应急方案。

然后说flush。delete的时候,只是把value设置成null。于是这个Table只需要在每次put/delete操作那里做一下记录,就可以知道哪些record是dirty了。用一个链表把脏数据的key链接起来就行了。而这个Map就用java.util.concurrent.ConcurrentSkipListMap或java.util.concurrent.ConcurrentHashMap,那个链表可采用java.util.concurrent.ConcurrentLinkedQueue,于是这些操作都是完全无锁化的。这是这个map本身也得采用上面所说的,对待value那样的方式,加一个版本号。

内存中的这个Map只是cache。每次cache不命中的时候会去Storage里面找。有一个flush线程,搜集脏数据然后刷。最简单的方式就是采用rwlock在事务及flush线程之间做互斥。

是很Simple。如果只是如此Simple,应该已经有人事先了这样的key-value DB。我是想把并发做到字段级而不是行级。所以flush如何搜集脏数据这一块还需要好好想想。得是事务commit的时候,根据每个字段往上回溯找到对应的map entry。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥