概论
从上图中,需要区分 B-Tree 类的存储引擎几个核心的模块:
最上层的 B-Tree 算法模块,在进行写事务的时候,是首先向页面管理器发起读页面到内存中的请求,注意到 B-Tree 模块并不会直接跟数据库文件打交道,而是经过页面管理器模块(下面会展开说),修改了页面之后标记为“脏页面”,页面管理器最终负责将脏页面落盘到数据库文件中。
现在来谈谈“页面管理器”模块的具体工作,也有的实现称为“缓存管理器(buffer manager)”。这个模块负责:在内存中管理页面
如果页面当前不在内存中,需要根据页面编号到磁盘上加载页面。
页面也并不是每一次读写时都要到磁盘上加载,有些时候页面已经在缓存中存在了,这种情况下不需要到磁盘上加载页面数据。于是,“页面管理器”模块还需要负责维护这些内存中的页面缓存,何时淘汰这些页面、淘汰哪些内存中的页面、何时真正从磁盘上加载,都是这个模块的工作。
对外部而言(这里的外部更多的是 B-Tree 算法模块),其实不需要也看不到页面缓存的细节,页面管理器对外提供根据页面编号读、写页面接口即可。
错误的恢复,事务的管理、比如:
journal
Journal 文件存储了一个事务所要修改的页面在修改之前的内容,这个定义有点拗口,姑且称为“旧页面内容”。
每次一个事务提交之后,意味着这个事务所有队页面的修改都已经落到了数据库文件中,这时候 Journal 文件里保存的旧页内容就不再需要了,可以被删除了。
由于每次事务修改都要落盘到数据库文件,这些落盘操作涉及到多次磁盘寻道,即一次事务多次随机磁盘寻道,这样代价其实是很大的。
当需要事务回滚的功能时,页面管理器就可以从 Journal 文件中读出来旧页面内容覆盖回去。
虽然这个算法很简单,但是缺陷也明显:它没有任何的读写并发支持。每次开始一个写事务,从开始写事务,到这个写事务提交完成的过程中间,其他的读写事务都不能开始,可以说是“一写全卡住”。
WAL
从上面的分析可以看出,以 Journal 文件的机制,每次写事务:
WAL 机制中,事务对页面的修改:
两个可能的优化方案
为了解决“checkpoint”时无法进行写事务”的痛点,sqlite 目前在尝试新的 WAL-2 机制。
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 管理的页面之间就不会发生冲突,顶多在落盘到数据库文件的时候加锁即可。
其次,即便多个写事务操作了同样的表,但只要同一张表的键值离得较远,发生冲突的可能性就不大。一旦在事务提交的时候发现有冲突,那么就从头开始再做一次事务,直到可以提交时没有冲突成功提交为止。后面这个冲突解决的思路实际上文档中并没有,是我自己根据其他论文想出来的一个办法:)。
引用链接
[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 是一款开源、弹性、低成本,基于对象存储也可以做实时分析的新式数仓。期待您的关注,一起探索云原生数仓解决方案,打造新一代开源 Data Cloud。