关于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

最早的页面管理器实现是基于 Journa l 文件的，这个文件存储页面在批改之前的内容：

能够看到的是：

• 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/sql…。

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/releas…
[2] SQLite: Begin Concurrent:

 https://www.sqlite.org/cgi/sr…
[3] sqlite3.36 版本 btree 实现（三）- journal 文件备份机制 – codedump 的网络日志:

 https://www.codedump.info/pos…
[4] sqlite3.36 版本 btree 实现（四）- WAL 的实现 – codedump 的网络日志: 

https://www.codedump.info/pos…

对于 Databend

Databend 是一款开源、弹性、低成本，基于对象存储也能够做实时剖析的旧式数仓。期待您的关注，一起摸索云原生数仓解决方案，打造新一代开源 Data Cloud。

• Databend 文档：https://databend.rs/
• Twitter：https://twitter.com/Datafuse_…
• Slack：https://datafusecloud.slack.com/
• Wechat：Databend
• GitHub：https://github.com/datafusela…

文章首发于公众号：Databend