【存储】etcd的存储是如何实现的(3)-blotdb

前两篇分别介绍了etcd的存储模块以及mvcc模块。在存储模块中，提到了etcd kv存储backend是基于boltdb实现的，其在boltdb的基础上封装了读写事务，通过内存缓存批量将事务刷盘，提升整体的写入性能。botldb是etcd的真正的底层存储。本篇，我们就来介绍boltdb。

---

在看具体细节之前，先大概介绍下boltdb。
etcd中引用的boltdb为bbolt package - go.etcd.io/bbolt - Go Packages，其是纯golang开发的持久化的kv存储，支持读写事务，允许多个读事务以及最多一个的写事务同时进行，读写事务之间具备快照级别的隔离。

boltdb中以bucket(桶)作为数据逻辑上的聚合，其概念等同于表。同一个桶中的数据以B+树的形式进行组织。

接下来，会从磁盘文件格式、内存数据结构、事务等方面对boltdb进行详细介绍。

文件格式

作为一个轻量化的存储，boltdb将所有的数据都存储在一个文件中，并以page为单位管理文件。page大小可以作为参数传入，或者取操作系统的page size。boltdb中有meta、freelist、branch、leaf四种page类型，通过page header的flag进行区分。

meta page，顾名思义，存储了boltdb的元信息，例如page size、freelist page、root bucket、当前最大的page id、全局的事务id等。freelist page，记录了文件中空闲的页。branch page和leaf page分别对应B+树的非叶子结点和叶子结点，存储真正的应用数据。

整体的布局如下。

page通过pgid来确定位置，其对应offset为pgid*page size。每个page的前16字节为header，其结构如下。

type pgid uint64type page struct {id       pgidflags    uint16count    uint16overflow uint32
}

• flags在前面提到过，用来标识page的类型，有meta、freelist、branch、leaf四种类型。
• count表明该页中保存的记录的条目数。
• overflow表示为溢出的页的数量。在某些数据的大小超过page size的时候，我们需要分配一块连续的超过page size的空间来存储数据，overflow就是用在这里。

header之后，就是数据。

meta

meta page的内容很好理解。header之后的64字节为meta的内容，字段如下。

type meta struct {magic    uint32version  uint32pageSize uint32flags    uint32root     bucketfreelist pgidpgid     pgidtxid     txidchecksum uint64
}

freelist

freelist的page value是顺序排列的pgid。freelist page也是目前我看到的唯一使用overflow的地方，当freelist的pgid数量较多，超过一页时，会分配连续的内存存储pgids。

branch and leaf

branch page和leaf page分别对应B+树的非叶子节点和叶子节点。其采用了将记录的header和value分开存储的方式，header的数据结构如下。pos字段为value距离header的offset，size为key或者value的长度。通过将记录的header和value分开存储，可以有效地增加按照index索引记录的效率。

// branch element header
type branchPageElement struct {pos   uint32ksize uint32pgid  pgid
}// leaf element header
type leafPageElement struct {flags uint32pos   uint32ksize uint32vsize uint32
}

branch page和leaf page的页面布局如下。

另外，可以看到leaf page element有一个字段为flags，该字段有什么用呢？

前面提到过boltdb中有bucket的概念，其是类似“表”的数据的逻辑的集。然后这一小节的开头又说了boltdb把所有的数据都存储在一个文件上。那么blotdb是如何组织bucket的呢？

实际上boltdb将所有的bucket存放在一个meta bucket中，该bucket的key为boltdb中其他bucket的名字，value为对应B+树根节点所在pgid。当操作数据时，先在meta bucket中找到目标bucket，再对目标bucket进行操作。
实际上，在meta page中的root字段就是meta bucket对应B+树的根节点所在的pgid。

内存数据结构

上一小节介绍了boltdb的文件格式。但在实际运行时，更多还是在做内存操作。这一小节主要介绍boltdb在其文件格式上构建的数据结构以及相应的操作。

node

node是B+树的节点，对应文件中的一个page(branchElementPage或者leafElementPag)，其从page中解析数据或者将数据写入free page。

// node represents an in-memory, deserialized page.
type node struct {bucket     *BucketisLeaf     boolunbalanced boolspilled    boolkey        []bytepgid       pgidparent     *nodechildren   nodesinodes     inodes
}

node的结构如上，作为B+树的节点，node的方法分别对应B+树的增删改查，节点的合并、分裂，和page的交互(从page读取或者写入page)。
bucket字段标识node所属的bucket。bucket前面提到过，是数据的逻辑的集合，同一bucket中的数据以B+树组织。

unbalanced字段表示该node存在合并的可能性，当删除node中的记录时会将该字段置为true。实际在rebalance时还会判断node的大小。如果node size小于25% page size或者记录数过少(叶子节点记录数小于1，非叶子节点记录数小于2)，就会和临近节点合并。注意，rebalance只是消除了过小的节点，但是可能会导致过大的节点。过大的节点是在spill(写入page)时解决的。

spilled字段表示该node是否写入了脏页。node在spill时会对节点按照page size进行拆分，以解决rebalance时可能存在的节点过大的问题。另外一个需要注意的点是，node在spill时，会将当前持有的page释放掉，申请一个新的page将内容写入。代码如下。

// bbolt/node.go node.spill
if node.pgid > 0 {// 释放现有的pagetx.db.freelist.free(tx.meta.txid, tx.page(node.pgid))node.pgid = 0
}// 分配新的page
// Allocate contiguous space for the node.
p, err := tx.allocate((node.size() + tx.db.pageSize - 1) / tx.db.pageSize)
if err != nil {return err
}// Write the node.
if p.id >= tx.meta.pgid {panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", p.id, tx.meta.pgid))
}
node.pgid = p.id
node.write(p)
node.spilled = true

这里解释了为什么boltdb为什么读写事务之间具备快照的隔离级别。因为写操作的改动会映射到新的页上，而读操作依然依赖读事务开始时的页。实际上，boltdb的这种实现名为copy shadow或者copy paging，是一种效率比较低、比较少见但又非常简单的实现。

parent字段指向当前节点的父节点，当合并或者分裂节点时需要回溯操作父节点。

Bucket

boltdb有bucket的概念，类似mysql的表或者mongodb的collection，是数据的逻辑的集合。

对应存在Bucket的结构体，结构如下。但Bucket和我们提到的桶的概念之间存在差异。注意Bucket持有tx字段，所以Bucket实际表示的是对应tx开启时的桶的一次快照。快照的实现在node中提到过，是通过copy paging实现的。

type Bucket struct {*buckettx       *Tx                // the associated transactionbuckets  map[string]*Bucket // subbucket cachepage     *page              // inline page referencerootNode *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的其他字段都相对比较好理解。这里就提一下buckets。

buckets字段是对subbucket的缓存。在meta page的介绍中提到过，boltdb所有的数据都存储在一个文件中，db中bucket的信息是存储在root bucket(meta page的root)中。所以对于root bucket，是存在subbucket的。

另外FillPercent表示节点分裂的阈值。node在spill时会根据page size进行分裂，此时会乘以FillPercent作为系数。当我们顺序写入时，可以将FillPercent设置的比较大。例如在etcd中将其设为0.9。

Bucket对应同样对应B+树的增删改查、以及rebalance、spill等方法。其中增删改查是在cursor和node基础上封装，在cursor中详细讲解。rebalance、spill等方法都是对node从child向parent进行递归的相应操作。

Cursor

Cursor是在Bucket上的一层封装，主要作用就是查找或者遍历。无论是增删改查，都需要定位key所在B+树的节点。cursor就是Bucket上利用二分法封装了查找方法。同时还封装了一层栈，来帮助做前序或者后序遍历。
B+树本质就是一颗多叉的平衡的排序树，其查找和二叉排序树也没什么区别，这里就不展开。

总结

整体的架构如下。(这个图不是非常形象。。。但是大概的关系还是说明白了，后面想想优化一下)

事务

本篇的最后，再来介绍一下事务。

开始之前，首先先明确一个点。在第二小节中所讲的node、Bucket、Cursor都不是绝对的，而是基于某一个事务开启时刻的快照版本。这点在第二小节中有提及但没有很明确地声明，在这里强调一下。

那么相应的，事务其实也只是在node、Bucket、Cursor之上封装出的增删改查、以及提交、回滚。

事务的结构体如下。

type Tx struct {writable       boolmanaged        booldb             *DBmeta           *metaroot           Bucketpages          map[pgid]*pagestats          TxStatscommitHandlers []func()// WriteFlag specifies the flag for write-related methods like WriteTo().// Tx opens the database file with the specified flag to copy the data.//// By default, the flag is unset, which works well for mostly in-memory// workloads. For databases that are much larger than available RAM,// set the flag to syscall.O_DIRECT to avoid trashing the page cache.WriteFlag int
}

增删改查、节点的合并分裂等就不再介绍。这里关注几个点：

1. 快照级别的隔离是如何实现的。
   在node中提到过，当脏页刷盘时，并不会覆盖原有的page，而是分配新的free page进行写入，这种技术称为copy paging。copy paging技术还有一个关键点是页表，页表包括了所有页的信息。所以记录快照时，只需要对页表进行快照，就相当于对db进行了快照。那boltdb的页表是什么呢，就是meta page。所以事务初始化时的最重要的操作就是copy meta。

2. 提交及回滚。
   事务的提交的过程为 rebalance and spill -> page write(include freelist) -> meta write，如下图。
   

可能存在问题的点为(a)spill出错；(b)page write出错；©meta write出错。我们逐个来分析可能的情况。

• (a)spill出错。此时仅做了内存操作，事务不需要回滚。
• (b)page write出错。由copy paging的特性可知，此时meta page还为旧的数据，page write失败产生的脏页会被视为free page，在后续操作中被分配覆写。所以page write不需要回滚操作。
• © meta write出错。meta write成功则事务成功提交，但是如果meta write失败且meta page被污染怎么办？回到第一小节文件格式的布局图中，可以看到boltdb存在两个meta page。meta page数据有效且tx id更大的才会被选为meta数据。结合boltdb同时最多一个写事务的特性，可以确保安全。

总结

本篇中，我们介绍了boltdb的文件格式、内存数据结构、事务等，相信会多boltdb有一个比较清晰全面的认知。
同时，还有一些内容，比如free list，这个是比较重要的数据结构，跨事务的管理page；比如mmap，boltdb利用mmap技术讲文件直接映射到内存，减少了系统调用。这些内容后面会再开一篇补充讲解。