sqlite3.36版本 btree实现（零）- 起步及概述

《sqlite3.36版本 btree实现》系列文章：

• sqlite3.36版本 btree实现（零）- 起步及概述 - codedump的网络日志
• sqlite3.36版本 btree实现（一）- 管理页面缓存 - codedump的网络日志
• sqlite3.36版本 btree实现（二）- 并发控制框架 - codedump的网络日志
• sqlite3.36版本 btree实现（三）- journal文件备份机制 - codedump的网络日志
• sqlite3.36版本 btree实现（四）- WAL的实现 - codedump的网络日志
• sqlite3.36版本 btree实现（五）- Btree的实现 - codedump的网络日志

起步

在去年大体把btree以及b+tree算法流程研究了之后，我写了两篇博客：

• B树、B+树索引算法原理（上） - codedump的网络日志
• B树、B+树索引算法原理（下） - codedump的网络日志

（鉴于b+tree只是btree的一个特例，下面描述将仅使用“btree”，不再严格区分两者。）

但是，这两篇文章仅仅只是让我懂得了最基本的原理。懂得原理，只是能做出toy级别的实现，拿btree类的存储引擎来说，要做到生产级产品，至少还有以下几个问题我当时不知道怎么做的：

• 如何处理不同大小的数据的存储？
• 删除一个数据之后，如何复用其留下的空间？
• 错误、崩溃恢复怎么做？
• 跟磁盘文件是如何交互的？
• 页面缓存模块如何实现？

等等等等，还有太多我还没有弄清楚的实现细节。

（我甚至还在微博上发问，得到了两个质量很高的回答，见本文最后的彩蛋部分。）

对LSM类存储引擎有了解的人都知道，Leveldb这个项目在LSM领域属于入门级别的生产级实现，即这个领域最精简、但是又能放心在某些要求不高的场景下用于生产的项目。在这之后，我一直在找那种btree领域的“leveldb”，很遗憾一直都没有找到，我分别看了目前WiredTiger、innodb、sqlite的对应实现，都太复杂了，看不下去。

直到有一天，无意间发现了这个项目：madushadhanushka/simple-sqlite: Code reading for sqlite backend，看介绍，作者把sqlite2.5里b-tree相关的部分代码抽取出来了，我编译运行了一下用例都能正常跑，代码量不过几千行，我只花了几天就看完了。

虽然按照Release History Of SQLite上的记载，sqlite 2.5版本是2002年的版本了，但是这个版本还是某种程度回答了我在上面的疑问。

趁热打铁，我又找来更新一些的sqlite 3.6.10代码继续看这部分的实现，这次花了更多的时间才看完，但是又增强了我的信心。由于这个版本的sqlite，还未实现btree的wal，还只是用了journal文件来做崩溃恢复（无论wal还是journal，都会在后面文章展开详细讨论），所以在有足够的信心之后，我接下来又继续看当时（2021.10月份）最新的sqlite 3.36版本的实现，这部分的实现对比3.6.10来说，在btree部分最大的变化就是多了wal的实现，在已经清楚3.6.10的前提下，再增加了解这部分的实现，也并不是什么难事了。

以上，简单描述了我探索一个生产级btree实现的初过程，btree类存储引擎的实现博大精深，更复杂者还有很多（WiredTiger、innodb、tokudb…），但是无疑从低版本sqlite开始的探索流程，终于让我打开了走上这条路的一扇大门。

本系列文章就sqlite 3.36版本的btree实现展开描述，希望对那些和我一样对“生产级btree类存储引擎实现”有好奇心的人有一点帮助。

当然，如果你还是觉得吃力，可以先从madushadhanushka/simple-sqlite: Code reading for sqlite backend这里看起。这里并不建议对btree原理没有了解的人直接上手sqlite的实现，如果需要了解原理请参考相关文章或者我上面给出的我写的两篇博客。这系列文章中，将不再对btree原理做过多描述，将假设读者已经了解这部分内容。

sqlite的btree架构概述

下面简单描述一下sqlite的btree架构，从高往低大体分为以下几个部分：

这三部分架构，由下往上依次是：

• 系统级API的实现：因为sqlite是一个可以在多个平台编译运行的数据库，所以系统级API这一层，需要解决平台相关的文件IO、锁等问题。这部分实现，将不在这系列文章中介绍，因为并不属于数据库实现时的核心问题。

• 页面管理模块：btree存储引擎，其操作文件的最基本单位就是页面。页面管理模块解决以下的问题：对上层的btree模块，暴露针对页面读、写的接口，内部会缓存页面的内容，何时将修改的页面（所谓脏页面，dirty page）落盘到磁盘，是否需要sync修改，崩溃或者重启时的数据恢复，这些都不需要上层的btree模块关心。为了达到这些效果，内部还有几个子模块：

  • 页面缓存模块：用于缓存页面的内存有限，何时淘汰缓存中的页面、何时将缓存中的脏页面落盘，等等都由这个模块负责。

  • 页面备份：从上面的描述可以看到，因为页面的修改并不一定马上落盘，而是可能只是修改了缓存中的页面，这样在系统发生崩溃的时候，需要做恢复操作，一些没有完成的事务需要回滚，等等。这部分页面管理模块由两种不同的实现：

    • journal文件：这是早期，但是效率并不高的实现。
    • WAL文件：这是从3.7之后引入的更高效的方式。

  • 事务：事务处理也放在了页面管理中。

• btree：基于页面管理模块之上，实现了可以存储可变数据的btree模块。

可以这样来简单区别理解“页面管理”模块和btree模块的功能：

• 页面管理：顾名思义，页面管理模块的最基本单位是”页面“，页面的读、写、缓存、落盘、恢复、回滚等，都由页面模块负责。上一层依赖页面管理模块的btree模块，不需要关心一个页面何时缓存、何时落盘等细节。即：页面模块负责页面的物理级别的操作。

• btree：

  • 负责按照btree算法，来组织页面，即负责的是页面之间逻辑关系维护。
  • 除此以外，一个页面内部的数据的物理、逻辑组织，也是btree模块来负责的。

  即：btree负责维护页面间的逻辑关系，以及一个页面内数据的组织。

从上面的分析可以看出来，“页面管理模块”无疑是这里最大最复杂的部分，Andy Pavlo在CMU 15445课程中提到过：任何用mmap来做页面管理的做法都是很糟糕的做法（如boltdb、LMDB等）。

这系列的文章，也将按照这个顺序，从下往上逐层分析sqlite的3.36版本的btree实现。

彩蛋

2021年9月5日，我在微博上就处理崩溃恢复的实现，提了一个问题：

那些很成熟的存储引擎，都是怎么处理崩溃恢复问题的呢，比如写数据落盘到一半，进程崩了，该如何恢复呢？求资料和指点。 ​

（见：那些很成熟的存储引擎… - @玩家老C的微博 - 微博）

得到了两个很不错的指点回复：

ba0tiao的回复

做InnoDB 这块挺久了, 我试试说说 InnoDB 是怎么做的吧..

其实你这里应该细分成两个问题

1. 16kb 的page 写入的原子性该如何保证
2. Btree 结构的完整性如何保证, 也就是你说的修改了n个页面以后如果修改了父子, 兄弟关系以后, 如果解决中间的crash 的问题

问题1 是通过double write buffer 来解决的, 因为InnoDB 的page 大小是16kb, 很多文件系统只能保证4kb 大小写入的原子性, 因此需要写入前先将page 的内容写入到double write buffer 来保证, 如果写入失败也不会将原有page 的内容覆盖.

问题2 是通过redo log + mtr(mini transaction) 进行保证.

InnoDB 里面的redo log 是由mtr 组成, mtr 是修改btree 的最小单位. 每次写入redo log 的时候必须是一个完整的mtr 的内容, 具体实现方式是mtr 会有MULTI_REC_END 标记, 在crash recovery 的时候, 如果读取到mtr 的内容没有MULTI_REC_END 标记, 那么则会认为这个mtr 不完整, 就会把这段mtr 抛弃.

那么是不是一次insert 操作产生的redo log 都包含在一个mtr 里面呢?

不是的.

我们知道在btree 里面对page 的修改都需要对page 加锁, 从fsp 模块分配一个new page 也需要对root page 进行加锁等等. 所以InnoDB 的mtr 里面自然就包含对锁的操作, 因此要修改某一个page 的时候, mtr begin 的时候会对该page 加锁, 然后写入修改的内容, 然后mtr commit 的时候, 对于修改的page 的锁就可以释放了.

如果整个insert 的过程都放在一个mtr 里面做, 那也是可以的, 也就是对于所有page 的latch 都是一开始持有, 最后的时候在释放, 就算后续这个page 已经不再修改了, 也依然要一直持有. 很容易理解这样并发自然就降低下来的, 因此在InnoDB 设计里面, mtr 的粒度是尽可能小的. 修改完page 就应该尽快的commit, 然后将page lock 释放. 但是又需要保证每一次的mtr 操作前和操作后btree 的完整性.

体现具体的例子就是, InnoDB里面对于一个简单的insert 操作, 其实是有非常多个mtr 组成, 尽可能减少持有锁的时间.

但是在做btree 分裂操作的时候, 分配新的page, 将之前page一半的数据迁移到new page 是在一个mtr 里面完成, 但是后续具体的insert 操作是在另外一个mtr 里面完成的. 那么如果在做分裂操作过程中crash, 那么这个分裂操作是不会完成的, 如果在分裂操作完成以后, insert 之前crash, 那么btree 是已经分裂过的, 只是数据没有插入了.

当然这里会有你说的更复杂的设计的父节点 and 父节点的父节点的分裂, 那么自然持有锁的时间就更长了, 但是在我们在这里是做的一些优化.

还有一些比如InnoDB redo log 是"physical to a page, logical within a page" 就是解决我们上面说的如果分裂操作成功了, 但是这个事务要回滚, 这个时候该如何处理等等..

具体的内容其实这些文章里面都有

1. C. Mohan, Don Handerle. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.
2. C. Mohan, Frank Levine. ARIES/lM: An Efficient and High Concurrency index Management Method Using Write-Ahead Logging.
3. Goetz Graefe. A Survey of B-Tree Logging and Recovery Techniques.
4. Goetz Graefe. A Survey of B-Tree Locking Techniques.

对了Goetz Graefe 号称Btree 守护神

（见：做InnoDB 这块… - @ba0tiao的微博 - 微博）

注：

• ba0tiao应该是阿里云负责PolarDB开发的资深开发。
• 他的博客是：baotiao
• 知乎专栏：MySQL内核揭秘 - 知乎

BohuTANG的回复

可以深入一点：如果每次写的log都在，怎么做到基于这些log做回放的问题？其实就是redo-log +checkpoint+ LSM的机制。redo解决数据不丢，checkpoint解决recovery的时候扫描的redo尽量少，LSM解决每次写入后新的page不会覆盖老的数据，这类实现是比较简单可行，也是目前的主流做法

（见：可以深入一点：如果每… - @BohuTANG的微博 - 微博）

以及：

目前大部分理论都参考于这篇 ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging – Mohan et al. 1992

（见：目前大部分理论都参考… - @BohuTANG的微博 - 微博）

注：

• BohuTANG已经在数据库领域沉浸多年，前阿里云数据库内核组早期成员、前青云数据库团队负责人。现在数据库领域创业，公司的项目是：datafuselabs/databend，欢迎围观。
• 博客地址：[ 虎哥的博客 ]