袁文亮 鐘寶榮 何先平

（1.池州學院 數(shù)學與計算機科學系，安徽 池州 247000；2.長江大學 計算機科學學院，湖北 荊州 434023；3.長江大學 信息與數(shù)學學院，湖北 荊州 434023）

基于邏輯日志的內存數(shù)據(jù)庫恢復子系統(tǒng)設計

袁文亮1鐘寶榮2何先平3

（1.池州學院 數(shù)學與計算機科學系，安徽 池州 247000；2.長江大學 計算機科學學院，湖北 荊州 434023；3.長江大學 信息與數(shù)學學院，湖北 荊州 434023）

根據(jù)嵌入式系統(tǒng)環(huán)境的特點及其恢復需要，提出一種基于邏輯日志的嵌入式內存數(shù)據(jù)庫恢復子系統(tǒng)設計模式，該子系統(tǒng)采用一主兩副的節(jié)點模式，保證了數(shù)據(jù)對象恢復時狀態(tài)與邏輯日志寫時狀態(tài)的一致性.經過驗證試驗表明該子系統(tǒng)有效地減少了日志信息量，縮短了系統(tǒng)的恢復時間，提高了系統(tǒng)的性能.

內存數(shù)據(jù)庫；邏輯日志；檢驗點；恢復

0 引言

現(xiàn)代數(shù)據(jù)庫應用有著與傳統(tǒng)的商務或事務型應用不同的要求：事務有定時限制，數(shù)據(jù)有“時間一致性”，有“有效期”.實事事務及其數(shù)據(jù)都具有定時限制，事務的正確性不僅依賴其邏輯結果，還依賴結果產生的時間，因此要求系統(tǒng)能較高準確地預報事務的運行時間［1］.實事數(shù)據(jù)庫系統(tǒng)（RTDBS）就是其數(shù)據(jù)和事務均可以有顯式的定時限制的數(shù)據(jù)庫系統(tǒng)，系統(tǒng)的正確性不僅依賴事務產生的邏輯結果，還要依賴于邏輯結果產生的時間.這就要求RTDBS能夠較準確地估計事務在系統(tǒng)中的運行時間，但以磁盤數(shù)據(jù)庫系統(tǒng)而言，存在著愈多不可預報的因素，其中重要的原因之一就是磁盤數(shù)據(jù)的I／O操作［2－4］.而對于內存數(shù)據(jù)庫而言，由于整個數(shù)據(jù)庫或“工作”部分已經訪入內存，一個事務在執(zhí)行過程中沒有I／O，則為系統(tǒng)較準確的估算和安排事務的運行時間，使之具有較好的動態(tài)可預報性提供有力的支持，同時也為實現(xiàn)事務的定時限制打下了基礎［5］.

由于MMDB較之通常的磁盤數(shù)據(jù)更為脆弱，更易受到多種系統(tǒng)故障的傷害，因為除了介質故障，事務與系統(tǒng)故障也都可以直接傷害數(shù)據(jù)庫，所以對于基于RTMMDB的系統(tǒng)來說，故障發(fā)生后，能準確及時地恢復數(shù)據(jù)庫至關重要［6－7］.

本文詳細闡述采用基于邏輯日志（logical logging）的恢復子系統(tǒng)，給出了基于邏輯日志的檢驗點策略及故障恢復策略.

1 基于邏輯日志恢復子系統(tǒng)LDMRS

恢復子系統(tǒng)由一個主節(jié)點和兩個副節(jié)點組成，主節(jié)點向用戶提供服務，而兩個副節(jié)點不向用戶提供服務，它們只為主節(jié)點提供數(shù)據(jù)刷出和故障恢復服務.正常情況下，主節(jié)點響應用戶的請求，執(zhí)行事務，副節(jié)點維護事務日志和執(zhí)行外存數(shù)據(jù)庫的更新.當故障發(fā)生，利用某一個副節(jié)點來恢復主節(jié)點，如圖1所示.

該子系統(tǒng)中，事務管理模塊為每一個事務單獨分配一個私有日志緩沖區(qū)和私有數(shù)據(jù)緩沖區(qū)，并采用延遲的數(shù)據(jù)庫修改策略.對每一個事務的操作（包括讀操作、寫操作、事務提交、事務夭折），先是把事務所更新的數(shù)據(jù)放在其私有數(shù)據(jù)緩沖區(qū)內，日志管理器負責為該事務在私有日志緩沖區(qū)創(chuàng)建一條對應的邏輯日志記錄.當一個事務的提交日志被寫入其私有日志緩沖區(qū)后，私有日志緩沖區(qū)的內容才同時刷到兩個副節(jié)點的日志緩沖區(qū)，副節(jié)點負責將其日志緩沖區(qū)內容刷到外存.該事務的日志寫完后，其私有數(shù)據(jù)緩沖區(qū)的更新才能被寫入到MMDB.

圖1 恢復子系統(tǒng)結構

2 主要數(shù)據(jù)結構

為了恢復的需要，系統(tǒng)在內存中創(chuàng)建并維護兩個表和一個鏈表：事務信息表（TIL）、MMDB頁表和數(shù)據(jù)信息鏈表（DIL）.TIL表由事務管理器創(chuàng)建并維護，為進入系統(tǒng)的每一個事務創(chuàng)建并維護一條記錄，每一條記錄包含兩個域：TID和State表示事務標識；State表示該事務所處狀態(tài).MMDB頁表為MMDB中每一個數(shù)據(jù)頁維護一項，每一項包括四個域：PID，BID，Ubit和Tbit.其中PID為MMDB中數(shù)據(jù)頁的標識.BID表示數(shù)據(jù)頁PID在兩個副節(jié)點的外存數(shù)據(jù)庫中所對應的數(shù)據(jù)塊的邏輯塊號.Ubit為更新位，用來表示MMDB數(shù)據(jù)頁PID的更新是否已經傳輸?shù)搅烁惫?jié)點，Ubit為1表示數(shù)據(jù)沒有被傳輸，Ubit為0表示數(shù)據(jù)被傳輸，PID和某個節(jié)點的BID處在一致性狀態(tài).Tbit為標識位，標識MMDB數(shù)據(jù)頁PID是否在檢驗點執(zhí)行期間被更新，Tbit為1，表示該數(shù)據(jù)頁被更新，Tbit為0，表示數(shù)據(jù)頁沒有被更新.MMDB頁表由恢復管理器負責維護.DIL鏈表的結點有三個域：PID，BID和Data，其中PID為MMDB中數(shù)據(jù)頁，它對應在副節(jié)點的外存數(shù)據(jù)庫中所對應的數(shù)據(jù)塊的邏輯塊號是BID，該數(shù)據(jù)頁的內容為Data.

3 日志和檢查點模式

子系統(tǒng)中有三類日志，其中TID為事務調度任務在創(chuàng)建該事務時賦予的編號.Length表示該日志記錄的長度.T＿type取值1，2，3，分別表示事務的開始、夭折和提交.body是邏輯日志體，C＿type取1，2，分別表示檢驗點開始、結束.TIL（事務信息表）用來記錄檢驗點開始時系統(tǒng)中事務的相關信息.

根據(jù)故障后恢復的需要，在檢驗點開始后，可以將事務分成如下3個集合（忽略處于夭折狀態(tài)的事務）：T1是檢驗點開始前已經提交的事務集；T2是當前是活躍的或當前時刻之后建立的事務集，它的提交時間發(fā)生在檢驗點結束之前；T3是當前是活躍的或當前時刻之后建立的事務集，它的提交時間發(fā)生在檢驗點結束之后.很明顯，這次檢驗點的T1是上次檢驗點的T2，T3的并集.

系統(tǒng)采用動態(tài)檢驗點模式，檢驗點進程和事務并發(fā)執(zhí)行.根據(jù)預先設置的閾值，當MMDB頁表中臟頁所占比率大于時，檢驗點進程被觸發(fā).可以通過調整值來達到調整檢驗點的執(zhí)行頻率.

檢驗點進程的執(zhí)行過程描述如下：根據(jù)節(jié)點選擇變量的值，判斷本次檢驗點執(zhí)行時，臟數(shù)據(jù)應該刷入哪個副節(jié)點（為了描述方便，假設這次選擇的節(jié)點為Pa）；讀取事務信息表的內容，寫入Begin＿Checkpoint日志到Pa日志文件；根據(jù)MMDB頁表依次將臟數(shù)據(jù)傳輸?shù)絇a節(jié)點的DIL鏈表中，同時修改相應的Ubit位（將Ubit位置0）.在具體刷新每一臟頁到SDB時，采用互斥量以確保在刷新過程中不會被并發(fā)事務所修改.T2類事務提交時，將其邏輯日志刷到副節(jié)點，私有數(shù)據(jù)區(qū)的數(shù)據(jù)刷入MMDB，更新的數(shù)據(jù)頁的Tbit置1，Ubit置0，該數(shù)據(jù)在此次檢驗點期間不被傳輸.檢驗點結束.T2類事務變成下一次檢驗點的T1類事務，將Tbit置0，Ubit置1；寫End＿checkpoint日志記錄到Pa日志文件；Pa節(jié)點根據(jù)DIL.BID把DIL.Data刷到外存；根據(jù)Pa節(jié)點數(shù)據(jù)庫更新Pb節(jié)點數(shù)據(jù)庫.

4 恢復

故障發(fā)生以后，迅速而有效地恢復對內存數(shù)據(jù)庫而言至關重要.對事務故障（事務夭折），由于采用了延遲寫技術，事務對數(shù)據(jù)庫的更新在事務提交后才能真正寫入數(shù)據(jù)庫.因而，對這類故障只需釋放事務的私有數(shù)據(jù)緩沖區(qū)和對應的活動日志區(qū)即可，無需對數(shù)據(jù)庫執(zhí)行部分Undo操作.如果是已提交事務在修改內存數(shù)據(jù)庫時出現(xiàn)故障，可以重新從事務的私有數(shù)據(jù)緩沖區(qū)刷出數(shù)據(jù).

對于系統(tǒng)故障，它導致系統(tǒng)非正常終止，MMDB遭到破壞，造成了數(shù)據(jù)的丟失，從而導致一些新近提交的事務（它們對數(shù)據(jù)的更新已經寫入了MMDB，但是尚未或尚未完全刷新外存數(shù)據(jù)庫）的效果丟失.系統(tǒng)重啟后，這部分事務必須被Redo，以確保事務的持久性.系統(tǒng)故障的恢復中，有如下三種情況（假設臟數(shù)據(jù)先刷入Pa節(jié)點）：

1）如果故障發(fā)生時，Pb節(jié)點也已經更新完畢，T2類事務中全部事務的日志已經刷到了兩個節(jié)點，T3類事務中已提交事務的日志也刷入到了兩個節(jié)點.此時，T1類事務的數(shù)據(jù)庫更新已經刷到兩個副節(jié)點，故此類事務無需Redo.但是T2類事務和T3類事務中已提交事務數(shù)據(jù)庫更新尚未開始刷出，此類事務必須Redo.恢復時任取某一個副節(jié)點，從日志文件尾反向掃描，直到遇到End＿checkpoint日志，該位置就是本類故障的Redo起始點.

2）如果故障發(fā)生時，Pb節(jié)點尚未更新完畢.此時，T1類事務的數(shù)據(jù)庫更新已經刷到Pa節(jié)點，T2類事務中全部事務的日志已經刷到了兩個節(jié)點，T3類事務中已提交事務的日志也刷入到了兩個節(jié)點，所以其恢復策略是利用Pa節(jié)點恢復MMDB，然后利用1）中的Redo起始點，重做檢驗點結束到故障發(fā)生期間提交的事務.在恢復主節(jié)點同時，恢復Pb節(jié)點.

3）如果故障發(fā)生時，當最后一次檢驗點尚未結束.此時T1類事務的數(shù)據(jù)庫更新尚未完全刷到Pa節(jié)點.T2類事務部分提交，已提交的事務需要Redo，T3類事務尚未提交，無需Redo.取Pb節(jié)點，從日志文件尾反向掃描，直到遇到End＿checkpoint日志（它是前一次檢驗點的結束，掃描過程經過本次檢驗點的Begin＿Checkpoint日志），該位置就是本類故障的Redo起始點.其恢復策略是利用Pb節(jié)點恢復MMDB，從Redo起始點重做T1類事務和已提交的T2類事務.在恢復主節(jié)點同時，恢復Pa節(jié)點.

5 性能分析

物理日志要求日志記錄中記錄數(shù)據(jù)庫元素的新值、舊值或二者都記錄.邏輯日志包括了比物理日志更高層的數(shù)據(jù)庫描述以及數(shù)據(jù)庫的狀態(tài)轉移情況，它指出邏輯值的改變，不涉及物理值.邏輯日志大小一般只有物理日志大小的1／2～1／4［4］.

6 結束語

本系統(tǒng)很好地解決了因日志信息量大，內存數(shù)據(jù)庫備份恢復時間過長的問題.通過建立兩個副節(jié)點，在滿足邏輯事務重做條件的同時，還使主節(jié)點在事務提交時避免I／O操作，提高了系統(tǒng)的性能.在數(shù)據(jù)操作比較頻繁的嵌入式內存數(shù)據(jù)庫系統(tǒng)中，具有很好的應用價值.下一步研究工作為解決T2類事務的數(shù)據(jù)庫修改刷出延遲的問題，它延長了系統(tǒng)的恢復時間，但可以接受，因為在基于物理日志的恢復系統(tǒng)中，它也是需要Redo的.

圖2 不同系統(tǒng)的日志操作開銷

［1］Eliezer L，Avi S.Incremental recovery in main memory database systems［J］.IEEE Transactions on Knowledge and Data Engineering，1992，4（6）：529-540

［2］肖迎元，劉云生，劉小峰，等.嵌入式實時內存數(shù)據(jù)庫故障恢復技術［J］.計算機科學，2005，32（8）：77-79

［3］許貴平，蔡博克.支持實時內存數(shù)據(jù)庫不間斷服務的恢復技術［J］.計算機工程，2008，34（6）：70-71

［4］宋廣華，楊長生.基于混合日志的內存數(shù)據(jù)庫恢復子系統(tǒng)［J］.浙江大學學報，2001，38（2）：164-168

［5］吳紹春，胡必鑫，梁少華，等.內存數(shù)據(jù)庫恢復及其實現(xiàn)機制［J］.江漢石油學院學報，1998（2）：101-105

［6］邱元杰，劉心松，楊 峰.一種高效的分布式并行數(shù)據(jù)庫日志機制［J］.計算機研究與發(fā)展，2004，41（11）：1 942-1 948

［7］Ciaccio G，Ehlert M，Schnor B.Exploiting gigabit ethernet ca-pacity for cluster applications［A］.In：Proc of the 27th Annual IEEEConf on Local Computer Networks（LCN 2002）［G］.Tampa，F(xiàn)lorida：IEEE Computer Society Press，2002：669-678

A Main-Memory Database Recovery Subsystem Based on Logical Logging

Yuan Wenliang1Zhong Baorong2He Xianping3
（1.Department of Mathematics and Computer Chizhou College，Chizhou 247000；2.School of Computer Science Yangtze University College，Jingzhou 434023；3.School of Information and Mathematics，Yangtzg University，Jingzhou 434023，China）

We introduce a embedded main-memory database recovery subsystem based on logical logging.The system uses a mode of one main and two minor nodes，which ensure the consistency of state when data objects are recovering and logical logging is writing.This system reduces the amount of logging information effectively，shortens recovery time of system and improves the performance of the system.

MMDB；logical logging；checkpointing；recovery

王映苗】

1672-2027（2011）03-0064-04

TP392

A

2011-03-28

國家自然科學基金項目（60873021／F0201）；安徽省池州學院院級科研重點項目（XK0902）.

袁文亮（1979-），男，湖南婁底人，碩士，池州學院數(shù)學與計算機系講師，主要從事現(xiàn)代數(shù)據(jù)庫理論研究.

book=67,ebook=133