景子奇，鄒兆年

（哈爾濱工業(yè)大學計算機科學與技術學院，哈爾濱 150001）

0 引言

SQLite［1］是當今非常流行的輕量級開源關系數(shù)據(jù)庫管理系統(tǒng)（Relational DataBase Management System，RDBMS）。與Oracle、MySQL、PostgreSQL 等主流RDMBS 不同，SQLite 是一個嵌入式RDBMS。嵌入式數(shù)據(jù)庫體積非常小，系統(tǒng)資源占用非常低，可以運行于手機等終端設備，使用時不需要運行獨立的數(shù)據(jù)庫引擎，可與應用一同編譯［2］。SQLite 支持大部分SQL92 標準，支持滿足ACID（Atomicity-Consistency-Isolation-Durability）特性（即原子性、一致性、隔離性和持久性）的事務，可以運行在Unix、Linux、Windows、MacOS 等諸多主流操作系統(tǒng)上，并支持C、Java、PHP、Tcl、C#等眾多計算機程序設計語言［3］。SQLite 是用ANSI C 語言編寫的，自身完全獨立，無需依賴任何外部函數(shù)庫。SQLite 的整個數(shù)據(jù)庫（包括數(shù)據(jù)庫模式定義、表和索引）都存儲在宿主機上的單一文件中，便于數(shù)據(jù)庫和應用程序的遷移。由于上述優(yōu)點，SQLite 目前已在移動應用開發(fā)中占據(jù)了相當大的市場份額［4］，并在氣象觀測［5］、礦業(yè)［6］、航空航天［7］等領域得到了廣泛應用。

SQLite 提供了對ACID 事務的完整支持。由于SQLite 的嵌入式特點，SQLite 僅支持數(shù)據(jù)庫級別的事務并發(fā)，允許同一時刻有多個讀事務并發(fā)執(zhí)行，但任何時刻最多只允許一個寫事務執(zhí)行，并且讀事務和寫事務之間可能存在沖突。在事務并發(fā)控制方面，SQLite 采用了兩階段鎖（two-Phase Locking，2PL）并發(fā)控制協(xié)議，通過對操作系統(tǒng)提供的文件鎖進行包裝，實現(xiàn)了數(shù)據(jù)庫粒度的鎖。此外，SQLite 提供了journal 日志機制，可用于故障恢復，無需額外編寫故障恢復模塊［8］。SQLite 的并發(fā)控制方法任意時刻只允許有一個正在執(zhí)行的寫事務，因此無法實現(xiàn)多個寫事務的并發(fā)執(zhí)行。另一方面，由于鎖的粒度為數(shù)據(jù)庫級，因此即使兩個并發(fā)執(zhí)行的讀寫事務分別讀寫不同的數(shù)據(jù)表，它們仍然會發(fā)生沖突。

多版本并發(fā)控制（Multi-Version Concurrency Control，MVCC）［9］是當今RDBMS 中非常流行的事務管理方法。在使用MVCC 的RDBMS 中，關系的每個元組都有多個版本（version），每個版本帶有一個時間戳（timestamp），版本越新，其時間戳越大。MVCC 實現(xiàn)了并發(fā)事務之間的快照隔離（snapshot isolation），保證每個事務在讀數(shù)據(jù)庫時讀到的是事務開始時的數(shù)據(jù)庫實例（即快照）。因此，在支持MVCC 的RDBMS 中不存在讀寫沖突（read-write conflict），即當一個寫事務和一個讀事務并發(fā)執(zhí)行時，讀事務會讀取它應該讀的數(shù)據(jù)庫版本，寫事務會寫入新版本的元組，因此兩個讀寫事務之間不存在沖突。盡管在支持MVCC 的RDBMS 中不存在讀寫沖突，但寫寫沖突（write-wirte conflict）仍然存在。

為了提高SQLite 處理并發(fā)讀事務和寫事務的能力，本文設計并實現(xiàn)了SQLite 上的MVCC。該設計利用SQLite 現(xiàn)有的鎖機制與執(zhí)行結構，通過修改數(shù)據(jù)庫文件頭與記錄格式來確定數(shù)據(jù)的可見性，并改寫SQLite 內置虛擬機的操作序列完成MVCC 的執(zhí)行。在大量數(shù)據(jù)上進行了實驗，驗證了在SQLite 上實現(xiàn)MVCC 可以有效提高數(shù)據(jù)庫上讀寫事務的并發(fā)性。

1 預備知識

1.1 SQLite的體系結構

與MySQL、PostgreSQL 等主流RDMBS 不同，SQLite 具有一個精致的、模塊化的體系結構，并采用了一些獨特的方法來管理關系數(shù)據(jù)庫。SQLite 包含3 個子系統(tǒng)和8 個獨立的模塊，這些模塊可以分為兩部分：前端解析系統(tǒng)和后端處理引擎。SQLite 的體系結構如圖1 所示。

圖1 SQLite的體系結構Fig.1 Architecture of SQLite

SQLite 的前端部分由分詞器、語法分析器和代碼生成器構成，作用是將SQL 語句轉換為SQLite 虛擬機上可以執(zhí)行的字節(jié)碼（opcode）序列。SQLite 的后端主要負責處理SQLite 數(shù)據(jù)庫文件的存儲與讀寫，主要由B-樹、頁緩存（pager）和操作系統(tǒng)接口三部分構成，其中B-樹的作用是對文件頁面中的元組進行索引；頁緩存的作用是通過操作系統(tǒng)接口在B-樹和磁盤之間傳遞頁面。

SQLite 的核心是虛擬機VDBE（Virtual DataBase Engine）。在SQLite 執(zhí) 行SQL 語句時SQLite 的前端 首先將SQL 語句轉換為虛擬機上可以執(zhí)行的字節(jié)碼序列，然后啟動虛擬機執(zhí)行字節(jié)碼，完成SQL 語句的執(zhí)行。在執(zhí)行字節(jié)碼的過程中，虛擬機通過SQLite 后端的B-樹模塊讀寫數(shù)據(jù)庫中的元組。

SQLite 支持ACID 事務，它使用庫級鎖來協(xié)調并發(fā)事務。SQLite 支 持4 種類型的鎖：SHARED 鎖、RESERVED 鎖、PENDING 鎖和EXCLUSIVE 鎖。表1 展示了這4 種類型鎖的相容性。在事務執(zhí)行過程中，讀操作在讀數(shù)據(jù)庫對象時須獲得SHARED 鎖，寫操作在修改未提交時須獲得RESERVED 鎖來阻止其他寫事務啟動。寫事務在內存中完成寫操作時，必須先獲取PENDING 鎖來阻止新的讀事務啟動，并在所有已啟動的讀事務提交后獲取EXCLUSIVE鎖，將修改寫入磁盤。

表1 SQLite中不同類型鎖之間的相容性Tab.1 Compatibility of mutex in SQLite

1.2 多版本并發(fā)控制

多版本并發(fā)控制（MVCC）提出于20 世紀70 年代末，盡管時間久遠，但仍是當前最流行的事務管理方案，幾乎被當今所有RDBMS 采用。

1.2.1 MVCC協(xié)議

MVCC 協(xié)議保證事務訪問到的數(shù)據(jù)庫內容等同于該事務啟動時已提交的數(shù)據(jù)庫內容（即一致性快照）。因此，MVCC 允許一個事務T在另一個并發(fā)事務T′更新對象X 時讀取X 的舊版本，使這兩個X 上的讀寫操作不沖突。盡管MVCC 避免了讀寫沖突，但并發(fā)事務的寫寫沖突仍然存在，需要采取特殊的手段來解決。根據(jù)解決手段的不同，MVCC可分為使用事務標識符（TID）標注元組可用性的MVTO（Multi-Version Timestamp Ordering）、使用樂觀鎖協(xié)議的MVOCC（Multi-Version Optimistic Concurrency Control）［10］和使用兩階段鎖協(xié)議的MV2PL（Multi-Version Two-Phase Locking）。圖2 展示了三種協(xié)議下元組的格式。

圖2 三種MVCC協(xié)議下元組的格式Fig.2 Tuple formats under three MVCC protocols

MVTO 是最初的MVCC，它使用事務的TID 來預計算事務的序列化順序。當事務T 對一條邏輯元組執(zhí)行讀操作時，DBMS 將搜索TID 位于元組begin-ts 和end-ts 字段范圍之間的版本，MVTO 從不允許事務讀取未提交的版本。在MVTO中，事務執(zhí)行寫操作先需要持有寫鎖（鎖有版本號），并將元組的txn-id 設置為事務的TID，且總是在元組的最新版本上進行寫操作。

在MVOCC 中，事務在執(zhí)行讀寫操作時無需獲得鎖，而是在提交前進行驗證，驗證通過后將更新過的對象寫入磁盤。在MVOCC 中，事務的執(zhí)行過程分為讀、驗證和寫入3 個階段，僅在寫入時短暫持有鎖。

MVP2L 使用2PL 來解決寫寫沖突，同時用read-cnt 表示同時在讀該版本的事務數(shù)量，將read-cnt 視為共享鎖，txn-id視為排他鎖。

MVTO 和MV2PL 由于在讀元組時修改了元組的頭部，可能會使其他事務中止，而MVOCC 不會使事務中止，但是驗證和回滾代價較大。為了解決這個問題，有研究將事務使用鏈表串聯(lián)起來，并根據(jù)時間戳進行快速驗證［11］。

1.2.2 數(shù)據(jù)版本的存儲與檢索

MVCC 設計中另一個重要的問題是數(shù)據(jù)版本的存儲與檢索。在版本存儲方面，主要有Append-only、Time-travel 和Delta 三種方法［12］。

Append-only 方法將元組的所有版本都存儲在同一個存儲空間中，并用單向鏈表將元組的不同版本連接起來。根據(jù)單向鏈表的方向是從新版本到舊版本，還是從舊版本到新版本，又可將該方法分為N2O（Newest-To-Oldest）方法和O2N（Oldest-To-Newest）方 法。Append-only 方法已用于PostgresSQL 等數(shù)據(jù)庫管理系統(tǒng)［13］中。

Time-Travel 方法將舊版本存放在單獨的表中，主表中只存儲最新版本［14］。該方法好處是索引始終指向元組的最新版本，省去了事務在更新元組時維護數(shù)據(jù)庫索引的開銷，并且非常適合于那些需要訪問元組最新版本的查詢。

Delta 方法僅在額外的存儲空間中存儲元組版本的變化，這樣做能夠降低寫事務的開銷，但讀事務需要通過計算才能得到所需版本的元組，開銷較大，不適合于讀密集型事務。作為MySQL 默認存儲引擎的InnoDB 便采取這種做法［15］。

1.2.3 垃圾回收

存儲各個版本的數(shù)據(jù)需要消耗大量存儲空間，必須在存儲資源耗盡前將無用的版本刪除，以回收存儲空間。垃圾回收的過程分為3 步：1）檢測無用的過期版本，其中過期版本是指無效的版本（即由中止事務創(chuàng)建的版本）或對任何活躍事務都不可見的版本。2）刪除過期的版本以及和它們有關的關聯(lián)鏈和索引鏈接。3）回收存儲空間。

垃圾回收又分為元組級垃圾回收和事務級垃圾回收［12］。元組級垃圾回收是在執(zhí)行查詢時會定期掃描過期的元組版本，刪除這些版本，從而實現(xiàn)垃圾回收。事務級垃圾回收則是按照事務的維度，要求記錄r/w set，這樣可以把不用的事務所創(chuàng)建的版本都過濾掉［16］。

1.2.4 索引

索引可以使用邏輯指針和物理指針兩種方式實現(xiàn)。物理指針只適用于append-only 版本存儲方法，因為該方法將全部版本存儲在同一個表中，所有索引都可以指向這些版本。當更新表中的元組時，DBMS 會將新創(chuàng)建的版本插入到所有二級索引中。在這種方式下，DBMS 可以在二級索引上查找元組，而無需將次關鍵字與所有索引版本進行比較。MemSQL 和Hekaton 等多個支持MVCC 的DBMS 都采用了這種方案。使用邏輯指針的主要思想是使用固定的邏輯標識符來標識元組，該標識符對于索引中的相同元組是不變的。DBMS 只需使用一個間接層，將元組的標識符映射到其版本鏈的頭部。該方法的優(yōu)點是當元組被修改時，不必更新所有索引，使索引項指向新的物理位置。該方法只需修改間接層中的映射條目即可。但是由于索引沒有指向確切的版本，DBMS 必須從元組版本鏈的頭部開始遍歷版本鏈從而找到可見的版本，查找效率較低，但比較適合于寫密集型事務。

1.3 事務的隔離級別

不同的事務同時對一個數(shù)據(jù)庫進行操作便構成了并發(fā)，并發(fā)事務的操作交叉執(zhí)行，可能會相互干擾，影響事務之間的隔離性。根據(jù)事務中的操作是否修改了數(shù)據(jù)庫的內容，事務被分為讀事務與寫事務。如果數(shù)據(jù)庫上僅執(zhí)行讀事務，則讀事務之間不會相互干擾；然而，當寫事務與其他事務同時執(zhí)行時，則可能會出現(xiàn)一些異常問題。解決這些異常問題的方法稱為并發(fā)控制。人們總結出了事務并發(fā)執(zhí)行時產生的幾種常見的異常問題：臟讀、不可重復讀和幻讀。

臟讀（dirty read）是指事務讀到了其他未提交事務寫的數(shù)據(jù)。若未提交的事務進行了回滾，則引發(fā)了臟讀。不可重復讀（unrepeatable read）是指如果事務已讀過的數(shù)據(jù)被其他事務修改了，該事務再次讀該數(shù)據(jù)時與前一次讀到的內容不一致。幻讀（phantom read）是指當事務多次執(zhí)行相同的查詢時，后面操作因涉及其他事務寫入的新數(shù)據(jù)，導致相同的查詢返回不同的結果。

根據(jù)上述3 種異常問題是否會在事務并發(fā)執(zhí)行過程中出現(xiàn)，可將事務的隔離性劃分成如表2 所示的不同級別。并發(fā)控制的設計目標就是在保證一定的隔離級別的前提下盡可能提高系統(tǒng)的并發(fā)性能［17］。

表2 不同隔離級別的劃分依據(jù)Tab.2 Division rules of different isolation levels

2 SQLite多版本并發(fā)控制的設計

本章介紹本文提出的SQLite 上的MVCC 設計方案。

2.1 設計目標

本節(jié)從多個方面分析SQLite 的設計方案，并提出SQLite上MVCC 的設計目標。

1）在數(shù)據(jù)庫存儲方面，為了便于數(shù)據(jù)庫和應用程序的遷移，SQLite 將整個數(shù)據(jù)庫存儲在單個文件中。在設計SQLite的MVCC 時仍將數(shù)據(jù)庫存儲在單個文件中，并沿用SQLite 的文件組織方式，即一切數(shù)據(jù)頁均為B 樹節(jié)點。MVCC 中，需要存儲一個元組的不同版本。在本設計中將一個表中的新舊版本的元組存儲在該表中。

2）在并發(fā)控制方面，出于移植性的考慮，SQLite 的鎖機制基于文件鎖實現(xiàn)，其粒度為庫級。一旦數(shù)據(jù)庫被某個事務加上了排他鎖，則整個數(shù)據(jù)庫無法被任何其他事務并發(fā)訪問。為保證可移植性，在進行設計MVCC 時應沿用SQLite 的鎖機制，故多個寫事務無法并發(fā)執(zhí)行。因此，本文的MVCC設計方案只支持讀事務與讀事務的并發(fā)執(zhí)行以及讀事務與寫事務的并發(fā)執(zhí)行，而不支持多個寫事務的并發(fā)執(zhí)行。

3）與其他RDBMS 不同，SQLite 并不記錄系統(tǒng)內的活躍（active）事務，因此無法從數(shù)據(jù)庫的角度知道系統(tǒng)內有哪些事務正在執(zhí)行。這使得無法根據(jù)活躍事務來劃分數(shù)據(jù)庫版本，也無法通過為事務分配自增ID 的方式進行版本控制。由于本文的MVCC 設計中不考慮寫-寫事務的并發(fā)，因此數(shù)據(jù)庫在邏輯上被已提交的寫事務劃分為不同的獨立狀態(tài)，可以使用已提交的寫事務將數(shù)據(jù)庫劃分為不同版本，并用單調遞增的版本號進行標記。下文中提到的版本號均指以該方法指定的版本號。

4）在隔離性方面，SQLite 支持的隔離級別為可串行化（serializable）與讀未提交（read uncommitted），其中讀未提交隔離級別僅提供給同一進程內不同線程間的并發(fā)事務。在本文的MVCC 設計中，只考慮可串行化隔離級別。

2.2 MVCC協(xié)議

本節(jié)介紹SQLite 上MVCC 協(xié)議的具體設計。

數(shù)據(jù)庫版本的表示 根據(jù)2.1 節(jié)介紹的設計思路，本設計中根據(jù)已提交的寫事務將數(shù)據(jù)庫劃分成不同的版本。數(shù)據(jù)庫的初始版本號為0。每當一個寫事務提交，數(shù)據(jù)庫的版本號增加1。在實現(xiàn)中在SQLite 數(shù)據(jù)庫文件的頭部記錄數(shù)據(jù)庫當前的版本號。每個版本的數(shù)據(jù)庫由該版本的全體元組構成。為了記錄元組的版本，在每條元組的頭部增加了3 個字段：T_START、T_END 和CID，其中T_START 代表該元組創(chuàng)建時數(shù)據(jù)庫的版本號，T_END 代表該元組結束時數(shù)據(jù)庫的版本號，CID 代表該元組版本在同一事務中被創(chuàng)建的順序。

數(shù)據(jù)可見性規(guī)則 由于數(shù)據(jù)庫存在多個版本，MVCC 規(guī)定一個事務只能看見該事務啟動前最后一個寫事務提交后數(shù)據(jù)庫的狀態(tài)（即一致性快照）。為了實現(xiàn)上述可見性，基于上面介紹的數(shù)據(jù)庫版本表示方法定義了如下數(shù)據(jù)可見性規(guī)則。設t是數(shù)據(jù)庫中的一條元組，使用T_START（t）、T_END（t）和CID（t）分別表示t的T_START、T_END 和CID 字段的值。設T是一個事務，使用TID（T）表示T啟動時數(shù)據(jù)庫的版本號。對于T中的第i個操作，根據(jù)以下3 條規(guī)則來判定元組t是否對該操作可見。

規(guī)則1 如果T是讀事務且T_START（t）≤TID（T）≤T_END（t），則t對T的第i個操作可見。

規(guī)則2 如果T是寫事務且T_START（t）≤TID（T）＜T_END（t），則t對T的第i個操作可見。

規(guī)則3 如果T是寫事務且T_START（t）=TID（T）+1，TID（T）＜T_END（t），CID（t）＜i，則t對T的第i個操作可見。

只要上述規(guī)則之一滿足，則t對T的第i個操作可見。

2.3 數(shù)據(jù)更新操作

在MVCC 協(xié)議下，數(shù)據(jù)更新不再是SQLite 采用的原地更新（in-place update），而是維護數(shù)據(jù)的版本。下面介紹MVCC協(xié)議下的數(shù)據(jù)更新操作。

插入（INSERT）操作 INSERT 操作用于向數(shù)據(jù)庫中插入新的元組。設事務T的第i個操作準備插入一條新元組，該元組的全部屬性值為val，T的TID 為TID（T）。該操作將在表中插入一條新的元組t，其中T_START（t）=TID（T）+1，T_END（t）=∞，CID=i，t的屬性值為val。根據(jù)2.2 節(jié)介紹的可見性規(guī)則，新插入的元組t對事務T后續(xù)操作可見。圖3 中展示了INSERT 操作的過程，其中執(zhí)行INSERT 操作的事務的TID 為1，該INSERT 操作是該事務的第0 個操作，新插入元組的屬性值為b。

圖3 INSERT操作的執(zhí)行過程Fig.3 Execution process of INSERT operation

刪除（DELETE）操作 DELETE 操作用于刪除數(shù)據(jù)庫中的元組。在MVCC 下，該操作不會在物理上刪除元組，而是修改該元組可見版本的T_END 字段，設置其可見的結束時間。設事務T準備刪除一條元組，t是T當前可見的元組版本，T的TID 為TID（T）。DELETE 操作將T_END（t）設置為TID（T）。根據(jù)2.2 節(jié)介紹的可見性規(guī)則，t對T不再可見，從而在邏輯上刪除了t，然而對于某些早于T啟動的事務，t仍然可見。圖4 展示了DELETE 操作的過程，其中執(zhí)行DELETE 操作的事務的TID 為2，rowid=0 的元組是該事務可見的待刪除元組版本。

圖4 DELETE操作的執(zhí)行過程Fig.4 Execution process of DELETE operation

更新（UPDATE）操作 UPDATE 操作用于修改數(shù)據(jù)庫中的元組。在MVCC 下，該操作不會原地修改元組，而是先執(zhí)行DELETE 操作，刪除該元組；再執(zhí)行INSERT 操作，插入更新后的元組。圖5 展示了UPDATE 操作的過程。設執(zhí)行UPDATE 操作的事務的TID 為2，該INSERT 操作是該事務的第1 個操作，該事務準備將rowid=0 的元組的值a修改為b。該事務首先執(zhí)行DELETE 操作，將rowid=0 的元組的T_END字段設置為2；然后執(zhí)行INSERT 操作，插入rowid=2 的元組。

圖5 UPDATE操作的執(zhí)行過程Fig.5 Execution process of UPDATE operation

2.4 事務的執(zhí)行流程

由于本文的MVCC 設計允許讀-寫事務并發(fā)，但不允許寫-寫事務并發(fā)，因此需要對SQLite 的事務執(zhí)行流程進行重新設計。圖6 展示了MVCC 下一個事務的執(zhí)行流程（這里未使用檢查點）。在事務執(zhí)行過程中，系統(tǒng)使用SHARED 與RESERVED 兩種類型的鎖來控制并發(fā)。寫事務通過持有RESERVED 鎖來阻止其他寫事務的執(zhí)行，但并不會影響讀事務的啟動和提交。

圖6 事務的執(zhí)行流程Fig.6 Flowchart of transaction execution

事務的提交發(fā)生在commit 或end 語句執(zhí)行時。如果提交的事務為寫事務，則SQLite 會將該事務修改過的數(shù)據(jù)寫入數(shù)據(jù)庫文件中。如2.3 節(jié)所述，寫事務在執(zhí)行寫操作時需要用到該事務的TID。在寫數(shù)據(jù)庫文件時需要判斷當前寫事務的TID 是否已經被其他已提交的事務使用過。進行該檢查的理由如下：即使當前寫事務已經獲得了RESERVED 鎖，使得其他事務無法升級到寫事務，然而在該寫事務提交后，其他訪問該版本數(shù)據(jù)的事務仍可以獲得RESERVED 鎖并嘗試提交。如果這種情況發(fā)生，兩個提交的寫事務提供的TID可能相同，因而無法正確劃分數(shù)據(jù)版本。由于上述原因，在寫事務提交前必須進行版本檢查，只有寫事務的TID 大于當前已提交的數(shù)據(jù)庫版本，寫事務才能成功提交，否則寫事務回滾（rollback）。該方法可以保證數(shù)據(jù)庫版本的唯一性。

2.5 并發(fā)事務的隔離級別

基于2.2～2.4 節(jié)的內容，給出本文提出的MVCC 設計方案下并發(fā)事務的隔離級別的分析。

定理1在本文提出的MVCC 設計方案下并發(fā)事務的隔離級別為可串行化（serializable）。

證明 根據(jù)可串行化隔離級別的定義，只需證明基于本文的MVCC 設計，并發(fā)事務不會產生臟讀（dirty read）、不可重復讀（unrepeatable read）和幻讀（phantom read）。

1）無臟讀。由SQLite 事務模型可知，未提交的事務不會將任何修改過的數(shù)據(jù)寫入數(shù)據(jù)庫文件中，因此任何事務讀到的數(shù)據(jù)一定是已提交事務寫入的版本，故不會產生臟讀。

2）無不可重復讀。設t是事務T1 可見的元組版本，根據(jù)可見性規(guī)則，有T_START（t）≤TID（T1）≤T_END（t）。設事務T2 對t進行了修改，則根據(jù)2.3 節(jié)介紹的UPDATE 操作，T2首先將T_END（t）設置為TID（T2），其中TID（T1）≤TID（T2）。根據(jù)2.2 節(jié)中的可見性規(guī)則，t仍然對T1 可見。然后，T2 插入一個新的元組版本t′，且T_START（t′）=TID（T2）+1。根據(jù)2.2 節(jié)中的可見性規(guī)則，t′對T1 不可見。T1 可見的仍然是t，故不會產生不可重復讀。

3）無幻讀。由于系統(tǒng)使用了庫級鎖，同一時刻只允許一個寫事務執(zhí)行，因此寫事務插入的新元組的版本號一定大于當先所有讀事務的TID。由可見性規(guī)則1 可知，這些新元組對任何讀事務均不可見，因此不會發(fā)生幻讀。

2.6 索引

索引用于對表中的元組進行快速查找。如果表被更新，則該表上的索引也要被更新。SQLite 中索引與表的格式相同，因此在MVCC 下，B+樹索引葉節(jié)點中的索引項也記錄著對應元組的T_START、T_END 和CID 字段的值。下面介紹如何在MVCC 下對索引進行查找和更新。

查找索引項 在索引上進行查找時，除了根據(jù)給定的索引鍵值進行查找外，還需要對查找到的索引項進行可見性檢查，確保事務可見的索引與事務可見的數(shù)據(jù)庫一致性快照是一致的。值得注意的是，在一個事務查找索引項的過程中，另一個事務可能同時更新了索引，導致B 樹葉節(jié)點發(fā)生分裂。這有可能導致葉節(jié)點中信息與緩存中的父節(jié)點中的信息不一致，從而查不到索引項。為了解決該問題，需要保證在查找索引項的過程中B 樹頁面的版本沒有發(fā)生變化。如果B 樹頁面的版本發(fā)生了變化，則需要終止本次索引查找并重新啟動索引查找操作。

插入索引項 當一條新元組被插入表中時，需要向該表上每個索引中插入相應的索引項。索引項的T_START、T_END 和CID 字段的值分別與新元組這3 個字段的值相同。

刪除索引項 當表中元組被刪除時，索引中與該元組對應的索引項并不會被物理上刪除，而是修改該索引項的T_END 字段，以改變該索引項的可見性。修改方法與2.3 節(jié)介紹的DELETE 操作修改元組T_END 字段的方法相同。

更新索引項 如2.3 節(jié)所述，當更新表中元組時，采取先執(zhí)行DELETE 操作再執(zhí)行INSERT 操作的方式。相應地，還要在每個索引上先刪除索引項，再插入更新后的索引項。刪除和插入索引項的方法均已在前面介紹過。

2.7 舊版本數(shù)據(jù)回收

當數(shù)據(jù)庫長時間運行后，會積累大量舊版本數(shù)據(jù)。舊版本數(shù)據(jù)對新啟動的事務不可見，因此不會被新事務訪問。然而，所有版本的數(shù)據(jù)均存儲于同一個SQLite 數(shù)據(jù)庫文件中，這會導致文件過大，嚴重降低系統(tǒng)性能。因此，MVCC 設計必須為SQLite 設計舊版本數(shù)據(jù)回收方法。

為SQLite 設計舊版本數(shù)據(jù)回收方法主要面臨兩個困難：1）現(xiàn)有基于MVCC 的RDBMS 采用多種方法（如版本鏈、undo日志）來記錄元組版本之間的關系，但受限于SQLite 的現(xiàn)有設計，無法在不大量改變SQLite 的前提下采取類似的方法來加速查詢符合當前事務可見性的數(shù)據(jù)。2）SQLite 并不記錄系統(tǒng)內的活躍事務，因此無法從數(shù)據(jù)庫的角度判斷元組的某個版本是否還在被某個活躍的讀事務讀取，因而無法主動清除數(shù)據(jù)庫中的舊版本數(shù)據(jù)。

設計提供了下面的舊版本數(shù)據(jù)回收方法。首先，SQLite是一種嵌入式數(shù)據(jù)庫，可以和應用程序的代碼一起編譯，用戶可以在應用程序中記錄系統(tǒng)內的活躍事務。然后，當系統(tǒng)內沒有活躍事務時，SQLite 可以啟動舊版本數(shù)據(jù)清理。具體過程如下：首先，阻止任何新事務啟動。然后，打開數(shù)據(jù)庫中所有的表，逐條掃描表中每條元組，使用所有最新版本的可見數(shù)據(jù)創(chuàng)建新的數(shù)據(jù)庫。當新數(shù)據(jù)庫創(chuàng)建完成后，用新數(shù)據(jù)庫替換原有的數(shù)據(jù)庫。

3 實驗與結果分析

3.1 實驗設置

本文在SQLite 3.34.0 上實現(xiàn)了MVCC，并在Visual Studio 2019 中使用nmake 指 令執(zhí)行SQLite 的Makefile.msc 文件，將實現(xiàn)了MVCC 的SQLite 編譯為動態(tài)鏈接庫。后文將實現(xiàn)了MVCC 的SQLite 稱為SQLite-MVCC。實驗測試程序用C++語言編寫，并用Visual Studio 2019 編譯。實驗測試程序在多個線程內打開SQLite-MVCC，并在事務中使用SQL 語句進行一系列操作。實驗所使用的計算機的配置如下：Intel Core i7-7700 處理器（4 核，2.8 GHz），16 GB 內存，120 GB 硬盤（讀取速度為546 MB/s），運行Windows 10 操作系統(tǒng)。

實驗在1 個隨機生成的表上進行。表中含有INT、TEXT、BLOB 和DOUBLE 類型的 屬性各1 個，其 中INT 和DOUBLE 類型的屬性值為隨機數(shù)，TEXT 和BLOB 類型的屬性值由隨機生成的短序列拼接而成。元組長度在設定值的±2 B 內變動。實驗中預設的元組長度分別為10 B、50 B 和20 B，用于反映不同應用情境下的數(shù)據(jù)。為使實驗數(shù)據(jù)在圖表中能合理顯示，將上述3 種元組長度下的表中元組數(shù)分別設置為50 萬條、20 萬條和10 萬條。

3.2 非并發(fā)情況下數(shù)據(jù)寫操作的性能

本文首先在非并發(fā)情況下對SQLite-MVCC 上INSERT、DELETE 和UPDATE 操作與SQLite 上對應操作的執(zhí)行時間進行了實驗對比。圖7 展示了實驗結果。

圖7（a）對比了SQLite 和SQLite-MVCC 上INSERT 操作的執(zhí)行時間。實驗中使用INSERT 語句分別在SQLite 和SQLite-MVCC 上依次插入50 萬條元組，每條語句插入1 條元組，然后測試插入操作的平均執(zhí)行時間。實驗結果顯示，SQLite 和SQLite-MVCC 上插入1 條元組的平均執(zhí)行時間接近。但由于SQLite-MVCC 中的元組增加了T_START、T_END和CID 字段，比SQLite 中的元組略長，故SQLite-MVCC 上的插入操作略慢于SQLite 上的插入操作，但總體差異不大。

圖7（b）對比了SQLite 和SQLite-MVCC 上DELETE 操作的執(zhí)行時間。實驗中使用DELETE 語句分別在SQLite 和SQLite-MVCC 上刪除50 萬條元組，并測試刪除1 條元組的平均執(zhí)行時間。實驗結果顯示，SQLite 和SQLite-MVCC 上刪除操作的平均執(zhí)行時間接近，因為SQLite 和SQLite-MVCC 均采用修改元組頭部的方式實現(xiàn)數(shù)據(jù)刪除，區(qū)別僅在于SQLite 修改元組的前4 個字節(jié)，而SQLite-MVCC 修改3 個字節(jié)長的T_END 字段，因此二者性能接近。

圖7（c）對比了SQLite 和SQLite-MVCC 上UPDATE 操作的執(zhí)行時間。實驗方法與測試DELETE 操作時類似。實驗結果顯示，SQLite-MVCC 上UPDATE 操作的平均執(zhí)行時間顯著高于SQLite 上UPDATE 操作。這是因為SQLite 進行原地更新，只需修改元組的屬性值即可，而SQLite-MVCC 需要先執(zhí)行1 次DELETE 操作，再執(zhí)行1 次INSERT 操作。因此，SQLite-MVCC 上UPDATE 操作在理論上要比SQLite 上UPDATE 操作多花費1 倍以上的時間，實驗結果驗證了這一點。另外，SQLite-MVCC 執(zhí)行過程中沿著B+樹葉節(jié)點遍歷新插入的元組，即使元組不可見，也要被讀取1 次并進行可見性判斷，從而花費更多額外的時間。

圖7 非并發(fā)情況下寫操作性能的對比Fig.7 Performance comparison of non-concurrent write operations

綜上所述，除UPDATE 外，SQLite-MVCC 上各項操作的時間性能比SQLite 上略有下降，但在可接受的范圍內。受實現(xiàn)方法的影響，SQLite-MVCC 上更新操作的時間性能下降較多，因此更新元組數(shù)量較多的事務不適于使用SQLite-MVCC。

3.3 非并發(fā)情況下數(shù)據(jù)讀操作的性能

本文還在非并發(fā)情況下對SQLite和SQLite-MVCC 的數(shù)據(jù)讀取性能進行了實驗對比。實驗分別在元組長度為10 B 和200 B 的2 個隨機生成的表上進行，查詢語句的選擇謂詞的選擇度約為0.1%，并在2 個表上各執(zhí)行了100 次查詢，測試100次查詢的總體執(zhí)行時間。圖8展示了實驗結果。如圖8（a）所示，當元組長度為10 B 時，SQLite-MVCC 處理1 個查詢的時間要比SQLite 多15%～20%。這是因為讀取元組中的版本信息并進行元組的可見性判斷耗費了額外的時間。如圖8（b）所示，當元組長度為200 B 時，SQLite 和SQLite-MVCC 的查詢執(zhí)行時間的差異在5%以內，基本可以忽略。

圖8 非并發(fā)情況下讀操作性能的對比Fig.8 Performance comparison of non-concurrent read operations

3.4 并發(fā)情況下數(shù)據(jù)庫的性能

接下來，在并發(fā)情況下對SQLite 和SQLite-MVCC 的性能進行了實驗比較。實驗中通過設置系統(tǒng)內的并發(fā)線程數(shù)來調整系統(tǒng)的并發(fā)度。

該部分實驗首先測試了SQLite 和SQLite-MVCC 在不同并發(fā)線程數(shù)下的吞吐量，其中吞吐量使用系統(tǒng)每秒鐘處理的事務數(shù)來衡量。圖9 展示了實驗結果。在該實驗中，同類事務的執(zhí)行時間基本相同，不存在因隨機性而導致的執(zhí)行時間偏差。實驗結果表明，在相同線程數(shù)下，SQLite-MVCC 的吞吐量高于SQLite。這表明SQLite-MVCC 的讀-寫事務并發(fā)設計提高了系統(tǒng)的并發(fā)性。然而，隨著線程數(shù)的增加，SQLite-MVCC 相較SQLite 的并發(fā)性能優(yōu)勢逐漸下降，主要原因如下：

圖9 不同線程數(shù)下系統(tǒng)的吞吐量Fig.9 System throughput under different numbers of threads

1）線程數(shù)的增加導致了并發(fā)事務發(fā)生沖突的概率下降。當線程數(shù)為2 時，約有55%的事務發(fā)生沖突；而當線程數(shù)為6時，僅有5%左右的事務發(fā)生沖突。這是因為SQLite-MVCC不持支寫-寫事務并發(fā)，系統(tǒng)中最多只有1 個線程能夠進行寫操作。隨著線程數(shù)的增加，讀事務在全體并發(fā)事務中的占比提高，寫事務的CPU 資源占用率下降，從而導致寫事務的提交變得緩慢，致使并發(fā)事務發(fā)生沖突的概率下降。

2）3.3 節(jié)的實驗表明，SQLite-MVCC 執(zhí)行讀事務的效率略低于SQLite，因此當線程數(shù)增加，讀事務占比提高時，吞吐量提升的速度會下降。此外，SQLite-MVCC 更容易使CPU 到達性能瓶頸，從而導致吞吐量隨線程數(shù)的增加其增長的速度放緩。

本文對并發(fā)狀態(tài)下SQLite-MVCC 和SQLite 執(zhí)行相同工作量的事務時所用的時間進行了實驗對比。圖10 展示了實驗結果。圖10 結果反映在各種線程數(shù)下，SQLite-MVCC 的執(zhí)行時間均少于SQLite。這是由于SQLite-MVCC 支持讀-寫事務并發(fā)，在實際執(zhí)行事務時總是可以提前完成寫事務，使整體效率變高。該實驗結果表明，在實際的有限任務工作負載下，SQLite-MVCC 的并發(fā)性顯著優(yōu)于SQLite。

圖10 不同線程數(shù)下完成固定事務所需的時間Fig.10 Time cost for handling same transactions using different numbers of threads

數(shù)據(jù)集的大小對數(shù)據(jù)庫系統(tǒng)的性能有內在影響，本文通過實驗對此進行了測試。圖11 展示了元組長度對數(shù)據(jù)庫大小的影響。從實驗結果來看，在相同的元組長度下，SQLite-MVCC 數(shù)據(jù)庫比SQLite 數(shù)據(jù)庫大，這是因為SQLite-MVCC 元組頭部包含額外的版本信息，占用了更多的空間。但是隨著元組長度的增大，版本信息所占的空間比例越來越低，對數(shù)據(jù)庫大小的影響越來越不明顯。圖12 展示了在不同的元組長度下SQLite-MVCC 相較SQLite 的并發(fā)性能提升比例。可見，隨著元組長度的增加，SQLite-MVCC 的并發(fā)性能提升越來越大，因為SQLite-MVCC 處理版本信息的開銷在總開銷中所占的比例越來越低，總性能提升。在實際使用數(shù)據(jù)庫時，URL、TEXT、BLOB 等類型數(shù)據(jù)的長度一般在50 B 以上，此時SQLite-MVCC 有著不錯的表現(xiàn)，并且此時存儲元組頭部的版本信息所消耗的存儲空間基本可以忽略不計。

圖11 元組長度對數(shù)據(jù)庫大小的影響Fig.11 Influence of tuple length on database size

圖12 不同元組長度下SQLite-MVCC并發(fā)性能的提升Fig.12 Concurrent performance improvement of SQLite-MVCC under different tuple lengths

基于以上實驗結果可知，SQLite-MVCC 相較SQLite 并發(fā)性能有所提高，并具有一定實際意義，且在一定范圍內并發(fā)事務中寫事務比例越高性能提升越大，該方法更適合寫事務占比高的并發(fā)場合使用。此外，當有長讀取事務執(zhí)行時也可考慮使用該方法提高數(shù)據(jù)庫性能。

4 結語

本文為SQLite 設計了支持可串行化隔離級別的MVCC協(xié)議，并實現(xiàn)了支持MVCC 的SQLite，使SQLite 上并發(fā)的讀事務和寫事務不會沖突，有效提高了SQLite 處理并發(fā)事務的能力，為研究如何提高SQLite 的并發(fā)性能提供了一種新的技術思路。后續(xù)還可以從以下幾個方面進行深入研究：1）將MVCC 與其他方法（如多粒度鎖）相結合，進一步提高系統(tǒng)的并發(fā)性能，并解決目前寫事務和寫事務無法并發(fā)執(zhí)行的問題。2）設計更符合MVCC 的編譯器與字節(jié)碼，使系統(tǒng)可以跳過不可見的元組，進一步提高系統(tǒng)性能。3）設計更加高效的舊版本數(shù)據(jù)回收機制。