存储层负责管理数据库元数据以及数据的读写，它主要关心：元数据、索引和原数据如何存储在磁盘上；缓存层负责管理数据库各数据在磁盘与内存之间的移动，它主要关心：何时将何种数据读入到内存的何地，何时将何种数据写出到磁盘的何地。由于 Bolt 的缓存层处理较简单，因此本文将缓存层与存储层合并讨论。
- 存储
- Page
- 类型与布局
- 数据溢出
- Heap File Organization
- Freelist
- Page
- 缓存
- 读缓存：mmap
- 写缓存
当我们新建一个 Bolt 实例时：
// api/open.go
func main() {
db, err := bolt.Open("1.db", 0600, nil)
if err != nil {
log.Fatal(err)
}
defer db.Close()
}当前目录下会新生成一个文件1.db，暂时称之为数据库文件，因为该文件包含了这个实例的所有数据，即元数据、索引和原数据。
Bolt 将数据库文件划分成固定大小的块，作为读写的最小单元。每个数据块被称为一个 page，每个 page 的大小由文件系统中的 PAGE_SIZE 决定，后者是数据在磁盘与内存中搬运的最小单位，由计算机组成结构决定，以我的 MacBook Pro 为例，单个 page 大小为 4k：
$ getconf PAGE_SIZE
4096以 PAGE_SIZE 来划分文件能最大效率地享受文件系统提供的读写能力。利用 Bolt 提供的命令行工具，可以看到刚刚创建的数据库文件的结构：
$ bolt pages 1.db
ID TYPE ITEMS OVRFLW
======== ========== ====== ======
0 meta 0
1 meta 0
2 freelist 0
3 leaf 0一个空的 Bolt 实例由 4 个 page 构成，其中 2 个 meta page、1 个 freelist page 和 1 个 leaf page：
在 page.go#17 中，Bolt 定义了 4 种 page:
const (
branchPageFlag = 0x01
leafPageFlag = 0x02
metaPageFlag = 0x04
freelistPageFlag = 0x10
)不论是哪种 page 都有 header 和 body 两部分：
展开 page header，其结构如下：
| 字段名 | 说明 |
|---|---|
| id | page id |
| flags | 区分 page 类型的标识 |
| count | 记录 page 中的元素个数 |
| overflow | 当遇到体积巨大、单个 page 无法装下的数据时，会溢出到其它 pages，overflow 记录溢出总数 |
| ptr | 指向 page 数据的内存地址，该字段仅在内存中存在 |
meta page
meta page 记录 Bolt 实例的所有元数据，它告诉用户这是什么文件以及如何解读这个文件，具体结构如下：
| 字段名 | 说明 |
|---|---|
| magic | 一个固定的 32 位随机数，用来确定该文件是一个 Bolt 数据库文件(另一种文件起始位置拥有相同数据的可能性极低) |
| version | 表明该文件所属的 Bolt 版本，便于日后做兼容与迁移 |
| page_size | 上文提到的 PAGE_SIZE |
| flags | 保留字段，未使用 |
| root | Bolt 实例所有索引和原数据被组织成一个树形结构，root 就是根节点 |
| freelist | Bolt 删除数据时可能出现富余的空间，这些空间的信息会被记录在 freelist 中备用 |
| pgid | 下一个要被分配的 page 的 id，取值大于已分配的所有 pages 的 id |
| txid | 下一个要被分配的事务 id。事务 id 单调递增，可以被理解为事务执行的逻辑时间 |
| checksum | 用于确认 meta page 数据本身的完整性，保证读取的是上一次写入的数据 |
其中 magic, version 和 checksum 一同用于验证数据库文件的合法性。
仔细观察1.db的布局，你可能会问：为什么有两份 meta page？ 这可以理解为一种本地容错方案：如果一个事务在 meta page 落盘的过程中崩溃，磁盘上的数据就可能处于不正确的状态，导致数据库文件不可用。于是 Bolt 准备了两份 meta page，暂且用 A 和 B 表示。如果上次写入的是 A，这次就写入 B，反之亦然。从而保证，读取数据库文件发现一份 meta page 失效时，可以立即将数据恢复到另一个 meta page 所记录的状态。如何恢复到上一个状态？Bolt 的思路很精简，所有发生更新的数据都写入到新的 page 中，保证数据库文件中总是保留上一次写入的数据，用空间换取更简单的处理逻辑。
freelist page
freelist 记录着一个有序的 page id 列表：
有序排列的 page id 方便 freelist 实施空间分配策略，具体将在 Heap File Organization 一节介绍。
branch/leaf page
Bolt 利用 B+ 树存储索引和键值数据本身，这里的 branch/leaf 指的就是 B+ 树的分支/叶子。 branch/leaf 需要存储大小不同键值数据，二者布局如下：
在 page header 之后，顺序地排列着 page 中每个键(值)数据的元信息，即为 element header，每个 element header 记录具体键(值)数据的位置和大小，这种布局技术也被称为 Slotted Pages。
branch page 存储 B+ 树的分支节点数据，每个分支节点需要存储若干个键，用来表示子节点所包含键的上下界，其布局如下：
将 element header 展开得到：
| 字段名 | 说明 |
|---|---|
| pos | 键的位置，即位移 |
| ksize | 键的长度 |
| pgid | 子节点所在 page 的 id |
leaf page 存储 B+ 树的叶子节点数据，即键值对数据，其布局如下：
将 element header 展开得到：
| 字段名 | 说明 |
|---|---|
| flags | 保留字段，同时方便对齐 |
| pos | 键值的位置，即位移 |
| ksize | 键的长度 |
| vsize | 值的长度 |
当需要存储超过单个 page 大小的数据时，比如：
- branch/leaf page 遇到大的键值对数据
- freelist page 中空闲 page 列表较长
我们该如何处理？Bolt 通过引入 overflow page 来解决这个问题，当需要存储超过单个 page 大小的数据时，就申请满足大小需求的连续 N 个 page，其中第 2 个到第 N 个是第 1 个 page 的 overflow，它们与第 1 个 page 共用 page header：
这些连续的 pages 在 Bolt 眼里就是一个巨大的逻辑 page，方便统一读写逻辑。在写出 overflow page 时，Bolt 会预先根据 page header 和 element header 计算出整个 page 的大小，若它的大小超过单个 page，则申请连续的多个 pages，并记录 overflow page 数量。在读取时，同样将其看作一个逻辑 page 读入，由于 pages 之间连续，直接根据 page header 中记录的 overflow page 数量就可以读出相关数据。但有一种情况需要特别考虑：
超大的 freelist page
freelist page 中的元素都是 pgid，没有 element header，没有数据的位移信息，只能通过 page header 中的 count 来判断整个逻辑 page 的大小。但有可能出现 freelist 的实际长度可能超过 count（uint16） 的上限 65535 的情况，Bolt 通过特殊的 count 取值来处理这种问题：
// If the page.count is at the max uint16 value (64k) then it's considered
// an overflow and the size of the freelist is stored as the first element.
idx, count := 0, int(p.count)
if count == 0xFFFF {
idx = 1
count = int(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0])
}当 count 取值恰好为上限值时，就认为在 page header 之后的 8 个字节 (uint64)，记录 freelist 的实际长度：
数据库从操作系统申请的文件空间一般只增不减，因为实践经验告诉我们：一旦数据库的数据存储量超过某个值，即使出现数据删除操作，在不久的将来存储量必将再次超过该值。Bolt 也不例外，我们可以做一个实验：
- 利用 api/generate_1000_users.go 往数据库中插入一定规模的数据
- 利用 api/delete_buckets.go 删除这些数据
在步骤 1 后利用 bolt stats 查看数据库文件：
$ bolt stats 2.db
Page count statistics
Number of logical branch pages: 1
Number of physical branch overflow pages: 0
Number of logical leaf pages: 80
Number of physical leaf overflow pages: 0
...
$ du -h 2.db
356K 2.db在步骤 2 后再次查看：
$ bolt stats 2.db
Page count statistics
Number of logical branch pages: 0
Number of physical branch overflow pages: 0
Number of logical leaf pages: 0
Number of physical leaf overflow pages: 0
...
$ du -h 2.db
356K 2.db可以看出，boltDB 并未将删除后多出的磁盘空间还给文件系统。那么 Bolt 如何管理多出的磁盘空间呢？这个问题就是 File Organization，而 Bolt 使用的方法被称为 Heap File Organization，可以类比程序运行时的 Heap 内存管理。实际负责管理这些磁盘空间的模块就是耳熟能详的 freelist。
freelist 负责管理空闲 pages 的分配与回收。读写事务申请磁盘空间时，freelist 总是先尝试寻找一段物理上连续的满足所需大小的磁盘空间，若找到则直接分配，否则就向操作系统申请新的磁盘空间。
freelist 中保存着顺序排列的空闲 page id，举例如下：
分配策略
由于 freelist 总是顺序保存当前的空闲 page id，分配时就从小到大遍历一次列表，一旦发现连续的 pages 满足需求，就将其从 freelist 中移除，分配给申请空间的事务。
以上图为例，若某读写事务向 freelist 申请 2 个 page 空间，则 page 5-6 将被分配；若申请 3 个 page 空间，则 page 15-17 将被分配；若申请 5 个 page 空间，则会向操作系统申请额外的磁盘空间来分配。
释放策略
当遇到删除数据时，读写事务会将多余的磁盘空间释放回 freelist 中，此时 freelist 不会立即将其分配出去，而是将这些释放的 page 标记成 pending 状态，直到系统中不存在任何读事务依赖这些 page 中的旧数据时，才正式将其回收再分配。场景举例如下：
只读事务 B 正在运行，这时读写事务 A 从数据库中删除了一部分数据，并将相应的磁盘空间释放回 freelist 中，若此时 freelist 立即将这些刚释放的 page 分配给下一个读写事务 C，后者可能对其修改后将其落盘，在这个过程中只读事务 B 仍然在读取数据，就可能读到相同数据的不同版本。而实际上，事务 A 释放磁盘空间时，freelist 仅仅将其标记为 pending 状态，等待类似 B 一样仍然依赖这些 page 的事务执行完毕后再将其回收再利用，从而避免数据不一致，保证事务隔离。这种释放策略在实现数据库多版本并发控制（MVCC）中尤为重要，我们将在事务一节中继续讨论这个话题。
计算机在内存中读写数据的速度要远远快于在磁盘中读写数据。通过预测数据的读取模式，缓存未来可能再次用到的数据避免重复从磁盘读取，就能提高数据库读效率；写出数据时，合理地将短期内不会再被修改的脏数据批量写出，减少写出频率，就能提高数据库写效率。以上两部分正是缓存层的主要工作。
mmap 是操作系统提供的系统调用，它将系统中的某个文件或设备的数据直接映射到一块大小给定的虚拟内存中，这块虚拟内存可以大于或小于该文件或设备的实际所占空间大小。映射完毕后，应用程序可以认为 (实际并不会) 映射对象的数据已经全部读入内存中，任意访问这块虚拟内存中的数据，操作系统在背后全权负责数据的缓冲读写。
Bolt 利用 mmap 管理数据的读缓冲，即让操作系统来决定何时将数据读入内存，当缓冲区大小不足时如何选择被置换的数据，Bolt 只管像访问字节数组一样访问数据库文件即可。当然，使用 mmap 也失去了数据读取的控制权，无法根据数据库系统的运行逻辑来优化数据预取 (prefetching) 及缓存置换 (buffer replacement)。话虽如此，实际情况是 Bolt 每次都选择将数据库文件 mmap 到一块不小于数据库文件本身大小的虚拟内存中，因此实际上只有 demand paging，没有 buffer replacement。
以以下的简化代码为例：
func mmap(db *DB, sz int) error {
b, _ := syscall.Mmap(fd, 0, sz, flags)
db.data = (*[maxMapSize]byte)(unsafe.Pointer(&b[0]))
}在执行 mmap 函数后，Bolt 实例得到一个内存地址。在 boltDB 实例眼里，以这个地址为起点的一段连续内存空间中映射着数据库文件，它可以随机访问其中的数据：
func (db *DB) page(id pgid) *page {
pos := id * pgid(db.pageSize)
return (*page)(unsafe.Pointer(&db.data[pos]))
}读写事务提交时，会将所有脏页 (dirty pages) 落盘。落盘前，Bolt 会将这些 page 按 page id 升序排列，然后依次写出到磁盘中。由于数据库文件中的所有 page 按 id 升序排列并两两相邻，这样写出就是顺序写，对块存储设备十分友好。