基于數據段優先級分區重裝策略

梁 平，劉云生

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

基于數據段優先級分區重裝策略

梁 平1，2，劉云生1

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

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

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

1 基于數據段優先級的分區方法

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

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

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

式（1）表明，數據段中包含的數據的有效期越短，數據段的重裝優先級越高；數據段中數據的更新頻率越高，數據段的重裝優先級越高；數據段中數據的關鍵程度越高，數據段的重裝優先級越高；存取數據段中數據的事務的優先級越高，數據段的重裝優先級越高。

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

2 數據段優先級分區重裝策略

在分區重裝策略中，為重裝優先級高的數據段所屬分區設置較高的重裝頻率，為刷新優先級低的數據段所屬分區設置較低的重裝頻率。根據分區長度H和分區數n，設置分區i的平均重裝優先級為

根據分區的平均重裝優先級，分區i的重裝頻率為

基于數據段優先級的分區重裝策略步驟為：

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

（2）重裝的數據分區數達到系統閥值后，系統重新開始提供服務。

（3）按數據分區的重裝優先級重裝剩余分區，可分為下列情形：①根據系統新事物對數據分區的存取需求和數據分區的重裝頻率，生成剩余分區i的重裝優先級為

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

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

3 PRS－DSP重裝性能測試

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

表1 模擬實驗主要參數Table 1 Simulation experiment parameters

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

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

PRS－DSP在不同分區數下的性能如圖2所示。從圖2中可看出，PRS－DSP隨分區數的增大，其整體性能隨之增強，當分區數較小（小于6）時，重裝性能（在相同事務到達率下）較CRS差，分區數超過8時，PRS－DSP性能開始優于CRS。這是由于分區數越小，即分區越大，事務等待所需數據裝入內存時間越長，事務處理與數據庫重裝互相影響，致使重裝處理速度降低。因此，要想獲得較佳的分區重裝性能，PRS－DSP需選擇適當大的分區數。

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

4 結論

（1）PRS－DSP降低了系統事務超截止期比率，系統性能優于CRS。

（2）要想獲得較佳的分區重裝性能，PRSDSP需選擇適當大的分區數。

［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］ 劉云生，李國徽.實時內存數據庫的裝入［J］.軟件學報，2000，11（6）：829－835.

［6］ 劉云生，付蔚.主動實時內存數據庫的組織與故障恢復［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