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

梁 平，劉云生

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

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

梁 平1，2，劉云生1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 PRS－DSP重裝性能測試

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

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

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

圖1 PRS－DSP、CRS在不同事務到達率下的性能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ù)的增大，其整體性能隨之增強，當分區(qū)數(shù)較?。ㄐ∮?）時，重裝性能（在相同事務到達率下）較CRS差，分區(qū)數(shù)超過8時，PRS－DSP性能開始優(yōu)于CRS。這是由于分區(qū)數(shù)越小，即分區(qū)越大，事務等待所需數(shù)據(jù)裝入內(nèi)存時間越長，事務處理與數(shù)據(jù)庫重裝互相影響，致使重裝處理速度降低。因此，要想獲得較佳的分區(qū)重裝性能，PRS－DSP需選擇適當大的分區(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)事務超截止期比率，系統(tǒng)性能優(yōu)于CRS。

（2）要想獲得較佳的分區(qū)重裝性能，PRSDSP需選擇適當大的分區(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］ 劉云生，李國徽.實時內(nèi)存數(shù)據(jù)庫的裝入［J］.軟件學報，2000，11（6）：829－835.

［6］ 劉云生，付蔚.主動實時內(nèi)存數(shù)據(jù)庫的組織與故障恢復［J］.計算機工程與應用，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

［責任編輯 彭金旺］

2011－07－19

國家自然科學基金資助項目（60673128）.

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