update README.md

jaydenwen123 · Aug 17, 2019 · 7a7e2c4 · 7a7e2c4
1 parent 8fad47e
commit 7a7e2c4
Show file tree

Hide file tree

Showing 6 changed files with 237 additions and 24 deletions.
diff --git a/API.md b/API.md
diff --git a/BUCKET.md b/BUCKET.md
@@ -41,7 +41,7 @@ boltDB 就在 root bucket 上创建了一个新的键值对，键为 bucket1，
 
 ## Bucket 的物理结构
 
-在 [B+ 树](./B_PLUS_TREE.md) 一节中介绍到 boltDB 使用 B+ 树存储键值数据及其索引，那么 boltDB 是如何利用 B+ 树实现 bucket 的抽象呢？我们从最简单的情形开始理解：
+在 [B+ 树](DATA_AND_INDEX.md) 一节中介绍到 boltDB 使用 B+ 树存储键值数据及其索引，那么 boltDB 是如何利用 B+ 树实现 bucket 的抽象呢？我们从最简单的情形开始理解：
 
 ### 初始化 DB
 

diff --git a/B_PLUS_TREE.md → DATA_AND_INDEX.md b/B_PLUS_TREE.md → DATA_AND_INDEX.md
@@ -4,7 +4,7 @@
 
 以数据主要存放的地点来划分，数据库可以分为 in-memory 和 disk-based 两种。前者将所有数据放进内存中，读写的过程不存在磁盘 io；后者将所有数据存放在磁盘中，读写过程需要频繁与磁盘交互，boltDB 就属于后者。对于 disk-based 数据库来说，数据库的性能瓶颈常常出现在磁盘 io 上，因此磁盘 io 次数常常被用来衡量这类数据库各操作的性能，减少磁盘 io 也就成为了数据库设计的重要目标。B+ 树就是优化磁盘 io 的核心数据结构，它可以很好的将数据查询与块存储的特点想结合，最大程度地减少数据读写过程中的磁盘 io。
 
-通常，磁盘中的一个 page 通常对应 B+ 树上的一个 node，数据库从磁盘中载入数据的过程就是将 page 反序列化成 node 的过程，而将数据写入磁盘的过程就是将 node 序列化成 page 的过程。在 [数据存储层](./STORAGE.md) 一节中，我们了解到的 branch page 和 leaf page 对应的正是 boltDB 中 B+ 树上的 branch node 和 leaf node。由于 boltDB 是键值数据库，非关系型数据库，每条数据只有一个字段，因此也只需要在这个字段上建立索引。在其极简的设计理念作用下，boltDB 直接将数据存储在 B+ 树 索引的 leaf node 上。
+通常，磁盘中的一个 page 通常对应 B+ 树上的一个 node，数据库从磁盘中载入数据的过程就是将 page 反序列化成 node 的过程，而将数据写入磁盘的过程就是将 node 序列化成 page 的过程。在 [数据存储层](STORAGE_AND_MEMORY_MANAGEMENT.md) 一节中，我们了解到的 branch page 和 leaf page 对应的正是 boltDB 中 B+ 树上的 branch node 和 leaf node。由于 boltDB 是键值数据库，非关系型数据库，每条数据只有一个字段，因此也只需要在这个字段上建立索引。在其极简的设计理念作用下，boltDB 直接将数据存储在 B+ 树 索引的 leaf node 上。
 
 为了方便，本文将以 node 为中心来讨论 boltDB 中的 B+ 树的结构及相关算法。
 

diff --git a/README.md b/README.md
@@ -1,34 +1,92 @@
-# learn-bolt
+# learn-boltdb
 
-# 名词解释
-写事务
-读写事务
+在最近的闲暇时间，我开始弥补自己数据库知识的盲点。前期花费若干个月时间认真阅读学习了：
 
-# 目录
+* CMU 15-445/645 Intro to Database Systems
+* Designing Data-Intensive Applications (DDIA)
 
-* [数据存储层](./STORAGE.md)
-* [内存管理](./MEMORY_MANAGEMENT.md)
-* [数据存储与索引: B+Tree](./B_PLUS_TREE.md)
-* [桶](./BUCKET.md)
+站在巨人的肩膀上，可以体会到数据库世界的广袤，已然与落后几十年的教科书描述的那般景象大相径庭。但这些努力始终只是在走近，而不是走进数据库。因此我迫切地想要认真阅读某个数据库的源码，了解那些常被提及的概念是如何被实现。在 DDIA 中 boltDB 被多次提及，对它最深刻的印象就是通过单线程执行读写事务的方式简单粗暴地实现最苛刻的可序列化的事务隔离。忽然有一天，我心血来潮地访问 boltDB 项目，“这决定就是它了”。
 
-# TODO
-Ben Johnson 说到：
+## 为什么选择 boltDB
 
-> The original goal of Bolt was to provide a simple pure Go key/value store and to not bloat the code with extraneous features. 
+> The original goal of Bolt was to provide a simple pure Go key/value store and to not bloat the code with extraneous features.  --- Ben Johnson
 
+boltDB 可能是最适熟悉 golang 的工程师最适合阅读的第一个数据库项目，原因在于它：
 
+* 功能简单：
+  * 它是键值数据库，没有关系的抽象，只有键和值
+  * 它对外只暴露简单的 api，没有 DSL 层
+  * 所有数据有且只有一个 B+ 树索引，没有查询计划
+  * 同时允许多个只读事务和最多一个读写事务运行，有并发场景，有事务隔离，但处理方式极简
+  * 使用 mmap 作读缓存，缓存管理逻辑达到最简
+* 源码结构简单，从存储层到对外暴露的 api 抽象分层思路清晰：
+  * 存储与缓存层：page.go, freelist.go, bolt_xxx.go
+  * 数据与索引层：node.go
+  * 桶层：bucket.go, cursor.go
+  * 事务层：tx.go
+  * API 层：db.go
+* 已经投入生产使用，功能稳定
+* 项目已经定稿、归档，不再更新，就如一本已经刊印的书，可以放心引用、批注
 
-learn bolt from different perspectives
+## 关于本系列文章
 
-why learn bolt?
+*要达到好的学习效果，就要有输出*。以我平时的工作节奏，在闲暇时间依葫芦画瓢写一个键值数据库不太现实。于是我选择将自己对源码阅读心得系统地记录下来，最终整理成本系列文章，旨在尽我所能正确地描述 boltDB。恰好我在多次尝试在网上寻找相关内容后，发现网上大多数的文章、视频仅仅是介绍 boltDB 的用法和特性。因此，也许本系列文章可以作为它们以及 [boltDB 官方文档](https://github.com/boltdb/bolt/blob/master/README.md) 的补充，帮助想了解它的人更快地、深入地了解 boltDB。
 
-* pure go k/v storage
-* serializable transaction isolation
-* the repo is archived, code is stable, easy to reference
+如果你和我一样是初学者，相信它对你会有所帮助；如果你是一名经验丰富的数据库工程师，也许本系列文章对你来说没有太多新意。**欢迎所有读者通过任意方式反馈文章中的错误**，帮助我们共同进步。
 
+### 阅读建议
 
+每篇文章将从以某个抽象层为中心，描述 boltDB 的实现思路，它们按自底向上的顺序介绍 boltDB，但各个模块又相对独立，因此顺序阅读和单篇阅读皆可。除了系列文章之外，我在阅读过程中，也会直接在源码上做一些额外的注释帮助理解，如果你愿意，也可以 fork 我的 boltDB fork 来阅读，所有额外添加的注释格式如下：
 
-page 在不同地方的意义，存储层的 page，内存中的 page
+```go
+// [M]
+// 中文版本
+//   ...
+// English version
+//   ...
+```
 
-内存块
+### 名词解释
+
+为了减小歧义，涉及到专业术语的部分，除了已经有稳定的、确定的中文翻译之外，文章中会保留原始英文单词。下面是一份中英文对照表，供参考：
+
+| 中文     | 英文                      |
+| -------- | ------------------------- |
+| B+树     | B+Tree                    |
+| 事务     | transaction/tx            |
+| 读写事务 | read-write transaction/tx |
+| 只读事务 | read-only transaction/tx  |
+| 桶       | bucket                    |
+| 游标     | cursor                    |
+
+除此以外，一些名词需要特别提及：
+
+#### 1. Page
+
+物理外存和物理内存通常会被分割为同样大小的块，这些块被称为 page frame/frame，是物理概念。当这些块被读入内存，在程序中被引用、读写时，被称为 page，是逻辑概念。在 boltDB 中，二者都可能被称为 page，如
+
+* pageSize 中的 page 指的是物理概念
+
+* page.go 中的大部分 page 指的是逻辑概念
+
+#### 2. boltDB 与 boltDB 实例
+
+boltDB 指这个数据库[项目](https://github.com/boltdb/bolt)本身，而 boltDB 实例指利用 api 创建的一个新的 database，也指在文件系统上相应创建的二进制数据库文件 "xxx.db"。
+
+## 目录
+
+* [存储与缓存层](./STORAGE_AND_MEMORY_MANAGEMENT.md)
+* [数据与索引层](./DATA_AND_INDEX.md)
+* [桶层](./BUCKET.md)
+* [事务层](./TX.md)
+* [API 层](./API.md)
+
+## 参考
+
+* Code
+  * [Github: bolt/boltdb](https://github.com/boltdb/bolt)
+* Video
+  - [CMU 15-445/645 Intro to Database Systems](https://www.youtube.com/playlist?list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7)
+* Book
+  - [Designing Data-Intensive Applications](https://dataintensive.net/)
 
diff --git a/STORAGE.md → STORAGE_AND_MEMORY_MANAGEMENT.md b/STORAGE.md → STORAGE_AND_MEMORY_MANAGEMENT.md
@@ -171,7 +171,7 @@ freelist 中存储的内容很简单，就是一个 page id 列表，如下图
 
 ![freelist_page_layout](./statics/imgs/storage_freelist_page_layout.jpg)
 
-但一个 page 只有 4K，最多只能存放 1K 个 page id，显然可分配空间只有 4MB 肯定不够，如何解决这个问题呢？boltDB 的做法很有意思，它利用了 page header 中的 count 字段，若 count 取值为 uint16 的最大值 (0xFFFF)，则认为该 freelist page 还有 overflow page，并以 page header 之后的第一个 uint64 数值表示 freelist 的总长度。在 boltDB 中，这些 freelist pages 会被连续地存储在 meta pages 后面，因此可以通过总长度一次性存取。
+但一个 page 只有 4K，最多只能存放 1K 个 page id，显然可分配空间只有 4MB 肯定不够，如何解决这个问题呢？boltDB 的做法很有意思，它利用了 page header 中的 count 字段，若 count 取值为 uint16 的最大值 (0xFFFF)，则认为该 freelist page 还有 overflow page，并以 page header 之后的第一个 uint64 数值表示 freelist 的总长度。在 boltDB 中，这些 freelist pages 会被连续地存储在一起，因此可以通过起点和总长度一次性读写。
 
 #### Branch/Leaf Page
 
@@ -425,7 +425,7 @@ type freelist struct {
 
 ![MVCC](./statics/imgs/storage_mvcc.jpg)
 
-当读写事务 A 执行完毕后，读事务 B 开始执行，若紧接着读写事务 C 开始执行，C 就可能修改 B 想要读取的数据，而 B 实际上只想读取 A 执行完毕之后、C 开始执行之前的数据，因此这时候 boltDB 不应该将 A 获取的存储空间释放到 freelist 中允许被分配，而将它置于即将释放的状态，等待 B 读取完成后再彻底释放，否则如果 C 修改了相关数据，B 就可能读到 C 执行完毕后的数据，这不符合 MVCC 的语义。
+当读写事务 A 执行完毕后，读事务 B 开始执行，若紧接着读写事务 C 开始执行，C 就可能修改 B 想要读取的数据，而 B 实际上只想读取 A 执行完毕之后、C 开始执行完毕之前的数据，因此这时候 boltDB 不应该将 A 获取的存储空间释放到 freelist 中允许被分配，而将它置于即将释放的状态，等待 B 执行完毕后再彻底释放，否则如果 C 修改了相关数据，B 就可能读到 C 执行完毕后的数据，这不符合 MVCC 的语义。
 
 ### freelist 的分配策略
 
@@ -435,7 +435,7 @@ freelist 向下游提供 allocate 方法用于分配闲置的数据：
 func (f *freelist) allocate(n int) pgid
 ```
 
-设计上，boltDB 使用极简的处理方式，每次从头遍历 freelist，尝试从中找到一段连续的 n 个 page，成功则将这n 个 page 返回给下游，并将其从 freelist 中去除。由于这些 page 是连续的，allocate 函数只需要告诉下游 n 个 page 的第一个即可。
+设计上，boltDB 使用极简的处理方式。首先 freelist 中的 page id 在任何时候都会被升序排列。每次分配时，顺序遍历 freelist，尝试从中找到一段连续的 n 个 page，成功则将这n 个 page 返回给下游，并将其从 freelist 中去除。由于这些 page 是连续的，allocate 函数只需要告诉下游 n 个 page 的第一个即可。
 
 # 参考
 

diff --git a/TX.md b/TX.md
@@ -0,0 +1,155 @@
+# 事务
+
+事务是数据库提供给应用的一层抽象，这层抽象将所有的并发问题和软硬件的各种可能的错误隐藏，只对应用暴露出两种状态：成功（commit）和终止（abort），所有事务中发生的修改要么执行、要么回滚，不存在执行到一半的情况。有了事务支持，应用的错误处理逻辑变得十分简单：重试即可。
+
+boltDB 为用户提供**可序列化**的、满足 **ACID** 性质的事务支持，理解它的原理能够让我们具体地感受 ACID 性质和事务隔离级别。本节从以下两个方面讨论 boltDB 中的事务：
+
+* 事务执行过程与 ACID
+* MVCC
+
+## 事务执行过程与 ACID
+
+boltDB 有两种事务类型：只读（read-only）事务和读写（read-write）事务。
+
+### 只读事务
+
+用户可以通过 db.View 执行只读事务，[举例](./tx/exec_example.go)如下：
+
+```go
+func main() {
+  // init db
+  err = db.View(func(tx *bolt.Tx) error {
+    bucket := tx.Bucket([]byte("b1"))
+    if bucket != nil {
+      v := bucket.Get([]byte("k1"))
+      fmt.Printf("%s\n", v)
+    }
+    return nil
+  })
+}
+```
+
+[db.View](https://github.com/boltdb/bolt/blob/master/db.go#L612) 接受用户的只读事务逻辑，在幕后帮助用户初始化、执行、关闭只读事务，并申请和释放相关资源，它的执行过程可以简化为：
+
+```go
+func (db *DB) View(fn func(*Tx) error) error {
+  t := db.Begin(false)
+  // ...
+  t.managed = true
+  fn(t)
+  t.managed = false
+  // ...
+  t.Rollback()
+}
+```
+
+这种由 boltDB 管理事务生命周期，用户只构建事务逻辑的事务，被称为托管（managed）事务。
+
+### 读写事务
+
+用户可以通过 db.Update 执行读写事务，[举例](./tx/exec_example.go)如下：
+
+```go
+func main() {
+  // init db
+  err = db.Update(func(tx *bolt.Tx) error {
+    bucket, err := tx.CreateBucketIfNotExists([]byte("b1"))
+    if err != nil {
+      return err
+    }
+    return bucket.Put([]byte("k1"), []byte("v1"))
+  })
+}
+```
+
+db.Update 接受用户的读写事务逻辑，在幕后帮助用户初始化、执行、提交（commit）或回滚、关闭读写事务，并申请和释放相关资源，它的执行过程可以简化为：
+
+```go
+func (db *DB) Update(fn func(*Tx) error) error {
+  t := db.Begin(true)
+  // ...
+  t.managed = true
+  err := fn(t)
+  t.managed = false
+  if err != nil {
+    t.Rollback()
+    return err
+  }
+  return t.Commit()
+}
+```
+
+类似地，利用 db.Update 执行的读写事务也是托管事务，由 managed 属性标明。
+
+### ACID
+
+* Atomicity：读写事务的执行，若成功则提交，若失败则回滚，满足原子性
+* Consistency：只要应用程序正确合理地使用事务操纵数据，而 boltDB 保证数据更新不会出现执行到一半的状态，就能够保证数据的一致性
+* Isolation：由于 boltDB 最多只允许一个读写事务同时进行，因此所有读写事务必然顺序执行，自然而然地满足最严苛的可序列化数据隔离级别
+* Durability：每次读写事务提交，即执行 t.Commit() 时，都会将脏数据写入磁盘，如果落盘失败则回滚。因此用户得到返回且无错误发生时，数据必然已持久化完成
+
+## MVCC
+
+数据库通常需要能够并发处理多个正在进行的只读事务和读写事务，但如果没能处理好 ”新写入的数据什么时候对哪些事务可见“ 的问题，就会导致读取的数据前后不一致。在最严苛的场景下，数据库用户认为数据库中的数据应该以读写事务为单位，进行原子性变化，如下图所示：
+
+![transactional-memory](/Users/hezheng/Desktop/Screen Shot 2019-08-10 at 5.31.40 PM.jpg)
+
+对于所有的只读事务来说，数据库的数据在不同时刻应该满足：
+
+* t < t1：未发生任何变化，记为 v1 版本
+* t1 <= t < t2：RW-Tx-1 完成后落盘的数据，记为 v2 版本
+* t2 <= t < t3：RW-Tx-1 和 RW-Tx-2 完成后落盘的数据，记为 v3 版本
+* t >= t3：RW-Tx-1、RW-Tx-2 和 RW-Tx-3 完成后落盘的数据，记为 v4 版本
+
+如果只读事务从开始到结束都落在以上任意单个区间内，它能看到的数据很显然为各自区间内数据所属的版本。但任何只读事务都可能跨越 t1、t2、t3 的边界。若只读事务 A 在 t1 之前开始，t3 之后结束，那么它应该读取到哪些数据？v1、v2、v3、v4 都有可能，如果是 v2 或 v3 会让用户感到疑惑，不能肯定自己每次能读到的数据版本。比较合理的做法应该是 t1 之前的数据或 t3 之后的数据，即 v1 或 v4。但如果取 v4，为了保证只读事务读取的数据是一致的，该只读事务将被阻塞直到 t3 之后才被执行从而给数据库带来负担。综合以上观点，通常事务 A 在结束前读到的数据都应该是 v1 版本的数据。
+
+从以上的分析我们发现，在多只读事务及多读写事务并发的场景下，要做一名合格的数据库，需要保存单个数据的多个版本，即多版本并发控制，MVCC。在数据库中存储单个数据的多个版本，可以**让只读事务不影响读写事务的进行、读写事务也不影响只读事务的进行**，只读事务只会读取到该事务启动时已经提交的所有读写事务的所有数据，在只读事务启动后写入的数据不会被只读事务访问到。
+
+### boltDB 的 MVCC 实现
+
+#### 两个版本还是多个版本
+
+boltDB 最多只允许一个读写事务同时进行，因此它实现 MVCC 时不需要考虑多个读写事务同时进行的场景。只允许一个读写事务同时进行是否意味着 boltDB 只需要同时保存最多 2 个版本的数据？答案如下图所示：
+
+![boltdb-mvcc](/Users/hezheng/Desktop/Screen Shot 2019-08-10 at 7.09.35 PM.jpg)
+
+横轴上方是读写事务，下方是只读事务。在 t3 到 t4 之间，只读事务 RO-Tx-1 要求 v1 版本数据还保存在数据库中；RO-Tx-2 要求 v2 版本数据还保存在数据库中；RO-Tx-3 要求 v3 版本数据还保存在数据库中。因此即使只允许一个读写事务同时进行，数据库也需要保存多版本的数据。
+
+#### 实现方案
+
+##### 以 page 为版本管理单位
+
+在数据存储层一节中介绍过，boltDB 将数据库文件分成大小相等的若干块，每块是一个 page，如下图所示：
+
+![boltdb-page](/Users/hezheng/Desktop/Screen Shot 2019-08-10 at 7.33.44 PM.jpg)
+
+那么我们是否可以以 page 为版本管理单位，实现 MVCC？如果每个 page 都带有版本，每当 page 中的数据将被读写事务修改时，就申请新的 pages 将修改后的数据写入其中，旧版本的 page 直到没有只读事务依赖它时才被回收。使用这种方案使得 MVCC 的实现无需考虑新旧版本共存于同一个 page 的情况，用空间换取了设计复杂度的降低，符合 boltDB 的设计哲学。
+
+*meta page*
+
+meta page 存储数据库的元信息，包括 root bucket 等。在读写事务执行过程中，可能在增删改键值数据的过程中修改 root bucket，引起 meta page 的变化。因此在初始化事务时，每个事务都需要复制一份独立 meta，以防止读写事务的执行影响到只读事务。
+
+*freelist page*
+
+freelist 负责记录整个实例的可分配 page 信息，在读写事务执行过程中，会从 freelist 中申请新的 pages，也会释放 pages 到 freelist 中，引起 freelist page 的变化。由于 boltDB 只允许一个读写事务同时进行，且只有读写事务需要访问 freelist page，因此 freelist page 全局只存一份即可，无需复制。
+
+*mmap*
+
+在数据存储层一节中介绍过，boltDB 将数据的读缓冲托管给 mmap。每个只读事务在启动时需要获取 mmap 的读锁，保证所读取数据的正确性；当读写事务申请新 pages 时，可能出现当前 mmap 的空间不足，需要重新 mmap 的情况，这时读写事务就需要获取 mmap 的写锁，这时就需要等待所有只读事务执行完毕后才能继续。因此 boltDB 也建议用户，如果可能出现长时间的只读事务，务必将 mmap 的初始大小调高一些。
+
+*版本号*
+
+每当 boltDB 执行新的读写事务，就有可能产生新版本的数据，因此只要读写事务的 id 是单调递增的，就可以利用事务 id 作为数据的版本号。
+
+## 参考
+
+* Designing Data-Intensive Applications - Transactions
+
+
+
+
+
+
+
+
+