袁文亮 鐘寶榮 何先平

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

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

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

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

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

內(nèi)存數(shù)據(jù)庫；邏輯日志；檢驗(yàn)點(diǎn)；恢復(fù)

0 引言

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

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

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

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

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

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

圖1 恢復(fù)子系統(tǒng)結(jié)構(gòu)

2 主要數(shù)據(jù)結(jié)構(gòu)

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

3 日志和檢查點(diǎn)模式

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

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

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

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

4 恢復(fù)

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

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

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

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

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

5 性能分析

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

6 結(jié)束語

本系統(tǒng)很好地解決了因日志信息量大，內(nèi)存數(shù)據(jù)庫備份恢復(fù)時間過長的問題.通過建立兩個副節(jié)點(diǎn)，在滿足邏輯事務(wù)重做條件的同時，還使主節(jié)點(diǎn)在事務(wù)提交時避免I／O操作，提高了系統(tǒng)的性能.在數(shù)據(jù)操作比較頻繁的嵌入式內(nèi)存數(shù)據(jù)庫系統(tǒng)中，具有很好的應(yīng)用價值.下一步研究工作為解決T2類事務(wù)的數(shù)據(jù)庫修改刷出延遲的問題，它延長了系統(tǒng)的恢復(fù)時間，但可以接受，因?yàn)樵诨谖锢砣罩镜幕謴?fù)系統(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í)時內(nèi)存數(shù)據(jù)庫故障恢復(fù)技術(shù)［J］.計(jì)算機(jī)科學(xué)，2005，32（8）：77-79

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

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

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

［6］邱元杰，劉心松，楊 峰.一種高效的分布式并行數(shù)據(jù)庫日志機(jī)制［J］.計(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

國家自然科學(xué)基金項(xiàng)目（60873021／F0201）；安徽省池州學(xué)院院級科研重點(diǎn)項(xiàng)目（XK0902）.

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

book=67,ebook=133