boltdb 磁盘布局

boltdb 文件指的是你 etcd 数据目录下的 member/snap/db 的文件， etcd 的 key-value、lease、meta、member、cluster、auth 等所有数据存储在其中。etcd 启动的时候，会通过 mmap 机制将 db 文件映射到内存，后续可从内存中快速读取文件中的数据。写请求通过 fwrite 和 fdatasync 来写入、持久化数据到磁盘。

image.png

文件的内容由若干个 page 组成，一般情况下 page size 为 4KB。

  • page 按照功能可分为元数据页 (meta page)、B+ tree 索引节点页 (branch page)、B+ tree 叶子节点页 (leaf page)、空闲页管理页 (freelist page)、空闲页 (free page)。
  • 文件最开头的两个 page 是固定的 db 元数据 meta page，
  • 空闲页管理页记录了 db 中哪些页是空闲、可使用的。
  • 索引节点页保存了 B+ tree 的内部节点，它们记录了 key 值，
  • 叶子节点页记录了 B+ tree 中的 key-value 和 bucket 数据。

boltdb API

boltdb 提供了非常简单的 API 给上层业务使用，当我们执行一个 put hello 为 world 命令时，boltdb 实际写入的 key 是版本号，value 为 mvccpb.KeyValue 结构体。

  1. // 打开boltdb文件，获取db对象
  2. db,err := bolt.Open("db"， 0600， nil)
  3. if err != nil {
  4.    log.Fatal(err)
  5. }
  6. defer db.Close()
  7. // 参数true表示创建一个写事务，false读事务
  8. tx,err := db.Begin(true)
  9. if err != nil {
  10.    return err
  11. }
  12. defer tx.Rollback()
  13. // 使用事务对象创建key bucket
  14. b,err := tx.CreatebucketIfNotExists([]byte("key"))
  15. if err != nil {
  16.    return err
  17. }
  18. // 使用bucket对象更新一个key
  19. if err := b.Put([]byte("r94"),[]byte("world")); err != nil {
  20.    return err
  21. }
  22. // 提交事务
  23. if err := tx.Commit(); err != nil {
  24.    return err
  25. }

核心数据结构介绍

boltdb 本身自带了一个工具 bbolt，它可以按页打印出 db 文件的十六进制的内容.

下图左边的十六进制是执行如下bbolt dump命令，所打印的 boltdb 第 0 页的数据，图的右边是对应的 page 磁盘页结构和 meta page 的数据结构。

  1. $ ./bbolt dump ./infra1.etcd/member/snap/db 0

image.png

page 磁盘页结构

每个 page 可以看成由 page header 和 page body 组成, 这里描述的应该是 page header.

它由页 ID(id)、页类型 (flags)、数量 (count)、溢出页数量 (overflow)、页面数据起始位置 (ptr) 字段组成。

页类型目前有如下四种：

  • 0x01 表示 branch page，
  • 0x02 表示 leaf page，
  • 0x04 表示 meta page，
  • 0x10 表示 freelist page。

数量字段仅在页类型为 leaf 和 branch 时生效，溢出页数量是指当前页面数据存放不下，需要向后再申请 overflow 个连续页面使用，页面数据起始位置指向 page 的载体数据，比如 meta page、branch/leaf 等 page 的内容。

数据存储在 page 上, 然而不同数据所需的 page 类型是不同的, 所以需要 meta page 来存储 “data page” 的结构信息.

meta page 数据结构

第 0、1 页我们知道它是固定存储 db 元数据的页 (meta page)，那么 meta page 它为了管理整个 boltdb 含有哪些信息呢？

结合 page 磁盘页和 meta page 数据结构我们可知:

  • 第一行前 8 个字节描述 pgid(忽略第一列) 是 0。
  • 接下来 2 个字节描述的页类型， 其值为 0x04 表示 meta page， 说明此页的数据存储的是 meta page 内容，因此 ptr 开始的数据存储的是 meta page 内容。

正如你下图中所看到的:

  • 第二行首先含有一个 4 字节的 magic number(0xED0CDAED)，通过它来识别当前文件是否 boltdb，
  • 接下来是两个字节描述 boltdb 的版本号 0x2，
  • 然后是四个字节的 page size 大小，0x1000 表示 4096 个字节，四个字节的 flags 为 0。

image.png

  • 第三行对应的就是 meta page 的 root bucket 结构（16 个字节），它描述了 boltdb 的 root bucket 信息，比如一个 db 中有哪些 bucket， bucket 里面的数据存储在哪里。
  • 第四行中前面的 8 个字节，0x3 表示 freelist 页面 ID，此页面记录了 db 当前哪些页面是空闲的。后面 8 个字节，0x6 表示当前 db 总的页面数。
  • 第五行前面的 8 个字节，0x1a 表示上一次的写事务 ID，后面的 8 个字节表示校验码，用于检测文件是否损坏。

bucket 数据结构

如下命令所示，你可以使用 bbolt buckets 命令，输出一个 db 文件的 bucket 列表。执行完此命令后，我们可以看到之前介绍过的 auth/lease/meta 等熟悉的 bucket，它们都是 etcd 默认创建的。那么 boltdb 是如何存储、管理 bucket 的呢？

  1. $ ./bbolt buckets  ./infra1.etcd/member/snap/db
  2. alarm
  3. auth
  4. authRoles
  5. authUsers
  6. cluster
  7. key
  8. lease
  9. members
  10. members_removed
  11. meta

注意 meta page 中的 bucket.root 字段，存储的是 db 的 root bucket 页面信息，你所看到的 key/lease/auth 等 bucket 都是 root bucket 的子 bucket。

  1. type bucket struct {
  2.    root     pgid   // page id of the bucket's root-level page
  3.    sequence uint64 // monotonically incrementing, used by NextSequence()
  4. }

image.png

上面 meta page 十六进制图中，第三行的 16 个字节就是描述的 root bucket 信息。root bucket 指向的 page id 为 4，page id 为 4 的页面是什么类型呢？ 我们可以通过如下 bbolt pages 命令看看各个 page 类型和元素数量，从下图结果可知，4 号页面为 leaf page。

  1. $ ./bbolt pages  ./infra1.etcd/member/snap/db
  2. ID       TYPE       ITEMS  OVRFLW
  3. ======== ========== ====== ======
  4. 0        meta       0
  5. 1        meta       0
  6. 2        free
  7. 3        freelist   2
  8. 4        leaf       10
  9. 5        free

leaf page

meta page 的 root bucket 直接指向的是 page id 为 4 的 leaf page， page flag 为 0x02， leaf page 它的磁盘布局如下图所示，前半部分是 leafPageElement 数组，后半部分是 key-value 数组。

image.png

leafPageElement 包含 leaf page 的类型 flags， 通过它可以区分存储的是 bucket 名称还是 key-value 数据。

  • 当 flag 为 bucketLeafFlag(0x01) 时，表示存储的是 bucket 数据，否则存储的是 key-value 数据，
  • leafPageElement 它还含有 key-value 的读取偏移量，key-value 大小，根据偏移量和 key-value 大小，我们就可以方便地从 leaf page 中解析出所有 key-value 对。
  • 当存储的是 bucket 数据的时候，key 是 bucket 名称，value 则是 bucket 结构信息。bucket 结构信息含有 root page 信息，通过 root page（基于 B+ tree 查找算法），你可以快速找到你存储在这个 bucket 下面的 key-value 数据所在页面。

branch page

boltdb 使用了 B+ tree 来高效管理所有子 bucket 和 key-value 数据，因此它可以支持大量的 bucket 和 key-value，只不过 B+ tree 的根节点不再直接指向 leaf page，而是 branch page 索引节点页。branch page flags 为 0x01。它的磁盘布局如下图所示，前半部分是 branchPageElement 数组，后半部分是 key 数组。

image.png

branchPageElement 包含 key 的读取偏移量、key 大小、子节点的 page id。根据偏移量和 key 大小，我们就可以方便地从 branch page 中解析出所有 key，然后二分搜索匹配 key，获取其子节点 page id，递归搜索，直至从 bucketLeafFlag 类型的 leaf page 中找到目的 bucket name。

这里可以回顾 “leaf page” 小节中所说的 bucket 名.

从上面分析过程中你会发现，boltdb 存储 bucket 和 key-value 原理是类似的，将 page 划分成 branch page、leaf page，通过 B+ tree 来管理实现。boltdb 为了区分 leaf page 存储的数据类型是 bucket 还是 key-value，增加了标识字段（leafPageElement.flags），因此 key-value 的数据存储过程我就不再重复分析了。

freelist

我们知道 boltdb 将 db 划分成若干个 page，那么它是如何知道哪些 page 在使用中，哪些 page 未使用呢？

答案是 boltdb 通过 meta page 中的 freelist 来管理页面的分配，freelist page 中记录了哪些页是空闲的。当你在 boltdb 中删除大量数据的时候，其对应的 page 就会被释放，页 ID 存储到 freelist 所指向的空闲页中。当你写入数据的时候，就可直接从空闲页中申请页面使用。

下面 meta page 十六进制图中，第四行的前 8 个字节就是描述的 freelist 信息，page id 为 3。我们可以通过 bbolt page 命令查看 3 号 page 内容，如下所示，它记录了 2 和 5 为空闲页，与我们上面通过 bbolt pages 命令所看到的信息一致。

image.png

  1. $ ./bbolt page  ./infra1.etcd/member/snap/db 3
  2. page ID:    3
  3. page Type:  freelist
  4. Total Size: 4096 bytes
  5. Item Count: 2
  6. Overflow: 0
  8. 2
  9. 5

下图是 freelist page 存储结构，pageflags 为 0x10，表示 freelist 类型的页，ptr 指向空闲页 id 数组。注意在 boltdb 中支持通过多种数据结构（数组和 hashmap）来管理 free page，这里我介绍的是数组。

image.png

Open 原理

  1. 首先它会打开 db 文件并对其增加文件锁，目的是防止其他进程也以读写模式打开它后，操作 meta 和 free page，导致 db 文件损坏。
  2. 其次 boltdb 通过 mmap 机制将 db 文件映射到内存中，并读取两个 meta page 到 db 对象实例中，然后校验 meta page 的 magic、version、checksum 是否有效，若两个 meta page 都无效，那么 db 文件就出现了严重损坏，导致异常退出。

Put 原理

为了方便你理解 B+ tree 查找、插入一个 key 原理，我给你构造了的一个 max degree 为 5 的 B+ tree，下图是 key r94 的查找流程图。

首先从 boltdb 的 key bucket 的 root page 里，二分查找大于等于 r94 的 key 所在 page，最终找到 key r9 指向的 page（流程 1）。r9 指向的 page 是个 leaf page，B+ tree 需要确保叶子节点 key 的有序性，因此同样二分查找其插入位置，将 key r94 插入到相关位置（流程二）。

image.png

当我们执行完一个 put 请求时，它只是将值更新到 boltdb 的内存 node 数据结构里，并未持久化到磁盘中。

事务提交原理

当你的代码执行 tx.Commit API 时，它才会将我们上面保存到 node 内存数据结构中的数据，持久化到 boltdb 中。下图我给出了一个事务提交的流程图，接下来我就分别和你简要分析下各个核心步骤。

image.png

首先从上面 put 案例中我们可以看到，插入了一个新的元素在 B+ tree 的叶子节点，它可能已不满足 B+ tree 的特性，因此事务提交时，第一步首先要调整 B+ tree，进行重平衡、分裂操作，使其满足 B+ tree 树的特性。上面案例里插入一个 key r94 后，经过重平衡、分裂操作后的 B+ tree 如下图所示。

image.png

由两层变为三层.

在重平衡、分裂过程中可能会申请、释放 free page，freelist 所管理的 free page 也发生了变化。因此事务提交的第二步，就是持久化 freelist。

事务提交的第三步就是将 client 更新操作产生的 dirty page 通过 fdatasync 系统调用，持久化存储到磁盘中。

最后，在执行写事务过程中，meta page 的 txid、freelist 等字段会发生变化，因此事务的最后一步就是持久化 meta page。