Fork me on GitHub

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

1.前言

BoltDB是一个纯Golang实现的极简的key/value数据库。
传送门:boltdb/bolt
主库从2018年起就不再更新了。但它有2个衍生版本
hashicorp/raft-boltdbetcd-io/bbolt分别被使用在ConsulEtcd。另外其它使用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 aNode 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


微信公众号

发表回复

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据