golang源码分析:boltdb(4)

golangLeetcode

发布于 2023-09-06 19:30:09

2820

发布于 2023-09-06 19:30:09

通过前面源码分析，我们差不多了解了boltdb的核心数据结构了，逻辑视图上是通过Bucket组建的嵌套结构来管理数据的，每一层都可以存储一一系列key和value，也是使用boltdb的用户需要关注的。物理视图上是通过node来定义B+树来管理磁盘页的。下面我们详细分析下它们在内存以及磁盘上存储结构。

先从磁盘上的存储结构开始，每一个boltdb对应一个文件，文件按照 page size(一般为 4096 Bytes) 划分为 page。它有三个特殊的page和通用的存储page组成，分别是：

保存 metadata的前两个page
特殊的 page 保存 freelist，存放空闲 page 的 id
构成B+树的剩余page

在构成B+树的page中又可以分成两类页面，分支页和叶子页。

branch: 每对 key/val 指向一个子节点，key 是子节点的起始 range，val 存放子节点的 page id；
leaf: 每对 key/val 存放数据，没有指针指向 sibiling node；通常的 B+ 树多出的一个指针会指向 sibiling node。可以看出，和标准的B+树的区别是叶子节点没有指向兄弟页面的指针，因为这对于k/v类型的存储boltdb来说是不必要的。内存中B+树的每个节点和node对应，一个节点包含多个连续的页，在磁盘上，它的结构和page对应，在page中定义了每个页面的头信息，具体如下：

type page struct {
id    pgid // page id
flags uint16 // 区分不同类型的 page
count    uint16 // page data 中的数据个数
overflow uint32 // 若单个 page 大小不够，会分配多个 page
ptr uintptr // 存放 page data 的起始地址
}

ptr 是保存数据的起始地址，不同类型 page 保存的数据格式也不同，共有4种 page, 通过 flags 区分:

meta page: 存放 db 的 meta data。

freelist page: 存放 db 的空闲 page。

branch page: 存放 branch node 的数据。

leaf page: 存放 leaf node 的数据。

// typ returns a human readable page type string used for debugging.
func (p *page) typ() string {
  if (p.flags & branchPageFlag) != 0 {
    return "branch"
  } else if (p.flags & leafPageFlag) != 0 {
    return "leaf"
  } else if (p.flags & metaPageFlag) != 0 {
    return "meta"
  } else if (p.flags & freelistPageFlag) != 0 {
    return "freelist"
  }
  return fmt.Sprintf("unknown<%02x>", p.flags)
}

node是B+ 树的单个结点，访问结点时首先将 page 的内容转换为内存中的 node，每个 node 对应一个或多个连续的 page。重点关注下page结构提字段的属性。

id：页面ID。
flags：标志位，不同类型的页面用不同的标志位来区分。分为：metaPageFlag、freelistPageFlag、branchPageFlag、leafPageFlag。
count：页面中存储的数据数量，仅在页面类型是branch以及leaf的时候起作用。
overflow：当前页面如果还不够存放数据，就会有后续页面，这个字段表示后续页面的数量。
ptr：指向页表头数据结尾，也就是页面数据的起始位置。一个页面的页表头由前面的id、flags、count和overflow字段构成，而ptr并不是页表头的一部分。

从磁盘解析出上述原始结构后，我们还需要根据页面类型，解析出ptr指向的具体数据，将它放入inodes，并根据inodes的具体信息，来进行对应的node的初始化操作，如果是叶子node，需要将对应的key和value取出来，根据value的类型判断是不是嵌套的Bucket；如果是branch节点，需要根据key对应的pageid加载对应的page获取孩子节点。

每种类型的页面中具体存储的数据结构定义如下：

叶子页

// leafPageElement represents a node on a leaf page.
type leafPageElement struct {
  flags uint32
  pos   uint32
  ksize uint32
  vsize uint32
}

分支页

// branchPageElement represents a node on a branch page.
type branchPageElement struct {
  pos   uint32
  ksize uint32
  pgid  pgid
}

meta页


type meta struct {
  magic    uint32
  version  uint32
  pageSize uint32
  flags    uint32
  root     bucket
  freelist pgid
  pgid     pgid
  txid     txid
  checksum uint64
}

freelist

// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
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.
}

而PageInfo定义类页头信息

// PageInfo represents human readable information about a page.
type PageInfo struct {
  ID            int
  Type          string
  Count         int
  OverflowCount int
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-05-27，如有侵权请联系 cloudcommunity@tencent.com 删除

存储