boltdb源码分析系列-Bucket

数据小冰

发布于 2022-08-15 15:03:25

1.8K00

代码可运行

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

运行总次数：0

代码可运行

Bucket是什么

Bucket翻译成中文为桶，正如其名，桶里面可以放东西。本文要介绍的Bucket是boltdb中的桶，它是一个数据结构。boltdb中每个Bucket是一颗B+树，它里面存放一批key-value数据对。

类比关系型数据库，每个Bucket可以看做关系型数据库中的table。一个boltdb中可以有多个Bucket, Bucket中可以嵌套Bucket.

在boltdb源码分析系列-内存结构文章中介绍了boltdb内存结构node，一个Bucket可以看做node的集合。总结起来，Bucket有如下要点：

每个Bucket是一颗B+Tree
一个Bucket中存储了一批key-value数据
Bucket类比做关系型数据库中的table概念
Bucket可以看做node的集合
Bucket中可以嵌套Bucket

Bucket结构体定义

Bucket结构中各个字段含义如下，关键的字段有*bucket和rootNode,它们描述的是的Bucket对应B+Tree的树根信息。

rootNode是这颗B+Tree的根节点node. 只要知道了树的根节点，就可以从根节点遍历获取所有的其他节点。在boltdb源码分析系列-内存结构文章中node结构定义中可以看到，它是一个递归的定义，node节点中的children记录它的孩子节点。所以Bucket只要记录根节点，便拥有了整颗树的信息。

*bucket是一个内嵌结构，它里面的核心字段是root，root是该Bucket所在page的id值。page描述的是boltdb的文件结构，即物理存储；node描述的是boltdb的内存结构，即逻辑结构。Bucket结构体中上面的两个字段分别从物理和逻辑层面描述了boltdb信息。

type Bucket struct {
 // B+树的根节点信息,主要是根节点的pgid
 *bucket
 // 操作Bucket的事务句柄
 tx       *Tx                
 // 子Bucket
 buckets  map[string]*Bucket 
 // 内联page
 page     *page              
 // Bucket管理的树的根节点
 rootNode *node              
 // node缓存
 nodes    map[pgid]*node    
    // 填充率
 FillPercent float64
}

这里再对Bucket结构体中其他字段做一个详细说明：

tx: 当前Bucket所属的事务
page: 内联Bucket的页引用，内置Bucket只有一个节点，即它的根节点，并且节点不存在独立的页面中，而是作为Bucket的value存在父Bucket所在页上，页引用是指向value中的内置页
nodes: Bucket中的node集合
FillPercent: Bucket中节点的填充百分比，该值与B+Tree的分裂有关，当节点中key的个数或者占用的空间大小超过整个node容量的某个值之后，节点必须分裂为两个节点
buckets是子Bucket的集合，因为Bucket中可以嵌套Bucket，所以需要一个字段记录子Bucket信息，这里通过一个map来记录，map的key为子Bucket的桶名，value为子Bucket对象指针。
内联page是指创建Bucket的时候，没有为它申请新的page来存储它，而是将它的信息存储在它的父Bucket中的叶子page中。内联的意义是，如果Bucket中存储key-value数据不大，将其内容存放在父Bucket的leaf page中，这样能够提升page的填充率，减少空间的浪费。
nodes缓存的是可能有影响的节点信息，当我们向Bucket中写入数据、删除数据或者更新数据的时候，并不是直接更新boltdb文件，而是更新它在内存中的node信息。因为所有对key-value的操作都是发生在叶子节点上。所以叶子节点会缓存到nodes，从根节点到叶子节点路径上的节点可能也会受到影响，它们也会缓存到nodes。这些nodes在事务提交的时候，会转换成dirty page，最后刷到磁盘上。

bucket与node关系

每个db文件，是一组树形组织的B+树。对于B+树来说，分支节点（branch node）用于查找，叶子节点(leaf node)存数据。

每个node都会属于某个桶，所以在node的结构体定义中有一个指向它所属桶的bucket字段。向boltdb中写入数据、修改数据或是删除数据，都是通过调用Bucket的方法，因为在逻辑上，Bucket是承载数据的地方。

通过Bucket查询key的value值

// 在桶中查找键值对为key的value
func (b *Bucket) Get(key []byte) []byte {
 ...
}

通过Bucket写入key-value数据

func (b *Bucket) Put(key []byte, value []byte) error {
 ...
}

通过Bucket删除key-value数据

func (b *Bucket) Delete(key []byte) error {
 ...
}

node结构体中记录有孩子节点的信息，所以node可以组成一颗树形结构，而Bucket只要记录了B+Tree的root node，相当于掌控了整颗B+树,所以Bucket结构中有一个rootNode字段，记录的是根节点信息。一个bolt db文件可以创建多个Bucket,并且Bucket可以嵌套，而每个Bucket是一颗B+Tree, 所以一个bolt db文件相当于多个B+Tree的集合。多个Bucket也需要一个伪根Bucket记录它们的信息，这个根Bucket就是tx.root，本文称之为根Bucket, 剩下的Bucket称之为普通Bucket.

经过前面的分析，将Bucket分为了根Bucket和普通Bucket两类。根Bucket所有叶子节点保存的都是子Bucket B+树根的page id.普通Bucket叶子节点可能是正常用户数据，也可能是子Bucket B+树根的page id.

根Bucket与普通Bucket关系如下,根Bucket即tx.root对外是不可见的。普通Bucket是用户程序可见的。

Bucket与node关系如下，下图中有4个Bucket,一个是根Bucket,其他3个都是普通Bucket. Bucket3是Bucket2的子Bucket.它们形成父子关系，从而所有Bucket形成树结构，通过根Bucket可以遍历所有子Bucket，但是注意，Bucket之间的树结构并不是B+Tree，而是一个逻辑树结构，如Bucket3是Bucket2的子Bucket，但并不是说Bucket3所在的节点就是Bucket2所在节点的子节点。

Bucket核心方法及实现

构造函数

返回一个Bucket对象，默认设置了Bucket填充率为50%，如果是读写事务，初始化两个map,它们分别记录子Bucket和Bucket中的node信息。

// Bucket构造函数
func newBucket(tx *Tx) Bucket {
 var b = Bucket{tx: tx, FillPercent: DefaultFillPercent}
 if tx.writable {
  b.buckets = make(map[string]*Bucket)
  b.nodes = make(map[pgid]*node)
 }
 return b
}

在桶中查找给定名称的Bucket

查找Bucket过程如下：

先查找缓存，Bucket对象中的map会记录它里面子Bucket信息，如果缓存中有，直接返回
遍历Bucket查找，需要先创建一个Bucket迭代器(Cursor),定位到叶子节点，然后通过key判断Bucket是否存在，以及是否是Bucket类型
创建一个Bucket对象缓存起来并返回

// 在Bucket中查找给定名称的bucket
func (b *Bucket) Bucket(name []byte) *Bucket {
 // 先从缓存中查找
 if b.buckets != nil {
  // 如果缓存中有，直接取缓存中的返回
  if child := b.buckets[string(name)]; child != nil {
   return child
  }
 }

 // 创建一个游标对象，用于对bucket进行遍历
 c := b.Cursor()
 // 在B+树中查找key为name的节点
 k, v, flags := c.seek(name)

 // 如果不存在或者不是一个bucket节点
 if !bytes.Equal(name, k) || (flags&bucketLeafFlag) == 0 {
  return nil
 }

 // 走到这里，说明找到了给定名称的桶，然后创建一个Bucket
 var child = b.openBucket(v)
 if b.buckets != nil {
  // 缓存起来
  b.buckets[string(name)] = child
 }

 return child
}

创建桶

创建桶的处理过程比较复杂：

对异常情况进行判断，包括db是否已关闭，是否是读写事务，桶的名称是否合法
检查桶是否已经存在，创建一个Bucket迭代器，对Bucket进行遍历，查找Bucket是否存在，如果桶已经存在，返回错误
桶不存在，创建一个Bucket, 加入迭代器游标位置，其中key是子Bucket的名字，value是子Bucket的序列化结果
将当前Bucket的page字段置空，因为当前Bucket包含了刚创建的子Bucket，它不会是内置Bucket
通过b.Bucket()方法按子Bucket的名字查找子Bucket并返回结果,为啥不直接返回上面的bucket呢？因为要设置bucket.root值和bucket.page

// 创建一个桶，如果名称已存在，则会返回错误
func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
 // 异常情况处理：1 db已关闭   2 非读写事务，不支持创建桶  3 桶的名称为空
 if b.tx.db == nil {
  return nil, ErrTxClosed
 } else if !b.tx.writable {
  return nil, ErrTxNotWritable
 } else if len(key) == 0 {
  return nil, ErrBucketNameRequired
 }

 // 创建一个游标对象
 c := b.Cursor()
 // 在B+中查找key
 k, _, flags := c.seek(key)

 // key已存在
 if bytes.Equal(key, k) {
  // key已经存在并且是个桶
  if (flags & bucketLeafFlag) != 0 {
   return nil, ErrBucketExists
  }
  // 桶的名称不能和数据中的key重名
  return nil, ErrIncompatibleValue
 }

 // 创建一个新的bucket
 var bucket = Bucket{
  bucket:      &bucket{},
  rootNode:    &node{isLeaf: true},
  FillPercent: DefaultFillPercent,
 }
 var value = bucket.write()

 // 对key进行深度拷贝，传入的key是用户空间的，防止用户后续修改key
 key = cloneBytes(key)
 // 将bucket加入到节点c.node()中
 c.node().put(key, key, value, 0, bucketLeafFlag)

 // 当前桶中已有子桶，不能在被内联
 b.page = nil
 // 为啥不直接返回上面的bucket呢？主要是要设置bucket.root的值
 return b.Bucket(key), nil
}

删除桶

删除桶先检查桶是否存在，如果桶存在，需要递归将要删除桶中包含的子桶信息删除，然后才能删除，并且需要释放待删除桶关联的page,放入freelist page中。

func (b *Bucket) DeleteBucket(key []byte) error {
 // 异常情况检查
 if b.tx.db == nil {
  return ErrTxClosed
 } else if !b.Writable() {
  return ErrTxNotWritable
 }

 // 创建一个迭代器对桶进行遍历查找给定的key
 c := b.Cursor()
 k, _, flags := c.seek(key)

 // 桶不存在
 if !bytes.Equal(key, k) {
  return ErrBucketNotFound
 } else if (flags & bucketLeafFlag) == 0 {
  // 存在给定名称的key,但它不是桶的名字
  return ErrIncompatibleValue
 }

 // 递归删除即将要删除桶的所有的子bucket
 child := b.Bucket(key)
 err := child.ForEach(func(k, v []byte) error {
  if v == nil {
   if err := child.DeleteBucket(k); err != nil {
    return fmt.Errorf("delete bucket: %s", err)
   }
  }
  return nil
 })
 if err != nil {
  return err
 }

 // 删除缓存map中桶
 delete(b.buckets, string(key))

 child.nodes = nil
 child.rootNode = nil
 // 释放桶关联的page
 child.free()

 // 从叶子节点c中删除该桶的key
 c.node().del(key)

 return nil
}

查找桶中数据

查找桶中数据，只是在当前桶中查找，并不会递归查找子桶，整个查找过程是通过迭代器完成的，迭代器工作方法在下一篇文章中详细介绍。

// 在桶中查找键值对为key的value
func (b *Bucket) Get(key []byte) []byte {
 k, v, flags := b.Cursor().seek(key)

 // key是一个桶的名字
 if (flags & bucketLeafFlag) != 0 {
  return nil
 }

 // key不存在
 if !bytes.Equal(key, k) {
  return nil
 }
 return v
}

向桶中放入数据

向桶中放入数据都是添加在B+Tree的叶子节点上，所以先要定位到待插入的叶子节点，这个过程是通过迭代器Cursor实现的。如果key已存在，相当于更新value，否则插入key-value，注意一点，对key是深拷贝，value是浅拷贝。

func (b *Bucket) Put(key []byte, value []byte) error {
 // 异常情况的校验：1 bucket关联的是读写事务，2 key不能为空 不能过长  3 value不能过长
 if b.tx.db == nil {
  return ErrTxClosed
 } else if !b.Writable() {
  return ErrTxNotWritable
 } else if len(key) == 0 {
  return ErrKeyRequired
 } else if len(key) > MaxKeySize {
  return ErrKeyTooLarge
 } else if int64(len(value)) > MaxValueSize {
  return ErrValueTooLarge
 }

 // 创建一个游标对象，对Bucket进行遍历，查找键值对为key的数据
 c := b.Cursor()
 k, _, flags := c.seek(key)

 // key是一个桶的名字，返回不兼容
 if bytes.Equal(key, k) && (flags&bucketLeafFlag) != 0 {
  return ErrIncompatibleValue
 }

 // 运行到这里，key有可能存在，也有可能不存在，不存在会创建一个key-value键值对，
 // 存在会更新原来key的value，这些处理都是在put函数中实现的
 // NOTE 对key是深拷贝，对value是浅拷贝
 key = cloneBytes(key)
 c.node().put(key, key, value, 0, 0)

 return nil
}

删除桶中数据

删除数据，也需要定位到key所在的叶子节点，然后将其删除。

func (b *Bucket) Delete(key []byte) error {
 if b.tx.db == nil {
  return ErrTxClosed
 } else if !b.Writable() {
  return ErrTxNotWritable
 }

 // 创建一个游标对象进行查询
 c := b.Cursor()
 _, _, flags := c.seek(key)

 // 如果存在同名的bucket
 if (flags & bucketLeafFlag) != 0 {
  return ErrIncompatibleValue
 }

 // 进行真正删除
 c.node().del(key)

 return nil
}

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

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

node.js