boltdb 持久化
在前面简介部分已经描述了一部分持久化相关的内容
boltdb采用单个文件来将数据存储在磁盘上，该文件的前4个page是固定的:
- 第1个page为meta
- 第2个page为meta
- 第3个page是freelist，存储了一个int数组，
- 第4个page是leaf page
page
page是boltdb持久化时，与磁盘相关的数据结构。page的大小采用操作系统内存页的大小，即getpagesize系统调用
的返回值，通常是4k大小。
每个page开始的几个字节存储的是page
的raw data:
type page struct {
id pgid // page的序号
flags uint16 // page的类型，有branchPageFlag/leafPageFlag/metaPageFlag/freelistPageFlag几种
count uint16 // 当page是freelistPageFlag类型时，存储的是freelist中pgid数组中元素的个数；
// 当page时其他类型时，存储的是inode的个数
overflow uint32 // 当写操作数据量大于1个page大小时，该字段记录超出的page数，例如：写入12k的数据，
// page大小为4k，则page.overflow=2，标明page header后的2个page大小区域也是该page的
// 区域。
ptr uintptr
}
每个page对应对应一个磁盘上的数据块。这个数据块的layout为:
| page struct data | page element items | k-v pairs |
其分为3个部分：
- 第一部分
page struct data是该page的header，存储的就是pagestruct的数据。 - 第二部分
page element items其实就是node(下面会讲)的里inode的持久化部分数据。 - 第三部分
k-v pairs存储的是inode里具体的key-value数据。
type meta struct {
magic uint32 // 存储魔数0xED0CDAED
version uint32 // 标明存储格式的版本，现在是2
pageSize uint32 // 标明每个page的大小
flags uint32 // 当前已无用
root bucket // 根Bucket
freelist pgid // 标明当前freelist数据存在哪个page中
pgid pgid //
txid txid //
checksum uint64 // 以上数据的校验和，校验数据是否损坏
}
freelist
根据前面简介中的描述，boltdb
是不会释放空间的磁盘空间的，因此需要一个机制来实现磁盘空间的重复利用，freelist就是实现该机制的
文件page缓存。其数据结构为：
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记录了当前缓存着的空闲page的pgid，cache中记录的也是这些pgid，采用map记录
方便快速查找。
当用户需要page时，调用freelist.allocate(n int) pgid，其中n为需要的page数量，其会遍历ids，从中
挑选出连续n个空闲的page，然后将其从缓存中剔除，然后将其实的page-id返回给调用者。当不存在满足需求的
page时，返回0，因为文件的起始2个page固定为meta page，因此有效的page-id不可能为0。
当某个写事务产生无用page时，将调用freelist.free(txid txid, p *page)将指定page p放入pending池和
cache中。当下一个写事务开启时，会将没有Tx引用的pending中的page搬移到ids缓存中。之所以这样做，
是为了支持事务的回滚和并发读事务，从而实现MVCC。
当发起一个读事务时，Tx单独复制一份meta信息，从这份独有的meta作为入口，可以读出该meta指向的数据，
此时即使有一个写事务修改了相关key的数据，新修改的数据只会被写入新的page，读事务持有的page会进入pending
池，因此该读事务相关的数据并不会被修改。只有该page相关的读事务都结束时，才会从pending池进入到cache池
中，从而被复用修改。
当写事务更新数据时，并不直接覆盖老数据，而且分配一个新的page将更新后的数据写入，然后将老数据占用的page
放入pending池，建立新的索引。当事务需要回滚时，只需要将pending池中的page释放，将索引回滚即完成数据的
回滚。这样加速了事务的回滚。减少了事务缓存的内存使用，同时避免了对正在读的事务的干扰。
B-Tree 索引
Cursor是遍历Bucket的迭代器，其声明是:
type elemRef struct {
page *page
node *node
index int
}
type Cursor struct {
bucket *Bucket // parent Bucket
stack []elemRef // 遍历过程中记录走过的page-id或者node，elemRef中的page、node同时只能有一个存在
}
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
}
type node struct {
bucket *Bucket
isLeaf bool // 标记该节点是否为叶子节点，决定inode中记录的是什么
unbalanced bool // 当该node上有删除操作时，标记为true，当Tx执行Commit时，会执行rebalance，将inode重新排列
spilled bool
key []byte // 当加载page变成node缓存时，将该node下边界inode[0]的key缓存在node上，用于在parent node
// 查找本身时使用
pgid pgid
parent *node
children nodes
inodes inodes
}
type inode struct {
flags uint32 // 当所在node为叶子节点时，记录key的flag
pgid pgid // 当所在node为叶子节点时，不使用，当所在node为分支节点时，记录所指向的page-id
key []byte // 当所在node为叶子节点时，记录的为拥有的key；当所在node为分支节点时，记录的是子
// 节点的上key的下边界。例如，当当前node为分支节点，拥有3个分支，[1,2,3][5,6,7][10,11,12]
// 这该node上可能有3个inode，记录的key为[1,5,10]。当进行查找时2时，2<5,则去第0个子分支上继
// 续搜索，当进行查找4时，1<4<5,则去第1个分支上去继续查找。
value []byte // 当所在node为叶子节点时，记录的为拥有的value
}
type bucket struct {
root pgid // page id of the bucket's root-level page
sequence uint64 // monotonically incrementing, used by NextSequence()
}
boltdb通过B-Tree来构建数据的索引，其B-Tree的根为Bucket，其数上的每个节点为node和inode或
branchPageElements和leafPageElement；B-Tree的上全部的Key-Value数据都记录在叶子节点上。
当Bucket的数据还没有commit写入磁盘时，在内存中以node和inode来记录，当数据被写入磁盘时，以
branchPageElements和leafPageElement来记录。
正式这样的混合组织方式，因此在搜索这个B-Tree的时候，遇见的数据可以是磁盘上的数据也可能是内存中的数据，
因此采用Cursor这样的迭代器。Cursor的stack []elemRef中几率的每次迭代操作是走过的路径。其路径可能是
磁盘中的某个page也可能是还未刷入磁盘的node。elemRef中的index用来记录search时命中的index。
这棵大B-Tree上总共有2中节点，一种是Bucket，一种是node，这两种不同是节点都存储在B-Tree的K-V对上，只是
flag不同。Bucket被当做树或者子树的根节点，node是B-Tree上的普通节点，依负在某一个Bucket上。Bucket
当做一个子树看待，所以不会跟同级的node一同rebalance。Bucket在树上记录的value为bucket，即根节点的
page-id和sequence。
Bucket
因此，很好理解Bucket的嵌套关系。子Bucket就是在父Bucket上创建一个Bucket节点。
关于Bucket的描述可以参考BoltDB之Bucket(一)/BoltDB之Bucket(二)
两篇文章的描述。看这2篇文章时，先忽略掉inline bucket部分的内容，不然不容易理解。inline bucket只不过是
一个对于磁盘空间的优化，通常Bucket的信息在磁盘上的记录很小，如果直接占用一个page有些浪费，则将Bucket
对应page的剩余部分当做Bucket可以使用的一个page，则当数据量较小时，可以节省一个page。
node并不是B-Tree上的一个节点，并不是最总存储数据的K-V对，在node上的inode才是最终存储数据的K-V对。
每个node对应唯一一个page，是page在内存中的缓存对象。在Bucket下会有node的缓存集合。当需要访问
某个page时，会先去缓存中查找其node，只有node不存在时，才去加载page。
MVCC
bolt的MVCC实现主要依赖COW和meta副本来实现。
每当一个Tx被创建时，就复制一份当前最新的meta。在Tx中的每个操作都会将变化后的B-Tree上的node缓存
Tx的Bucket副本中，这个变化只对该Tx可见。当有删除操作时，Tx会将要释放的page-id暂存在freelist的
pending池中，当Tx调用Commit时，freelist会将pending的page-id真正标记为free状态，如果Tx调用Rollback
则会将pending池中的page-id移除，则使Tx的删除操作回滚。
当Tx调用Commit时，
会触发Bucket的rebalance，rebalance会根据阈值条件，尽量提高每个修改过的node的
使用率(即Bucket缓存的node，只有put/del过的page才会加载成node缓存在Bucket下)，经过剪去空数据分
枝、合并相邻且填充率较低的分支，最后通过数据的搬移，释放更多的page。
然后再触发Bucket的spill，spill会再将rebalance聚拢后的node根据Bucket.FillPercent将每个node所持
有的数据将到pagesize*Bucket.FillPercent之下。然后获取新的page(获取新的page时，会先去freelist查找能复用
page-id，如果找不到就新分配一个，当新分配的page使文件大小超过只读mmap的大小时，会重新mmap一次)，然后将node
写入page。
然后更新freelist的持久化记录。然后将上面操作的page刷新到磁盘上。最后更新meta的在磁盘上的记录、释放Tx
的资源。
因此在没有更新meta之前，写入的数据对于读事务都是不可见的。
文件映射增长策略
当boltdb文件小于1GB时，每次重新映射时，映射大小翻倍，当文件大于1GB时，每次增长1GB，且与pagesize对齐。
有疑问加站长微信联系（非本文作者）
