梁 平，劉云生

（1.華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢，430074；2.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢，430081）

基于數(shù)據(jù)段優(yōu)先級(jí)分區(qū)重裝策略

梁 平1，2，劉云生1

（1.華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢，430074；2.武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢，430081）

提出一種基于數(shù)據(jù)段優(yōu)先級(jí)分區(qū)重裝策略PRS－DSP，其考慮數(shù)據(jù)特征及與之相關(guān)的事務(wù)特點(diǎn)，根據(jù)數(shù)據(jù)段優(yōu)先級(jí)對(duì)數(shù)據(jù)庫(kù)進(jìn)行分區(qū)，并為每個(gè)分區(qū)設(shè)置相應(yīng)重裝頻率，故障恢復(fù)時(shí)按照數(shù)據(jù)分區(qū)的重裝頻率來(lái)分區(qū)重裝數(shù)據(jù)庫(kù)，系統(tǒng)恢復(fù)服務(wù)后，根據(jù)新事務(wù)對(duì)數(shù)據(jù)的請(qǐng)求及數(shù)據(jù)分區(qū)重裝頻率來(lái)設(shè)置剩余分區(qū)的重裝優(yōu)先級(jí)。模擬實(shí)驗(yàn)結(jié)果表明，該分區(qū)重裝策略降低了系統(tǒng)事務(wù)超截止期比率，其重裝性能明顯優(yōu)于完全重裝策略。關(guān)鍵詞：嵌入式實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)；故障恢復(fù)；分區(qū)重裝；數(shù)據(jù)段優(yōu)先級(jí)

有效的故障恢復(fù)機(jī)制對(duì)于嵌入式實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)（Embedded Real－Time Main Memory Database Systems，ERTMMDBS）性能具有決定性的作用，重裝作為ERTMMDBS恢復(fù)機(jī)制的重要方面，其效率的高低直接影響系統(tǒng)整體性能的優(yōu)劣。有效的重裝策略不僅能減少系統(tǒng)重啟時(shí)間，還能滿足更多數(shù)據(jù)的時(shí)間有效性和事務(wù)截止期。完全重裝和部分重裝是目前內(nèi)存數(shù)據(jù)庫(kù)常用的兩種重裝策略。完全重裝［1］會(huì)嚴(yán)重阻塞事務(wù)執(zhí)行，不適合有時(shí)限性要求的ERTMMDBS；部分重裝策略［2］將數(shù)據(jù)庫(kù)部分裝入內(nèi)存便開(kāi)始運(yùn)行，減少了超截止期事務(wù)和數(shù)據(jù)量，適合于ERTMMDBS的重裝。文獻(xiàn)［3］和文獻(xiàn)［4］分別給出了支持實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)以頁(yè)作為重裝粒度的部分重裝策略及基于數(shù)據(jù)庫(kù)分區(qū)的部分重裝策略；文獻(xiàn)［5］分析了實(shí)時(shí)事務(wù)、數(shù)據(jù)特征對(duì)數(shù)據(jù)重裝的影響，構(gòu)造了數(shù)據(jù)相親度及相親矩陣，提出了基于裝入數(shù)據(jù)選擇函數(shù)的數(shù)據(jù)裝入算法。然而上述諸策略均未考慮嵌入式環(huán)境下恢復(fù)的特殊需求。為滿足ERTMMDBS的重裝需求及提高恢復(fù)過(guò)程系統(tǒng)的可用性，本文提出一種考慮數(shù)據(jù)特征及與之相關(guān)事務(wù)特點(diǎn)的基于數(shù)據(jù)段優(yōu)先級(jí)分區(qū)重裝策略。

1 基于數(shù)據(jù)段優(yōu)先級(jí)的分區(qū)方法

根據(jù)嵌入式實(shí)時(shí)數(shù)據(jù)所具有的不同特征（實(shí)時(shí)性、存取頻率、關(guān)鍵性和持久性等），綜合考慮ERTMMDBS的故障恢復(fù)。對(duì)于重裝策略，故障恢復(fù)時(shí)數(shù)據(jù)裝入需要考慮以下幾方面：①有效期較短的數(shù)據(jù)盡快裝入內(nèi)存；②關(guān)鍵數(shù)據(jù)優(yōu)先裝入內(nèi)存；③更新頻率高的數(shù)據(jù)優(yōu)先裝入內(nèi)存；④被高優(yōu)先級(jí)事務(wù)存取的數(shù)據(jù)優(yōu)先裝入內(nèi)存?；趦?nèi)存數(shù)據(jù)庫(kù)區(qū)段式內(nèi)存組織方式［6］考慮，重裝策略以數(shù)據(jù)段為單位，按上述幾方面綜合考慮包含在數(shù)據(jù)段中數(shù)據(jù)的不同特征，為每一個(gè)數(shù)據(jù)段設(shè)置一個(gè)優(yōu)先級(jí)，該優(yōu)先級(jí)表示了數(shù)據(jù)段在重裝時(shí)裝入內(nèi)存的優(yōu)先次序。

設(shè)嵌入式實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)DB由n個(gè)數(shù)據(jù)段組成，Si為其中的第i個(gè)數(shù)據(jù)段，即DB＝｛Si｜1≤i≤n｝，數(shù)據(jù)段Si的重裝優(yōu)先級(jí)為

式中：VTI（Si）為Si中包含的所有數(shù)據(jù)的有效期的最小值；UF（Si）為Si中包含的所有數(shù)據(jù)的更新頻率總和；CR（Si）為Si中包含的所有數(shù)據(jù)關(guān)鍵程度的最大值；P（Si）為存取了Si中數(shù)據(jù)的事務(wù)的最高優(yōu)先級(jí)；WVI、WUF、WCR和WP分別為VTI（Si）、UF（Si）、CR（Si）和P（Si）的加權(quán)因子。

式（1）表明，數(shù)據(jù)段中包含的數(shù)據(jù)的有效期越短，數(shù)據(jù)段的重裝優(yōu)先級(jí)越高；數(shù)據(jù)段中數(shù)據(jù)的更新頻率越高，數(shù)據(jù)段的重裝優(yōu)先級(jí)越高；數(shù)據(jù)段中數(shù)據(jù)的關(guān)鍵程度越高，數(shù)據(jù)段的重裝優(yōu)先級(jí)越高；存取數(shù)據(jù)段中數(shù)據(jù)的事務(wù)的優(yōu)先級(jí)越高，數(shù)據(jù)段的重裝優(yōu)先級(jí)越高。

按數(shù)據(jù)段重裝優(yōu)先級(jí)，將數(shù)據(jù)庫(kù)分為n個(gè)分區(qū)，每一分區(qū)長(zhǎng)度均為H，在分區(qū)Si被更新后，利用式（1）計(jì)算出分區(qū)Si的重裝優(yōu)先級(jí)SP（Si），再根據(jù)下列條件生成Si所屬的分區(qū)號(hào)j：若SP（Si）／H＜n，則j ＝SP（Si）／H；若SP（Si）／H≥n，則j＝n，然后把Si加入分區(qū)j。按照上述分區(qū)方式，在一個(gè)分區(qū)中的各數(shù)據(jù)段，其重裝優(yōu)先級(jí)都相互接近，因此可以給每個(gè)分區(qū)設(shè)置不同的重裝頻率，以便在重裝過(guò)程中按照數(shù)據(jù)段中所含數(shù)據(jù)的不同特征進(jìn)行重裝。

2 數(shù)據(jù)段優(yōu)先級(jí)分區(qū)重裝策略

在分區(qū)重裝策略中，為重裝優(yōu)先級(jí)高的數(shù)據(jù)段所屬分區(qū)設(shè)置較高的重裝頻率，為刷新優(yōu)先級(jí)低的數(shù)據(jù)段所屬分區(qū)設(shè)置較低的重裝頻率。根據(jù)分區(qū)長(zhǎng)度H和分區(qū)數(shù)n，設(shè)置分區(qū)i的平均重裝優(yōu)先級(jí)為

根據(jù)分區(qū)的平均重裝優(yōu)先級(jí)，分區(qū)i的重裝頻率為

基于數(shù)據(jù)段優(yōu)先級(jí)的分區(qū)重裝策略步驟為：

（1）根據(jù)分區(qū)的重裝頻率順序從高到低依次重裝每個(gè)分區(qū)，一個(gè)分區(qū)裝入后，其相 應(yīng)的日志處理立即開(kāi)始執(zhí)行，將該分區(qū)恢復(fù)到最近一致性狀態(tài)。

（2）重裝的數(shù)據(jù)分區(qū)數(shù)達(dá)到系統(tǒng)閥值后，系統(tǒng)重新開(kāi)始提供服務(wù)。

（3）按數(shù)據(jù)分區(qū)的重裝優(yōu)先級(jí)重裝剩余分區(qū)，可分為下列情形：①根據(jù)系統(tǒng)新事物對(duì)數(shù)據(jù)分區(qū)的存取需求和數(shù)據(jù)分區(qū)的重裝頻率，生成剩余分區(qū)i的重裝優(yōu)先級(jí)為

式中，Tj為事務(wù)j的等待時(shí)間，L為系統(tǒng)中當(dāng)前運(yùn)行的事務(wù)數(shù)，Mji（1≤j≤n，1≤i≤L）為事務(wù)Tj等待存取分區(qū)i的存取關(guān)系矩陣，W為重裝頻率與事務(wù)等待時(shí)間之間的權(quán)重因子；②根據(jù)各剩余分區(qū)的重裝優(yōu)先級(jí)，重裝剩余數(shù)據(jù)分區(qū)中重裝優(yōu)先級(jí)最高的分區(qū)，并根據(jù)相應(yīng)日志對(duì)該分區(qū)進(jìn)行恢復(fù)處理；③重復(fù)步驟①、②，處理剩余的數(shù)據(jù)分區(qū)。

按照數(shù)據(jù)分區(qū)的重裝優(yōu)先級(jí)重裝剩余分區(qū)時(shí)，一個(gè)分區(qū)被重裝后，由于系統(tǒng)運(yùn)行事務(wù)的等待時(shí)間發(fā)生了改變，因而需要重新計(jì)算各剩余分區(qū)的重裝優(yōu)先級(jí)，以滿足系統(tǒng)當(dāng)前事務(wù)對(duì)數(shù)據(jù)的快速存取請(qǐng)求，根據(jù)事務(wù)截止期要求縮短響應(yīng)時(shí)間，提高系統(tǒng)恢復(fù)效應(yīng)。

3 PRS－DSP重裝性能測(cè)試

以ARTs－EDB為實(shí)驗(yàn)?zāi)Ｐ?，?duì)基于數(shù)據(jù)段優(yōu)先級(jí)的分區(qū)重裝策略PRS－DSP進(jìn)行性能測(cè)試，用事務(wù)超過(guò)截止期比率（TMDP）作為該性能的主要衡量指標(biāo)，TMDP＝（超截止期事務(wù)數(shù)／系統(tǒng)產(chǎn)生事務(wù)總數(shù)）×100%。模擬實(shí)驗(yàn)主要參數(shù)如表1所示，其中，事務(wù)松馳因子Slack為一個(gè)均勻分布的隨機(jī)變量；U（i，j）表示區(qū)間［i，j］一個(gè)均勻分布的隨機(jī)變量。

表1 模擬實(shí)驗(yàn)主要參數(shù)Table 1 Simulation experiment parameters

數(shù)據(jù)段優(yōu)先級(jí)分區(qū)重裝策略（PRS－DSP）與傳統(tǒng)完全重裝策略（CRS）在不同事務(wù)到達(dá)率下的性能如圖1所示。從圖1中可看出，PRS－DSP性能明顯優(yōu)于CRS。這是因?yàn)镻RS－DSP采用了部分重裝方式，根據(jù)數(shù)據(jù)分區(qū)的重裝頻率來(lái)分區(qū)重裝數(shù)據(jù)庫(kù)，讓立即需要的數(shù)據(jù)優(yōu)先裝入數(shù)據(jù)庫(kù)，當(dāng)系統(tǒng)恢復(fù)服務(wù)后，根據(jù)事務(wù)對(duì)數(shù)據(jù)的請(qǐng)求和數(shù)據(jù)分區(qū)重裝頻率來(lái)設(shè)置剩余分區(qū)的重裝優(yōu)先級(jí)并進(jìn)行重裝，因而降低了對(duì)事務(wù)的響應(yīng)時(shí)間。

圖1 PRS－DSP、CRS在不同事務(wù)到達(dá)率下的性能Fig.1 Reload performance comparison of PRS－DSP and CRS at different transaction arrival rates

PRS－DSP在不同分區(qū)數(shù)下的性能如圖2所示。從圖2中可看出，PRS－DSP隨分區(qū)數(shù)的增大，其整體性能隨之增強(qiáng)，當(dāng)分區(qū)數(shù)較小（小于6）時(shí)，重裝性能（在相同事務(wù)到達(dá)率下）較CRS差，分區(qū)數(shù)超過(guò)8時(shí)，PRS－DSP性能開(kāi)始優(yōu)于CRS。這是由于分區(qū)數(shù)越小，即分區(qū)越大，事務(wù)等待所需數(shù)據(jù)裝入內(nèi)存時(shí)間越長(zhǎng)，事務(wù)處理與數(shù)據(jù)庫(kù)重裝互相影響，致使重裝處理速度降低。因此，要想獲得較佳的分區(qū)重裝性能，PRS－DSP需選擇適當(dāng)大的分區(qū)數(shù)。

圖2 PRS－DSP在不同分區(qū)數(shù)下的性能Fig.2 Reload performance of PRS－DSP at different partition numbers

4 結(jié)論

（1）PRS－DSP降低了系統(tǒng)事務(wù)超截止期比率，系統(tǒng)性能優(yōu)于CRS。

（2）要想獲得較佳的分區(qū)重裝性能，PRSDSP需選擇適當(dāng)大的分區(qū)數(shù)。

［1］ Hagmann R B.A crash recovery scheme for a memory－resident database system［J］.IEEE Transactions on Computers，1986，35（9）：839－843.

［2］ Gruenwald L，Huang J.MMDB partial reload［J］.Journal of Microcomputer Applications，1994，17（2）：113－133.

［3］ Huang J，Gruenwald L.Crash recovery for real－time main memory database systems［C］∥Proceedings of the 1996 ACM Symposium on Applied Computing，1996：145－149.

［4］ Huang J，Gruenwald L.A data priority reload technique for real－time main memory databases［C］∥Proceedings of the 8th Euromicro Workshop on Real－Time Systems，1996：96－101.

［5］ 劉云生，李國(guó)徽.實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)的裝入［J］.軟件學(xué)報(bào)，2000，11（6）：829－835.

［6］ 劉云生，付蔚.主動(dòng)實(shí)時(shí)內(nèi)存數(shù)據(jù)庫(kù)的組織與故障恢復(fù)［J］.計(jì)算機(jī)工程與應(yīng)用，2002，38（9）：170－172.

A partition reload strategy based on data segment priority

Liang Ping1，2，Liu Yunsheng1
（1.College of Computer Science and Technology，Huazhong University of Science and Technology，Wuhan 430074，China；2.College of Computer Science and Technology，Wuhan University of Science and Technology，Wuhan 430081，China）

A partition reload strategy PRS－DSP（partition reload strategy based on data segment priority）based on the priority of data segment is presented，which partitions the database in accordance with the priorities of data segments and sets the corresponding reload frequency for each partition.It reloads the database in terms of partition reload frequency for crash recovery，which the system can serve before the entire database is reloaded.The reload priorities of the remaining partitions are set according to the requests of new transactions and reload frequency of partition after the system restores services.Simulation experiments show that，PRS－DSP reduces the system halt servicing time and improves the system availability during the recovery，demonstrating a better performance than the complete reload strategy.

embedded real－time main memory database；crash recovery；partition reload；data segment priority

TP 311.5

A

1674－3644（2012）03－0232－03

［責(zé)任編輯 彭金旺］

2011－07－19

國(guó)家自然科學(xué)基金資助項(xiàng)目（60673128）.

梁 平（1975－），女，華中科技大學(xué)博士生，武漢科技大學(xué)講師.E－mail：lpnjh＠sohu.com