梁智興 羅軍

重慶大學計算機學院 重慶 400044

0 引言

內(nèi)存數(shù)據(jù)庫(main memory database,MMDB)區(qū)別于傳統(tǒng)磁盤數(shù)據(jù)庫(disk resident database,DRDB)，一般數(shù)據(jù)庫的數(shù)據(jù)存取是針對磁盤設計的，事務操作涉及磁盤I/O，速度較慢。而內(nèi)存數(shù)據(jù)庫其數(shù)據(jù)存取針對內(nèi)存設計，其“主拷貝”常駐內(nèi)存，活動事務只與內(nèi)存打交道，數(shù)據(jù)庫則不再作為大量存儲文件看待而作為內(nèi)存中可尋址的大量數(shù)據(jù)，這使得存取速度快速、存取時間易于預測，提高了數(shù)據(jù)庫性能，使內(nèi)存數(shù)據(jù)庫在實時系統(tǒng)等環(huán)境要求下表現(xiàn)良好。但由于內(nèi)存的易失性，MMDB必須在磁盤或者其它非易失性存儲器中保存它的備份，以防系統(tǒng)崩潰等故障導致內(nèi)存中數(shù)據(jù)丟失。而數(shù)據(jù)庫的備份、日志存儲及異常情況下的系統(tǒng)恢復需要執(zhí)行大量費時的磁盤I/O操作，這必將成為系統(tǒng)的瓶頸，影響系統(tǒng)正常的事務處理能力。

本文借鑒 Song's No-Log Recovery Mechanism采用了兩步恢復機制。即，第一步，當事務提交時，數(shù)據(jù)處理器把影子內(nèi)存(Shadow Memory)中的臟頁備份到備份緩沖區(qū)中；第二步，恢復處理器把備份緩沖區(qū)中的臟頁備份到歸檔磁盤的備份數(shù)據(jù)庫中，結合影子內(nèi)存技術，在增加穩(wěn)定內(nèi)存(stable memory)的情況下，設計一種用備份取代日志和檢查點的恢復方法。此種方法，無需記錄日志，同時，既可以減少恢復時間，又可確保響應時間的快速性和可預測性，更進一步的，它在兩個分開的區(qū)域分別執(zhí)行事務處理和備份，最小化避免了彼此之間的沖突。

1 MMDB數(shù)據(jù)恢復方法概述

當系統(tǒng)出現(xiàn)各種故障時，確保數(shù)據(jù)庫快速恢復到一致性狀態(tài)是M M D B恢復方法的目標。目前，對于M M D B的數(shù)據(jù)恢復方法已經(jīng)有了不少研究，比較典型的有預提交、成組提交、檢查點、影子頁面等技術。其中預提交技術可以增加事務并發(fā)度，但不會減少I/O次數(shù)；分組提交技術可以減少系統(tǒng)的磁盤I/O瓶頸，但會增加事務提交處理的平均時間；檢查點方面，較之非模糊檢查點、模糊檢查點、日志驅動檢查點三類，目前有研究表明模糊檢查點的性能在與事務并發(fā)方面表現(xiàn)最好，因為模糊檢查點進程不加任何鎖，不阻塞事務的正常執(zhí)行，但是模糊檢查點更新的數(shù)據(jù)庫映像無法保證事務一致性，系統(tǒng)故障后通過較復雜的恢復算法把數(shù)據(jù)庫恢復到較近的事務一致性狀態(tài)，而且在檢查點過程中讀寫無法并發(fā)。非模糊檢查點分為動作一致性和事務一致性檢查點，它們都在檢查點時刻對臟頁加鎖，影響到事務的正常運行，但是它們備份出來的數(shù)據(jù)庫由于滿足事務一致性恢復算法相對簡單。影子頁面技術是所有要更新的頁都復制副本影子頁，更新發(fā)生在這些影子頁上，如果事務成功提交，影子頁成為當前頁，否則影子頁丟棄，它可以節(jié)省記錄事務UNDO日志，但占用內(nèi)存空間比較大。

2 基于兩步備份機制的MMDB恢復方法

在這節(jié)里，首先描述兩步備份恢復機制的系統(tǒng)配置，然后詳細介紹當系統(tǒng)出現(xiàn)事故后，事務處理、系統(tǒng)備份以及系統(tǒng)恢復的詳細流程。

2.1 兩步備份恢復機制的系統(tǒng)配置

圖1顯示，恢復機制配置主要包括數(shù)據(jù)庫處理器(DP)，恢復處理器(RP)，內(nèi)存數(shù)據(jù)庫(MMDB)，影子內(nèi)存(SMEM)，備份緩沖區(qū)(Backup Buffer)以及備份數(shù)據(jù)庫(Backup DB)。其中MMDB和SMEM是置于易失性內(nèi)存當中，備份緩沖區(qū)則置于非易失性固定內(nèi)存之中，而永久磁盤剛存放備份數(shù)據(jù)庫。MMDB儲存基本的數(shù)據(jù)庫及在影子內(nèi)存中確實被執(zhí)行的所有數(shù)據(jù)更新。當事務引發(fā)M M D B中的一個更新操作時，它并不直接改變M M D B中的數(shù)據(jù)，而是在相應的影子內(nèi)存的影子頁中修改數(shù)據(jù)，當事務提交時，臟頁回寫MMDB。兩步備份恢復方法與其它恢復方法不同在于，當事務提交后，DP首先將影子內(nèi)存的臟頁備份到備份緩沖區(qū)中，最后把備份緩沖區(qū)中的臟頁備份到磁盤備份數(shù)據(jù)庫中。為了更好說明恢復和事務處理，在此作以下說明。

（1）Transaction Page List(TPList，事務頁表)，指影子內(nèi)存中，針對當前事務的一張連續(xù)的頁信息表，當事務提交時，這些頁被拷貝到備份緩沖區(qū)中，同時，追加到BackupList表中。

（2）Usable Page List(UsabIeList，可用頁表)，指影子內(nèi)存所有頁中，當前已執(zhí)行事務所涉及到的一張連續(xù)的可重復使用的頁表。已提交事務及當前事務所使用過的頁均屬于這個表。

（3）Shadow Memory Area Free Page List(SFreeList，影子內(nèi)存區(qū)空閑頁表)，指影子內(nèi)存區(qū)空閑頁表。

（4）Backup Page List(BackupList，備份頁表)，指備份緩沖區(qū)中一張連續(xù)的頁表，這些頁將由RP負責將它備份到備份數(shù)據(jù)庫。

（5）Backup Buffer Free Page List(BFreeList，備份緩沖區(qū)空閑頁表)，指備份緩沖區(qū)中連續(xù)的空閑頁清單。

由于在存取數(shù)據(jù)方面，內(nèi)存比磁盤快得多，因此，鎖的爭奪就不像在傳統(tǒng)磁盤上那樣激烈，基于這個原因，可以通過選擇整個數(shù)據(jù)庫作為鎖的粒度，從而避免并發(fā)控制消耗。許多研究也證明，這樣確實有利于提高M M D B性能。

2.2 事務處理

事務處理流程如下：

（1）開始事務

（2）對于事務的每一個操作opi

①假設opi是讀操作

a．如果讀操作opi所涉及的頁pagek在TPLIST中，則直接讀；

b．如果讀操作opi所涉及的頁pagek不在TPLIST中，則讀M M D B中的頁。

② 假設opi是寫操作

a．如果寫操作opi所涉及的頁pagek不在UsableList中 ；

I．從SFreeList中分配一個空閑頁；

II．將MMDB中的頁pagek拷貝到上步分配的空閑頁中 ；

III．追加pagek的影子頁到UsableList；

b．追加pagek的影子頁到TPList；

c．更新pagek影子頁。

（3）事務處理過程

①事務終止

a．比較UsableList和TPList，在UsableList 中刪除TPList中的頁；

b．釋放TPList 里頁并把他們追加到SFreeList；

c．置TPList為空。

② 事務提交

a．拷貝TPList里的所有頁到Backup Buffer；

b．在BackupList中，追加上一步已拷貝的頁；I．對于TPList中每頁pagei，如果它不在BackupList中或者正處于備份過程中，則把它追加到 BackupList；

II．否則，刪除pagei前一個拷貝頁，并且使指針指向當前頁pagei；

c．對TPList中每頁，回寫pagei至MMDB；

d．置TPList為空。

（4）結束事務

以上就是事務處理的步驟。下面進一步給出詳細解釋。

如果當前事務需要更新MMDB中的頁時，它首先搜索UsableList，確認此頁是否在SMEM中。如果此頁在UsableList中，則直接更新頁，否則，在SMEM中分配一個頁空間，并把MMDB中所對應的頁內(nèi)容拷貝到剛分配的頁空間來。當進行讀操作時，如果所涉及到的頁在TPList中，影子內(nèi)存中的頁應該可以讀(這是因為同一事務所對應的寫操作映射在影子內(nèi)存中而不是MMDB中)，否則MMDB中的頁可以讀。

當事務提交時，所有已經(jīng)更新的頁被拷貝到Backup Buffer及被追加到BackupList，最后回寫MMDB。如果某頁因為同一個邏輯頁號仍然保留在備份緩沖區(qū)中而沒被拷貝到Backup DB，則不得不把它從Backup Buffer 和 BackupList刪除，然后，當前頁被拷貝至 Backup Buffer 和 BackupList中。如果相同的邏輯頁備份正處于進程中，則當前頁不進行刪除操作，直接被拷貝到Backup Buffer 和 BackupList中。當TPList中的所有頁被拷貝到Backup Buffer 和 attached to BackupList中，則事務提交程序結束。

圖1 兩步備份恢復機制配置

一般的基于影子頁面的恢復技術，在事務提交后，將影子內(nèi)存區(qū)的影子頁全部刪除。但在這里，兩步備份機制卻讓他們留在影子內(nèi)存區(qū)中，這是因為它們后面的事務可以繼續(xù)使用它們。

當前事務的終止步驟就非常簡單，丟棄臟頁即可(因為更新操作發(fā)生在影子內(nèi)存中)。

2.3 備份步驟

一般的MMDB恢復技術都采用檢查點技術，就是周期地將MMDB中數(shù)據(jù)備份到磁盤。本文所提的兩步備份機制不采用檢查點技術，而是直接把Backup Buffer的頁備份到Backup DB。這種備份由于沒有MMDB的參與，也就不會影響事務的處理。但可能由于Backup Buffer沒有空閑空間，事務提交會延遲，但這種情況在其它系統(tǒng)中由于其它種種原因也是不可避免的。

RP備份BackupList中的頁，備份步驟如下：

① RP從BackupList中把他們刪除；

② RP把他們追加到BFreeList。

2.4 恢復步驟

當系統(tǒng)出現(xiàn)故障時，由于沒必要寫任何日志，快速恢復成為可能。stable memory維護的頁因為沒有undo 和 redo操作，也就沒有必要進行備份。系統(tǒng)重啟后的第一項工作(重載Backup Buffer中的頁至MMDB)只要花很短的時間就可在main memory 和stable memory中完成 ，盡管在恢復過程中，系統(tǒng)可能再次出現(xiàn)故障，但數(shù)據(jù)庫系統(tǒng)仍然保持數(shù)據(jù)一致性，這是因為BackupList 中的頁還在stable memory 中。

恢復步驟如下：

（1）系統(tǒng)重啟；

（2）加載BackupList 中的所有頁至MMDB；

（3）載入任務完成，開始新的事務。

如果新事務需要頁時，在MMDB中對它進行搜索。

①如果搜索失敗，從backup DB 中重載此頁到MMDB。

②否則，正常處理事務。

2.5 最壞情況性能分析

由于本文所提出的機制是在Song's No-Log Recovery Mechanism 的改進，自然也就選用Song's模型來做比較，分析兩步備份機制最壞情況下的性能。這里主要評價和比較最壞情況下的事務響應時間指標。

圖2 說明了分析模型所關聯(lián)的五個參數(shù)及它們所代表的意思。本文假設main memory (RAM)足夠容納整個數(shù)據(jù)庫和相應的影子頁面，stable memory 大小也足夠容納需要的信息，并且不會出現(xiàn)故障，事務連續(xù)被處理，stable memory 的存取時間比RAM慢2倍(相關研究表明stable memory 的存取時間比RAM慢2至4倍)。

最壞情況下，一個事務包含N個更新操作，每個更新操作存取不同的頁，將被更新的頁不在SMEM中，這樣的話，N個頁就應該從MMDB拷貝到SMEM。在Song's 的模型中，響應時間計算如下(RT 表示響應時間) ：

在兩步備份機制中，事務響應時間可以按如下計算：

按上面假設，stable memory存取時間比RAM慢兩倍，則可以用2* CMRead代替CSRead，2* CMWrite代替CSWrite，則兩種機制的響應時間為

從上面得出的結果可知，在考慮stable memory存取時間比RAM慢兩倍的情況下，兩種算法的響應時間基本相同。

如果stable memory存取時間比RAM慢4倍，則用4* CMRead代替CSRead，4*CMWrite代替CSWrite，則兩種機制的響應時間為

基于上面的比較，由此可見，兩步備份機制的響應時間相對來說更快。

以上是通過理論推理得出來的結論，其實，我們也可換種角度來分析。在Song's 的模型中，它利用Stable Memory作為影子內(nèi)存，而本文采用的兩步備份機制是在main memory中劃出一塊適當大小區(qū)域作為影子內(nèi)存，當事務處理涉及到的頁越多時，MMDB和影子內(nèi)存打交道的次數(shù)越多，由于main memory存取速度比Stable memory快，兩步備份機制的響應時間也就比Song's 的提出的模型響應時間快。

圖2 Parameters for the analytical model

綜上所述，在最壞情況下，兩步備份機制比Song's No-Log Recovery Mechanism具有更快的響應時間。

3 結束語

本文所提的兩步恢復機制模型相比一般的恢復機制具有更快的響應時間，原因有三：一是由于使用部分主存作為影子內(nèi)存，數(shù)據(jù)存取時間比使用 stable memory 更快，這樣也就降低了頁從M M D B到S M E M的復制損耗。第二，本文考慮到事務進程都是在主存中執(zhí)行的，通過直接將備份緩沖區(qū)的臟頁刷到備份磁盤中，消除了檢查點對事務進程的干擾。最后，由于沒有undo/redo日志，也就消除了記錄日志時產(chǎn)生的磁盤I/O。在接下來的工作中，可以考慮研究沒有stable memory硬件支持，具有更快的響應時間的恢復方法。

[1] E. M. Song, Y. K. Kim, C. H. Ryu, et. al., "No-Log Recovery Mechanism Using Stable Memory For Real-Time Main Memory Database Systems", RTCSA '99, IEEE CS.December 1999.

[2] G.Copeland, T.Keller, R.Krishnamurthy,and M.Smith, "The case for safe RAM", In proceedings 15th Int. Conference on Very Large Databases.1989.

[3] HUANG Lin, LU Jing, LIN Zhong, "Recovery method for main memory database systems based on shadow paging ",Computer Engineering and Design Vol.29, NO.10.May 2008.

[4] Eliezer Levy and Abraham Silberschatz, "incremental Recovery in Main Memory Database Systems," In IEEE Transactions on Knowledge and Data Engineering.Vol. 4, No. 6. Dec. 1992.