支持嵌入式实时内存数据库的检验点策略及重做起点确定策略

支持嵌入式实时内存数据库的检验点策略及重做起点确定策略 小 型 微 型 计 算 机 系 统 年 8 月 第 8 期2009 130 . 82009 V o lN o Jo u rna l o f C h ine se Com p u te r Sy stem s 支持嵌入式实时内存数据库的检验点策略及重做起点确定策略 梁勇平, 刘云生, 胡 ( ) 华中科技大学 计算机学院, 湖北 武汉 430074 2: @ . E m a illp n jh so h ucom 摘 要: 嵌入式环境下实时内存数据库系统发生故障时要求能快速恢复, 检验点策略是实时内存数据库恢复的关键技术. 本文基于一个自主开发的嵌入式实时内存数据库原型系统2 , 提出一种支持该系统故障恢复的模糊检验点策略, 并给出两种 ?A R T 故障恢复时重做起点的确定策略. 通过性能测试 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明: 所提出的检验点策略及重做起点的确定策略能提高实时事务满足截止期 的比率, 提高了整个系统的性能. 关 键 词: 嵌入式实时内存数据库; 数据库恢复; 检验点; 重做起点 () 文 章 编 号: 100021220 20090821588203 中图分类号: 311 文献标识码: T P A - Checkpo in t in g Stra tegy an d Redo Po in t Stra tegy f or Em bedded Rea lt im e M a in M em ory D a ta ba se s 2, , L IA N G P ingL IU Yun sh engHU Yo ng (), , 430074, C ol leg e of C om p u ter S cienceH u az h ong U n iv ersity of S cience and T ech nology W u h an C h ina 2: A bstrac tT h e fa ilu re reco ve ry o f th e rea lt im e m a in m em o ry da taba se sy stem need s th e rap id reco ve ry in th e em bedded , 2. env iro nm en tch eckpo in t ing is an im po r tan t reco ve ry tech n ique o f rea lt im e m a in m em o ry da taba seA fuzzy ch eckpo in t ing () 2 2, ?st ra tegy ba sed o n th e A R T an ac t ive rea lt im e m a in m em o ry da taba seis sugge stedand tw o typ e s o f redo po in t st ra teg ie s . fo r th is ch eckpo in t ing st ra tegy a re a lso deve lop edT h e p e rfo rm ance te st show s th a t th is ch eckpo in t ing st ra tegy and th e redo .po in t st ra teg ie s can inc rea se th e ra t io o f th e t ran sac t io n s m ee t ing th e dead line and th e p e rfo rm ance o f th e sy stem : 2; ; ; Key wordsem bedded rea lt im e m a in m em o ry da taba se sda taba se reco ve rych eckpo in t ingredo po in t ( 2, em bedded rea lt im e m a in m em o ry da taba se sy stem 1 引 言 ) 中是不适合的.ER TM M DB S 1 ( 实 时 内 存 数 据 库2rea lt im e m a in m em o ry da taba se 本文基于一个自主开发的嵌入式实时内存数据库原型系 ) , 中, 数据库主版本工作在易失性内存sy stem R TM M DB S 统2? , 讨论了一种支持该系统故障恢复的模糊验点策A R T ) ( 中, 数据极为脆弱, 恢复十分重要. 同时, vo la t ile RAM() 略, 并基于该策略给出了两种故障恢复时重做 起点 R EDO 中事务执行的过程可保证无 或 次数最 ƒƒR TM M DB S IO IO 的确定策略. 少, 恢复成为运行过程中唯一涉及 操作的部 ƒR TM M DB S IO () 2 嵌入式实时内存数据库 - ? 体系结构 A RT件, 因此恢复的性能对整个系统的总体性能非常关键. 由于在 嵌入式实时内存数据库系统2? 的系统构成如图 1 () A R T 恢复过程中非常重要的检验点 , 操作是ch eckpo in t ing C KP 所示. 为用户接口, 主要为终端用户提供一个 U se r In te rface 进行磁盘数据 ƒ的惟一机制, 其目的是在永久 R TM M DB S IO 操作数据库的友好图形界面, 包括菜单管理、命令管理及输入 存储设备中维持数据库最新版本, 确定恢复起始点以及减少 输出屏幕管理等. 为数据说明部分, 它由 D a ta Sp ec if ica t io n 故障恢复时间, 所以检验点操作的效率高低将直接影响恢复扩展 语言处理器、事件及触发器定义语言处理器、事务 SQ L 系统性能以至整个系统的总体性能的好坏.的定时说明语言处理器等主动实时说明语言处理器组成, 其 2 功 能主要是建立并维护数据字典、事件库 2、触发器库 DDE B嵌入式应用是数据库系统一个新的应用领域. 嵌入式 2、应用程序库 2、以及存储事务特性信息的事务表 .T BP BT T 应用环境往往是运行过程中无人工干预, 且要求系统发生故 为主动机制部分, 它主要由事件探测器、触 A c t ive M ech an ism 3 障后能自诊断、自适应恢复, 同时要求系统能快速恢复. 由发器监控器、条件 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 器组成, 用于事件的探测和条件的评价 于内存数据库能够极大地减少系统运行期间的 ƒ从而提 , IO () 及相关联活动 事务的触发. 为事务管 高系统处理的速度以满足实时性的要求, 因此嵌入式实时环 T ran sac t io n M anage r 境下的数据库系统一般以内存数据库作为基础. 显然, 传统恢 ( 理 部分, 其主要负责事务优先级分派、事务的调度 事务的接 复技术中的静态检验点技术在嵌入式实时内存数据库系统 ( ) 收稿日期: 2008204201 收修改稿日期: 2008207219 基金项目: 国家自然科学基金项目 60673128资助. 作者简介: 梁 平, 女, 1975 年 生, 博士研究生, 主要研究方向为实时内存数据库、数据库恢复; 刘云生, 男, 1940 年生, 教授, 博士生导师, 主要研究方向为主动、实时等现代数据 库系统及其集成的研究. ) 纳、事务的放行及调度执行及事务的并发控制等. ;的位置R eco ve ry ( ) 2为外存数据字典保存一个副本, 把内存数据字典刷 为恢复子系统. 完成对内存数据库的管理和M M DB M anage r 新到外存, 覆盖原来外存的数据字典; (( )遍 历 内 存 区 段 表, 刷 新 内 存 数 据 库 3 m em o ry ) ,到外存: 逐项扫描分区表, 根据分区表每一项 da taba seM DB 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 找到对应的段表的信息, 如该段有更新, 则把该有更新的 对应数据块复制到临时缓冲区并将临时缓冲区的内容刷新到 外存数据库中的对应块; 如该段没有更新, 则继续处理下一段 表项, 直到分区表处理完毕; ( ) 4 在外存日志文件中记录检验点结束日志< EN D () > 设其位置为;CH KT E ck () 5在日志文件头中记录重做起始点为BC k. () 其中, 在步骤 2中保存外存数据字典的副本是为了保证 图 1 2? 系统结构 A R T 数据字典的原子性 , 因为在故障时内存数据字典可能出现数 2. 1 ?F igSy stem st ruc tu re o f A R T 据不一致. () 3. 2 重做 起点的确定策略维护. 模块完成内外存数据交换, 确保事务执行过 REDO E xch ange r 程无 ƒ实现内存数据库的概念. 完成对外存 , IO SDB M anage r 对于传统的模糊检验点策略, 重做起点从日志文件头中 () 磁盘数据库的管理和维护. 记录的重做起点开始即可; 而上述的非静止模糊检验点策略, 3 检验点策略及重做起点的确定策略 由于采用延迟的数据库修改策略, 事务对数据库的更新在事 务提交后才能真正写入数据库, 在如下两种情况下会出现外 为了尽量不影响系统的运行, 同时又能快速的进行故障 存日志的交错, 即需要重做的事务其日志有部分出现在检验 恢复, 2? 系统的工作版本数据及日志缓冲区存放在易失 A R T 点开始日志位置之前, 使得起点不能从外存日志 BC k R EDO 性的主存中, 完整的数据库和日志均存储在硬盘中. 另外, 采 文件头中记录的开始. 这里所说的检验点都指最后一次 BC k 用延迟的数据库修改策略: 在运行过程中, 每个事务都 DBM S 成功的检验点. 有一个用户工作区, 称为该事务的日志缓冲区, 其中保存了该 ( ) 1某一事务在检验点开始前已提交, 同时该事务的日 事务所进行的数据库修改, 在事务提交时再将修改的数据更 志已刷新到外存日志中, 但检验点开始时, 其事务工作区的内 新到内存数据库中. 由于采用延迟的数据库修改策略, 在日志 容还没有完全刷新到等检验点结束后该刷新才完成, , M DB 中只需记录数据操作的后映像, 即型日志. 事务提交的 R EDO 但该事务对的修改未体现到外存数据库中, 此时发生故 M DB 时候, 采用先写日志原则, 如果该事务与已提交的事务 W A L 障, 该事务必须重做, 但此时该事务的日志在检验点日志之 没有冲突, 那么首先将该事务日志缓冲区中的日志写入到外 前, 重做起点不能是检验点开始的位置. 此时的日志记录时间 存日志中, 然后再执行更新; 如果事务提交失败, 或者事务夭 顺序如图 2 所 折, 则直接放弃该日志缓冲区, 对于事务故障的恢复过程并不 示.需要根据日志来进行逆向操作. ( ) 2某一 3. 1 检验点策略 事 务 在 提 交 由于嵌入式实时环境实时性要求高, 显然采用静止检验 4 时, 根据W A L点技术是不适合的, 应采用非静止模糊检验点策略, 即允许 5 先 写 日 志 原事务处理与检验点操作并发执行. 传统的模糊检验点需要 ( ) 记录已修改过数据块 脏数据块的列表, 或者需要记录当前 正 在运行的事务列表, 以及需要采用ƒ型日志, R EDO U N DO 因此对于系统的效率有很大的影响. 在2 系统中采用 ?A R T 图 2 日志记录时间顺序图 1 则, 先 要 将 其延迟的数据库修改策略, 只需要将内存中的数据块按某种顺 . 2 F igF ir st t im ing d iag ram o f lo g 日 志 写 到 外序进行遍历并将其中的脏数据块写入外存, 这样空间的需求 存, 如果在写日志的过程中检验点操作开始, 则会产生该事务减少了, 检验点操作所需的时间也可以预知, 检验点周期变 的一部分日志在检验点开始日志之前, 另一部分日志在检验 短, 因此可以获得更高的效率, 其恢复所需的工作量也并不会 增加. 点开始日志之后, 出现了日志交错的现象. 此时发生故障, 故 综 上所述, 支持嵌入式实时内存数据库2 系统的 ?A R T 障重做时, 该事务也要重做, 但其起始点在检验点开始日志之 一个检验点过程实现步骤为: 前, 所以重做起点不能是检验点开始的位置. 此时的日志记录 ( ) 1在外存日志文件中记录检验点开始日志< STA R T 时间顺序如图 3 所示. () > 设其位置为并在外存日志文件头中记录, CH KT BC k BC k 对于以上两种情况, 有如下两种确定重做起点的策略, 该 策略要求在检验点开始时, 首先查找到在该时刻的活动事务, 即还没有完成把提交日志写入外存日志, 或没有把其修改刷 新到的事务, 然后将其记入检验点开始日志中.M DB 策略1. 从开始, 往前扫描日志, 找出所有活动事务中BC k 小 型 微 型计 算 机 系 统 1590 2009 年 最早开始的那个事务的开始点位置: 逐条读出每条日志的事, 又会导致超截止期事务增多, 影响系统性所有活动事务结束 在实际系统中采取哪种策略主要以系统具体情况而定, 务 及日志类型信息, 看该条日志是否在活动事务集中且类 ID 如果系统存储空间要求小而实时性不强则可采取策略2; 如果 型是事务开始, 是则从活动事务集中删除, 直到活动事务集中 系统要求实时性强而存储空间较大则采取策略 1. 只剩最后一个事务, 则该事务就是活动事务集中最早开始的, 4. 2 检验点策略比较此开始日志位置即为重做起点. 因为该位置以前的事务不需 将本文提出的非静止模糊检验点策略与传统数据库模糊 要重做, 所以该位置以前的外存日志可以删除. 检验点策略通过实验进行性能比较, 采用实时事务错过截止 策略2. 约 () 期的比率作为主要性能指标, 定义为M R m issing ra t io M R 定在记检验点 ƒ×100 % , 其中表示超截止 N umM issN um T o ta l N umM iss 结束 日 志 前, () 期事务数, 表示事务总数, 重做 起点的确N um T o ta l R EDO 在该检验点开 定策略采用策略 2. 始时记录的活 动事务均已结 图 3 日志记录时间顺序图 2( 束 提 交撤 ƒ . 3 F igSeco nd t im ing d iag ram o f lo g ) 消. 即如果还 有活动事务未结束, 则检验点进程将等待, 直到所有在检验点开始时记录的活动事务都结束, 再往外存日志文件中记检验 图 4 策略 2 下两种检验点策略在不同事务到达率下性能比较 点结束标志. 此时重做起点的确定又分两种情况: . 4 F igP e rfo rm ance com p a r iso n o f tw o typ e s o f ch eckpo in t ing ? 故障发生在检验点结束以后. 由于此时在检验点开始 2时的所有活动事务均已结束, 重做起点就是这些活动事务中 st ra teg ie s o n d iffe ren t TA R w ith redo po in t st ra tegy 最早开始的那个事务的起始点. 只需要从本次成功的检验点 (图 4 和图 5 分别给出了在不同事务到达率 T ran sac t io in 的上一个成功检验点的开始位置向后扫描日志找到最早开始 ) () , 和故障发生率 , 情形下 A r r iva l R a teTA R F a ilu re R a teFR 的活动事务的起始点. 因为在上一个成功的检验点结束时, 在 本文提出的非静止模糊检验点策略与传统数据库模糊检验点 上一个成功检验点开始时的所有活动事务都已经结束, 只要 策略的性能比较情况. 最近一次检验点成功, 这些事务对的修改一定会被刷新 M DB ( ) 到外存数据库 , 不需要重做, 所以 seco nda ry da taba se SDB 可以保证这些活动事务都是在本次成功的检验点的上一个成 功的检验点开始点之后开始的, 上一个成功检验点开始之前 的日志可以删除. 其查找过程为: 读出每条日志的事务 及 ID 日志类型信息, 看该条日志是否在活动事务集中且类型是事 务开始, 是则该条日志的位置就是重做起点. ? 故障发生在检验点过程中. 由于此时在上一个检验点 图 5 策略 2 下两种检验点策略在不同故障发生率下性能比较 结束时已结束的事务其更新不确定是否已刷新到 所以 , SDB . 5 F igP e rfo rm ance com p a r iso n o f tw o typ e s o f ch eckpo in t ing 重做起始点必须是这些事务中最早开始的那个事务的起始 2st ra teg ie s o n d iffe ren t FR w ith redo po in t st ra tegy 点. 基于与?相同的原因, 可以保证这类事务都是在上上个成 图 4 和图 5 的结果表明本文提出的非静止模糊检验点策 功的检验点开始点之后开始的, 只需从上上个成功的检验点 略性能明显好于传统数据库模糊检验点策略, 提高了实时事 开始点向后扫描日志找到在最近一个成功的检验点开始处活 务满足截止期的比率, 从而提高了整个系统的性能. 动事务中最早开始的那个事务的起始点. 查找该事务的过程 为: 读出每条日志的事务 及日志类型信息, 看该条日志是 ID :Ref eren ce s 否在活动事务集中且类型是事务开始, 是则该条日志的位置 1 , , , . 2C ho i M SYoo n H SSo ng E M e t a lTw o step back up 就是重做起点. 综合上述两种情况, 日志只需要保存到上两个 2[ . m ech an ism fo r rea lt im e m a in m em o ry da taba se reco ve ry C 成功的检验点处, 前面的日志可以删除. : : InIE E E P ro ceed ing s o f Seven th In te rna t io na l Co nfe rence, 2000, 4532457.IE E E Com p u te r So c ie ty 4 性能评测与结论 2 W ang T o ng, W ang L iang. Summ a and app ra isa l o f em bedded 2001, 27 [ . , m o b ile da taba se sy stem J Com p u te r E ng inee r ing( ) 12: 1552157. 3 Se lt tze r M , O lso n M . C h a llenge s in em bedded da taba se sy stem adm in ist ra t io n [ EB OL . h t tp: www. sleep yca t. com do c s ƒƒƒƒƒƒ2. , 2005.refem beddedh tm l 4 22. [. : L iu Yun sh engA dvanced da taba setech no lo gy M B e ijing, 2001.N a t io na l D efence Indu st ry P re ss 4. 1 起点确定策略的比较 REDO 5 , , . W oo S K K im M H L ee Y JA n effec t ive reco ve ry unde r fuzzy 由于策略 1 需要反向往前扫描外存日志, 所以在每条日[ . ch eckpo in t ing in m a in m em o ry da taba se s J Info rm a t io n and ( ) , 2000, 42 3: 1852196.So f tw a re T ech no lo gy 志中必须记录上一条日志起始位置的信息, 这无疑将增加日志的大小, 使得日志缓冲区增大, 而且将导致外存日志文件过 :附中文参考文献 大, 浪费存储空间资源; 而在策略 2 中因为不需要反向扫描日 2 王 彤, 王 良. 嵌入式移动数据库的综述和评价[ . 计算机工 J ( ) 程, 2001, 27 12: 1552157. 志, 日志空间不会增加, 但是必须在记检验点结束日志时等待 4 刘云生. 现代数据库技术[. 北京: 国防工业出版社, 2001.M