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-21[1]），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[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 管理的頁面之間就不會發生衝突，頂多在落盤到數據庫文件的時候加鎖即可。

• 其次，即便多個寫事務操作了同樣的表，但只要同一張表的鍵值離得較遠，發生衝突的可能性就不大。一旦在事務提交的時候發現有衝突，那麼就從頭開始再做一次事務，直到可以提交時沒有衝突成功提交爲止。後面這個衝突解決的思路實際上文檔中並沒有，是我自己根據其他論文想出來的一個辦法：）。

目前這兩個優化，由於還並沒有合併到主幹，所以我也還沒有具體看實現，後續體現在 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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/dhZ-chslkUudyc_uXgVKzQ