BoltDB-MVCC的一种极简实践

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1.前言

BoltDB是一个纯Golang实现的极简的key/value数据库。
传送门:boltdb/bolt
主库从2018年起就不再更新了。但它有2个衍生版本
hashicorp/raft-boltdb和etcd-io/bbolt分别被使用在Consul和Etcd。另外其它使用BoltDB的项目

BoltDB之所以能够得到广泛的应用，最大原因是它足够轻量，核心代码只有4000多行，另外大多数关系数据库（SQLite 除外）都需要在应用程序之外独立运行服务。比如MySQL你需要启动MySQL Server，这样就增加了额外的维护成本。而BoltDB可以嵌入在应用程序之中，同生同死。

本文萌叔会把重点放在BoltDB的事务机制的实现上

2. 事务并发控制关系

在BoltDB中官方的描述是有2中类型的事务，读写事务和读事务

2.1 读写事务包含 Bucket.Put()和Bucket.Delete() 等操作

func (b *Bucket) Put(key []byte, value []byte) error

func (b *Bucket) Delete(key []byte) error

2.2 读事务包含 Bucket.Get() 等操作

func (b *Bucket) Get(key []byte) []byte 

注意: 读写事务在后面的文章中简写为写事务

2.3 写事务并发控制

2.3.1 同一个进程内部的多个协程

通过读写锁来保证某一时刻只能有一个写事务运行。

模式	可以并发	备注
读-读	是	可以并发
读-写	是	1个写事务和多个读事务可以并发
写-写	否	互斥

type DB struct {
    ...
    rwlock   sync.Mutex   // Allows only one writer at a time.
    ...
}

2.3.2 同一台设备上的多个进程

使用操作系统的文件读写锁控制并发

#include <sys/file.h>   
int flock(int fd, int operation);  

文件锁有2种类型，共享锁和排它锁。注意多个进程并发访问BoltDB，读事务和写事务也是互斥的。

LOCK_SH Place a shared lock. More than one process may hold a shared lock for a given file at a given time.
LOCK_EX Place an exclusive lock. Only one process may hold an exclusive lock for a given file at a given time.

模式	可以并发	备注
读-读	是	可以并发
读-写	否	互斥
写-写	否	互斥

根据萌叔的测试，纯粹写事务BoltDB并发写的性能不超过100/s。这主要是因为BoltDB的锁粒度太大，并发能力太弱导致的。

3. 事务的实现

建议读者先阅读参考资料1、2、3。对BoltDB的底层存储结构有了一定了解后，再来阅读本章可能会效果更好。
下图是一个BoltDB初始化之后，文件在磁盘上数据分布情况。每个小矩形代表是一个磁盘页(物理页)。

文件的头部有3个特殊的磁盘页
1）meta0 存储数据库的元数据
2）meta1 存储数据库的元数据
3）freelist 存储文件中的哪些磁盘页是闲置的，可以供下次写操作使用

细心的读者可能会问为什么会有2个meta，它们有什么区别吗？

先把这个问题放放，我们下来看看key/value数据在BoltDB中是怎么存储的

key/value数据在BoltDB中以B+树的形式存储

• 最终数据是存储在叶子节点上的
• 不同于其它的B+树实现，同一层级的sibling node之间没有指针相连
• meta指向了B+树的根节点对应的pageid(磁盘页)

type meta struct {
    root     bucket // 根节点信息
    txid     txid  // 事务ID
    ...
}

讲bucket展开

type bucket struct {
    root     pgid   // page id of the bucket's root-level page
    sequence uint64 // monotonically incrementing, used by NextSequence()
}

注意 BoltDB支持Bucket嵌套的概念，在下图中为了方便理解。暂时忽略这个细节

3.1 为什么会有meta0和meta1,2个meta结构？

meta0和meta1表示的是2棵不同的B+树，他们的部分节点可能是相同的

如上图所示，meta0表示数据库的上一个版本，meta1表示的是对数据库执行
put操作(假定put发生在Node d)之后，并commit后的结果。BoltDB使用的Copy on Write，所以对Node d的修改产生了一个新的Node d'。在BoltDB中，Node是一个或者多个连续磁盘页的的内存表示。只有当node需要被写入时，才会确定真正的pageid(磁盘页ID)，否则它只是被简单从文件读取，并展开成内存中的node结构。

当写事务提交时，首先Node a'、Node d'被写到磁盘上，Node a'不会覆盖Node a，Node d'不会覆盖Node d，而是会使用空闲的磁盘页或者申请新的磁盘页， 然后meta1会被写到磁盘文件上。写入及刷盘操作由spill()函数完成。

func (b *Bucket) spill() error 

3.2 那么如何确定哪个meta对应的是最新版本？

从下面的代码可以看出，事务ID最大且合法的meta就对应最新版本的B+树

// meta retrieves the current meta page reference.
func (db *DB) meta() *meta {
    // We have to return the meta with the highest txid which doesn't fail
    // validation. Otherwise, we can cause errors when in fact the database is
    // in a consistent state. metaA is the one with the higher txid.
    metaA := db.meta0
    metaB := db.meta1
    if db.meta1.txid > db.meta0.txid {
        metaA = db.meta1
        metaB = db.meta0
    }

    // Use higher meta page if valid. Otherwise fallback to previous, if valid.
    if err := metaA.validate(); err == nil {
        return metaA
    } else if err := metaB.validate(); err == nil {
        return metaB
    }

    // This should never be reached, because both meta1 and meta0 were validated
    // on mmap() and we do fsync() on every write.
    panic("bolt.DB.meta(): invalid meta pages")
}

MySQL事务机制依赖redo log和undo log。BoltDB则完全不同，它没有WAL。
如果commit失败，那么或者meta数据还没有被写入磁盘，或者meta写入的数据是破损的。那么后面的事务初始化时，会选中上一版本的meta。数据库自然而然的实现了回滚。

3.3 其它说明

3.3.1 只有写事务的事务ID是递增的

3.3.2 只有写事务会修改meta

修改规则是 txid % 2 。也就是说事务1的meta数据会写到meta1;事务2的meta数据会写到meta0。

// init initializes the transaction.
func (tx *Tx) init(db *DB) {
    ...
    // Increment the transaction id and add a page cache for writable transactions.
    if tx.writable {
        tx.pages = make(map[pgid]*page)
        tx.meta.txid += txid(1)
    }
}

5. 参考资料

1.Boltdb 源码导读（一）：Boltdb 数据组织
2.Boltdb 源码导读（二）：Boltdb 索引设计
3.Boltdb 源码导读（三）：Boltdb 事务实现
4.BoltDB 介绍与源代码分析（八）：MVCC 多版本并发控制
5.flock

---