Boltdb数据结构-二进制存储
概览
本文结合Boltdb的数据结构预览分析Boltdb的二进制存储文件格式。
示例程序创建一个db，创建MyBucket并写入两个kv，生成my.db文件后用二进制文件预览打开进行分析。
func TestMy(t *testing.T) {
// Open the my.db data file in your current directory.
// It will be created if it doesn't exist.
db, err := bolt.Open("my.db", 0600, nil)
if err != nil {
log.Fatal(err)
}
defer db.Close()
err = db.Update(func(tx *bolt.Tx) error {
b, err := tx.CreateBucketIfNotExists([]byte("MyBucket"))
if err != nil {
return fmt.Errorf("create bucket: %s", err)
}
err = b.Put([]byte("name1"), []byte("nicky1"))
if err != nil {
return err
}
err = b.Put([]byte("name2"), []byte("nicky2"))
if err != nil {
return err
}
return nil
})
if err != nil {
log.Fatal(err)
}
}
page
page(页)是Boltdb存储的基本单位，由一块固定大小的存储区域组成。我的操作系统默认页大小为16384(16K)即0x4000，因此0x0000~0x4000为第0页，0x4000~0x8000为第1页，以此类推。
Boltdb的页包括页头和一个任意大小的指针ptr。页头中标识了页类型、元素数量、溢出大小等信息，ptr用来指向页头的结束地址，或者说是页内容的开始地址，这样代码中可以用ptr跳过页头直接获取页面的内容。
值得注意的是除了物理的、实际存在的page，boltdb还会构造虚拟页来辅助存储，这些虚拟页并没有真实的页Id，在后续的bucket中会看到。
meta
第0x00，0x01页是meta页，负责存储meta信息，为什么有两个meta页我们在分析完Boltdb事务后会了解。
meta0存储了rootBucket的值。Boltdb的数据存储是一颗B+树，rootBucket指向这颗B+树的根节点所在的页id，示例中就是id为0x04的page。
meta1与meta0不同的值用红色标出。由于示例程序比较简单，meta1中的几个关键值(pgid,txid,rootBucket)实际上都是db在初始化后赋予的默认值，没有被更改。
可以看到，meta页除了包括db的基础元信息如版本号、页大小等，还包括重要的根节点、事务id等信息。
freelist
leaf
rootBucket
来到0x04页，也就是meta0中rootBucket所在的页面，我们看看在数据量较少的时候，B+树是如何存储的。
rootBucket存储在一个leafPage中，目前包括一个元素，这个元素是一个类型为bucket的leafPageElement，即概览图中的bucketElm。
为什么bucketElm的val是0x56=86个字节呢？首先bucketElm与一般leafPageElement不同，value是一个结构体，在代码中表示为小写的bucket struct，包括一个8字节的root和一个8字节的序列号。 而一般leafPageElement的value是用户写入的value。
其次由于我们的kv少，符合bucket内联(inline page)的条件，root值为0。用户数据被作为一个虚拟页直接拼在了当前页的后面，这个页的大小也会被统计到value里面。
// Bucket represents a collection of key/value pairs inside the database.
type Bucket struct {
*bucket
tx *Tx // the associated transaction
buckets map[string]*Bucket // subbucket cache
page *page // inline page reference
rootNode *node // materialized node for the root page.
nodes map[pgid]*node // node cache
// Sets the threshold for filling nodes when they split. By default,
// the bucket will fill to 50% but it can be useful to increase this
// amount if you know that your write workloads are mostly append-only.
//
// This is non-persisted across transactions so it must be set in every Tx.
FillPercent float64
}
// bucket represents the on-file representation of a bucket.
// This is stored as the "value" of a bucket key. If the bucket is small enough,
// then its root page can be stored inline in the "value", after the bucket
// header. In the case of inline buckets, the "root" will be 0.
type bucket struct {
root pgid // page id of the bucket's root-level page
sequence uint64 // monotonically incrementing, used by NextSequence()
}
有了这些基础，我们分析下val的总长度：
len(value) = len(bucket struct) + len(虚拟页)
= 8(root) + 8(sequence) + len(两个kv的leafPage)
= 8 + 8 + len(PH) + 2 * len(leafPageElement) + len('name1' + 'nicky1' + 'name2' + 'nicky2')
= 8 + 8 + 16 + 2*16 + 22 = 86
总结
到这里Boltdb的几种核心数据结构及其二进制结构都分析完毕，后面我们看Boltdb的源码，是如何基于这些数据结构实现事务和MVCC等特性。