面向非易失性內(nèi)存緩沖區(qū)的SQLite-CC

胡耀藝 胡卉芪 周烜 周傲英

摘要：近年來非易失性存儲(chǔ)（Non Volatile Memory，NVM）飛速發(fā)展，它具有的持久化、大容量、低延遲、按字節(jié)尋址、高密度和低能耗等優(yōu)越特性，強(qiáng)烈沖擊著目前的數(shù)據(jù)庫系統(tǒng)架構(gòu).SQLite是一款輕量級(jí)關(guān)系型數(shù)據(jù)庫，實(shí)現(xiàn)了無服務(wù)器、零配置、事務(wù)性的SQL數(shù)據(jù)庫引擎.其為每個(gè)連接維護(hù)一個(gè)緩沖區(qū)，有著空間開銷大和數(shù)據(jù)一致性檢測(cè)的問題，同時(shí)由于采用了相對(duì)簡(jiǎn)單的串行化單寫事務(wù)執(zhí)行方式和按頁記錄日志等方案，帶來了回滾日志模式性能低和寫入放大以及WAL模式存儲(chǔ)空間要求等問題.為了解決上述挑戰(zhàn)，構(gòu)建了一種新的基于非易失性內(nèi)存的SQLite緩沖區(qū)的方案SQLite-CC（Copy Cache），充分考慮了非易失性內(nèi)存的硬件特性，引入CC-manager用于維護(hù)事務(wù)原子性，加入修改頁面索引來保證數(shù)據(jù)庫文件與緩存的一致性.實(shí)驗(yàn)表明，其達(dá)到了和SQLite-WAL模式相當(dāng)?shù)牟l(fā)性能，相比于回滾日志模式事務(wù)吞吐量提升了3倍，讀寫延遲降低了40%且有效解決了磁盤中的寫放大問題.

關(guān)鍵詞：NVM;SQLite;緩沖區(qū)優(yōu)化;日志方案

中圖分類號(hào)：TP392文獻(xiàn)標(biāo)志碼：ADOI：10.3969/j.issn.l000-5641.2021.06.013

SQLite-CC based on non-volatile memory cache

HU Yaoyi，HU Huiqi，ZHOU Xuan，ZHOU Aoying

（School of Data Science and Engineering. East China Normal University，Shanghai 200062，China）

Abstract：In recent years，non-volatile memory （NVM）has developed rapidly. Its advantages，among others，include：persistence，large capacity，low latency，byte addressing，high density，and low energy consumption - all of which have impacted current database system architecture. SQLite is a lightweight relational database widely used in embedded fields such as mobile platforms. It operates as a serverless，zero-configuration，transactional SQL database engine. It maintains a cache for each connection，which results in problems with large space overhead and data consistency detection. At the same time，it adopts a relatively simple serialized single-write transaction execution method and page-based logging，which offers low performance and write amplification in the journal mode and a storage space requirement in the WAL mode during execution. In order to address the above challenges，a new scheme of SQLite Cache based on non-volatile memory，SQLite-CC （Copy Cache），is constructed，which fully considers the hardware characteristics of non-volatile memory and ensures the atomicity of transactions using a CC- manager and by adding an updated page index to ensure the consistency of database files and cache. Benchmarking tests show that it can achieve the same concurrency performance as SQLite- WAL mode. Compared with the rollback mode，it improves the execution performance of transactions by 3 times，reduces latency by 40%，and effectively solves the issue of writeamplification on disks.

Keywords：NVM;SQLite;cache optimization;logging solution

0引言

一直以來，關(guān)系型數(shù)據(jù)庫系統(tǒng)都是面向磁盤的，建立了由HDD/SSD和DRAM構(gòu)成的兩層存儲(chǔ)架構(gòu)：高延遲、持久化、大容量的磁盤搭配低延遲、易失性、容量小的內(nèi)存.然而，近年來隨著以Intel's optane DIMM為代表的非易失性內(nèi)存（Non Volatile Memory，NVM）的出現(xiàn)和飛速發(fā)展，憑借其持久化、大容量、低延遲、按字節(jié)尋址等優(yōu)越特性，被認(rèn)為是具有“革命性的”下一代存儲(chǔ)設(shè)備.這種新型硬件強(qiáng)烈地沖擊了文件系統(tǒng)，緩存系統(tǒng)等存儲(chǔ)系統(tǒng)，毫無疑問也對(duì)目前的數(shù)據(jù)庫系統(tǒng)架構(gòu)與設(shè)計(jì)產(chǎn)生了新的影響.在傳統(tǒng)的數(shù)據(jù)庫架構(gòu)不再適用于NVM的基礎(chǔ)之上，對(duì)此學(xué)界重點(diǎn)討論的領(lǐng)域包括三個(gè)方面：1）日志和恢復(fù)協(xié)議[1-2];2）存儲(chǔ)和緩沖區(qū)管理[3];3）索引數(shù)據(jù)結(jié)構(gòu)[4].本文聚焦于輕量級(jí)數(shù)據(jù)庫系統(tǒng)SQLite和非易失性內(nèi)存的緩沖區(qū)管理，SQLite具有小巧易用的特點(diǎn)，由于其開發(fā)效率高，可靠的事務(wù)支持和輕量級(jí)代碼，SQLite在實(shí)際的應(yīng)用中使用得非常廣泛.與此同時(shí)，對(duì)輕量級(jí)代碼庫的妥協(xié)迫使它采用不太復(fù)雜但成本更高的方案來提供事務(wù)支持，例如串行化的事務(wù)執(zhí)行方式，以頁面粒度進(jìn)行物理日志記錄，冗余日志和強(qiáng)制提交策略.這些設(shè)計(jì)使得其在事務(wù)執(zhí)行過程中負(fù)擔(dān)了過多的I/O開銷[5].同時(shí)在SQLite的緩沖區(qū)管理模塊中使用了默認(rèn)緩存和共享緩存兩種設(shè)計(jì)，前者為每一個(gè)連接創(chuàng)建一個(gè)緩沖區(qū)，造成空間的浪費(fèi)和需要花時(shí)間協(xié)調(diào)緩存之間不一致問題，后者則是多個(gè)連接共享一個(gè)緩沖區(qū)，減少了空間占用，卻降低了并發(fā).

針對(duì)以上問題，本文提出了一種新的緩沖區(qū)組織管理方案SQLite-CC（Copy Cache），在進(jìn)行緩沖區(qū)創(chuàng)建和管理的同時(shí)維護(hù)一份拷貝cache，NVM的大容量使得空間代價(jià)得以被容忍.本文加入了一個(gè)額外的管理器，對(duì)事務(wù)的執(zhí)行進(jìn)行協(xié)調(diào)，另外在cache中的頁面上分別進(jìn)行了是否修改的標(biāo)注，輔以一個(gè)修改頁的哈希索引結(jié)構(gòu)來保證數(shù)據(jù)的一致性.雙版本的存在，維護(hù)了并發(fā)性，減小了讀寫阻塞，實(shí)現(xiàn)了與WAL相似的一寫多讀并發(fā).同時(shí)保證事務(wù)的原子性和持久性.在對(duì)系統(tǒng)不做大量修改的前提下充分發(fā)揮NVM所帶來的優(yōu)勢(shì)，綜合了SQLite默認(rèn)緩存和共享緩存的優(yōu)勢(shì)，且做到steal和no-force的緩沖區(qū)管理策略.此項(xiàng)工作的主要貢獻(xiàn)點(diǎn)在于以下3點(diǎn)：

（1）發(fā)揮了非易失性內(nèi)存的特性，將其作為SQLite緩存部分的存儲(chǔ)，綜合了兩個(gè)緩沖區(qū)的優(yōu)點(diǎn)，減少了內(nèi)存與磁盤的交互，優(yōu)化了數(shù)據(jù)庫的讀寫性能，相比于回滾日志模式事務(wù)吞吐量提升了3倍，事務(wù)延遲降低了40%.

（2）憑借非易失性內(nèi)存相對(duì)于內(nèi)存的持久化的特性，以cache為載體，通過拷貝雙版本的方式，變相地實(shí)現(xiàn)了undo日志和redo日志的功能，優(yōu)化了在磁盤中的日志記錄，減少了磁盤的空間開銷和寫放大，加速了數(shù)據(jù)庫恢復(fù).

（3）保持了與SQLite-WAL模式相當(dāng)?shù)淖x讀并發(fā)和一寫多讀并發(fā)性能，并且解決了WAL模式中存在的尾部延遲問題，是NVM應(yīng)用的一次有效嘗試.

1相關(guān)背景

1.1非易失性內(nèi)存及PMDK

非易失性內(nèi)存（NVM）是一種新型的硬件存儲(chǔ)介質(zhì)，兼具磁盤和DRAM （Dynamic Random Access Memory）的特性.通常，它具有比磁盤小很多的讀寫延遲，并且讀延遲相當(dāng)接近DRAM，寫延遲略高于DRAM.同時(shí)，NVM有著比DRAM高的密度，意味著相同體積，它可以提供更大的容量，預(yù)示著其作為主存替代品的潛力[6].在使用時(shí)間方面，有實(shí)驗(yàn)表明，其耐久性，即每個(gè)內(nèi)存單元寫的最大次數(shù)，有著優(yōu)于閃存的耐久性[7].另外由于NVM不需要像DRAM那樣周期性地刷新來維持內(nèi)存中的數(shù)據(jù)庫，所以它在能耗方面也是有優(yōu)勢(shì)的[8]，其中，字節(jié)尋址和持久性等是其與生俱來的特性[9].

PMDK（Persistent Memory Development Kit）持久化內(nèi)存開發(fā)套件，是Intel開源的一個(gè)可用于持久化內(nèi)存開發(fā)的多種庫和工具的集合.這些都建立在Linux和Windows上均可以使用的Direct Access（DAX）功能的基礎(chǔ)上，允許應(yīng)用程序通過內(nèi)存映射文件直接訪問持久化內(nèi)存.PMDK抽象出了各種底層操作，并將某些操作封裝到事務(wù)性的API中，目前已經(jīng)有了十余個(gè)針對(duì)各種持久化的用例庫，為持久化內(nèi)存編程提供了不同的功能，并且支持C、C++、Java和Python語言的使用.通過PMDK可以更有效地管理持久化內(nèi)存.較為底層的庫有l(wèi)ibpmem，它為管理持久性內(nèi)存提供了底層支持.開發(fā)人員可以通過將內(nèi)存文件映射到DRAM來訪問持久性內(nèi)存，為防止內(nèi)存泄漏，需要顯式釋放持久性內(nèi)存. libpmemobj將持久性內(nèi)存文件轉(zhuǎn)換為靈活的對(duì)象存儲(chǔ)，支持事務(wù)，內(nèi)存管理，鎖定，列表和許多其他功能，并且保證了事務(wù)的原子性.使用libpmem和libpmemobj，C/C++開發(fā)人員可以輕松創(chuàng)建和管理內(nèi)存中的持久數(shù)據(jù).

1.2數(shù)據(jù)庫緩沖區(qū)管理

消除不完整或中止的事務(wù)以保持原子性的影響的過程稱為undo.為了持久性而恢復(fù)已提交事務(wù)影響的過程稱為redo.恢復(fù)子系統(tǒng)必須提供這些功能之一，執(zhí)行的工作量取決于數(shù)據(jù)庫緩沖區(qū)管理器如何處理正在提交的事務(wù)的更新數(shù)據(jù).緩沖區(qū)管理器是數(shù)據(jù)庫組件，它負(fù)責(zé)協(xié)調(diào)主內(nèi)存（易失性存儲(chǔ)）和磁盤（非易失性存儲(chǔ)）之間的數(shù)據(jù)傳輸.可以原子寫入非易失性存儲(chǔ)的存儲(chǔ)單元稱為page.將對(duì)（易失性）緩沖池中的頁面副本進(jìn)行更新，并在以后將這些副本寫到非易失性存儲(chǔ)中.如果緩沖區(qū)管理器允許未提交的事務(wù)進(jìn)行更新以覆蓋非易失性存儲(chǔ)器上數(shù)據(jù)項(xiàng)的最新提交值，則說它支持steal策略（反之稱為no-steal）.如果緩沖區(qū)管理器確保在允許提交事務(wù)之前將事務(wù)所做的所有更新都反映在非易失性存儲(chǔ)上，則可以說它支持force策略（反之則為no-force）.

支持steal策略意味著在需要回滾事務(wù)（由于事務(wù)失敗或系統(tǒng)崩潰）的情況下，撤消事務(wù)將涉及由該事務(wù)更新的所有非易失性數(shù)據(jù)副本的值恢復(fù)為先前的已提交狀態(tài).相反，no-steal策略可確保非易失性存儲(chǔ)上的數(shù)據(jù)值有效，因此不需要還原它們.no-force策略增加了某些已提交的數(shù)據(jù)值在系統(tǒng)崩潰期間丟失的可能性，因?yàn)闊o法保證將它們放置在非易失性存儲(chǔ)中.這意味著可能需要大量的redo工作來保持已提交更新的持久性.相比之下，force策略可確保將提交的更新放置在非易失性存儲(chǔ)上，以便在系統(tǒng)崩潰的情況下，更新仍將反映在非易失性存儲(chǔ)上的數(shù)據(jù)庫副本中.

可以明顯看出，支持no-steal和force組合的緩沖區(qū)管理器對(duì)undo和redo恢復(fù)的需求最少.但是，這些策略可能會(huì)在正常操作期間（沒有崩潰或回滾時(shí)）對(duì)DBMS的性能產(chǎn)生負(fù)面影響，因?yàn)樗鼈兿拗屏司彌_區(qū)管理器的適用性.no-steal要求緩沖區(qū)管理器將更新后的數(shù)據(jù)保留在內(nèi)存中，直到事務(wù)提交或?qū)?shù)據(jù)寫入非易失性存儲(chǔ)上的臨時(shí)位置（例如交換區(qū)）為止.force策略的問題在于，它可能會(huì)在提交事務(wù)的關(guān)鍵路徑期間施加大量的磁盤寫開銷.由于這些原因，許多緩沖區(qū)管理器都支持steal和no-force策略.

2系統(tǒng)架構(gòu)

本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)針對(duì)SQLite在非易失性內(nèi)存上應(yīng)用的緩沖區(qū)管理方案，用于提升其執(zhí)行和并發(fā)性能.本章將介紹其整體架構(gòu)，總體架構(gòu)圖和特點(diǎn)展示在圖1中.

SQLite是一個(gè)實(shí)現(xiàn)無服務(wù)器的事務(wù)型SQL數(shù)據(jù)庫引擎的軟件庫.應(yīng)用程序鏈接到SQLite庫以利用其數(shù)據(jù)庫管理功能，將數(shù)據(jù)庫作為單獨(dú)的文件存在磁盤中，并發(fā)事務(wù)可以訪問同一數(shù)據(jù)庫，但是在任何時(shí)候都只能有一個(gè)事務(wù)可以更新數(shù)據(jù)庫，因?yàn)檎麄€(gè)數(shù)據(jù)庫文件都由寫事務(wù)鎖定，直到完成為止. pager模塊負(fù)責(zé)管理內(nèi)存緩沖區(qū)，B樹模塊負(fù)責(zé)處理選擇和更新語句.

原始的SQLite設(shè)計(jì)有默認(rèn)的緩存模式和共享緩存模式，默認(rèn)緩存模式下，即使線程兩次或多次打開同一個(gè)數(shù)據(jù)庫文件，SQLite也會(huì)為打開的數(shù)據(jù)庫連接分配單獨(dú)的緩存，通過其不同的所有者的pager對(duì)象訪問緩存.啟用共享緩存模式后，如果一個(gè)線程打開對(duì)于一個(gè)數(shù)據(jù)庫的多個(gè)連接，則這些連接共享同一個(gè)page cache，且在3.5.0版本中，修改了共享緩存模式，以便可以在整個(gè)進(jìn)程中共享同一緩存，而不僅僅是在單個(gè)線程中共享.

所以在設(shè)計(jì)的過程中，本文將原始SQLite的緩沖區(qū)進(jìn)行了擴(kuò)展，通過記錄拷貝的cache來保證數(shù)據(jù)庫執(zhí)行正確性和優(yōu)化效果，所以將其稱為SQLite-CC（Copy Cache）.這個(gè)設(shè)計(jì)與原始的SQLite有三個(gè)不同點(diǎn)：CC manager，拷貝的緩沖區(qū)和修改頁的索引.

CC manager：用于管理緩沖區(qū)和保證事務(wù)的執(zhí)行，它為每個(gè)事務(wù)分配時(shí)間戳，用于協(xié)調(diào)讀寫事務(wù)之間的版本，當(dāng)寫事務(wù)進(jìn)行時(shí)，兩個(gè)cache呈現(xiàn)出不一致的狀態(tài)，完成寫事務(wù)之后，同步兩者的狀態(tài)，進(jìn)而允許提交事務(wù).

copy cache：在每個(gè)進(jìn)程所維護(hù)的緩沖區(qū)pcache中額外加入一個(gè)拷貝的cache.一方面，兩個(gè)cache以一主一副的身份存在，寫事務(wù)均在主cache中進(jìn)行，副cache可以在主cache處于修改狀態(tài)的過程中，提供數(shù)據(jù)讀取操作的支持，以此增強(qiáng)了并發(fā)性.另一方面，由于非易失性內(nèi)存的持久化特性，結(jié)合CC manager對(duì)當(dāng)前緩沖區(qū)狀態(tài)進(jìn)行管理，可以保證事務(wù)的原子性和持久性.拷貝的副cache在主cache進(jìn)行修改的時(shí)候，保證讀事務(wù)并發(fā)的同時(shí)，副cache仍然保持著原有數(shù)據(jù)，其承擔(dān)undo log的作用以保障事務(wù)的原子性.當(dāng)出現(xiàn)事務(wù)abort的時(shí)候或者事務(wù)修改未完成宕機(jī)時(shí)，副cache的值為準(zhǔn)確值，可以用于還原主cache中進(jìn)行的修改.當(dāng)出現(xiàn)事務(wù)修改已完成但是未提交的情況，即主cache已經(jīng)完成修改，副cache沒有同步，同樣通過CC manager的狀態(tài)檢查，判定當(dāng)前狀態(tài)，主cache可以承擔(dān)redo log的作用，將其修改值同步到副cache，并提交事務(wù)，以保障事務(wù)的持久性.

updated page index：記錄cache中修改的頁的編號(hào)，標(biāo)記出與磁盤中數(shù)據(jù)庫文件不同步的頁.而后通過延遲同步的方式，在被換出緩沖的時(shí)刻，將更新同步到磁盤上，以此來保證非易失性內(nèi)存中的緩沖區(qū)與磁盤中數(shù)據(jù)庫文件的一致性.

故而，本設(shè)計(jì)做到了比默認(rèn)緩存模式更小的空間占用，比共享緩存模式更高的并發(fā)性能，實(shí)現(xiàn)了steal和no-force的緩存區(qū)策略，而且事務(wù)的相關(guān)操作都由存儲(chǔ)在非易失內(nèi)存中的緩沖區(qū)層面進(jìn)行，在保證事務(wù)的原子性和持久性的同時(shí)，減少了磁盤讀寫，極大地提升了執(zhí)行效率.

3事務(wù)處理

3.1寫入/更新流程

在進(jìn)行寫操作的時(shí)候，SQLite通過B+ tree模塊向pager模塊發(fā)出請(qǐng)求，然后經(jīng)過page cache對(duì)數(shù)據(jù)進(jìn)行修改.在原始的SQLite回滾日志模式中，寫入/修改的操作，需要先進(jìn)行數(shù)據(jù)庫文件拷貝，將原有數(shù)據(jù)保存為回滾日志文件，并持久化到磁盤中，然后對(duì)內(nèi)存中的數(shù)據(jù)頁進(jìn)行修改，之后才將數(shù)據(jù)同步到磁盤上進(jìn)行持久化保存.在WAL模式中，則是采用了相反的方法，在進(jìn)行數(shù)據(jù)庫寫操作之前，會(huì)先在內(nèi)存中對(duì)數(shù)據(jù)進(jìn)行修改，然后將修改后的數(shù)據(jù)頁作為日志持久化到磁盤上，而原有的數(shù)據(jù)庫文件內(nèi)容保存不變，并在隨后的某個(gè)時(shí)間通過檢查點(diǎn)的方式同步到數(shù)據(jù)庫文件中.

但是在SQLite-CC中，進(jìn)行寫操作前，首先需要經(jīng)過CC manager的判定，確保當(dāng)前兩個(gè)cache處于同步狀態(tài)，即可獲得寫入權(quán)限時(shí)，分配給其寫時(shí)間戳.在修改過程中會(huì)在緩沖區(qū)中，短暫形成兩個(gè)cache不同步的時(shí)段，如圖2所示，兩個(gè)cache由一個(gè)pcache句柄統(tǒng)一管理，主cache對(duì)應(yīng)的hash table處于已修改的狀態(tài)，已被修改的頁，也被視為redo log page.拷貝cache對(duì)應(yīng)的hash table則是保持原有的值不變，所以此處與主cache中被修改處對(duì)應(yīng)的頁，可以視為undo log page，即正常的修改流程為經(jīng)歷同步，到不同步，再到同步的流程.由于NVM的持久性，無須擔(dān)心數(shù)據(jù)丟失，可以在同步之后僅記錄updated page index來確保當(dāng)緩沖區(qū)的頁被換出之后與數(shù)據(jù)庫文件的一致性，不用急切地將修改值刷新到磁盤中的數(shù)據(jù)庫文件，從而減少了磁盤I/O.

3.2讀取流程

在SQLite-CC中，讀操作將面臨著兩種不同的情況.一種情況是當(dāng)兩個(gè)cache處于同步狀態(tài)時(shí)，其讀取流程跟原始的SQLite相同.另一種情況則是，當(dāng)前的cache狀態(tài)不同步，即此時(shí)存在正在進(jìn)行當(dāng)中的寫入操作，根據(jù)讀寫事務(wù)的先后順序，分為兩種情況：當(dāng)讀在寫事務(wù)之后，將通過新的cache進(jìn)行讀取，讀取到修改后的值;反之則通過拷貝的cache進(jìn)行讀取，讀取到舊值，其余流程相同.如圖3所示，在時(shí)刻2有寫入操作，那么當(dāng)寫事務(wù)開始時(shí)，將出現(xiàn)新舊讀事務(wù)的劃分，對(duì)之前已經(jīng)執(zhí)行完成的讀操作的線程沒有影響，正在進(jìn)行的操作如讀事務(wù)3，讀事務(wù)6將被作為舊的讀事務(wù)，通過拷貝cache進(jìn)行舊值的讀取，然后當(dāng)舊事務(wù)線程全部完成之后，對(duì)兩個(gè)cache進(jìn)行同步，完成此次操作.在時(shí)刻2之后開始執(zhí)行的線程讀事務(wù)2，讀事務(wù)4則會(huì)在等待執(zhí)行過程中的寫事務(wù)提交完成之后通過主cache讀取到最新值.

3.3提交

與采用force策略的原始SQLite不同，SQLite-CC對(duì)提交操作采用了非常簡(jiǎn)單的過程.在提交時(shí)，原始SQLite將所有要修改的數(shù)據(jù)頁從緩沖區(qū)刷新到數(shù)據(jù)庫和回滾日志文件（在“刪除日志”模式下）或WAL日志文件（在WAL日志模式下）.提交時(shí)間開銷非常大，因?yàn)槊總€(gè)臟頁在物理上被寫入兩次（包括在WAL日志模式下由檢查點(diǎn)引起的寫入操作），并且寫入屏障操作（通過fsync調(diào)用）至少執(zhí)行一次[10].相反，SQLite-CC是將修改同步到拷貝的cache中并且在updated page index中標(biāo)記修改的頁號(hào).有這個(gè)簡(jiǎn)單的過程就足夠了，因?yàn)槊看蔚臄?shù)據(jù)讀寫都要通過cache進(jìn)行，只要保證了cache中為最新數(shù)據(jù)，之后采用組提交和清空更新頁面索引的方式跟數(shù)據(jù)庫文件進(jìn)行同步.

3.4中止

當(dāng)事務(wù)中止時(shí)，原始的SQLite從緩沖池中刪除由事務(wù)更新的臟頁.由于原始的SQLite采用了Steal緩沖區(qū)管理策略，因此中止的事務(wù)所做的某些更改可能已經(jīng)寫入數(shù)據(jù)庫或日志文件.需要通過將undo日志中的數(shù)據(jù)復(fù)制到數(shù)據(jù)庫文件中，以此來回滾之前的更改，或者通過忽略/刪除WAL日志中存儲(chǔ)的已修改的數(shù)據(jù)來保證事務(wù)的原子性.對(duì)于SQLite-CC未提交的修改則是停留在主cache中，而副cache中數(shù)據(jù)仍然未發(fā)生改變，因此當(dāng)發(fā)生回滾時(shí)，可以找到副cache中對(duì)應(yīng)的數(shù)據(jù)，以此作為undo日志的數(shù)據(jù)去回滾主cache中未提交的修改.

4恢復(fù)

當(dāng)出現(xiàn)宕機(jī)時(shí)，原始的SQLite有自己的方法在重新啟動(dòng)時(shí)進(jìn)行故障檢測(cè)，當(dāng)它在“刪除日志”模式下運(yùn)行時(shí)，若存在熱日志則表示SQLite在重新啟動(dòng)之前處于崩潰狀態(tài)，其中熱日志（宕機(jī)前已經(jīng)記錄，但是由于事務(wù)并未提交，仍然存在的日志）可用于恢復(fù)數(shù)據(jù)庫.當(dāng)原始的SQLite以WAL日志模式運(yùn)行時(shí)，WAL日志里沒有commit記錄的部分則表示崩潰時(shí)正在進(jìn)行的事務(wù)，刪除該部分修改即可.SQLite-CC檢測(cè)故障的方式與前兩者均不相同，其事務(wù)的原子性和持久性都是經(jīng)由cache來進(jìn)行保證的，由于NVM的持久性，任何情況下的故障恢復(fù)都能夠獲取到宕機(jī)前緩沖區(qū)的狀態(tài).如果存在需要恢復(fù)的數(shù)據(jù)，則SQLite-CC的緩沖區(qū)中的兩個(gè)cache肯定不是同步的，由于在任何時(shí)候最多只有一個(gè)寫事務(wù)在同一數(shù)據(jù)庫上運(yùn)行，那么兩個(gè)cache必有一個(gè)是準(zhǔn)確的，所以通過檢測(cè)副cache的啟用狀態(tài)，可以判斷所要恢復(fù)的狀態(tài)點(diǎn)，進(jìn)而做出對(duì)應(yīng)的回滾或者重做操作，使數(shù)據(jù)庫達(dá)到一致性狀態(tài).另外，如果宕機(jī)發(fā)生在將緩沖區(qū)中換出的頁同步到數(shù)據(jù)庫文件時(shí)，通過檢測(cè)updated page index中是否還記錄有該頁和對(duì)比換出頁與數(shù)據(jù)庫文件里對(duì)應(yīng)頁的值，可以判定是否需要再次將cache中的頁復(fù)制到數(shù)據(jù)庫文件中，以保證數(shù)據(jù)的一致性.

5實(shí)驗(yàn)分析

在本章中，展示了對(duì)SQLite-CC進(jìn)行實(shí)驗(yàn)評(píng)估的結(jié)果，實(shí)驗(yàn)使用YCSB（Yahoo！Cloud Serving Benchmark）的綜合負(fù)載[11]，通過對(duì)不同比例的讀寫負(fù)載來評(píng)估其運(yùn)行情況和性能.另外，為了檢測(cè)運(yùn)行的并發(fā)性能，本文分別對(duì)單線程、雙線程、四線程、八線程的情況進(jìn)行了負(fù)載測(cè)試.各組實(shí)驗(yàn)均加入了SQLite在Journal-Delete日志模式和WAL日志模式的對(duì)照組.

5.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)機(jī)器配置了兩個(gè)Intel（R）Xeon（R）Gold 6240 M CPU @ 2.60 GHz，每個(gè)CPU具有18個(gè)內(nèi)核.該系統(tǒng)配置了128 G DRAM和512 GB 3DXPoint內(nèi)存，然后，我們應(yīng)用PMDK將文件映射到程序的虛擬地址空間，加載和存儲(chǔ)數(shù)據(jù)到3DXPoint[12].為了比較，我們采用了YCSB的負(fù)載生成100000條數(shù)據(jù)，每條記錄的大小為100個(gè)字節(jié)，執(zhí)行了10000個(gè)操作進(jìn)行分析，負(fù)載分別是YCSB-A（讀寫比例50%/50%），YCSB-B（讀寫比例95%/5%），YCSB-C （讀寫比例100%/0%）.

5.2事務(wù)吞吐量

圖4比較并展示了3種模式下的事務(wù)吞吐量，可以看到，隨著寫操作比例的下降，三者的吞吐量均呈現(xiàn)上升趨勢(shì)，而在負(fù)載相同的情況下，SQLite-CC的性能略優(yōu)于SQLite-WAL，SQLite-journal表現(xiàn)最差.在讀寫比例為95%/5%的負(fù)載中，SQLite-CC約為SQLite-journal吞吐量的3倍.

5.3事務(wù)延遲

接下來評(píng)估了3種模式下事務(wù)執(zhí)行延遲，圖5、圖6分別展示了對(duì)于讀取和更新事務(wù)時(shí)延遲分布，不同模式下的延遲走勢(shì)大致相同，SQLite-CC延遲最低，大約是SQLite-journal模式下的60%.另外，SQLite-CC的修改操作方面的表現(xiàn)要優(yōu)于其在讀取操作方面的表現(xiàn)，這是由于SQLite串行化事務(wù)執(zhí)行所決定的.對(duì)于平均延遲，SQLite-WAL和SQLite-CC均表現(xiàn)出了不錯(cuò)的性能，而SQLite-journal模式則與前兩者有較大差距.這里是因?yàn)镾QLite-journal模式下默認(rèn)刪除之前記錄的日志文件造成的. 另外，SQLite-WAL模式尾部延遲過高是由于檢查點(diǎn)開銷所導(dǎo)致的，當(dāng)日志頁數(shù)達(dá)到閾值時(shí)首先會(huì)在WAL文件中檢查數(shù)據(jù)庫頁，時(shí)間由檢查點(diǎn)數(shù)據(jù)庫頁的數(shù)量控制，而SQLite-CC有著較大改善，如表1所示.

5.4多線程情況

為了展示并發(fā)效果，如圖7—10所示，本文分別用單線程、雙線程、四線程、八線程對(duì)3種模式在讀寫比例各不相同的四種負(fù)載上進(jìn)行了運(yùn)行時(shí)間測(cè)試，由于SQLite為確保線程安全，采用單寫的方式進(jìn)行數(shù)據(jù)修改.多線程對(duì)于SQLite并不是提升并發(fā)的好方法.同時(shí)可以看到的是在寫操作占比較大的負(fù)載中，SQLite-journal模式表現(xiàn)較差，而SQLite-WAL模式采用redo日志，記錄新值的一次刷盤，對(duì)此場(chǎng)景支持性較好，SQLite-CC則是做到了與SQLite-WAL模式下相當(dāng)?shù)膱?zhí)行時(shí)間.另外，很明顯，讀操作比例越高，SQLite單寫的影響就會(huì)越小，三者差距也就逐漸縮小.

6相關(guān)工作

SQLite-CC通過應(yīng)用實(shí)際的英特爾傲騰非易失性內(nèi)存，結(jié)合硬件特性與軟件相協(xié)調(diào)，以加快事務(wù)性數(shù)據(jù)庫系統(tǒng)的性能，并減少磁盤I/O.本章將從與SQLite-CC關(guān)聯(lián)的角度，回顧基于非易失性內(nèi)存相關(guān)應(yīng)用工作.

文獻(xiàn)[13]司將相變存儲(chǔ)器（Phase Change Memory，PCM）集成在SQLite數(shù)據(jù)庫系統(tǒng)中，與SQLite-CC不同的是，它們主要聚焦于日志的記錄方式，并未涉及數(shù)據(jù)庫的內(nèi)部組件.SQLite-PPL為了避免SQLite的寫放大，將相變存儲(chǔ)器PCM作為與各個(gè)數(shù)據(jù)頁關(guān)聯(lián)的日志記錄設(shè)備，采用per-page log和global log結(jié)合的記錄方式，利用PCM的差異寫入性能來優(yōu)化事務(wù)性能;SQLite-SSL[14]則是針

對(duì)移動(dòng)應(yīng)用設(shè)備負(fù)載大多是插入和本地更新的特性，采用在非易失內(nèi)存中進(jìn)行邏輯日志記錄（用以記錄SQL語句）結(jié)合現(xiàn)有的WAL模式進(jìn)行檢查點(diǎn)和恢復(fù).

Chen等[15]最先探討了在用非易失內(nèi)存代替DRAM，及在非易失內(nèi)存上進(jìn)行關(guān)系數(shù)據(jù)庫相關(guān)設(shè)計(jì)上的參數(shù)（cache misses、cache line write backs、words modified）和分析指標(biāo)（total wear、energy、total PCM access lantency）等;其他工作考慮非易失內(nèi)存對(duì)關(guān)系數(shù)據(jù)庫存儲(chǔ)的影響.文獻(xiàn)[16]從數(shù)據(jù)庫中非易失性內(nèi)存管理的角度，把非易失性內(nèi)存作為中間層，并且在DRAM和非易失性內(nèi)存中都維護(hù)一個(gè)緩沖區(qū)，在其間將DRAM以cache-line的粒度從NVM中加載數(shù)據(jù)進(jìn)行傳遞，并提出了一種減少內(nèi)存占用的Mini page數(shù)據(jù)結(jié)構(gòu)，以更好地利用NVM的隨機(jī)訪問快的特性，同時(shí)減小了DRAM的空間占用.

Oukid等[17]將NVM作為存儲(chǔ)，設(shè)計(jì)并實(shí)現(xiàn)了SOFORT，這是為OLTP（On-Line Transaction Process）和OLAP（Online Analytical Processing）工作負(fù)載設(shè)計(jì)的混合存儲(chǔ)引擎，該引擎采用MVCC和非易失性指針來避免記錄日志.Arulraj等[18]用MVCC和非易失性指針來避免記錄日志，針對(duì)NVM的特性，采用模擬退火算法調(diào)節(jié)數(shù)據(jù)遷移策略，同時(shí)提出了多存儲(chǔ)層次結(jié)構(gòu)的代價(jià)限制函數(shù)，以實(shí)現(xiàn)針對(duì)任意工作負(fù)載的存儲(chǔ)層次管理策略和自適應(yīng)機(jī)制.

7總結(jié)

在本文中，我們針對(duì)SQLite工作負(fù)載和設(shè)計(jì)特點(diǎn)結(jié)合非易失性內(nèi)存的特性提出了一種緩沖區(qū)優(yōu)化方案，被稱為SQLite-CC，并闡述其設(shè)計(jì)和實(shí)現(xiàn).它結(jié)合非易失性內(nèi)存，通過CC-manager中分配的全局時(shí)間戳來保證事務(wù)的原子性，合理使用拷貝的雙版本緩沖區(qū)優(yōu)化了數(shù)據(jù)庫的讀寫性能，并保留了與WAL模式相當(dāng)?shù)氖聞?wù)并發(fā)性能.在原始的SQLite中需要強(qiáng)制將所有頁面刷新到磁盤，SQLite- CC則充分利用了非易失性內(nèi)存的持久化的特性，減少了日志文件的寫入/刪除操作等磁盤I/O，并有效解決了磁盤中的寫放大問題.

[參考文獻(xiàn)]

[1]ARULRAJ J，PERRON M，PAVLO A. Write-behind logging [J]. Proceedings of the VLDB Endowment，2016，10（4）：337-348.

[2]COBURN J，BUNKER T，SCHWARZ M，et al. From ARIES to MARS：Transaction support for next-generation，solid-state drives [C]// Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 2013：197-212.

[3]LEE H G，BAEK S，NICOPOULOS C，et al. An energy-and performance-aware DRAM cache architecture for hybrid DRAM/PCM main memory systems [C]// Proceedings of the 2011 IEEE 29th International Conference on Computer Design （ICCD）. IEEE，2011：381-387.

[4]ARULRAJ J，LEVANDOSKI J，MINHAS U F，et al. BzTree：A high-performance latch-free range index for non-volatile memory [J]. Proceedings of the VLDB Endowment，2018，11（5）：553-565.

[5]TUAN D Q，CHEON S，WON Y. On the IO characteristics of the SQLite transactions [C]// Proceedings of the International Conference on Mobile Software Engineering and Systems. 2016：214-224.

[6]HUANG Y，LIU T，XUE C J. Register allocation for write activity minimization on non-volatile main memory for embedded systems [J]. Journal of Systems Architecture，2012，58（1）：13-23.

[7]QURESHI M K，SRINIVASAN V，RIVERS J A. Scalable high performance main memory system using phase-change memory technology [C]// Proceedings of the 36th Annual International Symposium on Computer Architecture. 2009：24-33.

[8]WANG K L，ALZATE J G，AMIRI P K. Low-power non-volatile spintronic memory：STT-RAM and beyond [J]. Journal of Physics D：Applied Physics，2013，46（7）：074003.

[9]MUSTAFA N U，ARMEJACH A，OZTURK O，et al. Implications of non-volatile memory as primary storage for database management systems [C]// 2016 International Conference on Embedded Computer Systems：Architectures，Modeling and Simulation （SAMOS）. IEEE，2016：164-171.

[10]KANG W H，LEE S W，MOON B，et al. X-FTL：Transactional FTL for SQLite databases [C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013：97-108.

[11]COOPER B F，SILBERSTEIN A，TAM E，et al. Benchmarking cloud serving systems with YCSB [C]// Proceedings of the 1st ACM Symposium on Cloud Computing. 2010：143-154.

[12]YANG J，KIM J，HOSEINZADEH M，et al. An empirical guide to the behavior and use of scalable persistent memory [C]// Proceedings of the 18th USENIX Conference on File and Storage Technologies. 2020：169-182.

[13]OH G，KIM S，LEE S W，et al. SQLite optimization with phase change memory for mobile applications [J]. Proceedings of the VLDB Endowment，2015，8（12）：1454-1465.

[14]PARK J H，OH G，LEE S W. SQL statement logging for making SQLite truly lite [J]. Proceedings of the VLDB Endowment，2017，11（4）：513-525.

[15]CHEN S，GIBBONS P B，NATH S. Rethinking database algorithms for phase change memory [C]// Proceedings of the 5th Biennial Conference on Innovative Data Systems Research. 2011：21-31.

[16]VAN RENEN A，LEIS V，KEMPER A，et al. Managing non-volatile memory in database systems [C]// Proceedings of the 2018 International Conference on Management of Data. 2018：1541-1555.

[17]OUKID I，BOOSS D，LEHNER W，et al. SOFORT：A hybrid SCM-DRAM storage engine for fast data recovery [C]// Proceedings of the Tenth International Workshop on Data Management on New Hardware. 2014：Article No.8.

[18]ARULRAJ J，PAVLO A，MALLADI K T. Multi-tier buffer management and storage system design for non-volatile memory [EB/OL]. （2019-01-30）[2020-05-04]. https：//arxiv.org/abs/1901.10938.

（責(zé)任編輯：陳麗貞）