boltdb源码分析系列-文件结构

数据小冰

发布于 2022-08-15 15:01:59

1.2K00

代码可运行

运行总次数：0

代码可运行

小编在阅读etcd源码的时候，看到它的存储storage使用了BoltDB数据库。查阅资料发现它是一个go语言开发的单机的KV数据库，是awesome-go推荐学习的项目，它的代码组织结构非常清晰，代码量也不是很大，于是小编阅读了BoltDB的源码，希望有两方面的收获，一是学习代码的组织分层，提升代码品味；二是加深对数据库知识的理解，数据快速查找是怎么实现的，MVCC机制具体是怎么实现的。

本系列文章是小编学习完BoltDB源码的总结输出，通过图示、理论说明和源码分析结合的方式，讲述bolt是怎么实现的，用了哪些黑科技等等。分析的BoltDB源码地址在https://github.com/boltdb/bolt。

bolt简介

BoltDB是根据LMDB项目开发的一个go语言版的key-value存储，它的目标是为应用提供一个简单、高效和可靠的嵌入式数据库存储。github地址为https://github.com/boltdb/bolt, 由于作者精力和鉴于当前版本已经稳定，作者不在更新此项目。etcd项目中使用的bolt单独拉取了分支(https://github.com/etcd-io/bbolt)，相应的由etcd维护.

readme介绍比较长,这里对BoltDB关键性概念做一个说明。

支持事务操作 BoltDB支持两种事务类型：只读事务和读写事务，多个只读事务可以并发执行，多个只读事务和一个读写事务也可以并发执行，但是多个读写事务不能并发执行
单机型 BoltDB是单机型数据库，不是分布式数据库，比较使用的场景一般是做日志存储
key-value存储也就是说BotdDB是一款nosql数据库，与redis同类型。不过，它存储的key和value都是[]byte类型，不像redis提供了丰富的数据类型。
文件型 BoltDB属于文件型数据库，因为它的所有数据都是存储在磁盘上，这与redis是内存数据库有差别。

BoltDB具有不错的性能，得益于它实现中使用了一些黑科技，总结有以下几点：

采用mmap技术使用操作系统提供的mmap技术，减少了文件内容的复制次数，从而提高了文件的读写效率
COW技术为了提高读操作的并发性，使用了写时复制技术（copy on write）
B+树通过使用B+树实现索引，提高了随机读操作的性能

BoltDB文件

boltDB是一个文件型数据库，写入的数据存储在磁盘的文件上。下面的test.db文件就是一个BoltDB文件，以十六进制查看它，长的是下面这样的，第一列是文件偏移量地址，后面的是内容。

db文件是按页(page)为单位进行顺序存储的，页的大小和操作系统页的大小是相同的，一般都是4KB. 为什么要将db文件划分成页处理，小编认为是方便管理和减少存储空间的浪费。

一个db文件文件由多个page构成，每个page大小为4KB。

所以BoltDB文件的大小一般都是4KB的整数倍，像32KB,64KB,256KB。

page

前面介绍了BoltDB文件是按page组织的，本小节详细介绍page有哪几种类型，以及page的构成。

page有四种类型，分别是meta page、freelist page、branch page和leaf page,翻译成中文是元数据页、空闲列表页、分支页和叶子节点页。

const (
 // 分支节点页
 branchPageFlag   = 0x01
 // 叶子节点页
 leafPageFlag     = 0x02
 // 元数据页
 metaPageFlag     = 0x04
 // 空闲列表页
 freelistPageFlag = 0x10
)

page数据结构定义如下, id为页id，每页有唯一的id值，flags表示页的类型，对应的就是上面的四种类型之一，count表示页中元素的数量，overflow数据是否有溢出，主要在空闲列表上有用, ptr存储真实的数据。

type page struct {
 id       pgid
 flags    uint16
 count    uint16
 overflow uint32
 ptr      uintptr
}

type pgid uint64

一个page分为两部分，分别是page header和page data。header部分是固定的，它描述了page的基本信息，它的id值，页类型等，data部分是真正存储数据的。

meta page

1个BoltDB文件中meta page有两个，分别是meta0和meta1，它们的结构是一样的。meta0和meta1是文件开头的两个page. header部分前面已经介绍过了，这里我们主要关注它的data部分。data部分包含字段信息如下：

magic: 魔数，用于判断文件是否是BoltDB文件
version:版本号，固定为2
pageSize:描述页的大小，为4KB
root: BoltDB文件虽然是按page线性存储在磁盘上的，但是它的组织结构是B+树的形式，是为了快速检索查找。root存储的树根所在的page id信息
freelist:空闲列表页的page id值
txid:数据库事务操作序号
checksum:data数据的hash摘要，用于判断data部分数据是否损坏

至于为什么有两个meta page页以及meta页的作用，留着在后续的事务介绍文章中做说明。这里我们对meta page结构有个整体认识即可。

freelist page

空闲列表页中的data部分存储的是一个一个的pgid值，pgid即为page id，它是uint64类型。这些pgid对应的page是空闲的，可以进行复用存储数据。header中的count描述了data中存储pgid数量，因为count类型为uint16,所以它的最大值为0xFFFF。当count的值小于0xFFFF时候，它的值即为data中真实的pgid数量，对应下图。

那数量超过了uint16怎么处理呢? BoltdDB将真实数量存储在data部分最开头的8字节中，此时header中的count值为0xFFFF是一个标记，表示真实的数量在data部分开头。后面的部分在开始存储pgid值。如下图所示。

branch page

分支节点页存储索引信息，BoltDB通过B+索引来加快数据查询检索，所以除了要存储key-value数据，还要存储B+内部分支节点信息。分支节点中的data存储的是索引key和pgid值，格式如下图。整个data分为branchPageElements和keys两部分，branchPageElements描述了key的大小，每个key起始位置信息。通过branchPageElement刻画了每个key的信息。

pos:key的起始位置距离它的branchPageElement头的差值
ksize:描述key的长度
pgid:子page页的id

leaf page

叶子节点页是真正存储key-value数据的地方，向BoltDB中存储的数据都存放在叶子节点上。它的结构如下，与branchPageElement有点类似，data部分也分为leafPageElement和key-value两部分，leafPageElement描述了每个key的起始位置，key的大小和value的大小。

BoltdDB中有Bucket（桶）的概念，这里先做一点说明，一个Bucket可以看做关系型数据像MySQL中的一个表，BoltDB中比较独特的是Bucket中可以嵌套Bucket，Bucket的子Bucket信息存储在叶子节点上。所以我们看到下图中leafPageElement中有个flags字段，它的值为0表示存储的key-value数据，值为1表示这个是一个子Bucket.Bucket有一个名称，一个Bucket中的存储的key-value数据中的key值不能和它的子Bucket的名称相同。Bucket结构和功能在后续的文章中做详细介绍。leafPageElement中pos的值描述的是key距离它的差值，ksize和vsize分别表示key的长度和value长度。