Sqlite 并發(fā)讀寫的演進(jìn)之路
概論
sqlite 底層的存儲(chǔ)基于 B-tree，B-Tree 對(duì)底層存儲(chǔ)的基本讀寫單位是頁(yè)面，而每個(gè)頁(yè)面都由全局唯一的頁(yè)面編號(hào)與之對(duì)應(yīng)，一般來(lái)說(shuō)頁(yè)面編號(hào)從 1 開始遞增。類 B-Tree 的存儲(chǔ)引擎修改數(shù)據(jù)的流程如下圖所示：
從上圖中，需要區(qū)分 B-Tree 類的存儲(chǔ)引擎幾個(gè)核心的模塊：
B-Tree 算法模塊：從頁(yè)面管理器中讀取頁(yè)面到內(nèi)存，進(jìn)行邏輯的修改，修改完畢之后標(biāo)記該頁(yè)面為臟頁(yè)面，這樣頁(yè)面管理器就知道哪些頁(yè)面被修改，后續(xù)需要進(jìn)行落盤。
頁(yè)面管理器：負(fù)責(zé)向 B-Tree 算法模塊提供根據(jù)頁(yè)面編號(hào)讀、寫頁(yè)面的接口。
數(shù)據(jù)庫(kù)文件：這其實(shí)不是一個(gè)模塊，泛指在磁盤上的數(shù)據(jù)庫(kù)相關(guān)文件，任何的修改最終都要落到數(shù)據(jù)庫(kù)文件。在 sqlite 中，數(shù)據(jù)庫(kù)文件是單一文件，在其他存儲(chǔ)引擎里可能是一組相關(guān)的文件。
最上層的 B-Tree 算法模塊，在進(jìn)行寫事務(wù)的時(shí)候，是首先向頁(yè)面管理器發(fā)起讀頁(yè)面到內(nèi)存中的請(qǐng)求，注意到 B-Tree 模塊并不會(huì)直接跟數(shù)據(jù)庫(kù)文件打交道，而是經(jīng)過(guò)頁(yè)面管理器模塊（下面會(huì)展開說(shuō)），修改了頁(yè)面之后標(biāo)記為“臟頁(yè)面”，頁(yè)面管理器最終負(fù)責(zé)將臟頁(yè)面落盤到數(shù)據(jù)庫(kù)文件中。
現(xiàn)在來(lái)談?wù)劇绊?yè)面管理器”模塊的具體工作，也有的實(shí)現(xiàn)稱為“緩存管理器（buffer manager）”。這個(gè)模塊負(fù)責(zé)：在內(nèi)存中管理頁(yè)面
在內(nèi)存中管理頁(yè)面。這涉及到兩部分內(nèi)容：
如果頁(yè)面當(dāng)前不在內(nèi)存中，需要根據(jù)頁(yè)面編號(hào)到磁盤上加載頁(yè)面。
頁(yè)面也并不是每一次讀寫時(shí)都要到磁盤上加載，有些時(shí)候頁(yè)面已經(jīng)在緩存中存在了，這種情況下不需要到磁盤上加載頁(yè)面數(shù)據(jù)。于是，“頁(yè)面管理器”模塊還需要負(fù)責(zé)維護(hù)這些內(nèi)存中的頁(yè)面緩存，何時(shí)淘汰這些頁(yè)面、淘汰哪些內(nèi)存中的頁(yè)面、何時(shí)真正從磁盤上加載，都是這個(gè)模塊的工作。
對(duì)外部而言（這里的外部更多的是 B-Tree 算法模塊），其實(shí)不需要也看不到頁(yè)面緩存的細(xì)節(jié)，頁(yè)面管理器對(duì)外提供根據(jù)頁(yè)面編號(hào)讀、寫頁(yè)面接口即可。
錯(cuò)誤的恢復(fù)，事務(wù)的管理、比如：
一次事務(wù)要修改 N 個(gè)頁(yè)面，修改到中間的時(shí)候，進(jìn)程崩潰了，這時(shí)候重新啟動(dòng)時(shí)需要恢復(fù)到這個(gè)事務(wù)之前的數(shù)據(jù)成功啟動(dòng)，即需要提供回滾事務(wù)的功能。
同樣的一個(gè)事務(wù)要修改 N 個(gè)頁(yè)面，在事務(wù)還未提交的時(shí)候，如果事務(wù)級(jí)別不是 read uncommitted， 那么前面的修改效果不能被其他事務(wù)可見，這也是頁(yè)面管理器需要做的事情，畢竟它對(duì)外提供了讀、寫頁(yè)面的接口，同一個(gè)頁(yè)面編號(hào)的頁(yè)面什么時(shí)候的內(nèi)容可見都由它來(lái)決定。
有了這些基礎(chǔ)的了解，我們來(lái)看看?sqlite 在并發(fā)讀寫方面的演進(jìn)之路
journal
最早的頁(yè)面管理器實(shí)現(xiàn)是基于 Journal 文件的，這個(gè)文件存儲(chǔ)頁(yè)面在修改之前的內(nèi)容：
可以看到的是：
Journal 文件存儲(chǔ)了一個(gè)事務(wù)所要修改的頁(yè)面在修改之前的內(nèi)容，這個(gè)定義有點(diǎn)拗口，姑且稱為“舊頁(yè)面內(nèi)容”。
每次一個(gè)事務(wù)提交之后，意味著這個(gè)事務(wù)所有隊(duì)頁(yè)面的修改都已經(jīng)落到了數(shù)據(jù)庫(kù)文件中，這時(shí)候 Journal 文件里保存的舊頁(yè)內(nèi)容就不再需要了，可以被刪除了。
由于每次事務(wù)修改都要落盤到數(shù)據(jù)庫(kù)文件，這些落盤操作涉及到多次磁盤尋道，即一次事務(wù)多次隨機(jī)磁盤尋道，這樣代價(jià)其實(shí)是很大的。
當(dāng)需要事務(wù)回滾的功能時(shí)，頁(yè)面管理器就可以從 Journal 文件中讀出來(lái)舊頁(yè)面內(nèi)容覆蓋回去。
雖然這個(gè)算法很簡(jiǎn)單，但是缺陷也明顯：它沒(méi)有任何的讀寫并發(fā)支持。每次開始一個(gè)寫事務(wù)，從開始寫事務(wù)，到這個(gè)寫事務(wù)提交完成的過(guò)程中間，其他的讀寫事務(wù)都不能開始，可以說(shuō)是“一寫全卡住”。
WAL
從上面的分析可以看出，以 Journal 文件的機(jī)制，每次寫事務(wù)：
需要把內(nèi)容修改全部落盤到數(shù)據(jù)庫(kù)文件才算完成。
這個(gè)過(guò)程中間，不能同時(shí)存在其他并發(fā)的讀、寫操作。
從 sqlite3.7.0 版本開始（SQLite Release 3.7.0 On 2010-07-211，sqlite 引入了更常見的 WAL 機(jī)制來(lái)解決頁(yè)面的讀寫并發(fā)問(wèn)題，WAL 的原理如下圖所示：
WAL 機(jī)制中，事務(wù)對(duì)頁(yè)面的修改：
并沒(méi)有馬上落到數(shù)據(jù)庫(kù)文件里，而是首先寫入 WAL 文件中。這樣有兩個(gè)好處：
?WAL文件是 append-only 的文件，在文件結(jié)尾處添加新內(nèi)容，對(duì)寫磁盤文件這種操作而言是更快的，因?yàn)樯倭撕芏啻疟P尋道的流程。
有了 WAL 之后，讀寫并發(fā)有了一些改善：由于事務(wù)的修改并沒(méi)有馬上落盤到數(shù)據(jù)庫(kù)文件，所以就不可見，后續(xù)如果需要回滾事務(wù)的修改也更容易：不要這個(gè)事務(wù)修改的那部分 WAL 內(nèi)容即可。
由于修改有時(shí)候還未落盤，需要維護(hù)一個(gè) wal 中頁(yè)面的索引，用于根據(jù)頁(yè)面編號(hào)定位到 WAL 中的頁(yè)面。由于 wal 索引可以控制哪些 wal 文件內(nèi)容“可見”，于是就能控制未提交的事務(wù)修改對(duì)讀操作并不可見了。
WAL 文件不能一直增長(zhǎng)下去，需要定期把 WAL 文件中已經(jīng)提交的事務(wù)修改內(nèi)容落盤到數(shù)據(jù)庫(kù)文件，這個(gè)流程被稱為“checkpoint”。在“checkpoint”之后，wal 索引就可以修改了。雖然 checkpoint 過(guò)程將 WAL 文件中的內(nèi)容落盤到數(shù)據(jù)庫(kù)文件，仍然是針對(duì)數(shù)據(jù)庫(kù)文件的隨機(jī)寫流程，有很多磁盤尋道操作，但是由于一次 checkpoint 累計(jì)了多次寫事務(wù)一次性落盤，代價(jià)小了一些。
雖然同一時(shí)間仍然只能有一個(gè)寫事務(wù)在進(jìn)行，但是讀事務(wù)同時(shí)存在多個(gè)。其核心原因是因?yàn)樾薷牟](méi)有馬上直接落盤到數(shù)據(jù)庫(kù)文件中，這樣修改的可見性就可以由 wal 索引來(lái)控制，即：寫事務(wù)盡管寫，讀事務(wù)盡管讀，只要控制這些寫事務(wù)的修改不在 wal 索引中可見即可。WAL 雖然支持“一寫多讀”，而不是 Journal 文件那樣的“一寫全卡住”，但是還有一個(gè)問(wèn)題沒(méi)有解決：在做 checkpoint 操作的時(shí)候，連寫事務(wù)也不能進(jìn)行了。
兩個(gè)可能的優(yōu)化方案
以下介紹 sqlite 目前在討論的兩個(gè)優(yōu)化方案，之所以說(shuō)是“可能”，因?yàn)榭催@部分代碼還并沒(méi)有合并到主干中，目前暫時(shí)還在分支里，參見：https://github.com/sqlite/sqlite/tree/begin-concurrent-pnu-wal2。
WAL2：
為了解決“checkpoint”時(shí)無(wú)法進(jìn)行寫事務(wù)”的痛點(diǎn)，sqlite 目前在嘗試新的 WAL-2 機(jī)制。
引入 WAL-2 之后，同時(shí)有兩個(gè) WAL 文件，這樣可以：checkpoint 其中一個(gè) WAL 文件時(shí)，繼續(xù)寫另一個(gè) WAL 文件，下一次再進(jìn)行 checkpoint 時(shí)進(jìn)行切換，這樣 checkpoint 就不會(huì)阻塞住寫操作。
BEGIN CONCURRENT：
目前的 WAL 機(jī)制，都只能支持同一時(shí)間一個(gè)寫事務(wù)，BEGIN CONCURRENT 機(jī)制可以實(shí)現(xiàn)多個(gè)寫并發(fā)，這篇?SQLite: Begin Concurrent?文檔中，大概描述了一下這個(gè)優(yōu)化的思路：
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.
簡(jiǎn)單的理解上面的這段話：
不同的寫事務(wù)，如果操作的是不同的表，不同的表數(shù)據(jù)雖然物理上在同一個(gè)數(shù)據(jù)庫(kù)文件，但是邏輯上卻分屬于不同的 B-Tree，這樣不同的 B-Tree 管理的頁(yè)面之間就不會(huì)發(fā)生沖突，頂多在落盤到數(shù)據(jù)庫(kù)文件的時(shí)候加鎖即可。
其次，即便多個(gè)寫事務(wù)操作了同樣的表，但只要同一張表的鍵值離得較遠(yuǎn)，發(fā)生沖突的可能性就不大。一旦在事務(wù)提交的時(shí)候發(fā)現(xiàn)有沖突，那么就從頭開始再做一次事務(wù)，直到可以提交時(shí)沒(méi)有沖突成功提交為止。后面這個(gè)沖突解決的思路實(shí)際上文檔中并沒(méi)有，是我自己根據(jù)其他論文想出來(lái)的一個(gè)辦法：）。
目前這兩個(gè)優(yōu)化，由于還并沒(méi)有合并到主干，所以我也還沒(méi)有具體看實(shí)現(xiàn)，后續(xù)體現(xiàn)在 sqlite 主干中的存儲(chǔ)引擎方面的優(yōu)化，再梳理出來(lái)。
引用鏈接
[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實(shí)現(xiàn)（三）- journal文件備份機(jī)制 - codedump的網(wǎng)絡(luò)日志:
?https://www.codedump.info/post/20211222-sqlite-btree-3-journal
[4]?sqlite3.36版本 btree實(shí)現(xiàn)（四）- WAL的實(shí)現(xiàn) - codedump的網(wǎng)絡(luò)日志:?
https://www.codedump.info/post/20220106-sqlite-btree-4-wal
關(guān)于 Databend
Databend 是一款開源、彈性、低成本，基于對(duì)象存儲(chǔ)也可以做實(shí)時(shí)分析的新式數(shù)倉(cāng)。期待您的關(guān)注，一起探索云原生數(shù)倉(cāng)解決方案，打造新一代開源 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
?文章首發(fā)于公眾號(hào)：Databend
