可嵌入式数据库 BoltDB 实现原理 · Analyze

文章目录

BoltDB 是使用 Go 语言实现的嵌入式 K/V 数据库,其目标是为不需要完整数据库服务(如 Postgres 或 MySQL)的项目提供一个简单、快速、可靠的嵌入数据库。BoltDB 已在 e tcd、Bitcoin 等项目中作为底层数据库实现。这篇文章对 BoltDB 的设计原理进行简要分析。

BoltDB 目前已经被原作者归档,因此文中分析的是由 etcd 进行维护的版本:etcd-io/bbolt

BoltDB 主要设计思想源于 LMDB,支持 ACID 事务、无锁并发事务 MVCC,提供 B+Tree 索引。BoltDB 采用一个单独的文件作为持久化存储,利用mmap将文件映射到内存中,并将文件划分为大小相同的 Page 存储数据,使用写时复制技术将脏页写入文件。

MMAP

内存映射文件(Memory-Mapped File,mmap)技术是将一个文件映射到调用进程的虚拟内存中,通过操作相应的内存区域来访问被映射文件的内容。mmap()系统调用函数通常在需要对文件进行频繁读写时使用,用内存读写取代 I/O 读写,以获得较高的性能。

mmap@2x

传统的 UNIX 或 Linux 系统在内核中设有多个缓冲区,当我们调用read()系统调用从文件中读取数据时,内核通常先将该数据复制到一个缓冲区中,再将数据复制到进程的内存空间。

而使用mmap时,内核会在调用进程的虚拟地址空间中创建一个内存映射区,应用进程可以直接访问这段内存获取数据,节省了从内核空间拷贝数据到用户进程空间的开销。mmap并不会真的将文件的内容实时拷贝到内存中,而是在读取数据过程中,触发缺页中断,才会将文件数据复制到内存中。

现代操作系统中常用分页技术进行内存管理,将虚拟内存空间划分成大小相同的 Page,其大小通常是 4KB,在类 UNIX 系统中,我们可以使用下面的命令获取 page 的大小:

1
2
$ getconf PAGESIZE
4096

因此为了减少随机 I/O 次数,在 BoltDB 的数据文件中,也会以 4KB 大小进行划分。但在使用过程中,频繁读写数据仍会导致随机 I/O 过多影响性能。

BoltDB 中对文件的写入并没有使用mmap技术,而是直接通过Write()fdatasync()这两个系统调用将数据写入文件。

数据结构

BoltDB 的数据文件被组织为多个 Page,数据库初始化时,会预先分配 4 个 Page,第 0 页和第 1 页初始化meta页,第 2 页初始化为freelist页,第 3 页初始化为一个空的leafPage,用来写入键值对数据。关于这几种类型的 Page 会在下文介绍,我们首先分析 page 的数据结构。

Page

每一个 Page 都有一个固定大小的Header区域,用于标记这个页面的 id、页面类型等信息,由于 BoltDB 使用 B+Tree 索引,因此除了存放数据的leafPage,还会有做为数据索引的branchPage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
const (
    branchPageFlag = 0x01   // 分支节点
    leafPageFlag = 0x02     // 叶子节点
    metaPageFlag = 0x04     // meta 页
    freelistPageFlag = 0x10 // freelist 页,存放无数据的空 page id
)

type pgid uint64

type page struct {
    id pgid         // 页 id
    flags uint16    // 此页中保存的具体数据类型,即上面四个 Flag
    count uint16    // 数据计数
    overflow uint32 // 是否有后序页,如果有,overflow 表示后续页的数量
}

在旧版本的实现中会有一个额外的ptr字段指向数据存储地址,但在 Go 1.14 中无法通过指针安全性检查,因此这个字段已经去除了,详细了解可以参考 :PR#201 Fix unsafe pointer conversions caught by Go 1.14 checkptr

BoltDB 会为每个page分配一个唯一标识 id,并通过 id 查找对应的页。pageHeader之后就是具体的数据存储结构。每一个键值对用一个Element结构体表示,并利用偏移量pos进行指针运算获取键值对的存储地址:&Element + pos == &key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
type branchPageElement struct {
    pos uint32   // Element 对应 key 存储位置相对于当前 Element 的偏移量
    ksize uint32 // Element 对应 key 的大小,以 byte 为单位
    pgid pgid    // Element 指向的子节点所在 page id
}

type leafPageElement struct {
    flags uint32 // 当前 Element 是否代表一个 Bucket,如果是则其值为 1,如果不是则其值为 0;
    pos uint32   // Element 对应的键值对存储位置相对于当前 Element 的偏移量
    ksize uint32 // Element 对应 key 的大小,以 byte 为单位
    vsize uint32 // Element 对应 value 的大小,以 byte 为单位
}

上面两种不同的Element结构体用于不同类型的page中,如果是用做数据索引的branchPage,一个branchPageElement中只会存储 key 的大小字段ksize和下一级页面的pgid,用于数据索引。

leafPageElement用于存储真实的键值对数据,因此增加了vsize字段,以快速获取查询的键值对信息。flags字段的含义会在 Bucket 一节中介绍。

通过对Element的分析可以得出branchPageleafPage的内存布局如下图所示:

Page-Layout@2x

Element 和键值对分开存储减少了查找的时间,因为Element结构体的大小是固定的,我们可以在 O(1) 时间复杂度内获取所有的Element ,若是以 [Element header][key value][...] 格式存储,需要按顺序遍历查找。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func (p *page) leafPageElements() []leafPageElement {
    if p.count == 0 {
        return nil
    }
    return *(*[]leafPageElement)(unsafe.Pointer(&reflect.SliceHeader{
        Data: uintptr(unsafe.Pointer(p)) + unsafe.Sizeof(*p),
        Len:  int(p.count),
        Cap:  int(p.count),
    }))
}

Node

page是数据在磁盘文件中的布局格式,当 Page 加载到内存中要反序列化为node,以便进行数据修改操作。一个 node表示为一个 B+Tree 节点,因此需要额外的unbalancedspilled字段表明节点是否需要旋转与分裂。node中还会存储父节点与子节点的指针,用于对 key 进行范围查询。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
type node struct {
    bucket *Bucket  // 每一个 Bucket 都是一个完整的 B+ Tree
    isLeaf bool     // 区分 branch 和 leaf
    unbalanced bool // 是否平衡
    spilled    bool // 是否溢出
    key  []byte     // 该 node 的起始 key
    pgid pgid
    parent *node    // 父节点指针
    children nodes  // 子节点指针
    inodes inodes   // 存储键值对的结构体数组
}

type inode struct {
    flags uint32    // 用于 leaf node,是否代表一个 subbucket
    pgid  pgid      // 用于 branch node, 子节点的 page id
    key   []byte
    value []byte
}

type inodes []inode

page中的键值对会存在node.inodes中,并且一一对应,可以通过切片下标访问某个键值对。

序列化

BoltDB 中为了方便对数据的修改操作,需要将对应的page实例化为node,修改完成后再序列化回page写入磁盘。nodepage 的相互转换通过 node.read(p *page)node.write(p *page)这两个方法实现,以page 的反序列化过程为例,其转化过程如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func (n *node) read(p *page) {
    n.pgid = p.id
    n.isLeaf = ((p.flags & leafPageFlag) != 0)
    n.inodes = make(inodes, int(p.count))

    for i := 0; i < int(p.count); i++ {
        inode := &n.inodes[i]
        if n.isLeaf {
            elem := p.leafPageElement(uint16(i))
            inode.flags = elem.flags
            inode.key = elem.key()
            inode.value = elem.value()
        } else {
            elem := p.branchPageElement(uint16(i))
            inode.pgid = elem.pgid
            inode.key = elem.key()
        }
        _assert(len(inode.key) > 0, "read: zero-length inode key")
    }

    // Save first key so we can find the node in the parent when we spill.
    if len(n.inodes) > 0 {
        n.key = n.inodes[0].key
        _assert(len(n.key) > 0, "read: zero-length node key")
    } else {
        n.key = nil
    }
}

在向 inodes 中填充键值对时。如果是leafPageinode.flags即为元素的flags,key 和 value 分别为元素对应的 Key 和 Value;如果是branchPageinode.pgid即为子节点的页号,inode 与 page 中的Element一一对应。

Bucket

Bucket 是更为上层的数据结构,每一个 Bucket 都是一个完整的 B+Tree,将多个节点页面组织起来。

数据结构

Bucket 由Bucket结构体定义,其中包含一个由bucket定义的 Header 字段,包含根节点的页面 id 和唯一标识自增 id。Bucket 之间是相互独立的,其概念相当于 namespace。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
type Bucket struct {
    *bucket
    tx *Tx // the associated transaction
    buckets map[string]*Bucket // subbucket cache
    page *page // inline page reference
    rootNode *node // materialized node for the root page.
    nodes map[pgid]*node // node cache
    FillPercent float64
}

// In the case of inline buckets, the "root" will be 0.
type bucket struct {
    root pgid // page id of the bucket's root-level page
    sequence uint64 // monotonically incrementing, used by NextSequence()
}

Bucket 中的节点可能是已经实例化的node,也可能是序列化存储的page。当需要从 Bucket 中查找某个页面的键值对时,会先从Bucket.nodes缓冲查看是否存在相应的node(只有进行过数据修改操作的 page 才会被缓存为node),如果没有,再从page中查找。

Bucket.FillPercent字段记录着节点的填充百分比,当节点中已使用的空间超过整个 node 容量的某个百分比后,该节点必须进行分裂,以减少 B+ Tree 中插入键值对时触发再平衡操作的概率。该值的默认值是 50%,只有当大数多写入操作是在尾部添加时,增大该值才有帮助。

数据查询

为了便于数据查询,Bucket 可能持有多个迭代器,这个迭代器由Cursor定义,包含该迭代器正在遍历的 Bucket 和存储搜索路径的栈。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
type Cursor struct {
    bucket *Bucket  // 遍历的 bucket
    stack []elemRef // 记录游标的搜索路径,最后一个元素指向游标当前位置
}

type elemRef struct {
    page *page      // 当前节点的 page
    node *node      // 当前节点的 node
    index int       // page 或 node 中的下标
}

stack是一个切片,每个elemRef指向 B+ Tree 的一个节点,节点可能是已经实例化的node,也可能是未实例化的pageelemRef会存储对应结构的指针,另一个指针则为空,并记录键值对所在的位置。

进行查询时,Cursor 首先从 Bucket.root 对应的 page 开始递归查找,直到最终的叶子节点。Cursor.stack 中保存了查找对应 key 的路径,栈顶保存了 key 所在的结点和位置。除了常规的键值查询操作,Cursor 也支持查询 Bucket 的FirstLastNextPrev方法,用于相关场景的优化。

Bucket 嵌套

BoltDB 中的 Bucket 可以形成嵌套关系,根据嵌套形式的不同分为subBucketinlineBucket。在使用过程中,我们通常使用如下方式创建一个新的 Bucket 并设定一个名称:

1
2
3
4
5
6
7
db.Update(func(tx *bolt.Tx) error {
    b, err := tx.CreateBucket([]byte("NewBucket"))
    if err != nil {
        return fmt.Errorf("create bucket: %s", err)
    }
    return nil
})

subBucket本身也是一个完整的 B+Tree,其名称做为 key,一个bucket结构体做为 value,索引到子 Bucket 根节点所在的页面。BoltDB 持有一个 rootBucket,存储着数据库中所有 B+ Tree 的根节点,我们创建的每一个 Bucket 都是 rootBucketsubBucket

SubBucket@2x

从上图可以看出,父 Bucket 中只保存了subBucketbucket字段,每个 subBucket 都会占用额外的 page 存储数据,通常情况下嵌套的子 Bucket 不会拥有大量的数据,这造成了空间的浪费。BoltDB 使用inlineBucket解决这个问题,将较小的子 Bucket 的值直接存储在父 bucket 的叶子节点中,从而减少 page 的使用数量。

inlineBucket是对subBucket 的优化,我们可以通过下面这段代码推理出,其本质是在subBucket 的值后面追加一个完整的 page 结构,并以字节数组的形式写入文件。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (b *Bucket) inlineable() bool {
    var n = b.rootNode

    // Bucket must only contain a single leaf node.
    if n == nil || !n.isLeaf {
        return false
    }

    // Bucket is not inlineable if it contains subbuckets or if it goes beyond
    // our threshold for inline bucket size.
    var size = pageHeaderSize
    for _, inode := range n.inodes {
        size += leafPageElementSize + uintptr(len(inode.key)) + uintptr(len(inode.value))

        if inode.flags&bucketLeafFlag != 0 {
            return false
        } else if size > b.maxInlineBucketSize() {
            return false
        }
    }

    return true
}

为保证程序的稳定运行,BoltDB 对inlineBucket做出了一些限制要求:

  1. inlineBucket的大小不能超过 pageSize 的 1/4;
  2. inlineBucket只能含有一个叶子节点;
  3. inlineBucketbucket.root字段值为 0,用以表明结构类型。

事务

BoltDB 支持 ACID 事务,并采用了使用读写锁机制,支持多个读操作与一个写操作并发执行,让应用程序可以更简单的处理复杂操作。每个事务都有一个 txid,其中db.meta.txid 保存了最大的已提交的写事务 id。BoltDB 对写事务和读事务执行不同的 id 分配策略:

  • 读事务:txid == db.meta.txid
  • 写事务:txid == db.meta.txid + 1
  • 当写事务成功提交时,会更新了db.meta.txid为当前写事务 id.。

MVCC

BoltDB 通过meta副本机制实现多版本并发控制,meta页是事务读取数据的入口,记录了数据的版本信息与查询起点。meta的定义如下,选取了一些重要的字段:

1
2
3
4
5
6
7
type meta struct {
    root bucket     // 存储 rootBucket 所在的 page
    freelist pgid   // freelist 所在的 pgid,初始化为 2
    pgid pgid       // 已经申请的 page 数量,值为 max_pgid +1
    txid txid       // 上次写事务的 id
    checksum uint64 // 上面各字段的 64 位 FNV 哈希校验
}

数据库初始化时会将页号为 0 和 1 的两个页面设置为meta页,每个事务会获得一个txid,并选取txid % 2meta页做为该事务的读取对象,每次写数据后会交替更新meta页。当其中一个出现数据校验不一致时会使用另一个meta页。

BoltDB 的写操作都是在内存中进行,若事务未 commit 时出错,不会对数据库造成影响;若是在 commit 的过程中出错,BoltDB 写入文件的顺序也保证了不会造成影响:因为数据会写在新的 page 中不会覆盖原来的数据,且此时 meta中的信息不发生变化。

  1. 开始一份写事务时,会拷贝一份 meta数据;
  2. rootBucket 开始,遍历 B+ Tree 查找数据位置并修改;
  3. 修改操作完成后会进行事务 commit,此时会将数据写入新的 page;
  4. 最后更新meta的信息。

Freelist

BoltDB 的工作原理是分配 4KB 的 page 并将它们组织成一个B+ Tree,并根据需要在结尾处分配更多的 page。 BoltDB 在写入文件时使用了写时复制技术,当一个页面被更新时,它的内容会被复制到一个新页面,旧页面会被释放。

当经过反复的增删改查后,文件中会出现没有数据的部分。被清空数据的页可能位于任何位置,BoltDB 并不打算搬移数据、截断文件来将这部分空间返还,而是将这部分空 page,加入内部的freelist来维护,当有新的数据写入时,复用这些空间。

因此BoltDB 的持久化文件只会增大,而不会因为数据的删除而减少。

freelist是一个复杂的结构体,其中包含一些函数定义,为了便于理解,下面列出了几个重要的字段:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
type freelist struct {
    freelistType   FreelistType        // freelist type
    ids            []pgid              // all free and available free page ids.
    allocs         map[pgid]txid       // mapping of txid that allocated a pgid.
    pending        map[txid]*txPending // mapping of soon-to-be free page ids by tx.
    cache          map[pgid]bool       // fast lookup of all free and pending 
}

type txPending struct {
    ids              []pgid
    alloctx          []txid // txids allocating the ids
    lastReleaseBegin txid   // beginning txid of last matching releaseRange
}

freelistFreelistArrayTypeFreelistMapType两种类型,默认为FreelistArrayType格式,下面内容也是根据数组类型进行分析。当缓存记录为数组格式时,freelist.ids字段记录了当前空 page 的 pgid,当程序需要 page 时,会调用对应的freelist.arrayAllocate(txid txid, n int) pgid方法遍历ids,从中挑选出n 个连续的空page供调用者使用。

当某个写事务产生无用 page时,将调用freelist.free(txid txid, p *page)将指定 page 放入freelist.pending池中,并将freelist.cache中将该 page 设为 true,需要注意的是此时数据被没有被清空。当下一个写事务开启时,会调用freelist.release(txid txid)方法将没有任何事务使用的pending池中的 page 搬移到ids中。

BoltDB 这种设计思路,是为了实现多版本并发控制,加速事务的回滚,同时避免对读事务的干扰:

  1. 当写事务更新数据时,并不会直接覆盖旧数据所在的页,而且分配一个新的 page 将更新后的数据写入,然后将旧数据占用的 page 放入freelist.pending池中,并建立新的索引。当事务需要回滚时,只需要将pending池中的 page 删除,将索引回滚为原来的页面。
  2. 当发起一个读事务时,会单独复制一份meta信息,从这份独有的meta作为入口,可以读出该meta指向的数据。此时即使有写事务修改了相关 key 的数据,修改后的数据只会被写入新的 page,读事务引用的旧 page 会进入pending 池,与该读事务相关的数据并不会被修改。当该 page 相关的读事务都结束时,才会被复用修改。

Page-Freelist@2x

freelist实现了 MVCC 与空间的复用,只有当剩余空间不满足写入要求时才会进行文件映射增长,当数据文件小于 1GB 时,每次重新映射大小翻倍,当文件大于 1GB 时,每次增长 1GB,以充分利用空间。

总结

BoltDB 是一个精简的数据库实现模型,使用mmap将磁盘的 page 映射到内存的 page,实现了数据的零拷贝,利用 B+ Tree 进行索引,对理解数据库系统的相关概念很有帮助。BoltDB 的写事务实现比较巧妙,利用 meta 副本和 freelist 机制实现并发控制,提供了一种解决问题的思路。操作系统通过 COW (Copy-On-Write) 技术进行 Page 管理,通过写时复制技术,系统可实现无锁的读写并发,但是无法实现无锁的写写并发,这就注定了这类数据库读性能很高,但是随机写的性能较差,因此非常适合于『读多写少』的场景。

使用写时复制技术也产生了一定的弊端,如果长时间执行只读事务,则会导致脏页面不能被回收;如果长时间执行的读写事务,会导致其他读写事务挂起等待。在使用 BoltDB 过程中要注意尽量避免长期运行的事务。

文中并没有详细介绍 B+Tree 这一数据结构,可以自行阅读文章Concepts of B+ Tree and Extensions – B+ and B Tree index files in DBMS

Reference

相关文章