BoltDB内存结构
在boltdb源码分析系列-文件结构文章中讲述了BoltdDB文件是按page位单位进行物理存储的，当我们Open打开一个BoltDB文件之后，文件内容会被加载到内存。文件中的page页在内存中以node来组织，如果说page是BoltDB物理存储单元，那么node是BoltDB的逻辑单元，是page在内存中的表示。
node
node是page在内存中逻辑表示，现在我们来看node的构成，它的结构体定义如下。
代码语言：javascript复制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。
代码语言：javascript复制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处的地址返回。对应到下面的源码。
代码语言：javascript复制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数据。
代码语言：javascript复制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处理的。
代码语言：javascript复制// 元数据写入磁盘
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内容。
代码语言：javascript复制// 将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
}
