理解Boltdb

[toc]

😃

在不同的场景、不同的组件中。具体采用自底向上还是自顶向下来分析。见仁见智，也具体问题具体分析。在本篇中自底向上分析boltdb，然后到etcd，应为etcd的底层就依赖于boltdb的数据存储。

1. boltdb

1.1 boltdb基本理解

boltdb 是一个纯 go 编写的支持事务的文件型单机 kv嵌入式数据库。目前支持的事务包括：读写事务、只读事务。事务中的所有操作都在内存中进行，只有commit时候才会写磁盘。boltdb所有数据都存储在磁盘上，数据涉及在内存和磁盘的交换，适用于读多写少的存储场景。其对外暴露的是kv的接口，支持数据类型均是[]byte的key和value。

boltd的源码大约4000行¹， 目前已经归档，是目前etcd，InfluxDb依赖的底层存储。boltdb中三大概念名词：DB, Bucket， K/V。如果把boltdb比喻成衣柜，我们把东西整理放入衣柜就是对boltd的操作，Bucket就是柜子分隔后的小柜子或者抽屉，K/V就是放入衣柜的每个东西，其中K就是这个东西的标记，V就是具体的东西。换着说：boltdb是有多个桶Bucket，每个桶存放键值对数据kv。

boltdb每个db对应一个文件，文件按照page来组织，page id为0和1的两个page是metadata，同时还有freelist的page用来存放空闲的page id， 剩下的page构成一个B+树包括brach page用于存放具体的索引信息以及leaf page存放真实的用户数据。通过Bucket来支持namespace，每个Bucket是一个完整的B+树。

全局视图如下：

1.2 boltdb数据结构

对于文件数据库的性能提升，因为文件是在磁盘上，为了减少读磁盘的时间（寻道时间+旋转时间+传输时间），同时顺序读写比随机更快，因而性能提升主要聚焦在如何最大程度进行顺序读写方式来进行数据的写入和查询。

如何将用户写进来在内存中的数据尽可能采用顺序写的方式放进磁盘，同时在用户读数据时候，将磁盘中保存的数据尽可能少的IO调用次数加载到内存中，而返回给用户。

对于boltdb在存储结构上，磁盘上是按照4K的page进行数据结构组织，内存中的数据结构是node，还有一个page和node之间的相互转化。对于boltdb的set操作，本质上对应的就是set->node>page->file， 而对于get操作是file->page->node->get的过程。

boltdb没有实现page cache，而是调用mmap将整个文件进行内存映射，并且调用madvise(MADV_RANDOM)由操作系统管理page cache，后续对磁盘上的文件的所有读写操作直接读取db.data即可。

// mmap memory maps a DB's data file.
func mmap(db *DB, sz int) error {
	// Map the data file to memory.
	b, err := syscall.Mmap(int(db.file.Fd()), 0, sz, syscall.PROT_READ, syscall.MAP_SHARED|db.MmapFlags)
	if err != nil {
		return err
	}
	// Advise the kernel that the mmap is accessed randomly.
	if err := madvise(b, syscall.MADV_RANDOM); err != nil {
		return fmt.Errorf("madvise: %s", err)
	}
	// Save the original byte slice and convert to a byte array pointer.
	db.dataref = b
	db.data = (*[maxMapSize]byte)(unsafe.Pointer(&b[0]))
	db.datasz = sz
	return nil
}

boltdb中，一个Bucket对象是一颗B+树，它上面存储一批kv键值对，同时一个Bucket下还可以由嵌套的subbucket。

Page

数据在磁盘上按照Page页来存储的，以page为单位来读取和写入数据，page大小是保持和操作系统对应的内存页大小一致。page上由两部分数据组成：header+data，即页头数据和真实数据，页头数据占用16字节。

boltdb在写入数据到磁盘文件时候直接写入的是page结构体的二进制，避免了序列化和反序列化的开销；

meta page, 其pageId是固定的0和1，该page主要用来保存数据库的基本信息，比如根节点、版本号、空闲列表，当前元数据页的id，最大的事务txid等；其中一个元数据页出问题了，可以使用另外一份进行修复来保证数据库可用。每次读写事务前，都会选取txid最大的那个meta进行事务初始化，同时MVCC时，会拷贝最新的meta。

leaf page，是用户的数据实际存储的结构，相关的对应地址信息可以通过header中的数据获取得到。存在如下的关系:&leafPageElement + pos == &key、&leafPageElement + pos + ksize == &val。

对于上述的leafPageElement中的flags取值为0时，表示叶子节点为普通的key/value类型，取值为1时，标识叶子节点为桶类型，其key为桶的key，当桶中的元素很少时，value会填充为桶的pgid以及其内联的kv节点数据。

branch page, 主要用于构建索引，方便提升查询效率。一个分支页节点页上会存储多个分支页元素即branchPageElement，branch node的value是子节点的pageId，存放在branchPageElement中，而key的存储相同都是通过pos获得。

B+树的存储中单个节点为node，包括branch和leaf节点，访问节点时首先将page的内容转化为内存中的node，每个node对应一个或多个连续的page。

对于branch节点而言，每对key/val指向一个节点，key是子节点的其实range，val存放子节点的pageId。对于leaf节点，每对key/val存放数据，没有指针指向sibiling node；

对于数据的查询过程如下步骤：

1. 找到bucket的根节点，也就是B+树的根节点page id；
2. 读取对应的page，转化为内存中的node；
3. 若是branch node，则更具key查找合适的子节点的page id;
4. 重复2/3步骤找打leaf node，返回node中对应的value；

freelist page，空闲列表页中主要包含三个部分：所有已经可以重新利用的空闲页列表ids，将来很快释放掉的事务关联页的列表pending，页的id缓存。

1.3 boltdb事务

对于boltdb同一时间有且只能由一个读写事务执行，但是同一时刻允许多个只读事务执行。每个事务都拥有自己的一套一致性视图。

boltdb所有的数据最终会保存在文件中，当事务结束后，会将数据进行刷盘。由于用户的直接改动数据最终都发生在叶子节点，为了维持B+树的性质，会在commit前进行调整，调整过程中会引起中间节点的级联变化。所有这些节点在spill阶段通过node.write转化为页，所有变动的页称为脏页，在spill后会对这些脏页进行刷盘，按照下述的步骤：

1. 将脏页按page id排序后逐个遍历；
2. 将page id转化为offset；
3. 通过db.ops.writeAt将脏页在offset处刷盘；
4. 通过page pool服用page size = 1的脏页，以备allocate时复用；

对于刷盘有个开关控制db.NoSync，如果配置为true，每次commit后并不会刷盘，而是写入缓冲区，有操作系统决定真正落盘的时机；上述刷盘结束后，会对元信息（freelist和整个db元数据）进行刷盘，只有元信息页落盘成功，才会使得改动对用户可见。元信息页作为全局指针，该指针的写入原子性来保证事务的原子性，如果宕机元数据没有写入完成，所有改动便不会生效，达到了自动回滚的效果。

boltdb会通过冗余一份元数据来做容错，当事务提交时，如果写入一般机器挂了，此时数据会有问题。当boltdb再次恢复时，会对元数据进行校验和修复。

boldtb在上层支持多个进程以读写或者只读的方式打开数据库，在内部实现的时候底层是不同的锁，只读模式是共享锁，而读写模式是互斥锁。在数据库内部中支持上述说的读写事务和只读事务，两种类型的事务底层都保留一套完整的视图和元数据，彼此间相互隔离；

1. 增量写内存。
2. 穿透读磁盘。

读写事务的变动都在内存中，而只读事务通过 mmap 直接读取的磁盘上的内容，因此读写事务的改动不会为只读事务所见。多个读写事务是串行的，也不会互相影响。而每个只读事务期间所看到的状态，就是该只读事务开始执行时的状态。

REF