云原生 etcd 系列|存储引擎 boltdb 的设计奥秘?

2022-03-16 00:00:00 数据 更新 事务 节点 的是



etcd 的存储


etcd v3 是使用的持久化存储来存储它的 kv 数据,etcd  存储的是非常核心的元数据信息,所以重要的是稳定。使用的是 boltdb 。下面说道说道这个 boltdb 。


boltdb 是什么?


boltdb 是一个非常出名的存储引擎,纯 Go 语言实现的 KV 存储引擎。

boltdb 项目非常值得学习,封装的 API 简单,内部实现很精巧。整个项目去掉注释,测试代码啥的,就几千行代码。Github 地址为 https://github.com/boltdb/bolt 。但 boltdb 项目已经由原作者封版了,不再迭代更新。

etcd 自己 fork 了一个 boltdb 分支出来,上面做了一些自己的小优化。

boltdb 启发于 Howard Chu's LMDB[1] 项目,感兴趣的也可以去看下。

特点:

  1. 整个数据库就一个 db 文件,贼简单;
  2. 基于 B+ 树的索引,读效率高效且稳定;
  3. 读事务可多个并发,写事务只能串行;

缺点:

  1. 事务的实现贼简单,但是写的开销太大;
  2. boltdb 写事务不能并发,只能靠批量操作来缓解性能问题;

下面我们从外到内一步步探索下 boltdb 的实现。


boltdb 看起来是什么样子?


整个 db 就一个单文件,只不过这个文件内容是有格式的。先用 hexdump 看一眼:



仔细的童鞋会发现,这个数据间隔有点意思?

0000    // 0   偏移
1000    // 4k  偏移
2000    // 8k  偏移
3000    // 12k 偏移
4000    // 16k 偏移
5000    // 16k 偏移

每个偏移都是 4k 的间隔,里面还有一些看不懂的二进制数据。以前奇伢说过,越往底层都会有一个存储单元的概念,因为要合并一些边际开销,比如,文件系统大多以 4k 为单位进行管理,page cache 也以 4k 为单位管理。再看硬件,也是如此,磁盘的小处理单位是扇区( 512字节 ),ssd 的读写是以 4k 为单位管理的。

boltdb 作为一个存储引擎,自然要统筹管理空间的使用,自然也有这么一个概念。boltdb 以 4k 定长为存储单元划分空间,这一个个 4k 叫做 page,boltdb 在上面建立更抽象的概念。

来看看 boltdb 怎么管理空间的吧。


怎么管理空间?


上面提到是以 4k 为粒度来管理空间的,每个 4k 叫做 page 。


 1   page 页


为了方便管理,page 自然也是会有格式的,每个 page 都会有 header ,header 后面是 data 数据。

// header 结构体
type page struct {
 id       pgid       // page 编号
 flags    uint16      // 标明 page 的属性
 count    uint16      // 标明 page 上有多少个元素
 overflow uint32       // 标明后面是不是还有连续的页跟着
 ptr      uintptr      // 这就是个用来定界的
}

示意图:



从物理层面来说

boltdb 的 db 文件来说就是由这样一个个 page 组成的。举个例子,如果是一个 32K 的文件,那么就由 8 个 page 组成,每个 page 都有自己的编号( pgid ),从 0 到 7 。

从逻辑层面来说

boltdb 把这一个个 page 组成了一个树形结构,它们之间通过 page id 关联起来。我们再往下思考:

  • 个点:树自然会有个源头,比如从那个 page 开始索引,还有一些关键的元数据( meta 数据 );
  • 第二个点:既然是一颗树,那么自然有中间节点、叶子节点;
  • 第三个点:既然是空间管理,那么自然要知道哪些是存储了用户数据 page ,哪些是空闲的 page ;

上面提到的三个点都指向一个结论:page 的用途是不一样的。也就是说,虽然大家都是 page,但是身份不一样。有的是叶子节点,有的是中间节点,有的是 meta 节点,有的是 free 节点。这个由 page.flag 来标识。

const (
  branchPageFlag   = 0x01
 leafPageFlag     = 0x02
 metaPageFlag     = 0x04
 freelistPageFlag = 0x10
)

下面分开聊聊这几种 page 页。


 2   meta page


元数据的 page ,这可太重要了。对于 boltdb 来说,meta 的 page 位置是固定的,就在 page 0,page 1 这两个位置( 也就是前两个 4k 页 )的位置。一切索引从此开始,简单看下里面的数据含义:



  • Root :指明树根的位置;
  • Freelist :指明空闲列表的位置;
  • Txn :事务编号(写事务的时候,事务号会递增);

有童鞋可能会疑惑了,为什么会有两个 meta 页?

这是一个非常重要的设计,在 boltdb 里有一个非常重要的设计:没有覆盖写,也就是不会原地更新数据。这个是 boltdb 实现 ACID 事务的秘密。

以前也提过,覆盖写是数据损坏的根源之一。因为写数据的时候可能会出现任何异常,比如写部分成功,部分失败 这种就不符合事务的 ACID 原则。

但由于 meta 是 boltdb 一切的源头,所以它必须是固定位置( 不然就找不到它 )。但为什么会有 paid 0,1 两个位置呢?

诀窍就在于:通过轮转写来解决覆盖写的问题。 每次 meta 的更新都不会直接更新新的位置,而是写上上次的位置。



    // 计算 page id 的位置
    p.id = pgid(m.txid % 2)

举个例子:

  • 事务 0 写 page 0 ;
  • 事务 1 写 page 1 ;
  • 事务 2 写 page 0 ;
  • 事务 3 写 page 1 ;

 3   branch page


branch 的 page 就是做了树的叶子节点,这个没啥讲的,里面就是存储的 branch 的节点。本质也是 key/value,key 是用户的 key,只不过 value 是 page 的索引而已。看一下结构体:



 4   leaf page


叶子节点里面主要存储的是用户的数据,这个没啥讲的,一堆 key/value ,key 是用户的 key,value 是用户的数据。



 5   freelist page


所谓 freelist page 也就是说 page 里面存储的是一个个 pgid ,这些个 pgid 都是空闲可用的 page 的 id 。当写事务需要空闲的 page 存储数据的时候,就可以从这个里面捞一个来用。




怎么索引数据的?


现在我们知道了存储的管理单元是 page,每个都由 header + data 组成,page 的类型则决定了 data 里面装什么数据。主要是四种 page :

  1. meta 的数据;
  2. 中间节点的数据(主要是索引数据);
  3. 叶子节点,存储的是 key/value 数据( 有意思的是这里的 key/value 也是有讲究的,既可能是用户的 key/value 数据,也可能是 bucket 的结构数据 );
  4. freelist 的数据,里面存储的是一个个 pgid ;

那现在我们看 boltdb 是怎么来组织 page,索引这些数据。


 1   B+ 树 ?


都说 boltdb 用的是 B+ 树的形式,说的也是对的,但是 boltdb 的 B+ 树有些变异,几点差异如下:

  1. 节点的分支个数不是固定值;
  2. 叶子节点不相互感知,它们之间不存在相互的指向引用;
  3. 并不保证所有的叶子节点在同一层;

划重点:boltdb 它用的是一个不一样的 B+ 树。 除了上面的,索引查找和数据组织形式都是 B+ 树的样子。

在 boltdb 里面有几个封装的概念:

  1. Bucket :这是一个 boltdb 封装的一个抽象概念,但本质上呢它就是个命名空间,就是一些 key/value 的集合,不同的 Bucket 可以有同名的 key/value ;
  2. node :B+ 树节点的抽象封装,可以说 page 是磁盘物理的概念,node 则是逻辑上的抽象了;

在 boltdb 中,Bucket 是可以嵌套的,这一点也带来了很大的灵活性,同样也是代码略微难懂的地方。其实 boltdb 天生就有一个 Bucket ,这个是自动生成的,由 meta 指向,不是用户创建的,后续创建的 Bucket 都是这个 Bucket 的 subbucket 。




怎么实现的事务?


划重点:boltdb 实现事务的方式非常简单,就是不覆盖更新数据。 其中 meta 是通过两个互为备份的 page 页轮转写实现的,数据页又是怎么实现的呢?

秘密就是:每次都写新的地方,后更改路径引用。我们来看一下它是怎么做的?看一下演绎的过程:


 1   现状一棵树


假如当前如下,有个 key/value 键值对( "hello", "world" )存储在一个叶子 page 上。




 2   更新前先找位置


现在用户要更新这个 key="hello" 的值,更新 value 为 "qiya" ,那么很自然的,开启一个写事务,事务号递增+1,boltdb 需要通过 B+ 树的搜索算法定位到叶子节点。




 3   定位到后,读改写


定位到 node 节点之后,怎么修改呢?这个节点里面可不止这一对 key/value,里面还有很多 key/value 。

做法很简单,读改写!也就是先把这个 node 对应的 page 读到内存,把所有的 key/value 加载出来,然后把 key="hello" 的值更新到 value="new_world" ,并且写到新的 page 里。

那问题来了,叶子节点更新了,那指向这个叶子节点的 branch 节点要不要更新呢 ?

自然是要的。那 branch 节点更新了,那 branch 的 branch 节点要不要更新呢?自然是要的。所以这一层层往上推,终要更新到 meta page 的,也就是树根。




 4   后切换树根,被新 page 替换的终会被释放


终这些被替换的 page 就会被纳入到 freelist 里面,完全没有事务引用的话就会被释放。



 5   小结一下


上面就是写事务的方式,总结一下:

  1. 通过 key 查询到位于 B+ 树的那个 page ;
  2. 把这个 page 读出来,构建 node 节点,更新 node 的内容;
  3. 把 node 的内容写到空闲的的 page ,并且一层层往上;
  4. 终更新 meta 索引内容;

这里我先提一点个人的思考,很多人提到 boltdb 这是一种 cow ( copy-on-write )的方式,但其实我更偏向于把这个理解成 row 的方式。你觉得呢?


总结


  1. etcd 使用 boltdb 来做存储引擎,读性能还行,写性能很一般,但是它稳
  2. boltdb 的物理存储单元是 page ,一般为 4k 一个;
  3. page 有不同的类型,里面的内容根据类型不一样而不同;
  4. boltdb 使用 row 的方式(个人理解),保证无覆盖写,等到 commit 的时候,终修改引用,从而切换整个 db 的路径。这样的方式几乎是 0 成本实现的 ACID 事务;
  5. meta 的 page 有两个,它们通过轮转写来实现的不覆盖写,从而保证了数据更新的安全;
  6. B+ 树相比 LSM Tree 天然就有随机读的性能优势,它的树高度稳定,boltdb 通过 mmap 把文件映射到内存,这样简化了代码,读的缓存交给了操作系统的 page cache ;
  7. boltdb 写性能可能很差,因为只要改了一点点东西,都会导致这个节点到 root 节点整条链路的更新,写放大挺严重的,所以它只能靠 batch 操作来安慰自己;

参考资料

[1]

LMDB Github 地址: https://github.com/LMDB

相关文章