基于数据段优先级分区重装策略

梁 平，刘云生

（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