技术学习分享_一航技术 技术资讯 Sqlite 并发读写的演进之路

Sqlite 并发读写的演进之路

广告位

概论

sqlite 底层的存储基于 B-tree,B-Tree 对底层存储的基本读写单位是页面,而每个页面都由全局唯一的页面编号与之对应,一般来说页面编号从 1 开始递增。类 B-Tree 的存储引擎修改数据的流程如下图所示:

Sqlite 并发读写的演进之路

从上图中,需要区分 B-Tree 类的存储引擎几个核心的模块:

  • B-Tree 算法模块:从页面管理器中读取页面到内存,进行逻辑的修改,修改完毕之后标记该页面为脏页面,这样页面管理器就知道哪些页面被修改,后续需要进行落盘。
  • 页面管理器:负责向 B-Tree 算法模块提供根据页面编号读、写页面的接口。
  • 数据库文件:这其实不是一个模块,泛指在磁盘上的数据库相关文件,任何的修改最终都要落到数据库文件。在 sqlite 中,数据库文件是单一文件,在其他存储引擎里可能是一组相关的文件。

最上层的 B-Tree 算法模块,在进行写事务的时候,是首先向页面管理器发起读页面到内存中的请求,注意到 B-Tree 模块并不会直接跟数据库文件打交道,而是经过页面管理器模块(下面会展开说),修改了页面之后标记为“脏页面”,页面管理器最终负责将脏页面落盘到数据库文件中。

现在来谈谈“页面管理器”模块的具体工作,也有的实现称为“缓存管理器(buffer manager)”。这个模块负责:在内存中管理页面

在内存中管理页面。这涉及到两部分内容:

  • 如果页面当前不在内存中,需要根据页面编号到磁盘上加载页面。

  • 页面也并不是每一次读写时都要到磁盘上加载,有些时候页面已经在缓存中存在了,这种情况下不需要到磁盘上加载页面数据。于是,“页面管理器”模块还需要负责维护这些内存中的页面缓存,何时淘汰这些页面、淘汰哪些内存中的页面、何时真正从磁盘上加载,都是这个模块的工作。

  • 对外部而言(这里的外部更多的是 B-Tree 算法模块),其实不需要也看不到页面缓存的细节,页面管理器对外提供根据页面编号读、写页面接口即可。

错误的恢复,事务的管理、比如:

  • 一次事务要修改 N 个页面,修改到中间的时候,进程崩溃了,这时候重新启动时需要恢复到这个事务之前的数据成功启动,即需要提供回滚事务的功能。
  • 同样的一个事务要修改 N 个页面,在事务还未提交的时候,如果事务级别不是 read uncommitted, 那么前面的修改效果不能被其他事务可见,这也是页面管理器需要做的事情,毕竟它对外提供了读、写页面的接口,同一个页面编号的页面什么时候的内容可见都由它来决定。

有了这些基础的了解,我们来看看 sqlite 在并发读写方面的演进之路

journal

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

Sqlite 并发读写的演进之路

可以看到的是:

  • Journal 文件存储了一个事务所要修改的页面在修改之前的内容,这个定义有点拗口,姑且称为“旧页面内容”。

  • 每次一个事务提交之后,意味着这个事务所有队页面的修改都已经落到了数据库文件中,这时候 Journal 文件里保存的旧页内容就不再需要了,可以被删除了。

  • 由于每次事务修改都要落盘到数据库文件,这些落盘操作涉及到多次磁盘寻道,即一次事务多次随机磁盘寻道,这样代价其实是很大的。

  • 当需要事务回滚的功能时,页面管理器就可以从 Journal 文件中读出来旧页面内容覆盖回去。

  • 虽然这个算法很简单,但是缺陷也明显:它没有任何的读写并发支持。每次开始一个写事务,从开始写事务,到这个写事务提交完成的过程中间,其他的读写事务都不能开始,可以说是“一写全卡住”。

WAL

从上面的分析可以看出,以 Journal 文件的机制,每次写事务:

  • 需要把内容修改全部落盘到数据库文件才算完成。
  • 这个过程中间,不能同时存在其他并发的读、写操作。

从 sqlite3.7.0 版本开始(SQLite Release 3.7.0 On 2010-07-211,sqlite 引入了更常见的 WAL 机制来解决页面的读写并发问题,WAL 的原理如下图所示:

Sqlite 并发读写的演进之路

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 机制。Sqlite 并发读写的演进之路

引入 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。

Sqlite 并发读写的演进之路 文章首发于公众号:Databend

本文来自网络,不代表技术学习分享_一航技术立场,转载请注明出处。

作者: 一航技术

上一篇
下一篇
广告位

发表回复

返回顶部