Boltdb源码分析——page结构

约定不等于承诺〃 2022-09-11 01:11 182阅读 0赞

boltdb是一个纯粹的key Value数据库，其宗旨是提供一个简单，快速，可信的数据库。此数据库广泛应用于各大开源组件中。源码目录为：  
![在这里插入图片描述][ad0b11e1dbf54517b20b3c6b766efe25.png]

## 内存页 ##

### boltdb 存储 ###

概括来讲，boltdb 的存储有如下特点：

*  每个 db 对应一个文件，文件按照 page size(一般为 4096 Bytes) 划分为 page:  
    前2个 page 保存 metadata；特殊的 page 保存 freelist，存放空闲 page 的 id；剩下的 page 构成一个 B+ 树结构。
 *  支持 namespace，每对 K/V 存放在一个 Bucket 下，不同 Bucket 可以有相同的 key，支持嵌套的 Bucket。每个 Bucket 是一个完整的 B+ 树；
 *  B+ 树的每个结点对应一个或多个连续的 page；
 *  因为内存比磁盘小，一般会实现 page cache 缓存部分 page，比如使用 LRU 算法。boltdb 没有实现，而是使用 mmap() 创建共享、只读的文件映射并调用 madvise(MADV\_RANDOM)，由操作系统 管理 page cache；
 *  没有 WAL，事务中所有操作都在内存中进行，只有 commit 时才会写到磁盘；
 *  commit 时会将 dirty page 写入新的 page，从而保证同时读的事务不受到影响。

### page结构体 ###

bolt/page.go --> page结构体。page指的是内存中的页，这个结构体其实是用来对应页，然后将其管理起来的数据结构。

*  id：是pgid类型，是给page的编号。
 *  flags：是指的此页中保存的具体数据类型。详细解释可阅读后续章节。
 *  count：记录具体数据类型中的计数，不同的类型具有不同的含义
 *  overflow：用来记录是否有跨页
 *  ptr：是具体的数据类型。这种用法让我想起来了c语言中的用法。在Linux内核中经常用到。比如典型的场景就是虚拟文件系统的接口。

type pgid uint64
    type page struct { 
    	id    pgid // page id
    	flags uint16 // 区分不同类型的 page
    	count    uint16 // page data 中的数据个数
    	overflow uint32 // 若单个 page 大小不够，会分配多个 page
    	ptr uintptr // 存放 page data 的起始地址
    }
    type pages []*page

flags是指的此页中保存的具体数据类型：branchPageFlag 分支节点、leafPageFlag 叶子节点（以上是用树结构来管理页的关系）、metaPageFlag meta页、freelistPageFlag freelist页。

const (
    	branchPageFlag   = 0x01
    	leafPageFlag     = 0x02
    	metaPageFlag     = 0x04
    	freelistPageFlag = 0x10
    )
    // typ returns a human readable page type string used for debugging.
    func (p *page) typ() string { 
    	if (p.flags & branchPageFlag) != 0 { 
    		return "branch"
    	} else if (p.flags & leafPageFlag) != 0 { 
    		return "leaf"
    	} else if (p.flags & metaPageFlag) != 0 { 
    		return "meta"
    	} else if (p.flags & freelistPageFlag) != 0 { 
    		return "freelist"
    	}
    	return fmt.Sprintf("unknown<%02x>", p.flags)
    }

ptr 是保存数据的起始地址，不同类型 page 保存的数据格式也不同，共有4种 page, 通过 flags 区分:

*  meta page: 存放 db 的 meta data。
 *  freelist page: 存放 db 的空闲 page。
 *  branch page: 存放 branch node 的数据。
 *  leaf page: 存放 leaf node 的数据。

page的头部包含了一些信息，最后的ptr是具体的数据结构，也就是相应的数据。下面是获取meta page数据指针的函数。

const pageHeaderSize = int(unsafe.Offsetof(((*page)(nil)).ptr))
    const branchPageElementSize = int(unsafe.Sizeof(branchPageElement{ }))
    const leafPageElementSize = int(unsafe.Sizeof(leafPageElement{ }))
    // meta returns a pointer to the metadata section of the page.
    func (p *page) meta() *meta { 
    	return (*meta)(unsafe.Pointer(&p.ptr))
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16]  
如下是叶子节点的转换，获取存放 leaf node 的数据指针的函数。主要是数组的整个转化\[0x7FFFFFFFF\]leafpageElement 类型，指针是p.ptr，返回了数组转化后的\[:\]。

// leafPageElement retrieves the leaf node by index
    func (p *page) leafPageElement(index uint16) *leafPageElement { 
    	n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
    	return n
    }
    // leafPageElements retrieves a list of leaf nodes.
    func (p *page) leafPageElements() []leafPageElement { 
    	if p.count == 0 
    		return nil
    	return ((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[:]
    }

如下是分支节点的转换

// branchPageElement retrieves the branch node by index
    func (p *page) branchPageElement(index uint16) *branchPageElement { 
    	return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
    }
    // branchPageElements retrieves a list of branch nodes.
    func (p *page) branchPageElements() []branchPageElement { 
    	if p.count == 0 {  return nil }
    	return ((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[:]
    }

### page存储 ###

磁盘上的格式和结构体相同，将数据写入文件会首先分配一个 page，然后设置 page header 和 page data:  
![在这里插入图片描述][060a9575dcf240b2a5001c516a4f98fd.png]  
boltdb 直接将 page 结构体的二进制格式写入文件，避免了序列化和反序列化的开销:

*  写的时候直接将需要写入的结构体转换为 byte 数组写入文件：`ptr := (*[maxAllocSize]byte)(unsafe.Pointer(p))`
 *  读的时候直接将 byte 数组转换为对应结构体即可:

// page retrieves a page reference from the mmap based on the current page size.
    func (db *DB) page(id pgid) *page { 
      pos := id * pgid(db.pageSize)
      return (*page)(unsafe.Pointer(&db.data[pos])) }

需要注意只能转换为数组而不是 slice，否则会受到 sliceHeader 的影响。

page cache  
boltdb 没有实现 page cache，而是调用 mmap() 将整个文件映射进来，并调用 madvise(MADV\_RANDOM) 由操作系统管理 page cache，后续对磁盘上文件的所有读操作直接读取 db.data 即可，简化了实现:  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 1]

// mmap memory maps a DB's data file.
    func mmap(db *DB, sz int) error { 
    	// Map the data file to memory.
    	b, err := syscall.Mmap(int(db.file.Fd()), 0, sz, syscall.PROT_READ, syscall.MAP_SHARED|db.MmapFlags)
    	if err != nil { 
    		return err
    	}
    	// Advise the kernel that the mmap is accessed randomly.
    	if err := madvise(b, syscall.MADV_RANDOM); err != nil { 
    		return fmt.Errorf("madvise: %s", err)
    	}
    	// Save the original byte slice and convert to a byte array pointer.
    	db.dataref = b
    	db.data = (*[maxMapSize]byte)(unsafe.Pointer(&b[0]))
    	db.datasz = sz
    	return nil
    }

### 元数据(metadata) ###

元数据存两份，pageid为0和1，pageid是固定的，以后也不会改变。meta的作用：  
1.保存数据库基本信息，如根节点，版本号，空闲列表等  
2.其中一个元数据出了问题，可以使用另外一份进行修复来保证数据库可用  
3.保证一致性：每次读写事务前，都会选取txid最大的那个meta进行事务初始化，同时做MVCC时，也会拷贝最新的meta。

type meta struct { 
        magic    uint32     // 标识db文件为boltdb产生的
        version  uint32     // 版本号
        pageSize uint32     // 页大小，根据系统获得，一般为4k
        flags    uint32     // 表示为metadata
        root     bucket     // 内含根节点的pageid，起始时从3开始
        freelist pgid       // 空闲列表pageid，起始时从2开始
        pgid     pgid       // 下一个要分配的pageid
        txid     txid       // 下一个要分配的事务id
        checksum uint64     // 检查meta完整性时使用
    }

### leaf page ###

leaf node 在文件中的格式如下:  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
node 的数据存放在 page.ptr 的位置：首先是所有的 leafPageElement，然后是所有的 key 和 value，通过 pos、ksize 和 vsize 获取对应的 key/value 的地址（`&leafPageElement + pos == &key、&leafPageElement + pos + ksize == &val`）。key函数用于获取key数组，val函数用于获取value数组。

// leafPageElement represents a node on a leaf page.
    type leafPageElement struct { 
      flags uint32 // 通过 flags 区分 subbucket 和普通 value
      pos   uint32 // key 距离 leafPageElement 的位移
      ksize uint32
      vsize uint32
    }
    // key returns a byte slice of the node key.
    func (n *leafPageElement) key() []byte { 
    	buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
    	return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize:n.ksize]
    }
    // value returns a byte slice of the node value.
    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]
    }

### branch page ###

branch page在文件中的格式如下:  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
和 leaf node 的区别是：branch node 的 value 是子节点的 page id，存放在 branchPageElement 里，而 key 的存储相同都是通过 pos 得到：

// branchPageElement represents a node on a branch page.
    type branchPageElement struct { 
    	pos   uint32
    	ksize uint32
    	pgid  pgid
    }
    // key returns a byte slice of the node key.
    func (n *branchPageElement) key() []byte { 
    	buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
    	return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
    }

boltdb 中典型的 B+ 树结构如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
它的实现和通常意义上的 B+ 树有些不同，结点上的 key 和 val 个数是相同的，而一般 B+ 树 val 会比 key 多一个:

*  branch: 每对 key/val 指向一个子节点，**key 是子节点的起始 range，val 存放子节点的 page id**；
 *  leaf: 每对 key/val 存放数据，没有指针指向 sibiling node；通常的 B+ 树多出的一个指针会指向 sibiling node。

boltdb 中有 3 个结构和 B+ 树密切相关：

*  page: 大小一般为 4096 bytes，对应文件里的每个 page，读写文件都是以 page 为单位。
 *  node: B+ 树的单个结点，访问结点时首先将 page 的内容转换为内存中的 node，每个 node 对应一个或多个连续的 page。
 *  Bucket: 每个 Bucket 都是一个完整的 B+ 树，所有操作都是针对 Bucket。

一个典型的查找过程如下：  
首先找到 Bucket 的根节点，也就是 B+ 树的根节点的 page id；  
读取对应的 page，转化为内存中的 node；  
若是 branch node，则根据 key 查找合适的子节点的 page id;  
重复2、3直到找到 leaf node，返回 node 中对应的 val。

### freelist page ###

https://blog.csdn.net/screscent/article/details/79807625  
https://youjiali1995.github.io/storage/boltdb/  
https://zhuanlan.zhihu.com/p/341416264

[ad0b11e1dbf54517b20b3c6b766efe25.png]: /images/20220829/959ad6a0aff44013b99fd8a6c4498a3e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/98915a93466447c28fca9ee67667bf4c.png
[060a9575dcf240b2a5001c516a4f98fd.png]: /images/20220829/d0dd269e478d4bb5acece59c5450c9ad.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/be950d140ed443f792ef0cabbbf6b9f4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/b6a5721b8c7840cea71e8b22bec91002.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/27b163af7afa4a07b853327482cf95c7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6IKl5Y-U6I-M_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/f0003b862ec54b6da09c30afb7d8da88.png