袁文亮,鐘寶榮,何先平

(1.池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000;

2.長(zhǎng)江大學(xué) a.計(jì)算機(jī)科學(xué)學(xué)院；b.理學(xué)院，湖北 荊州 434023)

基于Cluster的并行內(nèi)存數(shù)據(jù)庫(kù)恢復(fù)子系統(tǒng)模型研究

袁文亮1,鐘寶榮2a,何先平2b

(1.池州學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽 池州 247000;

2.長(zhǎng)江大學(xué) a.計(jì)算機(jī)科學(xué)學(xué)院；b.理學(xué)院，湖北 荊州 434023)

文章提出的恢復(fù)子系統(tǒng)模型是根據(jù)差分日志記錄的特點(diǎn)，將已提交事務(wù)的日志經(jīng)并行日志管理器收集后并行寫入到多個(gè)磁盤，通過“協(xié)調(diào)者”全局檢驗(yàn)點(diǎn)和站點(diǎn)局部檢驗(yàn)點(diǎn)的協(xié)調(diào)操作,具有更高的并發(fā)度和更高的系統(tǒng)吞吐量，并且能快速的支持系統(tǒng)失敗恢復(fù)。經(jīng)過驗(yàn)證試驗(yàn)表明該子系統(tǒng)有效的減少了日志信息量，縮短了系統(tǒng)的恢復(fù)時(shí)間，提高了系統(tǒng)的性能。

并行內(nèi)存數(shù)據(jù)庫(kù)；差分日志；恢復(fù)子系統(tǒng)；檢驗(yàn)點(diǎn)

引言

基于Cluster的并行內(nèi)存數(shù)據(jù)庫(kù)，是將數(shù)據(jù)分片到機(jī)群的站點(diǎn)上，而每個(gè)站點(diǎn)上的整個(gè)數(shù)據(jù)庫(kù)放在內(nèi)存里，一般事務(wù)所涉及的數(shù)據(jù)無需要進(jìn)行I/O操作即可進(jìn)行存取(檢驗(yàn)點(diǎn)事務(wù)需要I/O操作),跨平臺(tái)之間的數(shù)據(jù)存取通過網(wǎng)絡(luò)通信來實(shí)現(xiàn)，這樣提高了事務(wù)執(zhí)行的效率,為高性能應(yīng)用提供了保障。目前，主機(jī)互連網(wǎng)絡(luò)技術(shù)已經(jīng)取得了很大的發(fā)展,其帶寬不斷增加,而存取延遲則不斷下降。在千兆以太網(wǎng)中,每個(gè)主機(jī)能得到128 MB/s的帶寬，其網(wǎng)絡(luò)存取的延遲僅為40μs左右,這個(gè)存取延遲和帶寬比硬盤的I/O操作要快的多。但是，由于內(nèi)存的脆弱性，在發(fā)生故障時(shí)，內(nèi)存數(shù)據(jù)庫(kù)中的數(shù)據(jù)將全部丟失。為此，基于Cluster的并行內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)需要一種高效、可靠的恢復(fù)機(jī)制以使在發(fā)生故障時(shí)能將數(shù)據(jù)庫(kù)恢復(fù)到一致的狀態(tài)。

本文的并行內(nèi)存數(shù)據(jù)庫(kù)恢復(fù)方案是利用差分日志記錄的特點(diǎn)，在并行日志管理器將已提交事務(wù)的日志并行寫入到多個(gè)磁盤，通過全局檢驗(yàn)點(diǎn)控制和各站點(diǎn)局部檢驗(yàn)點(diǎn)的具體操作，具有更高的并發(fā)度和更高的系統(tǒng)吞吐量，能快速的支持系統(tǒng)失敗恢復(fù)。

1 恢復(fù)子系統(tǒng)模型與主要數(shù)據(jù)結(jié)構(gòu)

恢復(fù)子系統(tǒng)設(shè)計(jì)如圖1所示。系統(tǒng)中有日志管理器和并行日志管理器。日志管理器在事務(wù)運(yùn)行時(shí)生成和管理日志,當(dāng)事務(wù)對(duì)數(shù)據(jù)進(jìn)行更新，日志管理器根據(jù)數(shù)據(jù)對(duì)象的舊值和新值，生成差分日志。當(dāng)事務(wù)進(jìn)入提交狀態(tài)，差分日志和事務(wù)提交投票信息(Commit和Abort)一起，由事務(wù)參與者返回給事務(wù)發(fā)起者站點(diǎn)。在事務(wù)成功提交后,事務(wù)發(fā)起者站點(diǎn)的并行日志管理器將來自各個(gè)參與者的日志記錄亂序合并，然后并行地把日志一起寫入磁盤。

稱設(shè)置了一致全局檢驗(yàn)點(diǎn)的站點(diǎn)為 “協(xié)調(diào)者”。當(dāng)一個(gè)站點(diǎn)檢驗(yàn)點(diǎn)被觸發(fā) (該站點(diǎn)即為協(xié)調(diào)者)，協(xié)調(diào)者傳遞消息給各站點(diǎn)，要求各站點(diǎn)進(jìn)行基于分區(qū)的內(nèi)存數(shù)據(jù)庫(kù)一致局部檢驗(yàn)點(diǎn)。任何一個(gè)站點(diǎn)局部檢驗(yàn)點(diǎn)結(jié)束時(shí)，返回消息給協(xié)調(diào)者。只有所有的站點(diǎn)都返回消息給協(xié)調(diào)者后，這次全局檢驗(yàn)點(diǎn)結(jié)束。這樣設(shè)置的優(yōu)勢(shì)在于，當(dāng)子事務(wù)所操作數(shù)據(jù)中有分布式數(shù)據(jù)，當(dāng)整個(gè)事務(wù)提交后，如果該站點(diǎn)失敗，可以直接Redo該事務(wù)。

圖1 恢復(fù)子系統(tǒng)模型

為了恢復(fù)的需要，系統(tǒng)在每個(gè)站點(diǎn)的內(nèi)存中創(chuàng)建并維護(hù)三個(gè)表：活動(dòng)事務(wù)信息表（ATIL）、MMDB數(shù)據(jù)分區(qū)表以及并行日志管理器內(nèi)維護(hù)的鏈表LTD。其中ATIL表由事務(wù)管理器創(chuàng)建并維護(hù)，為系統(tǒng)中的每一個(gè)活動(dòng)子事務(wù)創(chuàng)建并維護(hù)一條記錄，該記錄包含兩個(gè)域：TID和TState,其中TID表示子事務(wù)標(biāo)識(shí)；TState表示該子事務(wù)所處狀態(tài) （活動(dòng)、阻塞、預(yù)提交、提交等狀態(tài)）。日志管理器根據(jù)ATIL表中TState的值決定是否將差分日志返回給事務(wù)發(fā)起者站點(diǎn)。事務(wù)發(fā)起者的LTD表包括三個(gè)域，鏈表存放最近一個(gè)全局檢驗(yàn)點(diǎn)來，提交事務(wù)的各參與點(diǎn)的信息，對(duì)應(yīng)的Redo日志在日志磁盤的起始頁(yè)及長(zhǎng)度。在恢復(fù)過程中，根據(jù)LTD表的內(nèi)容，可查找到失敗站點(diǎn)在最近一個(gè)全局檢驗(yàn)點(diǎn)來所寫出的日志記錄所在的日志磁盤的始頁(yè)及長(zhǎng)度，從而可以得到改失敗站點(diǎn)在最近一個(gè)全局檢驗(yàn)點(diǎn)來的所有日志。

MMDB數(shù)據(jù)分區(qū)表由恢復(fù)管理器負(fù)責(zé)維護(hù)，它為各站點(diǎn)的內(nèi)存數(shù)據(jù)庫(kù)中每個(gè)數(shù)據(jù)分區(qū)都維護(hù)一條記錄，該記錄包括三個(gè)域：PID、Ubit和Tuf。其中PID為數(shù)據(jù)分區(qū)的標(biāo)識(shí)。Ubit為更新位，用來表示PID分區(qū)的更新是否寫入固定存儲(chǔ)器，Ubit為1表示該分區(qū)沒有寫，Ubit為0表示該分區(qū)已經(jīng)寫。Tuf為標(biāo)識(shí)位，標(biāo)識(shí)PID分區(qū)自上一個(gè)檢查點(diǎn)操作以來的更新頻率，Tuf為整數(shù)值N，N值越大，說明該分區(qū)更新的頻率越大，Tuf為0，表示該分區(qū)沒有被更新。

2 差分日志

差分日志(differential log)是基于按位異或操作的。用表示按位異或操作。當(dāng)事務(wù)將數(shù)據(jù)對(duì)象的值B(beforeimage)更新為值A(chǔ)(after image)時(shí),該操作相應(yīng)的差分日志Dl(B,A)定義為BA。

差分日志具有如下基本特點(diǎn):

1)交換律:V1V2=V2V1。

2)結(jié)合律:(V1V2)V3=V1(V2V3)。

定理1 (亂序重做與撤消)數(shù)據(jù)對(duì)象的初始值是V0,，x的最終值為Vm，Dli(i=1,…,m)是上的差分日志，可以通過把差分日志亂序應(yīng)用到V0，得到Vm。

證明：假設(shè)差分日志以Dlk(1),Dlk(2),…,Dlk(m)的順序應(yīng)用到V0上,(k(i)∈{1,2,…,m},且當(dāng)i≠j有k(i)≠k(j)).當(dāng)m=1,V0Dlk(1)=V0Dl1=V1.假設(shè)當(dāng)m=n時(shí),上述結(jié)論成立,那么當(dāng)m=n+1的時(shí)候,假設(shè)k(i)=n+1,根據(jù)異或操作的交換律,有V0Dlk(1)Dlk(2)… Dlk(i-1)Dlk(i)Dlk(i+1)… Dlk(m)=V0Dlk(1)Dlk(2)… Dlk(i-1)Dlk(i+1)… Dlk(m)Dln+1=…=V0Dl1Dl2… Dln+1=Vn+1。

根據(jù) 定理1，得出如下的結(jié)論:1)差分日志記錄相對(duì)于傳統(tǒng)的Undo/Redo日志而言，只需記錄位異或操作的結(jié)果而無需記錄數(shù)據(jù)對(duì)象的舊值和新值，日志的數(shù)據(jù)量可以減少近一半。2)只要有初值，就可以在數(shù)據(jù)對(duì)象的初值上按照任意的順序應(yīng)用差分日志記錄都可以得到數(shù)據(jù)的最終值。根據(jù)這個(gè)結(jié)論，在系統(tǒng)正常運(yùn)行時(shí)可以對(duì)多個(gè)站點(diǎn)來源的日志記錄進(jìn)行亂序的整合，然后并行的將其寫入多個(gè)日志磁盤。在恢復(fù)過程中，從多個(gè)日志磁盤并行讀取記錄并且及時(shí)無序應(yīng)用到數(shù)據(jù)對(duì)象上，可以提高系統(tǒng)恢復(fù)的效率。

3 檢驗(yàn)點(diǎn)機(jī)制

在全局檢驗(yàn)點(diǎn)的協(xié)調(diào)下，各站點(diǎn)采用基于分區(qū)更新頻率的動(dòng)態(tài)局部檢驗(yàn)點(diǎn)模式，檢驗(yàn)點(diǎn)進(jìn)程和事務(wù)并發(fā)執(zhí)行。根據(jù)預(yù)先設(shè)置的閾值α，當(dāng)某站點(diǎn)MMDB頁(yè)表中臟頁(yè)所占比率大于閾值α?xí)r，檢驗(yàn)點(diǎn)進(jìn)程被觸發(fā)。

檢驗(yàn)點(diǎn)算法描述如下：

(1)當(dāng)站點(diǎn)的MMDB頁(yè)表中臟頁(yè)所占比率大于α?xí)r，檢驗(yàn)點(diǎn)進(jìn)程被觸發(fā)。該站點(diǎn)為“協(xié)調(diào)者”；

(2)協(xié)調(diào)者傳遞消息給各站點(diǎn)，各站點(diǎn)準(zhǔn)備進(jìn)行局部檢驗(yàn)點(diǎn)；

(3)各站點(diǎn)進(jìn)行局部檢驗(yàn)點(diǎn)；

(3.1)根據(jù)MMDB數(shù)據(jù)分區(qū)表統(tǒng)計(jì)各站點(diǎn)的更新頻率 Tuf(i)，i=1，…，N。

(3.2)設(shè)DP是數(shù)據(jù)分區(qū)按照Tuf的降序列表。DP第一個(gè)結(jié)點(diǎn)是Tuf最大的數(shù)據(jù)分區(qū)i，對(duì)該分區(qū)進(jìn)行事務(wù)一致的檢查點(diǎn)操作：首先在數(shù)據(jù)分區(qū)i的日志記錄中寫入 BC(Begin Checkpoint)日志記錄，表示該分區(qū)檢驗(yàn)點(diǎn)開始，也是該站點(diǎn)的局部檢驗(yàn)點(diǎn)開始；將分區(qū) i內(nèi)所有的數(shù)據(jù)頁(yè)面中的數(shù)據(jù)對(duì)象讀取到內(nèi)存緩沖區(qū)中，該分區(qū)檢驗(yàn)點(diǎn)結(jié)束；

(3.3)按DP順序依次讀取各分區(qū)的數(shù)據(jù)頁(yè)面，當(dāng)該站點(diǎn)所有分區(qū)的數(shù)據(jù)頁(yè)面都讀取完畢后，在日志中寫入 EC(End Checkpoint)日志記錄，表示該該站點(diǎn)的局部檢驗(yàn)點(diǎn)結(jié)束；將內(nèi)存緩沖區(qū)的內(nèi)容刷到固定存儲(chǔ)器中，形成新的檢查點(diǎn)文件；

(3.4)把各個(gè)數(shù)據(jù)分區(qū)的Tuf置為0；

(4)站點(diǎn)返回消息給協(xié)調(diào)者；

(5)協(xié)調(diào)者收集各站點(diǎn)返回消息，決定本次檢驗(yàn)點(diǎn)是否成功。如果成功，則清空鏈表LTD。

4 恢復(fù)

并行內(nèi)存數(shù)據(jù)庫(kù)站點(diǎn)失敗，進(jìn)行恢復(fù)的基本單位是數(shù)據(jù)分區(qū)。由于更新頻率高的數(shù)據(jù)分區(qū)很有可能再次被存取，所以應(yīng)該盡快的將在列表DP中靠前的數(shù)據(jù)分區(qū)恢復(fù)。而在列表DP靠后的數(shù)據(jù)分區(qū)可以暫時(shí)放在穩(wěn)定外存里。在站點(diǎn)的恢復(fù)過程中，一旦關(guān)鍵的數(shù)據(jù)分區(qū)(列表DP中靠前的數(shù)據(jù)分區(qū))裝載完成。系統(tǒng)就可以接納新所需事務(wù)。為了保證系統(tǒng)新事務(wù)的盡快投入運(yùn)行，必須對(duì)新事務(wù)的數(shù)據(jù)請(qǐng)求盡快進(jìn)行滿足；如果新事務(wù)所需存取的數(shù)據(jù)分區(qū)，還沒有載入內(nèi)存，則事務(wù)管理器堵塞該事務(wù)，等待所需數(shù)據(jù)分區(qū)載入后再喚醒該事務(wù)的執(zhí)行。站點(diǎn)恢復(fù)步驟：

（1）失敗站點(diǎn)向并行日志管理器提出日志查找申請(qǐng)。

（2）并行日志管理器根據(jù)鏈表LTD信息。得到最近一個(gè)全局檢驗(yàn)點(diǎn)后該站點(diǎn)的提交的日志記錄。并返回給失敗站點(diǎn)。

（3）根據(jù)該站點(diǎn)每個(gè)數(shù)據(jù)分區(qū)的更新頻率，得到不同數(shù)據(jù)分區(qū)被事務(wù)更新的頻繁程度。

（4）恢復(fù)管理器按頻繁程度讀取分區(qū)檢查點(diǎn)文件，并且以異或操作應(yīng)用到內(nèi)存緩沖區(qū)數(shù)據(jù)影像上（數(shù)據(jù)影像初值為0）。

（5）恢復(fù)管理器的日志裝載線程將并行日志管理器傳遞來的日志裝載到內(nèi)存緩沖區(qū)，再亂序應(yīng)用到分區(qū)數(shù)據(jù)影像上。

（6）分區(qū)數(shù)據(jù)裝載和差分日志亂序應(yīng)用完畢以后，將該分區(qū)標(biāo)記為可用狀態(tài)。關(guān)鍵的數(shù)據(jù)分區(qū)恢復(fù)完成后，如果有等待事務(wù)，由事務(wù)管理器喚醒等待事務(wù)繼續(xù)運(yùn)行。

5 驗(yàn)證試驗(yàn)

由于采用差分日志記錄法，在進(jìn)行日志的恢復(fù)的時(shí)候，Redo日志信息通過鏈表LTD從日志磁盤收集過來以后，不需要一個(gè)排序過程，可以直接應(yīng)用到內(nèi)存數(shù)據(jù)影像上。

驗(yàn)證試驗(yàn)操作平臺(tái)的性能數(shù)據(jù)為：磁盤尋道概率為50%，磁盤尋道平均時(shí)間約為5ms，網(wǎng)絡(luò)速度為1000Mbps。實(shí)驗(yàn)環(huán)境中并行內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)有6個(gè)站點(diǎn)，2個(gè)日志磁盤，數(shù)據(jù)分片為 256MB，整個(gè)數(shù)據(jù)庫(kù)的大小是 256*6=1.5GB，最近檢查點(diǎn)以來運(yùn)行的事務(wù)的數(shù)量是400K，差分日志記錄的日志數(shù)據(jù)大約是267MB。實(shí)驗(yàn)數(shù)據(jù)如圖2。

從圖2可以看出，在系統(tǒng)恢復(fù)的前幾秒，整個(gè)數(shù)據(jù)庫(kù)數(shù)據(jù)恢復(fù)的比率較低，系統(tǒng)吞吐量受到了影響也較低，恢復(fù)過程中的前5秒、5～10秒，系統(tǒng)的平均吞吐量分別只有37.2Ktps和42.9Ktps。隨著數(shù)據(jù)庫(kù)恢復(fù)過程的深入，新事務(wù)所存取的數(shù)據(jù)已經(jīng)駐留在內(nèi)存中，系統(tǒng)的吞吐量增長(zhǎng)明顯，在恢復(fù)過程中的 10～15秒、15～20秒、20～25秒以及 25～30秒，系統(tǒng)的平均吞吐量分別為 60.2Ktps、87.2Ktps、97.3Ktps、104.3Ktps，成明顯的遞增的趨勢(shì)，最后到達(dá)峰值——116Ktps。

圖2 恢復(fù)過程中的系統(tǒng)吞吐量

6 小結(jié)

恢復(fù)機(jī)制是利用差分日志的亂序應(yīng)用的特性，在事務(wù)提交后，并行的寫出日志到多個(gè)日志磁盤。檢驗(yàn)點(diǎn)被觸發(fā)后，在全局檢驗(yàn)點(diǎn)協(xié)調(diào)下，采用基于數(shù)據(jù)分區(qū)的局部檢驗(yàn)點(diǎn)模式，恢復(fù)過程中不僅各個(gè)日志磁盤可以并行裝載，而且數(shù)據(jù)分區(qū)的裝載和日志的裝載及應(yīng)用可以并行進(jìn)行，能盡快的把數(shù)據(jù)分區(qū)恢復(fù)到最近的一致狀態(tài)。特別是在子事務(wù)操作的分布式數(shù)據(jù)比較頻繁的并行內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)中，具有很好的應(yīng)用價(jià)值。不足之處在于全局檢驗(yàn)點(diǎn)協(xié)調(diào)如果不成功，將會(huì)導(dǎo)致檢驗(yàn)點(diǎn)重復(fù)多次被激活。

[1]LEE I,YEOM H Y,PARK T.A new approach for distributed main memory database systems:A causal commit protocol[J].IEICE Transactions on Infor-mation and Systems E Series D,2004,87(1): 196-204.

[2]周曉云,覃雄派，等.一種高效的并行內(nèi)存數(shù)據(jù)庫(kù)事務(wù)提交與恢復(fù)技術(shù)[J].中國(guó)礦業(yè)大學(xué)學(xué)報(bào),2009,38(1):68-74.

[3]杜曄，郭麗麗.空間實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)恢復(fù)機(jī)制研究與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013,33(2):734-739.

[4]邱元杰,劉心松,楊峰.一種高效的分布式并行數(shù)據(jù)庫(kù)日志機(jī)制[J].計(jì)算機(jī)研究與發(fā)展,2004,41(11):1942-1948.

[5]周曉云,覃雄派.基于網(wǎng)絡(luò)內(nèi)存的內(nèi)存數(shù)據(jù)庫(kù)高效恢復(fù)技術(shù)[J].系統(tǒng)工程理論與實(shí)踐,2011,31(2):81-87.

[6]STEPHEN B,KORTH H F.An almost-serial pro-tocol for transaction execution in main-memory data-base systems[C]// FREDERICK H L.Proceedings of the 28th International Conference on Very Large Data Bases.Hong Kong:VLDB Endowment,2002:706-717.

[責(zé)任編輯：桂傳友]

TP311

A

1674-1104(2013)06-0045-03

2013-06-19

國(guó)家自然科學(xué)基金項(xiàng)目 (60873021/F0201)。

袁文亮（1979－），男，湖南婁底人，池州學(xué)院數(shù)學(xué)與計(jì)算機(jī)系講師，碩士，研究方向?yàn)楝F(xiàn)代數(shù)據(jù)庫(kù)理論。