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-211，sqlite 引入了更常见的 WAL 机制来解决页面的读写并发问题，WAL 的原理如下图所示：
WAL 机制中，事务对页面的修改：
并没有马上落到数据库文件里，而是首先写入 WAL 文件中。这样有两个好处：
WAL文件是 append-only 的文件，在文件结尾处添加新内容，对写磁盘文件这种操作而言是更快的，因为少了很多磁盘寻道的流程。
有了 WAL 之后，读写并发有了一些改善：由于事务的修改并没有马上落盘到数据库文件，所以就不可见，后续如果需要回滚事务的修改也更容易：不要这个事务修改的那部分 WAL 内容即可。
由于修改有时候还未落盘，需要维护一个 wal 中页面的索引，用于根据页面编号定位到 WAL 中的页面。由于 wal 索引可以控制哪些 wal 文件内容“可见”，于是就能控制未提交的事务修改对读操作并不可见了。
WAL 文件不能一直增长下去，需要定期把 WAL 文件中已经提交的事务修改内容落盘到数据库文件，这个流程被称为“checkpoint”。在“checkpoint”之后，wal 索引就可以修改了。虽然 checkpoint 过程将 WAL 文件中的内容落盘到数据库文件，仍然是针对数据库文件的随机写流程，有很多磁盘寻道操作，但是由于一次 checkpoint 累计了多次写事务一次性落盘，代价小了一些。
虽然同一时间仍然只能有一个写事务在进行，但是读事务同时存在多个。其核心原因是因为修改并没有马上直接落盘到数据库文件中，这样修改的可见性就可以由 wal 索引来控制，即：写事务尽管写，读事务尽管读，只要控制这些写事务的修改不在 wal 索引中可见即可。WAL 虽然支持“一写多读”，而不是 Journal 文件那样的“一写全卡住”，但是还有一个问题没有解决：在做 checkpoint 操作的时候，连写事务也不能进行了。
两个可能的优化方案
以下介绍 sqlite 目前在讨论的两个优化方案，之所以说是“可能”，因为看这部分代码还并没有合并到主干中，目前暂时还在分支里，参见：https://github.com/sqlite/sqlite/tree/begin-concurrent-pnu-wal2。
WAL2：
为了解决“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 主干中的存储引擎方面的优化，再梳理出来。
引用链接
[1] SQLite Release 3.7.0 On 2010-07-21:
https://www.sqlite.org/releaselog/3_7_0.html
[2] SQLite: Begin Concurrent:
https://www.sqlite.org/cgi/src/doc/begin-concurrent/doc/begin_concurrent.md
[3] sqlite3.36版本 btree实现（三）- journal文件备份机制 - codedump的网络日志:
https://www.codedump.info/post/20211222-sqlite-btree-3-journal
[4] sqlite3.36版本 btree实现（四）- WAL的实现 - codedump的网络日志:
https://www.codedump.info/post/20220106-sqlite-btree-4-wal
关于 Databend
Databend 是一款开源、弹性、低成本，基于对象存储也可以做实时分析的新式数仓。期待您的关注，一起探索云原生数仓解决方案，打造新一代开源 Data Cloud。
Databend 文档：https://databend.rs/
Twitter：https://twitter.com/Datafuse_Labs
Slack：https://datafusecloud.slack.com/
Wechat：Databend
GitHub ：https://github.com/datafuselabs/databend
文章首发于公众号：Databend
