boltdb源码分析系列-内存结构

数据小冰

发布于 2022-08-15 15:02:47

4150

发布于 2022-08-15 15:02:47

文章被收录于专栏：数据小冰

BoltDB内存结构

在boltdb源码分析系列-文件结构文章中讲述了BoltdDB文件是按page位单位进行物理存储的，当我们Open打开一个BoltDB文件之后，文件内容会被加载到内存。文件中的page页在内存中以node来组织，如果说page是BoltDB物理存储单元，那么node是BoltDB的逻辑单元，是page在内存中的表示。

node

node是page在内存中逻辑表示，现在我们来看node的构成，它的结构体定义如下。

type node struct {
 // 该node节点属于哪个桶
 bucket     *Bucket
 // 是否是叶子节点
 isLeaf     bool
 // 是否平衡，即节点中的元素是否在一定范围，不平衡，则需要合并
 unbalanced bool
 // 节点中的元素是否太多了，需要分裂, spilled为true表示已经分裂过了
 spilled    bool
 key        []byte
 pgid       pgid
 // 当前节点的父节点
 parent     *node
 // 孩子节点
 children   nodes
 // 节点中存储的数据
 inodes     inodes
}

node中各个字段与page构成各字段没有明确的对应关系。为了好理解，小编将node中所有的字段分成两类，一类是描述的是page中的内容，另一类是操作控制信息。下面对这两类字段分别进行详细介绍。

在介绍node是如何描述page内容之前，先说一点，就是这里的node描述的只是branch page和leaf page在内存中表示。在boltdb源码分析系列-文件结构中介绍了BoltDB文件由meta page、freelist page、branch page和leaf page。那meta page和freelist page在内存是怎么表示的呢？因为meta page只有固定的两个page,freelist page一般是一个，并且meta page在db文件的最开头位置，所以meta和freelist page直接放在了DB结构体中，也很好理解，一个db文件它们是固定的，放在这里操作也方便。

下面是DB的结构体定义，这里只抽取出了与meta page和freelist page相关信息，可以看到，两个meta page内容保存在meta0和meta1中，freelist page保存在freelist。

type DB struct {
 ...
    // meta0 保存 mate page1信息
 meta0    *meta
    // meta1 保存 mate page2信息
 meta1    *meta
 ...
    // freelist存储freelist page信息
 freelist *freelist
 ...
}

BoltDB有四种类型的page,现在就剩下branch page和leaf page了。它们在内存中的信息保存在node结构中。

现在开始分析node是如何描述page内容的，branch page和leaf page格式基本是相似的。page header中的id对应到node中是pgid，node中isLeaf表示是分支节点还是叶子节点，对应到page header中的flags字段。page中的data信息存在node中的inodes中，因为inodes信息是结构化的，它是一个切片数组，可以直接定位第几个key以及它的内容。通过inodes切片的长度我们就知道了元素的个数，所以page header中的count值隐含在inodes中，同理branchPageElements和leafPageElements信息也隐含在inodes中。所以node结构完整的描述了page内容。

node结构中另一类是字段是方便控制操作用的，这个属于附加信息，用在读写、查询各种逻辑操作上。像指向父节点node的parent指针，以及标识节点是否进行过平衡操作的unbalanced，节点是否进行过分裂的spilled。

node与page相互转换

当我们打开一个BoltDB文件之后，它的信息(page)会被加载到内存以node表示。进行事务操作，无论执行写入key-value，还是修改已有key的value值等操作，都是对内存中的node进行修改，最后执行事务Commit操作时，内存中的node才会写入磁盘永久存储。这个过程涉及到node和page相互转换，下面结合源码分析这个过程。

「page转成node的过程可以看做node的反序列化，node转成page的过程可以看做node序列化」，就像对内存中的结构体对象进行json序列化和反序列化操作那样，可以将一个对象序列化成二进制，相反，也可以将二进制反序列化成结构体对象。

page转成node

将page转成node操作由方法func (n *node) read(p *page)完成，该方法在node.go文件中，具体实现如下：

// 根据一个page页初始化节点n，相当于对node进行反序列化
func (n *node) read(p *page) {
 // 赋值page id
 n.pgid = p.id
 // 是否是叶子节点
 n.isLeaf = ((p.flags & leafPageFlag) != 0)
 // 节点中元素的大小，开辟空间
 n.inodes = make(inodes, int(p.count))

 // 填充节点中的元素数据
 for i := 0; i < int(p.count); i++ {
  inode := &n.inodes[i]
  if n.isLeaf {
   // 叶子节点有flags-key-value信息
   elem := p.leafPageElement(uint16(i))
   inode.flags = elem.flags
   inode.key = elem.key()
   inode.value = elem.value()
  } else {
   // 内部节点只有key-pgid信息，可以把pgid理解为内部节点的value信息，它指向的是孩子节点的page id
   elem := p.branchPageElement(uint16(i))
   inode.pgid = elem.pgid
   inode.key = elem.key()
  }
  _assert(len(inode.key) > 0, "read: zero-length inode key")
 }

 // 初始节点n的key值为元素中第一个key-value中的key值
 if len(n.inodes) > 0 {
  n.key = n.inodes[0].key
  _assert(len(n.key) > 0, "read: zero-length node key")
 } else {
  n.key = nil
 }
}

read处理过程非常简单，根据page信息给node各字段赋值。根据page中count的值，开辟对应大小的inodes空间，inode中填充的信息根据page的类型有所不同，如果是branch page，inode中装载的是key和pgid信息，如果是leaf page，inode中装载的是key-value信息。

核心点在于从page中获取key-value数据的过程，得益于page数据结构非常好的定义，运用了unsafe.Pointer将p.ptr指针，先转成branchPageElement或leafPageElement数组的「数组指针」，最后获取下标为index处的地址返回。对应到下面的源码。

func (p *page) branchPageElement(index uint16) *branchPageElement {
 return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
}

func (p *page) leafPageElement(index uint16) *leafPageElement {
 n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
 return n
}

成功获取到page中每个branchPageElement或leafPageElement之后，就可以通过它直接来获取key-value数据了。这个过程利用elem中记录的偏移量pos，以及key的长度，运用unsafe.Pointer黑科技，提取出key-value数据。

func (n *leafPageElement) key() []byte {
 buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
 return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize:n.ksize]
}

func (n *leafPageElement) value() []byte {
 buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
 return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos+n.ksize]))[:n.vsize:n.vsize]
}

func (n *branchPageElement) key() []byte {
 buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
 return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
}

node转成page

node转成page的过程与上面的过程刚好相反，在func (n *node) write(p *page)方法中实现，源码也在node.go文件中。

write操作是根据node结构中字段值初始化page的过程，例如根据n.isLeaf是否是叶子节点初始化p(page)的flags信息，根据n.inodes的大小初始化p.count。这里可以看到，inodes的大小是小于65535的，如果超过了，直接panic，这说明page中的元素的个数是不能超过这个数值的。

最核心的操作就是定位到page data中的位置，将inode中的信息写入，通过elem:=p.leafPageElement(uint16(i))或elem:=p.branchPageElement(uint16(i))操作，定位到了要操作的内存地址，返回的elem是指针，所以后续对elem的赋值内容，都填充到page中。在填充page data的时候，先填充描述key-value的元数据信息branchPageElements和leafPageElements，最后通过copy深拷贝填充key-value数据。

// 上面过程的逆过程，根据节点n的内容初始page,相当于对node进行序列化
func (n *node) write(p *page) {
 // 初始化是否是页节点标记位
 if n.isLeaf {
  p.flags |= leafPageFlag
 } else {
  p.flags |= branchPageFlag
 }
    // 节点中的元素个数超过2^16=65535个，溢出了
 if len(n.inodes) >= 0xFFFF {
  panic(fmt.Sprintf("inode overflow: %d (pgid=%d)", len(n.inodes), p.id))
 }
 p.count = uint16(len(n.inodes))

 // 节点n中没有元素，直接返回，因为没有要处理的元素
 if p.count == 0 {
  return
 }

 // 定位到key-value数据要写入的位置，循环写入key-value
 b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[n.pageElementSize()*len(n.inodes):]
 for i, item := range n.inodes {
  _assert(len(item.key) > 0, "write: zero-length inode key")

  // 叶子节点
  if n.isLeaf {
   // elem是个指针，给elem赋值，相当于对p中的数据进行修改
   // 修改的是p中描述元素的元素头信息，即元素的key-value的起始位置，类型，以及key和value的大小
   elem := p.leafPageElement(uint16(i))
   elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
   elem.flags = item.flags
   elem.ksize = uint32(len(item.key))
   elem.vsize = uint32(len(item.value))
  } else {
   // 处理分支节点
   elem := p.branchPageElement(uint16(i))
   elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
   elem.ksize = uint32(len(item.key))
   elem.pgid = item.pgid
   _assert(elem.pgid != p.id, "write: circular dependency occurred")
  }
        
  // See: https://github.com/boltdb/bolt/pull/335
  klen, vlen := len(item.key), len(item.value)
  // b的空间不能装下key-value数据，进行扩容
  if len(b) < klen+vlen {
   b = (*[maxAllocSize]byte)(unsafe.Pointer(&b[0]))[:]
  }

  // 拷贝数据key
  copy(b[0:], item.key)
  b = b[klen:]
  // 拷贝数据value
  copy(b[0:], item.value)
  b = b[vlen:]
 }

 // DEBUG ONLY: n.dump()
}

上面详细分析了branch page、leaf page与node转换过程，此过程概括起来用下面的这种图描述。

DB.meta与meta page相互转换

前面说的node与page相互转换实际是branch page和leaf page与node相互转换，因为meta page和freelist page中的data比较特别，所以它们加载到内存后是存放在DB.meta字段和DB.freelist字段中的。

本小节分析meta page与DB.meta之间的相互转换。两个meta page与DB.meta0和DB.meta1是一一对应的。将meta page转换为DB.meta的处理在db.go文件func (db *DB) mmap(minsz int) error方法中。下面只抽取出了相关的逻辑。

func (db *DB) mmap(minsz int) error {
 ...
 // Save references to the meta pages.
 // 加载meta page到内存中的db.meta0和meta1中
 db.meta0 = db.page(0).meta()
 db.meta1 = db.page(1).meta()

 err0 := db.meta0.validate()
 err1 := db.meta1.validate()
 ...
}

// 根据id，计算出数据偏移地址，获取起始地址处page大小的数据
func (db *DB) page(id pgid) *page {
 pos := id * pgid(db.pageSize)
 return (*page)(unsafe.Pointer(&db.data[pos]))
}

两个meta page的id分别是0和1，所以直接通过db.page()传入pgid，通过unsafe.Pointer获取到了meta page0和meta page1。然后调用page的meta方法获取page data数据。

上面分析了meta page转换为DB.meta过程，下面分析它的逆过程，即如何将DB.meta转为meta page.对数据库有更新操作，元数据meta才会有变化，才会将DB.meta转成page，刷新到磁盘中。

BoltDB事务操作分为只读事务和读写事务，只读事务不会更新数据库内容，所以不会更新meta page, 只有读写事务会更新meta page. 所以内存中DB.meta转换为meta page，最后写入磁盘，这个过程在事务提交tx.Commit处理的。

// 元数据写入磁盘
func (tx *Tx) writeMeta() error {
 // 开辟一个4KB大小的字节数组
 buf := make([]byte, tx.db.pageSize)
 // 将字节数组转为page,page和buf都是同一片空间，转成page，是为了
 // 方便向里面填充值
 p := tx.db.pageInBuffer(buf, 0)
 // 将DB.meta写入p(page)中
 tx.meta.write(p)

 // 将buf,也就是meta page写入到磁盘文件上
 if _, err := tx.db.ops.writeAt(buf, int64(p.id)*int64(tx.db.pageSize)); err != nil {
  return err
 }
 ...
}

下面是真正meta中的数据转为page过程，处理非常简单，就是将m.txid赋值给p.id，设置p的flags属性，填充p的ptr内容。

// 将meta中的内容输出到page中
func (m *meta) write(p *page) {
 ...
    
 // 轮流写入，一次写入meat page0，另一次写入meta page1
 p.id = pgid(m.txid % 2)
 // 设置flags为元数据页标识
 p.flags |= metaPageFlag

 // 计算数据校验和
 m.checksum = m.sum64()
 // 将m中的内容填充到p.ptr中
 m.copy(p.meta())
}

DB.freelist与freelist page相互转换

DB.freelist与freelist page的相互转换逻辑在freelist.go文件中，现在来看详细的转换处理流程。

将freelist page转换为DB.freelist的过程是通过func (f *freelist) read(p *page)实现的。处理过程就是根据page中字段值填充freelist，对应p.count有一种特殊情况，如果它的值为0xFFFF，这是一个特殊的标记，真正的数量存储在p.ptr的第一个8byte中。

func (f *freelist) read(p *page) {
 // 获取page data中存储的pgid的数量，如果p.count的值为0xFFFF，这是一个特殊的标记
 // 真正的数量存储在p.ptr的第一个8byte中
 idx, count := 0, int(p.count)
 if count == 0xFFFF {
  idx = 1
  count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
 }

 // count为0，说明db文件中没有空闲页，即没有任何page的浪费
 if count == 0 {
  f.ids = nil
 } else {
  // 获取所有的pgid值
  ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
  // 为f.ids开辟装载pgid的内存空间
  f.ids = make([]pgid, len(ids))
  // pgid值保存到f.ids中，缓存起来
  copy(f.ids, ids)

  // 将f.ids值按升序排序
  sort.Sort(pgids(f.ids))
 }

 // 将f.ids中的pgid缓存到f.cache中，f.cache是一个map类型，方便查找
 f.reindex()
}

将DB.freelist转换为freelist page的过程，即freelist的序列化过程是在func (f *freelist) write(p *page) error实现的。处理过程非常简单，下面代码做了注解，相信每个同学都看得懂，这里就不在进一步说明了。

func (f *freelist) write(p *page) error {
 // 设置flags为空闲列表页标识
 p.flags |= freelistPageFlag

 // 获取空闲的pgid数量
 lenids := f.count()
 if lenids == 0 {
  // 没有空闲页，p.count为0
  p.count = uint16(lenids)
 } else if lenids < 0xFFFF {
  // 空闲页的数量小于65535，数量直接保存在page的count中
  p.count = uint16(lenids)
  // 填充page的ptr
  f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:])
 } else {
  // 空闲页的数量大于等于65535,将空闲页的数量保存在page的ptr的第一个8byte处
  p.count = 0xFFFF
  ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
  // 填充page的ptr,偏移8个字节开始
  f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
 }

 return nil
}

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

原始发表：2021-12-02，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js