周刊（第24期）：sqlite并发读写的演进之路
引言：本文梳理sqlite并发读写方案的演进之路。
sqlite并发读写的演进之路
概论
sqlite底层的存储基于B-tree，B-Tree对底层存储的基本读写单位是页面，而每个页面都由全局唯一的页面编号与之对应，一般来说页面编号从1开始递增。
类B-Tree的存储引擎修改数据的流程如下图所示：
从上图中，需要区分B-Tree类的存储引擎几个核心的模块：
- B-Tree算法模块：从页面管理器中读取页面到内存，进行逻辑的修改，修改完毕之后标记该页面为脏页面，这样页面管理器就知道哪些页面被修改，后续需要进行落盘。
- 页面管理器：负责向B-Tree算法模块提供根据页面编号读、写页面的接口。
- 数据库文件：这其实不是一个模块，泛指在磁盘上的数据库相关文件，任何的修改最终都要落到数据库文件。在sqlite中，数据库文件是单一文件，在其他存储引擎里可能是一组相关的文件。
最上层的B-Tree算法模块，在进行写事务的时候，是首先向页面管理器发起读页面到内存中的请求，注意到B-Tree模块并不会直接跟数据库文件打交道，而是经过页面管理器模块（下面会展开说），修改了页面之后标记为“脏页面”，页面管理器最终负责将脏页面落盘到数据库文件中。
现在来谈谈“页面管理器”模块的具体工作，也有的实现称为“缓存管理器（buffer manager）”。这个模块负责：
- 在内存中管理页面，这涉及到两部分内容：
- 如果页面当前不在内存中，需要根据页面编号到磁盘上加载页面。
- 页面也并不是每一次读写时都要到磁盘上加载，有些时候页面已经在缓存中存在了，这种情况下不需要到磁盘上加载页面数据。于是，“页面管理器”模块还需要负责维护这些内存中的页面缓存，何时淘汰这些页面、淘汰哪些内存中的页面、何时真正从磁盘上加载，都是这个模块的工作。
- 对外部而言（这里的外部更多的是B-Tree算法模块），其实不需要也看不到页面缓存的细节，页面管理器对外提供根据页面编号读、写页面接口即可。
- 错误的恢复、事务的管理。比如：
- 一次事务要修改N个页面，修改到中间的时候，进程崩溃了，这时候重新启动时需要恢复到这个事务之前的数据成功启动，即需要提供回滚事务的功能。
- 同样的一个事务要修改N个页面，在事务还未提交的时候，如果事务级别不是read uncommitted， 那么前面的修改效果不能被其他事务可见，这也是页面管理器需要做的事情，毕竟它对外提供了读、写页面的接口，同一个页面编号的页面什么时候的内容可见都由它来决定。
有了这些基础的了解，我们来看看sqlite在并发读写方面的演进之路。
Journal
最早的页面管理器实现是基于Journal文件的，这个文件存储页面在修改之前的内容：
可以看到的是：
- Journal文件存储了一个事务所要修改的页面在修改之前的内容，这个定义有点拗口，姑且称为“旧页面内容”。
- 每次一个事务提交之后，意味着这个事务所有队页面的修改都已经落到了数据库文件中，这时候Journal文件里保存的旧页面内容就不再需要了，可以被删除了。
- 由于每次事务修改都要落盘到数据库文件，这些落盘操作涉及到多次磁盘寻道，即一次事务多次随机磁盘寻道，这样代价其实是很大的。
- 当需要事务回滚的功能时，页面管理器就可以从Journal文件中读出来旧页面内容覆盖回去。
- 虽然这个算法很简单，但是缺陷也明显：它没有任何的读写并发支持。每次开始一个写事务，从开始写事务，到这个写事务提交完成的过程中间，其他的读写事务都不能开始，可以说是“一写全卡住”。
WAL
从上面的分析可以看出，以Journal文件的机制，每次写事务：
- 需要把内容修改全部落盘到数据库文件才能算完成。
- 这个过程中间，不能同时存在其他并发的读、写操作。
从sqlite3.7.0版本开始（SQLite Release 3.7.0 On 2010-07-21），sqlite引入了更常见的WAL机制来解决页面的读写并发问题，WAL的原理如下图所示：
WAL机制中，事务对页面的修改：
- 并没有马上落到数据库文件里，而是首先写入WAL文件中。这样有两个好处：
- WAL文件是append-only的文件，在文件结尾处添加新内容，对写磁盘文件这种操作而言是更快的，因为少了很多磁盘寻道的流程。
- 由于事务的修改并没有马上落盘到数据库文件，所以就并不可见，后续如果需要回滚事务的修改也更容易：不要这个事务修改的那部分WAL内容即可。
- 由于修改有时候还未落盘，需要维护一个wal中页面的索引，用于根据页面编号定位到WAL中的页面。由于wal索引可以控制哪些wal文件内容“可见”，于是就能控制未提交的事务修改对读操作并不可见了。
- WAL文件不能一直增长下去，需要定期把WAL文件中已经提交的事务修改内容落盘到数据库文件，这个流程被称为“checkpoint”。在“checkpoint”之后，wal索引就可以修改了。虽然checkpoint过程将WAL文件中的内容落盘到数据库文件，仍然是针对数据库文件的随机写流程，有很多磁盘寻道操作，但是由于一次checkpoint累计了多次写事务一次性落盘，代价小了一些。
有了WAL之后，读写并发有了一些改善：
- 虽然同一时间仍然只能有一个写事务在进行，但是读事务同时存在多个。其核心原因是因为修改并没有马上直接落盘到数据库文件中，这样修改的可见性就可以由wal索引来控制，即：写事务尽管写，读事务尽管读，只要控制这些写事务的修改不在wal索引中可见即可。
- WAL虽然支持“一写多读”，而不是Journal文件那样的“一写全卡住”，但是还有一个问题没有解决：在做checkpoint操作的时候，连写事务也不能进行了。
两个可能的优化方案
以下介绍sqlite目前在讨论的两个优化方案，之所以说是“可能”，因为看这部分代码还并没有合并到主干中，目前暂时还在分支里，参见：https://github.com/sqlite/sqlite/tree/begin-concurrent-pnu-wal2。
WAL-2
为了解决“checkpoint时无法进行写事务”的痛点，sqlite目前在尝试新的WAL-2机制。
引入WAL-2之后，同时有两个WAL文件，这样可以：checkpoint其中一个WAL文件时，继续写另一个WAL文件，下一次再进行checkpoint时进行切换，这样checkpoint就不会阻塞住写操作。
BEGIN CONCURRENT
目前的WAL机制，都只能支持同一时间一个写事务，BEGIN CONCURRENT机制可以实现多个写并发，这篇SQLite: Begin Concurrent文档中，大概描述了一下这个优化的思路：
The key to maximizing concurrency using BEGIN CONCURRENT is to ensure that there are a large number of non-conflicting transactions. In SQLite, each table and each index is stored as a separate b-tree, each of which is distributed over a discrete set of database pages. This means that:
- Two transactions that write to different sets of tables never conflict, and that
- Two transactions that write to the same tables or indexes only conflict if the values of the keys (either primary keys or indexed rows) are fairly close together.
简单的理解上面的这段话：
- 不同的写事务，如果操作的是不同的表，不同的表数据虽然物理上在同一个数据库文件，但是逻辑上却分属于不同的B-Tree，这样不同的B-Tree管理的页面之间就不会发生冲突，顶多在落盘到数据库文件的时候加锁即可。
- 其次，即便多个写事务操作了同样的表，但只要同一张表的键值离得较远，发生冲突的可能性就不大。一旦在事务提交的时候发现有冲突，那么就从头开始再做一次事务，直到可以提交时没有冲突成功提交为止。后面这个冲突解决的思路实际上文档中并没有，是我自己根据其他论文想出来的一个办法：）。
目前这两个优化，由于还并没有合并到主干，所以我也还没有具体看实现，后续体现在sqlite主干中的存储引擎方面的优化，再梳理出来。
其它
本文概述了sqlite B-Tree存储引擎并发读写的演进，如果想了解更多细节，可以参考之前的文章：