嵌入式數(shù)據(jù)庫(kù)SQLite上多版本并發(fā)控制的設(shè)計(jì)與實(shí)現(xiàn)

景子奇，鄒兆年

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150001）

0 引言

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

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

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

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

1 預(yù)備知識(shí)

1.1 SQLite的體系結(jié)構(gòu)

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

圖1 SQLite的體系結(jié)構(gòu)Fig.1 Architecture of SQLite

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

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

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

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

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

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

1.2.1 MVCC協(xié)議

MVCC 協(xié)議保證事務(wù)訪問到的數(shù)據(jù)庫(kù)內(nèi)容等同于該事務(wù)啟動(dòng)時(shí)已提交的數(shù)據(jù)庫(kù)內(nèi)容（即一致性快照）。因此，MVCC 允許一個(gè)事務(wù)T在另一個(gè)并發(fā)事務(wù)T′更新對(duì)象X 時(shí)讀取X 的舊版本，使這兩個(gè)X 上的讀寫操作不沖突。盡管MVCC 避免了讀寫沖突，但并發(fā)事務(wù)的寫寫沖突仍然存在，需要采取特殊的手段來(lái)解決。根據(jù)解決手段的不同，MVCC可分為使用事務(wù)標(biāo)識(shí)符（TID）標(biāo)注元組可用性的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，它使用事務(wù)的TID 來(lái)預(yù)計(jì)算事務(wù)的序列化順序。當(dāng)事務(wù)T 對(duì)一條邏輯元組執(zhí)行讀操作時(shí)，DBMS 將搜索TID 位于元組begin-ts 和end-ts 字段范圍之間的版本，MVTO 從不允許事務(wù)讀取未提交的版本。在MVTO中，事務(wù)執(zhí)行寫操作先需要持有寫鎖（鎖有版本號(hào)），并將元組的txn-id 設(shè)置為事務(wù)的TID，且總是在元組的最新版本上進(jìn)行寫操作。

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

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

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

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

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

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

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

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

1.2.3 垃圾回收

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

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

1.2.4 索引

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

1.3 事務(wù)的隔離級(jí)別

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

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

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

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

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

本章介紹本文提出的SQLite 上的MVCC 設(shè)計(jì)方案。

2.1 設(shè)計(jì)目標(biāo)

本節(jié)從多個(gè)方面分析SQLite 的設(shè)計(jì)方案，并提出SQLite上MVCC 的設(shè)計(jì)目標(biāo)。

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

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

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

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

2.2 MVCC協(xié)議

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

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

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

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

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

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

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

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

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

插入（INSERT）操作 INSERT 操作用于向數(shù)據(jù)庫(kù)中插入新的元組。設(shè)事務(wù)T的第i個(gè)操作準(zhǔn)備插入一條新元組，該元組的全部屬性值為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對(duì)事務(wù)T后續(xù)操作可見。圖3 中展示了INSERT 操作的過程，其中執(zhí)行INSERT 操作的事務(wù)的TID 為1，該INSERT 操作是該事務(wù)的第0 個(gè)操作，新插入元組的屬性值為b。

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

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

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

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

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

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

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

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

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

2.5 并發(fā)事務(wù)的隔離級(jí)別

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

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

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

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

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

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

2.6 索引

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

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

插入索引項(xiàng) 當(dāng)一條新元組被插入表中時(shí)，需要向該表上每個(gè)索引中插入相應(yīng)的索引項(xiàng)。索引項(xiàng)的T_START、T_END 和CID 字段的值分別與新元組這3 個(gè)字段的值相同。

刪除索引項(xiàng) 當(dāng)表中元組被刪除時(shí)，索引中與該元組對(duì)應(yīng)的索引項(xiàng)并不會(huì)被物理上刪除，而是修改該索引項(xiàng)的T_END 字段，以改變?cè)撍饕?xiàng)的可見性。修改方法與2.3 節(jié)介紹的DELETE 操作修改元組T_END 字段的方法相同。

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

接下來(lái)，在并發(fā)情況下對(duì)SQLite 和SQLite-MVCC 的性能進(jìn)行了實(shí)驗(yàn)比較。實(shí)驗(yàn)中通過設(shè)置系統(tǒng)內(nèi)的并發(fā)線程數(shù)來(lái)調(diào)整系統(tǒng)的并發(fā)度。

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

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

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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