boltdb 源码阅读

前言

最近抽时间看了boltdb的源码，代码量不大（大概 4000 行左右），而且支持事务，结构也很清晰，由于比较稳定，已经归档，确实是学习数据库的最佳选择。而且不少出名的开源项目在使用它，比如 etcd，InfluxDB 等。

本文记录下笔者在阅读源码后了解到的其工作原理，以留备忘。

简介

boltdb 数据库是一款 go 开发的 k/v 数据库。其设计源于 LMDB（Lightning Memory-Mapped Database），持久化到单文件中,通过 mmap 将文件映射到内存，这样读文件可以减少一次 IO,但是写文件并不是通过 mmap，而是通过调用写函数进行 seek+write，后面会具体讲。

通过 B+树进行索引。

按块写入，块的大小根据操作系统获得，大部分操作系统都是 4k.

支持事务：多个读事务可以并发执行，但是写事务是串行的。

工作流程

一段简单使用代码如下：

path := "./bolt.db"    db, err := bolt.Open(path, 0666, nil)    if err != nil {        fmt.Println("open db failed:", path, err)        return    }    defer db.Close()
    tx, err := db.Begin(true)    if err != nil {        fmt.Println("begin trans failed:", err)        return    }    defer tx.Rollback()
    bucket, err := tx.CreateBucketIfNotExists([]byte("nums"))    if err != nil {        fmt.Println("create bucket failed")        return    }    kv := []byte("128")
    bucket.Put(kv, kv)
    val := bucket.Get(kv)    fmt.Println(val)
    tx.Commit()

可以看出其工作流程为：

1.打开数据库文件 2.开始一个事务 3.创建一个 bucket（一系列的 k/v 集合，可嵌套） 4.在 bucket 中放入一个 k/v 数据 5.关闭事务

每一系列的操作都是一次事务操作，要么是只读事务，要么是读写事务。 每次对数据的增删改查操作都是基于 bucket 进行。

数据结构

boltdb 所有的修改操作都是在内存中完成，最终提交事务后进行落盘操作。

所以其存储的数据存在内存和文件两种数据结构，通过 unsafe 函数将 byte array 转换为对应的结构体

内存相关

node

代表内存中一个树节点

type node struct {    bucket     *Bucket      isLeaf     bool     // 用来区分树枝和叶子节点    unbalanced bool    spilled    bool    key        []byte   // 该节点中的最小的key    pgid       pgid    parent     *node    children   nodes    inodes     inodes   // node中真正存数据的地方}

inode

inodes 中保存 k/v 数据.树枝和叶子节点公用这个数据结构。

type inode struct {    flags uint32    // 仅叶子节点使用。存放数据内容标识,为bucket或普通数据中的一种    pgid  pgid      // 仅树枝节点使用。存放子节点的page id    key   []byte    // 树枝节点和叶子节点公用。key    value []byte    // 仅叶子节点使用。存放普通数据或bucket}

文件相关

page

type page struct {    id       pgid       // pageid    flags    uint16     // 这块内容标识：可以为元数据、空闲列表、树枝、叶子 这四种中的一种    count    uint16     // 存储数据的数量    overflow uint32     // 溢出的数量(一页放不下，需要多页)    ptr      uintptr    // 真正存储数据的指向（仅内存中的标识，并不落盘）}

每个 page.ptr 指向的数据结构在落盘后其前面都会存 page，我们称为 PageHeader,下文用 PH 表示

其在文件中如下所示：

page.ptr 指向的数据结构

元数据(metadata)

元数据存两份，pageid 为 0 和 1，pageid 是固定的，以后也不会改变。 meta 的作用：

1.保存数据库基本信息，如根节点，版本号，空闲列表等 2.其中一个元数据出了问题，可以使用另外一份进行修复来保证数据库可用 3.保证一致性：每次读写事务前，都会选取 txid 最大的那个 meta 进行事务初始化，同时做 MVCC 时，也会拷贝最新的 meta。

type meta struct {    magic    uint32     // 标识db文件为boltdb产生的    version  uint32     // 版本号    pageSize uint32     // 页大小，根据系统获得，一般为4k    flags    uint32     // 表示为metadata    root     bucket     // 内含根节点的pageid，起始时从3开始    freelist pgid       // 空闲列表pageid，起始时从2开始    pgid     pgid       // 下一个要分配的pageid    txid     txid       // 下一个要分配的事务id    checksum uint64     // 检查meta完整性时使用}

空闲列表(freelist)

boltdb 中使用了 MVCC 多版本，增删改的数据都会新分配 page 存放，以前的 page 中的数据并不会被删除，待事务版本升高，旧数据持有的 page 便可以释放用来重新进行分配给新的写事务存放数据。而控制哪些 page 空闲，哪些 page 将要空闲，就是由 freelist 这个数据结构控制。

而我们也可以看到，boltdb 的数据库文件并不会因为删除数据而减小。空闲空间是由 freelist 来重复利用。

freelist 数据结构：

// freelist represents a list of all pages that are available for allocation.// It also tracks pages that have been freed but are still in use by open transactions.type freelist struct {    ids     []pgid          // all free and available free page ids.    pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.    cache   map[pgid]bool   // fast lookup of all free and pending page ids.}

落盘时只存储 ids 字段，会把 pending 和 ids 合并后存储。所以 page.ptr 指向的是 ids 列表。如果 ids 数量超过 0xFFFF（page.count 的最大值），则会把 ptr 指向的第一个位置作为 ids 的长度。

pending 是还未被释放的空闲页面 id，而 ids 为已经可以使用的空闲 page id，为什么 pending 可以和 ids 合并存储呢？

在说原因前先说明下下面背景：

1.首先要明确的是，freelist 被整个 db 持有（所有的写事务共享），只有写事务才能修改它，所有它不需要加锁（为什么？前文说过，写事务是串行执行，不是并发执行）。 2.每个事务都有一个版本号：读事务 txid = db.meta.txid，写事务 txid = db.meta.txid + 1 3.每个事务都会拷贝一份 metadata 数据，该数据持有基本信息。

原因如下：

1.只有写事务在提交事务时，其在事务期间受到操作的数据才需要重新分配新的 page 来存储，而他们原本所在的 page 会被 pending，在事务完成期间并不会被释放到 ids 里（为什么？因为有读事务在，一个读事务如果执行时间较长，该写事务此时释放到 ids 里，就会被随后的写事务拿去写入新数据，该读事务还在进行中，就导致了脏读出现）。 2.对于该写事务成功提交后，此时 freelist 会写入一个新 page。这个新 page 上保存了该事务的 ids+pending。此时，对于读事务来说，有两种情况： 1.某个读事务还未执行完（该读事务可能在这个写事务之前开始，也可能在这个写事务还未提交时开始） 2.这个写事务成功后新创建了一个读事务 3.对于上面情况一来说，此时 db.freelist 中 pending 仍然存在，所以这个读事务进行过程中，数据一直存在，所以并不会被覆盖，保证了事务的隔离。 4.对于情况二来说，写事务成功后了 metadata 中 freelist 的新 pageid，新开始的读事务可直接读取到较新的数据。这正是多版本控制。 5.新的写事务开始时会找到最小的事务 txid，然后把小于这个 txid 的 freelist.pending 中的 pageid 都放入 freelist.ids 中（说明没有读事务在用这些 pending 状态的 page 了，可以进行释放了）。 6.如果数据库关闭后重新打开了，更不用关心了，因为事务还没开始。

树枝

type branchPageElement struct {    pos   uint32    // key的位置    ksize uint32    // key的大小    pgid  pgid      // 指向的下层pageid}

树枝在文件中的结构如下:

通过 pos 可定位到 key，通过 pos:ksize 即可取得 key.通过 pgid 可获取下一层数据（树枝或树叶）

叶子

type leafPageElement struct {    flags uint32    // 内容标识，可以为普通数据或bucket两者中的任一种    pos   uint32    // key的位置    ksize uint32    // key的大小    vsize uint32    // value的大小}

叶子在文件中的结构如下：

通过 pos 可定位到 key，通过 pos:ksize 获取到 key，通过 pos+ksize:vsize 可获取到 value。

其中叶子内容可为 bucket（sub-bucket），可为普通数据。

当为 bucket 时，flags 为 bucketLeafFlag=0x01；

当为普通数据时，flags=0。

page 和 node 对应转换

从 page 转为 node：通过node.read(p *page)函数转换，按需转化。

从 node 转为 page：通过node.write(p *page)函数转换

因为修改操作都在内存中完成，所以往插入数据都是在 node 中进行，然后经过一系列操作再保存到文件中。

往 node 中插入数据：node.put(oldKey, newKey, value []byte, pgid pgid, flags uint32)

上面已经说过，插入数据仅两种情况，插入 bucket，插入普通数据：

c.node().put(key, key, value, 0, bucketLeafFlag)

c.node().put(key, key, value, 0, 0)

在落盘前插入数据时，均不会分配 pgid（pgid=0）。只会影响内存中的数据，文件中不会受影响。

bucket

在 boltdb 中，bucket 是一个重要的概念，它是一些列的键值对的集合。一个 bucket 相当于一个命名空间，每个 bucket 中表示了一个完整的 b+树，另外 bucket 可以嵌套。对数据的增删改查都基于 bucket。

结构体如下：

// Bucket represents a collection of key/value pairs inside the database.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
    // Sets the threshold for filling nodes when they split. By default,    // the bucket will fill to 50% but it can be useful to increase this    // amount if you know that your write workloads are mostly append-only.    //    // This is non-persisted across transactions so it must be set in every Tx.    FillPercent float64}
// bucket represents the on-file representation of a bucket.// This is stored as the "value" of a bucket key. If the bucket is small enough,// then its root page can be stored inline in the "value", after the bucket// header. 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 在持久化到文件后为下面两种情况之一：

1.占用一整个 page 2.bucket 和其数据作为一个 leaf 存在

情况一在文件中的结构如下：

其中 root 为该 bucket 的起始 pageid，后续对该 bucket 中的元素查询操作时，都从该 pageid 开始进行二分法查找。其占用一个 pagesize。

情况二在文件中的结构如下：

bucket 和其中的数据做为一个 leafPageElement 存在。假设 leaf1 为 inline-bucket，则其 value 值中存储的内容为 BucketHeader+PageHeader+PageData(该 bucket 的 k/v 集合).

其与正常 bucket 的区别是不会单独分配 pageid，root 值为 0，pageid 也为 0.

inline-bucket 存在的目的是为了降低存储空间的占用。

其实新创建的 bucket 默认就是一个 inline bucket，然后在内存中做 k/v 的一系列操作，在落盘时判断是否满足 inline bucket，判断函数为Bucket.inlineable()。

全貌

我们看下一个对于一个 bucket 形成的完整 b+树

说明： 为了好画图，上面做了简写： PH：PageHeader

LE：leafPageElement

BH：bucketHeader

BE：branchPageElement

K:key

V:value

对于内存中的全貌，可以用 node+inodes 可同样描绘出来，在此不再赘述

查找

有了上面这些基础，我们看下查找。

不管内存中 inodes 里存储的内容，还是 page 中 Element（leafPageElement+branchPageElement），它们的 key 都是有序排列的。

二分法查找。

查找中使用的数据结构：

// Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order.// Cursors see nested buckets with value == nil.// Cursors can be obtained from a transaction and are valid as long as the transaction is open.//// Keys and values returned from the cursor are only valid for the life of the transaction.//// Changing data while traversing with a cursor may cause it to be invalidated// and return unexpected keys and/or values. You must reposition your cursor// after mutating data.type Cursor struct {    bucket *Bucket    stack  []elemRef}
// elemRef represents a reference to an element on a given page/node.type elemRef struct {    page  *page    node  *node    index int}

cursor 相当于一个游标，查找会记录所经过的路径(page+node+命中的 key 的 index)，并放入 stack 中。

因为 b+树叶子节点存储 value，所以最终，stack 的顶部（最后一个元素）就为叶子节点。然后进行相关操作（增删改）

查找过程中会先在内存中（node）查找，然后从 page 中查找并缓存到内存。

B+树平衡

在读写事务提交阶段进行持久化。

上面说过，所有的修改，都是在内存中变更的，增加和删除都会破坏 b+树结构，所以在持久化前需要调整内存中树结构。

此时涉及两个操作:

1.rebalance:删除操作会对 node 打上 unbalanced 标记，因为删除数据可能会引起 page 填充率不够，此时会对这些节点检查并进行合并。 2.spill：添加操作会使得 page 填充率过高，需要对节点进行分裂。

rebalance

Bucket 中，b.nodes 字段和 b.buckets 字段为有过操作的缓存字段，所以需要对这两个字段中的节点进行 rebalance 处理。

对于可能不平衡的节点（删除时打上 unbalanced 的节点），判断其填充率是否满足下面两个条件（两个条件都要满足）：

1.条件为大于 1/4 pagesize 2.当前节点为叶子节点的话，key 的数量要大于 1；为树枝节点的话，key 数量要大于 2

不满足上面条件的话就进行 rebalance 处理

处理函数为：b.rebalance()

合并流程为：

1.如果是根节点，且是树枝节点，含有一个数据，则把叶子节点往上提（删除树干节点） 2.对于不含数据的节点，进行删除处理 3.优先使用同一层左边的节点进行合并，如果没有的话使用右边的节点进行合并（第一个节点无左节点，需选用右边节点） 4.合并可能会引起父节点不满足条件（看上面的全貌图，父节点的 key 是子节点最小（最左）的 key，孩子合并后，这个 key 就不需要了），需要递归处理父节点

spill

b.spill()

函数对 Bucket 中 node 进行分裂。

一个节点能被分裂成多个节点需满足下面条件（两个条件都要满足）

1.inodes 中的数据量大于 4 2.inodes 中的数据大小大于 pagesize

因为可能存在大 key 问题：inodes 中 key 数量满足条件 1，但它里面的某个 key 的 value 值很大，大于 pagesize，此时无需分裂。

上文说过，新增的节点在落盘前均不会分配 pageid，那 pageid 啥时分配呢？ 其实 spill 除了负责分裂外，还会为分裂好的 node 申请 pageid。

分裂

对涉及到的 buckets 中节点均进行判定及分裂：先对每个 sub bucket 进行判断，看是否是 inline-bucket，非 inline-bucket 中每个节点均需进行判定及分裂

分裂流程：

1.从每个 bucket 中的根节点开始，自顶往下递归到叶子节点 2.对每个节点进行判定及分裂为多个节点（根据填充率分割） 3.对分裂后的多个节点，依次对每个节点分配 pageid，如果该节点有 pageid 的话，需放入 freelist pending 中(freelist 这个数据结构会用来记录空闲 pageid 列表和当前待释放 pageid 列表)。 4.分裂可能会导致父节点 key 数量过多，所以也需要进行分裂

分配 pageid

会根据需要的空间在 freelist 中寻找满足条件的空闲pageid。因为存储的数据可能需要一个 page，有的需要多个 page（大 key），多个 page 需要连续。

这时候如果大小大于文件大小，需要调整 mmap 映射的文件大小(mmap 映射的磁盘大小是 pagesize 的整数倍，故会大于文件大小）。

另外可以看出分配 pageid 的过程，是一个顺序遍历的过程，直到满足条件。随着数据量增加，freelist 的 id 碎片化会很严重，而我们又想寻找一个大的 page 的情况下会成为瓶颈。我看 etcd 维护的版本中已经修复了这个问题（通过合并及归类）。

数据落盘

上文说过，读取是通过 mmap 来减少一次 IO，落盘是使用写文件的方式。

1.先更新文件描述信息中的文件最终大小。 2.在指定偏移量处写入数据 3.使用 syscall.Fdatasync 确保数据落盘。

这种先定文件大小，然后再使用 fdatasync 可以减少一次 IO

事务

boltdb 是支持事务的：只读事务和读写事务。

支持多个读事务和一个写事务。

我们看下它是如何支持 ACID 的。

原子性（atomicity)

修改事务在事务开始时拷贝 metadata，

所有的修改操作都在内存中完成，不会影响到数据库文件。

落盘时先写 b+数据和 freelist 数据，最后写 metadata 的顺序执行。只有 metadata 写入成功，才算成功，如果任何一步写入失败，直接丢掉 freelist 中该事务分配的 pageid，重新载入 freelist 即可。

一致性（consistency)

写事务只有在 metadata 成功写入才算事务成功执行。即使故障或断电，也不会影响数据库的一致。

隔离性（isolation）

写事务串行执行，读事务可并发执行。使用 MVCC 多版本并发控制。每个事务都会分配一个事务版本号 txid。

读事务 txid = db.meta.txid，写事务 txid = db.meta.txid + 1

读事务的生命周期中，不会受到写事务影响：

1.写操作在持久化前都在内存中进行 2.持久化后，修改后的数据会分配额外的 pageid，不会影响以前的 page，修改过的 page 均处于 pending 状态，版本号低的 txid 是无法访问到的 3.在每次读事务开始时，都会获取最新的 db.meta.txid，写事务开始时，会把小于最小 txid 的处于 pending 状态的给放入空闲 id 列表，保证了新开始的读事务能读到较新的版本。

持久性（durability）

boltdb 使用了两个 metadata 来保证故障或重启时进行恢复。metadata 选取时有校验机制，使用一个 metadata 来恢复另一个 metadata 时，只需要恢复 freelist。

参考

boltdb/bolt

boltdb 源码分析