走进blotdb的数据组织

blotdb【etcd底层的kv存储】，本文改编自作者：青藤木鸟 www.qtmuniao.com/2020/11/29/…, 转载请注明出处

BoltDB 是一个单机的支持事务的KV存储，etcd v3 存储中提供的事务就是基于 BoltDB 的事务实现的。BlotDB 支持事务和多版本机制。

概述

• no 归档功能
• shadow page
• 使用mmap将内存与磁盘建立映射，由OS管理磁盘page load到内存的过程，大大减少了boltdb手动管理的复杂度。

open init

• 创建和删除Bucket属于写事务
• 操作key/value包括：新建/更新/删除/查询。所有的key/value对都必须属于某个具体的Bucket. 因此操作key/value之前必须找到Bucket对象。

page.go: 磁盘上的page layout，包括meta page, freelist page, branch page, leaf page。
node.go: 磁盘上的page反序列化到内存之后的数据结构，也作为B+树节点。
freelist.go: page管理, 支持page申请、释放、回滚等操作。
cursor.go: 用于访问B+树的迭代器
bucket.go: Bucket数据结构，支持创建/删除子Bucket、新建/更新/删除kv数据。
db.go.go: 用于访问DB, 支持打开/关闭DB、创建读/写事务、db file自动扩容。

数据组织

在文件系统上，boltdb 采用页（page）的组织方式，将一切数据都对齐到页；

在内存中，boltdb 按 B+ 树组织数据，其基本单元是节点（node），一个内存中的树节点对应文件系统上一个或者多个连续的页。

• 顶层组织

  • 每个db对应一个文件

  • 逻辑：

    • 一个db包含多个桶 = 多个命名空间，桶可以无限嵌套
    • 每个桶对应一棵B+树

  • 物理

    • 一个db文件是按页为单位进行顺序存储
    • 一个页的大小和操作系统页大小保持一致（4kb）

• 页和节点（连续的

  数据页

  序列化加载到内存中就成为一个数据节点）

  • 种类

    • 元信息页
    • 空闲列表页
    • 两种数据页 —— B+树中间节点和叶子节点

  • 总结：在文件系统上线性组织的数据页，通过页内指针，在逻辑上组织成了一棵二维的 B+ 树，该树的树根保存在元信息页中，而文件中所有其他没有用到的页的 id 列表，保存在空闲列表页中。

• 页格式和内存表示

  • 枚举标记表示页类型
  • 每个页都由定长的header和数据部分组成

• 元信息页 —— meta

  • only two 【pageid = 0 和 1】
  • 在元信息页中，ptr指向的内容并非元素列表，而是整个db的元信息的各个字段

• 空闲列表页 —— freelistPage

  • 保存在db使用过程中由于修改操作而释放的页的id列表

    • 可以分配的空闲页列表ids
    • 按照事务id分别记录了在对应事务期间新增的空闲页列表

  • pending单独记录，主要是为了做MVCC的事务

    • 回滚时，对应事务代释放的空闲页列表要从pending项中删除
    • 某个写事务已经提交，但可能仍有一些毒食物仍然在使用其刚刚释放的页，因此不能立即做分配

  • 空闲列表转化为page

    • freelist通过write函数，在事务提交时将自己写入给定的页进行持久化。

    • ？pending和ids合并写入

      • write函数是在写事务提交时调用，写事务时串行的，因此pending中对应的写事务都已经提交
      • 写入文件是为了应对奔溃后重启，而重启没有任何读操作，所以不用担心有读事务还在用刚释放的页

  • 空闲列表从page中加载

    • 数据库重启时，回首先从两个元信息页恢复出一个合法的元信息。然后根据元信息中的freelist字段，找到存储freelist页的启示地址，进而恢复到内存中

  • 空闲列表分配

    • 分配单位是页，分配策略是首次适应

• 叶子节点页 —— leafPage

  • 对应B+树中的叶子节点，存储的元素可以是普通的kv数据、该bucket的subbucket。

    • 页中存储的元素可以是某个bucket中的一条用户数据
    • 页中的一个元素为该db中的某个subbucket

  • 元素头和元素本身分开存储

  • pos存储的是元素头的起始地址到元素的起始地址的相对偏移量，而非以ptr指针为起始地址的绝对偏移量

• 中间节点页 —— branchPage

  • 页中保存的数据的value是page id，即该中间节点在哪些key上的分支分别指向的page。

• 转换流程

  • 使用mmap将db文件映射到内存空间。在构建树并且访问过程中，按需将对应的页加载到内存里，并且利用操作系统的页缓存策略进行替换

• 文件增长

  • 初始化——内存4个页（4*4k=16k),两个元信息页，一个空的空闲列表页和一个空的叶子节点页。
  • 增加——boltdb 首先会去 freelist 中找有无可重复利用的页，如果没有，就只能进行 re-mmap（先 mumap 在 mmap），扩大 db 文件。每次扩大会进行倍增（因此从 16K * 2 = 32K 开始），到达 1G 后，再次扩大会每次新增 1G。
  • 限制——在 32位 机器上文件最大不能超过 maxMapSize= 2G；在 64 位机器上，文件上限为 256T。

• 读写流程

  • 在打开一个已经存在的 db 时，会首先将 db 文件映射到内存空间，然后解析元信息页，最后加载空闲列表。
  • 在 db 进行读取时，会按需将访问路径上的 page 加载到内存，并转换为 node，进行缓存。
  • 在 db 进行修改时，使用 COW 原则，所有修改不在原地，而是在改动前先复制一份。如果叶子节点 node 需要修改，则 root bucket 到该 node 路径上所涉及的所有节点都需要修改。这些节点都需要新申请空间，然后持久化

• 数据库初始化：打开数据库时，会渐次进行以下操作：

  1. 利用 mmap 将数据库文件映射到内存空间。
  2. 解析元信息页，获取空闲列表页 id 和 root bucket 页 id。
  3. 依据空闲列表页 id ，将所有空闲页列表载入内存。
  4. 依据 root bucket 起始页地址，解析 root bucket 根节点。
  5. 根据读写需求，从树根开始遍历，按需将访问路径上的数据页（中间节点页和叶子节点页）载入内存成为节点（node）。

• 小结：

  • boltdb 在数据组织方面只使用了两个概念：页（page） 和节点 （node）。每个数据库对应一个文件，每个文件中包含一系列线性组织的页。页的大小固定，依其性质不同，分为四种类型：元信息页、空闲列表页、叶子节点页、中间节点页。

  • 节点分两种类型：中间节点（branch node）和叶子节点（leaf node）。

  • 另外需要注意的是，bucket 可以进行无限嵌套，boltdb 使用独特的索引设计组织多个 bucket 以及单个 bucket 内的 B+ 树索引。

    BoltDB 在逻辑上以桶来组织数据，一个桶可以看做一个命名空间，是一组 KV 对的集合，和对象存储的桶概念类似。每个桶对应一棵 B+ 树，命名空间是可以嵌套的，因此 BoltDB 的 Bucket 间也是允许嵌套的。在实现上来说，子 bucket 的 root node 的 page id 保存在父 bucket 叶子节点上实现嵌套。