空間實時內存數據庫恢復機制研究與實現

杜 曄，郭麗麗

(1.中國科學院光電研究院，北京100094;2.中國科學院空間應用工程與技術中心，北京100094;3.中國科學院研究生院，北京100094)

0 引言

空間應用對數據管理的實時性和可靠性有著較高的要求。傳統數據庫旨在處理持久穩定的數據，無法滿足實時應用的需要，而內存數據庫 (Main Memory Database，MMDB)由于其工作版本常駐內存，所有數據的存取和管理在內存中完成，訪問速度比傳統數據庫高1-2個數量級，對于實時性要求較高的空間數據管理系統是一個較好的選擇。然而由于內存具有易失性，內存數據庫必須在磁盤或其他非易失性存儲器存儲器中保存備份，以防止程序錯誤、系統掉電等系統故障帶來的數據損失。但備份所需要的大量磁盤I/O操作將影響系統效率，因此高效的恢復策略是內存數據庫的關鍵技術之一。目前較廣泛應用的是用基于日志和檢查點的方法來對內存數據庫進行恢復。為了減少日志的數量，常采用本地更新 (in Place Update)的方式來對數據進行操作，記錄日志時僅需要記錄被修改數據的后像(after image)，即Redo日志。同時為了減少系統恢復所需要的日志數量，使用檢查點將MMDB備份到磁盤。

Swallow是為空間應用研發的實時內存數據庫，本文針對Swallow內存數據庫結構，研究并設計了一個基于日志驅動修改、影子頁面技術、模糊檢查點思想的內存數據庫恢復機制，主要包括:設計了基于日志驅動修改的事務執行算法，減少了需記錄日志的數量并提高了事務故障的恢復效率;設計了日志快速提交算法以提高事務并發度;設計了系統的檢查點策略，減少系統恢復需要的日志量以及檢查點運行時對系統效率的影響。在此恢復機制下，實現了Swallow內存數據庫數據和日志的快速備份以及在內存數據庫出現事務故障和系統故障時的快速恢復策略。最后通過實驗證明了該恢復機制的高效性。

1 Swallow恢復模型概述

Swallow的主要模塊有事務管理器，內存池頁面管理器，存儲管理模塊和恢復模塊。內存中的數據以分頁的形式存在，通過內存池頁面管理器進行統一的管理和維護，在此之上提供了數據庫的常用接口 (如表、關鍵字和數據的增刪查改等)，同時頁面管理器維護一個臟頁表，記錄了從上次檢查點之后被更新過的頁面。系統通過多線程來支持多個事務并發，并由事務管理器在系統中維護一個事務信息表，系統每接收一個新的事務線程，都在事務信息表里記錄相關信息。存儲管理模塊負責MMDB和磁盤數據庫文件的數據交換?；謴湍K包括全局日志的寫入，檢查點的執行以及故障后的系統恢復。

圖1是Swallow的恢復模型。事務對MMDB的修改是由日志驅動的，某個事務要對MMDB中的頁面進行更新操作時，并不直接對MMDB進行修改，只是將其Redo日志記錄在其對應的私有日志區里，事務進入提交階段后，將其對應的私有日志放入全局日志緩沖，寫日志線程定期將全局日志緩沖刷新到磁盤的日志文件里，事務提交完成后由頁面管理器根據日志對MMDB進行相應修改。若事務尚未進入提交階段就夭折則直接釋放其對應的私有日志，不對MMDB進行操作，不需記載Undo日志。

圖1 系統恢復模型

根據Redo日志的先寫日志 (write ahead logging，WAL)規則，事務提交時應將該事務的所有日志都寫入日志中，才能進行事務對數據庫的更改，這意味著事務提交必須有I/O過程，對實時性較強的內存數據庫系統將是很大的性能瓶頸，此處的設計參考了預提交協議和成組提交協議，在事務私有日志已放入全局日志緩沖后即對MMDB進行更新，然后釋放鎖，以提高了內存事務的并發度。但在將MMDB的數據刷新到外存時仍需要遵守WAL規則，即在一個檢查點開始前需要將已提交事務的日志刷新到磁盤日志文件。

檢查點操作是為了減少恢復時需要讀取的日志數量，將內存數據庫中的臟頁刷到磁盤數據庫文件進行持久性備份的過程。靜態檢查點要求檢查點過程中系統處于完全停滯狀態，對實時性要求較強的空間實時內存數據庫這是無法接受的。傳統的模糊檢查點不對待刷新的臟頁上鎖，檢查點過程中事務對MMDB的頁面可讀寫，這樣保持的磁盤備份極易違反WAL規則。Swallow的檢查點設計為與事務并發進行，檢查點對頁面加讀鎖，保證事務的一致性;同時為了在檢查點過程中減少對事務的影響，在檢查點執行過程中，若事務需要訪問的頁面被檢查點鎖住，則頁面管理器復制一個當前頁面并記錄為該頁面的影子頁面，此后事務對該頁面的修改都在影子頁面里進行，等到檢查點完成后，將對應的影子頁面替代原頁面即可。當系統中臟頁數量達到一個閾值后，頁面管理器喚醒檢查點線程進行檢查點操作。檢查點完成后，在日志中記錄新的重做起點。由于檢查點是事務一致的，系統故障后，裝入磁盤的數據庫文件并利用讀取的磁盤日志文件從重做起點對MMDB進行Redo操作即可恢復到一個最近的一致性狀態。

這個恢復模型的特點有:僅需要記載Redo日志，事務失敗則直接丟棄日志，無需回滾操作，因此對于事務故障的恢復是實時的，且日志驅動的修改方式保證事務在提交前不直接在MMDB中修改數據，事務讀寫的并發性得到了提高;事務對MMDB的修改采取預提交方式，當私有日志放入全局緩沖即可對MMDB進行修改，減少了傳統提交方式需要等到日志寫到磁盤后才能修改MMDB的I/O需要;利用全局日志緩沖和成組提交方式減少了日志帶來的磁盤I/O;檢查點的設計利用了影子頁面，結合了事務一致性檢查點和模糊檢查點的優點，減小了檢查點過程對事務的正常執行的影響。

2 主要數據結構和算法

2.1 主要數據結構

(1)臟頁表:MMDB中的每個頁面具有一個外頁頭，存儲了該頁的相關信息 (如頁號、是否為臟頁，影子頁面指針等)，內存池頁面管理器通過外頁頭來對頁面進行組織。內存池中維護了一個臟頁表，當頁面被修改后即將該頁的臟頁位置1并加入臟頁表。在檢查點線程將臟頁刷入磁盤后，將臟頁位置0。臟頁表中的所有頁面將在下一次檢查點的時候刷入磁盤數據庫文件。

(2)事務信息表:事務管理器每一個新接收的事務將其加入事務信息表，表中記錄了事務的標識號TransID，事務狀態標識TransState和日志頭指針，其中事務狀態包括1開始，2提交，3夭折，4完成。日志頭指針指向事務的私有日志。

(3)事務私有日志:圖2是事務日志的格式，事務的日志共有3種類型:事務開始 (TransBeginLog)，Redo節點(TransOperationLog)和事務提交 (TransCommit)。TransBe-ginLog中記錄了事務的ID號以及日志的長度 (LogLength);TransCommitLog中記錄了事務完成時的時間戳。事務進行的Redo日志其實是一個數據操作鏈表，每個鏈表元素是一個TransOperationLog結構體，記錄了這個操作的類型及相關數據。事務執行時，為每一個事務建立一個鏈表，記錄下事務需要對數據庫進行的所有修改，當事務提交時，鏈表中的操作會被依次執行，當事務夭折時，刪除鏈表。

圖2 事務日志格式

(4)全局日志緩沖:全局日志是一個臨界區資源，提交的事務線程對其進行同步訪問。事務將私有日志掛載到全局日志鏈時需先獲得其寫鎖，不同事務按照提交的先后順序將私有日志鏈掛載到全局日志鏈上去，這保證了數據庫狀態的一致性。當日志緩沖達到一定數量或者檢查點線程通知將要開始一個檢查點時，寫日志線程將全局日志緩沖寫入磁盤。

2.2 事務執行算法

本系統采取了日志驅動修改的方式來完成內存數據庫頁面的更新操作。對要更新的數據庫頁面，事務在提交前并不直接進行修改，而是將所有的更新操作都記錄在私有日志里。如果事務成功提交，內存頁面管理器根據事務的私有日志對內存中的數據庫頁面進行修改;如果事務失敗，則丟棄事務的私有日志，內存數據庫不會受到任何影響。由于沒有對內存數據庫的頁面直接進行修改，所以不必記錄事務的Undo日志。

系統接收了一個新的事務后，將其加入事務信息表，由TransState標識事務的狀態，事務開始執行階段的算法如下:

輸入:事務ID，事務私有日志指針

輸出:執行成功返回_OK，失敗返回_Error。

步驟1 在事務日志區寫入一條TransBeginLog;

步驟2 獲得事務要修改的頁面的鎖;

步驟3 將事務對頁面的修改操作即TransOperationLog掛到事務的Redo日志鏈上，將LogLength加1;

步驟4 重復2和3，如果事務正常提交，則進入“事務提交”處理;如果事務失敗則進入“事務夭折”處理。

“事務提交”算法描述如下:

輸入:事務私有日志指針，待掛載全局日志緩沖，當前時間

輸出:執行成功返回_OK，失敗返回_Error。

步驟1 在事務私有日志鏈尾部寫入一條TransCommitLog并記錄時間戳，將TransBeginLog的Loglength修改為當前值;

步驟2 獲得全局日志緩沖的鎖，將事務的私有日志鏈掛到全局日志緩沖上;

步驟3 內存頁面管理器根據事務的私有日志鏈將事務的所有修改執行，修改過的頁的臟頁位標識置為1;

步驟4 釋放事務擁有的鎖;

步驟5 將事務狀態標識TransState標記為提交;根據先寫日志規則，等待該事務對應的Redo日志全部刷新到磁盤后，事務才完全成功。

按照Redo日志的規則，修改數據庫數據前應保證相關的日志記錄都保存到了磁盤，因此，在步驟4時事務并沒有完全結束，此時使用了預提交技術，在事務日志刷新到磁盤前就釋放所有的鎖，減小了事務對資源的競爭，提高了事務的并發度。

“事務夭折”算法描述如下:

輸入:事務ID，事務私有日志指針

輸出:執行成功返回_OK，失敗返回_Error。

步驟1 將事務狀態標識TransState標記為夭折;

步驟2 刪除事務在內存中的Redo日志鏈表。

2.3 日志寫入算法

全局緩沖日志寫入磁盤的時機有兩個，一是系統開始一個新的檢查點前，通知寫日志線程將所有的日志寫入磁盤，二是當全局日志緩沖里的日志達到一定數量后成批寫入磁盤。由于每個事務開始的日志中都記載了事務日志的長度，日志寫入磁盤線程在取日志時以事務為單位取出，也就是同一事務的日志一定是在同一批被取出并寫入硬盤。為減少日志寫入磁盤線程和事務線程掛載日志時對全局日志緩沖的競爭，全局日志采取雙緩沖隊列的方式。日志寫入磁盤線程的算法為:

輸入:待寫日志緩沖隊列，待掛載日志緩沖隊列

步驟1 檢查當前待寫日志緩沖隊列是否為空，若不空則從當前日志緩沖隊列中取出一組日志緩沖，若為空則轉1.1;

步驟1.1檢查待掛載日志緩沖隊列是否為空，若不為空則獲得其寫鎖，將其置為待寫日志緩沖隊列，將原來的待寫日志緩沖隊列置為待掛載日志緩沖隊列，若為空則掛起;

步驟2 將取出的日志緩沖寫入外存的日志文件中;

步驟3 釋放取出的日志緩沖

步驟4 根據事務開始日志中TransID的值將事務信息表中對應的事務狀態從提交改為完成;

步驟5 轉步驟1。

2.4 檢查點算法

由于檢查點過程涉及到大量磁盤I/O操作，檢查點的模式和執行頻率對系統性能較大。本系統中，檢查點是非連續的，啟動的頻率由系統中臟頁比例決定，當臟頁鏈中的節點數量與總頁面數量之比達到一個閾值后，頁面管理器喚醒檢查點線程進行檢查點操作。

Swallow的檢查點方法借鑒了事務一致檢查點的思想和影子頁面的技術，在檢查點進行過程中對MMDB加讀鎖，確保事務的一致性，同時利用影子頁面來使檢查點進行過程中事務對MMDB的讀寫不受影響，達到模糊檢查點的效果。由于事務對MMDB的更改使用日志驅動的方法，因此當檢查點線程成功獲得臟頁的讀鎖時，MMDB一定處于事務一致性的狀態。檢查點過程中，若有事務提交的頁面仍被檢查點鎖住，內存頁面管理器就復制一個被鎖住臟頁的影子頁，事務提交的修改在影子頁面上進行，修改完后將臟頁鏈表中該臟頁的影子指針指向影子頁面，此后若還有別的事務對該頁面進行操作，都從影子頁面進行讀取或操作。直到檢查點釋放了該頁的鎖后，用相應的影子頁替代原來的頁面，仍然置臟頁位，這樣在下一次檢查點時會被刷到磁盤。

檢查點算法如下:

輸入:全局日志緩沖，臟頁表，磁盤數據庫映像

步驟1 檢查點線程啟動，獲取全局日志緩沖的鎖，并記錄一條檢查點開始的日志BClog，以區分檢查點啟動前后的日志;

步驟2 釋放全局日志緩沖的鎖;

步驟3 根據WAL規則 (磁盤數據庫被更改前必須先記錄Redo日志)，將BClog之前的事務日志都刷新到磁盤日志中;

步驟4 獲取臟頁表中所有臟頁的讀鎖，依次將臟頁復制到臨時緩沖區，釋放讀鎖，臟頁位置0，然后將臨時緩沖區的數據刷新到磁盤數據庫的對應頁面上;

步驟5 獲取全局日志緩沖的鎖，寫入一條檢查點結束的日志EClog;

步驟6 釋放全局日志緩沖的鎖;

步驟7 在日志文件的頭結構中記錄下本次BCLog在日志文件中的位置，即LastBC;

步驟8 通知頁面管理器將所有的影子頁面替代原頁面(影子頁面的臟頁位已由事務在修改時置為1)。

至此，一個檢查點過程已經完全完成。以下分析證明這個檢查點是事務一致的 (見圖3):

圖3 檢查點與系統故障

(1)在BCi之前已經提交的事務T1，它的日志在檢查點啟動時已強制刷入硬盤，T1對MMDB的修改也已在BCi之前完成，檢查點將其產生的臟頁刷新到了磁盤;

(2)在BCi之前已經啟動但是尚未提交的事務T2，在BC前并未修改MMDB，BCi后它對MMDB的修改反映在MMDB的影子頁中，因此這一次檢查點中不會記錄T2對MMDB的影響;

(3)在BCi之后才啟動的事務T3，與T2同理，它對MMDB的影響不會被檢查點所記錄。

由上可知，在檢查點完成之前提交的事務信息已全部由檢查點刷入磁盤，磁盤備份目前的狀態是BC時MMDB的一個事務一致性映像。因此在BC之前的磁盤日志文件已經沒用了，為節省空間可將其刪除。

2.5 檢查點算法

對于事務故障，由于事務在提交前并未將其對數據庫的修改反應到MMDB中而只是記錄在私有Redo日志里，因而事務故障時只要丟棄事務在內存中的Redo日志鏈即可，并不涉及磁盤I/O或MMDB讀寫，因此恢復過程非常迅速。

對于系統故障，恢復包括重裝和重做兩個階段。即將磁盤中的數據庫映像加載到內存，再根據Redo日志對數據庫做Redo操作。系統故障發生的時間可能在檢查點過程中和非檢查點過程中，如圖3所示。

(1)若系統故障發生時不在檢查點過程中，如圖中故障1，由檢查點算法可知，此時磁盤數據庫備份的狀態是ECi時的狀態，也就是BCi之前提交的事務對MMDB的修改已刷新到磁盤，之后提交的事務尚未反映到磁盤中，因此將BCi作為重做的起始點，從磁盤日志文件中讀取BCi之后的Redo日志對MMDB進行Redo操作。

(2)如果系統故障發生在檢查點過程中，如圖中故障2，此時磁盤數據庫備份已刷入了部分在BCi后提交事務產生的臟頁，但并不完整，因此仍需要從BCi開始重做。

綜上，系統故障后恢復的重做起點是最近一次完整的檢查點的開始位置處，也就是上文我們在磁盤日志文件里記錄的LastBC。因此恢復的算法為:

步驟1 將磁盤的數據庫映像導入內存;

步驟2 從LastBC處開始讀取Redo日志，根據Redo日志鏈對數據庫做Redo操作。

3 性能測試及分析

Swallow的恢復機制通過在事務提交、日志和檢查點上的研究與設計，使得內存數據庫在遇到事務故障和系統故障時能夠快速得到恢復，并且該機制不會對系統的性能造成太大的影響，通過實驗測試，對比了Swallow和開源內存數據庫 FastDB、SQLite的恢復機制及系統性能。其中，FastDB有兩種運行模式，磁盤模式和無盤模式，前者會產生磁盤文件，后者則不產生磁盤文件，僅在內存中操作;類似地，SQLite同樣有內存模式和磁盤模式。Swallow分別測試在恢復機制正常運行以及關閉恢復機制，在內存索引結構中進行操作時的性能情況。

測試環境:PC機，Intel雙核處理器，主頻2.40GHz，內存1G

軟件環境:

(1)自主開發的空間實時內存數據庫系統Swallow、用于對比的內存數據庫FastDB、SQLite。(2)編寫隨機數據生成程序用于產生實驗數據，數據內容為Key-data記錄，單條記錄長度不大于10字節 (3)編寫測試程序分別調用以上數據庫的接口進行實驗

實驗方法:

(1)通過隨機數據生成器生成10000條和100000記錄分別插入數據庫，每次插入作為一個單獨的事務，計算出數據庫的平均事務處理能力TPS;

(2)通過非正常退出程序來模擬系統崩潰，記錄恢復需要的時間。

測試結果如表1所示。

表1 內存數據庫性能測試結果

實驗結果可以看出，在不加入恢復機制的情況下三款數據庫的TPS在一個數量級上，但FastDB和SQLite在使用磁盤數據后性能下降非常巨大，這是頻繁的磁盤I/O帶來的。Swallow在自動進行檢查點和日志記錄的情況下性能也有所下降，但相比其它兩個數據庫高出了一個數量級。在這個機制下，Swallow的系統故障恢復時間與FastDB和SQLite相比相差并不大，數據損失率則由事務級增加到日志成組提交的每組大小。考慮到系統故障的發生概率較小，而犧牲的少量數據保證了系統性能的大幅度改善，這個恢復機制是有著良好的表現的。

4 結束語

本文設計了一個空間實時內存數據庫Swallow的恢復機制，綜合了日志驅動修改、影子頁面、預提交和模糊檢查點的思想，達到了日志、檢查點過程不影響事務并發執行，減輕磁盤I/O對系統效率的影響。日志驅動修改使得系統無須記載Undo日志，事務故障不需要回滾即可直接恢復，系統故障后也能迅速確定恢復起點，在保證數據庫可靠性的同時也降低了對系統實時性的影響。

［1］Hector Garcia-Molina，Jeffey D Ullman，Jennifer Widom.Database systems:The complete book［M］.Upper Saddle River，New Jersey:Prentice Hall，2008.

［2］WANG Shan，XIAO Yanqin，LIU Dawei，et al.Research of main memory database ［J］.Computer Applications，2007，27(10):2353-2357(in Chinese).［王珊，肖艷芹，劉大為，等.內存數據庫關鍵技術研究 ［J］.計算機應用，2007，27(10):2353-2357.］

［3］GAN Shan，GUO Lili.Research on access mechanism of real-time memory database systems for space:MCacheTree［J］.Computer Engineering and Design，2010，31(17):3827-3830(in Chinese).［甘杉，郭麗麗.航天實時內存數據庫存取機制MCacheTree的研究 ［J］.計算機工程與設計，2010，31(17):3827-3830.］

［4］HUANG Lin，LU Jing，LIN Zhong.Recovery method for main memory database systems based on shadow paging［J］.Computer Engineering and Design，2008(5):2470-2473(in Chinese).［黃琳，路京，林中.基于影子頁面的MMDB的數據恢復方法［J］.計算機工程與設計，2008(5):2470-2473.］

［5］FENG Yuao.Fault recovery strategy research on the real-time embedded memory database ARTs-EDB［D］.Wuhan:Huazhong U-niversity of Science and Technology，2008(in Chinese).［馮宇傲.嵌入式實時內存數據庫ARTs_EDB的故障恢復策略研究［D］.武漢:華中科技大學，2008.］

［6］XIAO Y Y，LIU Y S，LIAO G Q，et al.Real-time commitment in one-phase for distributed real-timetransactions［J］.Journal of Huazhong University of Science and Technology(Nature Science Edition)，2006，34(3):1-4.

［7］CHEN Anlong.Research and implement of recovery in main memory database［D］.Ningbo:Zhejiang University，2006(in Chinese).［陳安龍.內存數據庫中數據恢復技術的研究與實現［D］.寧波:浙江大學，2006.］

［8］QIN Xiongpai，XIAO Yanqin，CAO Wei，et al.A parallel recovery scheme for update intensive main memory database［C］//Otago:PDCAT，2008:509-516.

［9］XIAO Yingyuan，LIU Yunsheng，LIAO Guoqiong，et al.A realtime dynamic database crash recovery strategy［J］.Journal of Software，2007(10):2516-2527(in Chinese).［肖迎元，劉云生，廖國瓊，等.一種實時動態數據庫故障恢復策略［J］.軟件學報，2007(10):2516-2527.］

［10］LI Zhengyu，CHEN Lei.Research on the testing method and performance evaluating and testing for database［J］.Electronic Design Engineering，2011(2):4-6(in Chinese).［李征宇，陳磊.數據庫性能評測指標及其測試方法研究［J］.電子設計工程，2011(2):4-6.］