本文作者：刘代明（常用网名:行如风，常用游戏名:学长的棉被），一个文艺青年（纳尼？青年？是的，你没看错：世界卫生组织（2020年）对青年的定义：18-65周岁[来自百度百科]）。现在奇虎360搜索技术部任web服务端技术专家职位。 本文为作者原创，祝大家阅读愉快。
前言
最近抽时间看了boltdb的源码，代码量不大（大概4000行左右），而且支持事务，结构也很清晰，由于比较稳定，已经归档，确实是学习数据库的最佳选择。而且不少出名的开源项目在使用它，比如etcd，InfluxDB等。
本文记录下笔者在阅读源码后了解到的其工作原理，以留备忘。
简介
boltdb数据库是一款go开发的k/v数据库。其设计源于LMDB（Lightning Memory-Mapped Database），持久化到单文件中,通过mmap将文件映射到内存，这样读文件可以减少一次IO,但是写文件并不是通过mmap，而是通过调用写函数进行seek+write，后面会具体讲。
通过B+树进行索引。
按块写入，块的大小根据操作系统获得，大部分操作系统都是4k.
支持事务：多个读事务可以并发执行，但是写事务是串行的。
工作流程
一段简单使用代码如下：
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
29
30
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
代表内存中一个树节点
1
2
3
4
5
6
7
8
9
10
11
12
13
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数据.树枝和叶子节点公用这个数据结构。
1
2
3
4
5
6
7
8
type inode struct {
flags uint32 // 仅叶子节点使用。存放数据内容标识,为bucket或普通数据中的一种
pgid pgid // 仅树枝节点使用。存放子节点的page id
key []byte // 树枝节点和叶子节点公用。key
value []byte // 仅叶子节点使用。存放普通数据或bucket
}
文件相关
page
1
2
3
4
5
6
7
8
9
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。
1
2
3
4
5
6
7
8
9
10
11
12
13
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数据结构：
1
2
3
4
5
6
7
8
9
// 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.如果数据库关闭后重新打开了，更不用关心了，因为事务还没开始。
树枝
1
2
3
4
5
6
7
type branchPageElement struct {
pos uint32 // key的位置
ksize uint32 // key的大小
pgid pgid // 指向的下层pageid
}
树枝在文件中的结构如下:
通过pos可定位到key，通过pos:ksize即可取得key.通过pgid可获取下一层数据（树枝或树叶）
叶子
1
2
3
4
5
6
7
8
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。
结构体如下：
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
// 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都是有序排列的。
二分法查找。
查找中使用的数据结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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.先更新文件描述信息中的文件最终大小。
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。
