《恢复系统.ppt》由会员分享，可在线阅读，更多相关《恢复系统.ppt（181页珍藏版）》请在三一文库上搜索。
1、第9章 恢复系统,本章内容参考: 数据库概念(第四版) by A. Silberschatz Chapter 17 Recovery System 补充内容 本章内容特色: 数据库恢复的“道理”较容易理解 但编程实现较难，算法较多 本章要解决的关键问题： 如何预防和应付各种”故障”,保证ACID性质,搐域项剂蔫受谰推诲椎返蘸傍换背浙迸腔洗膝子钝墒财捌矛纲刽弛因牛伎恢复系统恢复系统,主要内容,故障分类 存储器结构 恢复与原子性 基于日志的恢复 Shadow Paging 并发事务的恢复 缓冲管理 非易失性存储器丢失信息的故障 Advanced Recovery Techniques ARIES
2、Recovery Algorithm,轩牵退权怔冠本烧阴痕田檬夺钒谨柠吼锈遥酥掀泛沮殃谆踪吴屈廉窑菏廷恢复系统恢复系统,故障分类,事务故障: 逻辑错误: 因为某些内部错误条件导致事务不能完成 系统错误: 因为某种错误条件(如死锁)导致数据库系统终止一个活跃事务 系统崩溃: 停电故障或者其他软硬件故障导致系统崩溃 故障-停止假设: 假设非易失性存储器的内容不会因系统崩溃而破坏 数据库系统可通过许多完整性检查来防止磁盘数据被破坏 介质故障: 磁头损坏或类似的磁盘故障可能破坏全部或部分磁盘存储器 假设损坏是可以检测到的: 磁盘驱动器使用校验和来检测故障,良境涅田糕芽识吃哑筏阵刚癸广遁涣石薛恨唬钳捆液
3、嫉簿敷衡痴踌诌塔首恢复系统恢复系统,恢复算法,恢复算法是指即使发生故障也能确保数据库一致性和事务原子性及持久性的技术 恢复算法两个部分 在正常事务处理过程中采取动作来确保有足够的信息用于从故障恢复(即事前预防措施，保证有尽量多的信息在故障中保存下来) 在故障发生后采取行动作将数据库内容恢复到一个确保原子性, 一致性和持久性的状态(即事后的恢复措施，保证原子性，一致性，耐久性),牢氏浚徊窗灵庐它模蜀寥雏不炙疼截蔑誓阮眩啊惟咕躇袋颠巾谍裤莲拆孟恢复系统恢复系统,存储器结构,易失性(Volatile)存储器 不能在系统崩溃后保存下来 例如: 主存, 高速缓存 非易失性(Nonvolatile)存储器
4、 可以在系统崩溃后保存下来 例如: 磁盘, 磁带, 闪存, 非易失性RAM (电池供电) 稳定(Stable)存储器 虚构的能够经受任何故障的存储器 可用多个非易失性介质存储相同的副本来近似,疡慧镁锯杠阉省嚏罚藉逻亨踢遵裤职暮浩疤码人骡轴脚纵裕蔫卑芹灶教枷恢复系统恢复系统,稳定存储器的实现,在不同磁盘上维持多个副本 副本可以在远程站点上, 以防止象火灾或洪水之类的灾难 在数据传输过程中的故障仍然可导致不一致的副本，块传输的结果可能是 成功完成 部分失败: 目标块有错误信息 完全失败: 目标块根本没有更新 在数据传输过程中防止存储介质出故障的解决方法 输出操作如下执行 (假设每个块有两个副本):
5、 将信息写到第一个物理块 当第一个写操作成功完成, 再将相同信息写到第二个物理块 仅当第二个写操作成功完成之后输出才算完成,枢张途湾窃储刚蹋截凿嚣淑躬掀袍炉饵奔旺枢粘聋盛证贼溺咆体安递目氟恢复系统恢复系统,稳定存储器的实现,在数据传输过程中防止存储介质出故障 (续): 块的副本间可能因输出操作过程中的故障而有不同,为了从故障恢复: 首先找到不一致的块 高代价的解决方法: 比较每个磁盘块的两个副本 更好的解决方法 将正在进行的磁盘写操作记录在非易失性存储器上(非易失性RAM或者磁盘的特定区域) 恢复时利用此信息找到可能不一致的块, 只需比较这些块的副本 用于硬件RAID系统 如果不一致块的一个副
6、本上检测到错误(错误的校验和), 则用另一副本覆盖它即可 如果两个副本都没有错误但却不一致, 则用第二个块覆盖第一个块,雏叶那荒辗呜免车佃棉点戎航赫孝钝跋裔舵男痊薪蝎箍橱蔫蜒信炯值典器恢复系统恢复系统,数据存取,物理块是位于磁盘上的块 缓冲块是临时位于主存中的块 磁盘和主存之间的块移动通过下列两个操作来引发: input(B) :将物理块 B 传入主存 output(B): 将缓冲块 B 传到磁盘, 并且替换相应的物理块 每个事务Ti 都有自己的私有工作区, 用来保存它存取和更新的所有数据项的局部副本 Ti 对应于数据项 X 的局部副本记为xi 为简单起见, 假设每个数据项都能存入并且确实存储
7、在单个块中,朝渠亚财裹薄蛹桶躇卖钠舷饰津辖觉启高哦尼要尿骂莽烹党贯泪鲸剂渤腮恢复系统恢复系统,数据存取,事务使用下列操作来在系统缓冲块和它的私有工作区之间传送数据项: read(X) 将数据项X 的值赋给局部变量xi. write(X) 将局部变量 xi 的值赋给缓冲块中的数据项 X 这两条命令在赋值前都可能要求发出 input(BX) 指令, 如果X 所在的块 BX 当前不在主存中的话,券痢波绅岭鼻遇榜赘烬侗鼠掠凰辕冗米壕肯咨督嗡省刑餐眷臆仙恼庞媳栈恢复系统恢复系统,数据存取,事务 第一次访问 X 时执行read(X) 以后的访问是对局部副本进行的 最后一次访问之后, 执行write(X)
8、output(BX) 不必紧随write(X)立即执行 系统可在它认为适当的时候执行output 操作,访占抒孪候疡莱固田朗响酗项许炙数疚杭惭辛最毗续敖涧喧蜗媚譬蔑愚彭恢复系统恢复系统,数据存取例,x,Y,A,B,x1,y1,缓冲区,缓冲块 A,缓冲块 B,input(A),output(B),read(X),write(Y),磁盘,T1的工作区,T2的工作区,内存,x2,凤螟狰看宝柳喉彬醒敏射蛤尊妄胞铝戒宵哩酒授凿苍寸槽蹦遁锻邵栅盖阀恢复系统恢复系统,恢复与原子性,问题 一个较长事务进行若干查插删改操作 设计时假定整个事务作为原子是保持一致性 但执行可能半途而废（意外原因，停电等） 如何恢复
9、？,签日唉铃胆袱邢兴淆云炸夺趴巾道饭琉袋照威方躬镰虱邢憾藐笛憎扳腾琼恢复系统恢复系统,恢复与原子性,为了在故障的情况下仍确保原子性, 应首先输出描述修改操作的信息到稳定存储中(先记账)，描述将作的操作，然后动作(恢复有据） 下面介绍两种方法: 基于日志的恢复 影子分页shadow-paging 先假设事务是串行执行的,愈塞撅枚棍杠穴蛊实综滁屋藤玻扭蛔倘肝陪锡祝自菩曙授毙萨亡符洪咸舜恢复系统恢复系统,基于日志的恢复,日志(log)保存在稳定存储器上 日志是日志记录的序列, 用来记录对数据库的更新活动 当事务Ti 启动, 写入一条登记自己的日志记录 Ti 执行write(X)之前, 写入日志记录
10、, 各分量依次是:事务,变量,前值,后值 当Ti 完成了最后一条语句, 写入日志记录,邵陨议愈垄师妆泊盏绝族蛛司恢笼敢疥怔欠遵酮辟亨轧鹰阎寸蛤尸驮镁猛恢复系统恢复系统,基于日志的恢复,目前假设日志记录直接写入稳定存储器(即不经过缓冲) 两种使用日志的方法 延迟更新数据库(先记账，后补工，保守，稳妥) 立即更新数据库(边记，边做，积极，冒险),协痰含肉顾铬吐蘑兰似弟镭僻惶檬寥侵檄肘丸廉睫凭到儒挡嫂奖汰刹询鸽恢复系统恢复系统,延迟更新数据库,延迟更新数据库方案在日志中记录所有更新, 但推迟write 直至部分提交之后 假设事务串行执行 事务启动时向日志写入 记录 write(X) 操作导致写入日志
11、记录, 其中V 是X的新值 注: 这种方案不需要保留旧值 这时并未执行对X 的写操作, 而是延迟了 当Ti 部分提交时, 向日志写入 最后, 读取日志记录并用来实际执行前面延迟的写操作(把被延迟的写动作（欠工账） 补作完成) 生活中，一个“拖”字或“研究研究”就是这种延迟策略,遍化颇测砌住艰备拯诣桓闲观李舱院赵砷褒投耸射淳寅称候际藐诅扎址漱恢复系统恢复系统,延迟更新数据库,故障后恢复过程中,，事务需要重做(redo)，当且仅当日志中存在和(这样恢复有据) 重做事务Ti ( redoTi) 将事务更新过的所有数据项的值置为新值(即有底子，有工账，在底子上，重来一次) 但正在恢复时出错有怎么办?
12、例如事务T0 和T1 (T0 在T1 之前执行): T0: read (A) T1 : read (C) A := A - 50 C:= C- 100 Write (A) write (C) read (B) B:= B + 50 write (B),奏宠倒郭观绸权盔吞剔鸡窒别系畴菏宪糖宫酗督舍据饿傈赶宁所妥碳垄宜恢复系统恢复系统,延迟更新数据库,下面给出了日志在三个时刻的情形 如果故障发生时稳定存储器上的日志处于情形: (a) 不需重做(因为工账并未实施) (b) 必须执行redo(T0), 因为存在 (c) 必须先执行redo(T0) 再执行redo(T1), 因为存在 和,捷昌军僳审谩粱
13、登唆蝎顷针贞兽烙警帘戒遣粕蛔臆尼耐两茸疯抑毯敝激斧恢复系统恢复系统,立即更新数据库,立即更新数据库方案允许一个未提交事务在发出写操作时更新数据库 由于可能需要取消操作, 日志记录必须包含旧值和新值 对更新的日志记录必须在数据库数据修改之前写入稳定存储器 假设日志记录直接输出到稳定存储器 可以扩展成推迟日志记录的输出, 只要满足: 在执行数据块B的output(B) 操作之前, 所有对应于B 的日志记录都已写入稳定存储器 被更新块的输出可能发生在事务提交之前或之后的任何时刻 块输出的次序可以与修改块的次序不同,睦聘杖严脚选约还撼斧躁轴奸准谍锤剧床岛牛毛喉振扇祖棘蝎峰倔瞻姥韭恢复系统恢复系统,立即
14、更新数据库,恢复过程需要两种操作: undo(Ti) 复原所有被Ti 更新了的数据项的旧值, 从Ti 的最后一条日志记录向前进行（后退） redo(Ti) 将所有被Ti 更新了的数据项的值置为新值, 从Ti 的第一条日志记录向后进行（朝前） 两种操作都必须是幂等的 亦即, 即使该操作被执行多次, 效果与只执行一次是一样的 由于在恢复过程中可能重复执行这两个操作, 所以需要此性质,鹤杀珐叠什伸女嗡醋济省粮婆懈铰塞熙怕竿辊删萝媚范赐拆庚撕蹬入惑式恢复系统恢复系统,立即更新数据库,故障后恢复 如果日志中包含但不包含, 则事务Ti 需要取消(undo)(即日志中有头无尾时要复旧（急性子将有的麻烦）)
15、如果日志中包含和, 则事务Ti 需要重做(redo)(即日志中有头有尾时，需要重作) 取消(undo)操作先做, 重做(redo)操作后做,沁避瞧馆饺堂澎尾纷雕艰伍富革沂乳十表街慑骨年壕塘热肉坞钻院揽菲熙恢复系统恢复系统,立即更新数据库的例子,销糖嘻眼智弱狐啮岂甘仰榜荡鸳毒硼少捉染寝驱土藩气涡卫房掺振河查螺恢复系统恢复系统,检查点,前述恢复过程的问题 搜索整个日志很费时 可能不必要地重做事务(已经将更新输出到数据库的事务) 通过周期性地执行检查点来精简恢复过程 将当前驻留在主存中的所有日志记录输出到稳定存储器 将所有更新过的缓冲块输出到磁盘 将一条日志记录写入稳定存储器,议恨妆几赫荫多衰牲嫁拼
16、示弄跨播褥莫们痒兆感曹鲁坦反渊马尺殆呆显返恢复系统恢复系统,检查点,恢复时仅需考虑在检查点之前启动的最近的事务Ti, 以及在Ti 之后启动的事务 从日志末尾反向扫描, 找到最近的记录 继续反向扫描直到找到一个记录 仅需考虑日志中在上面这个启动记录之后的部分，之前的部分在恢复时可以忽略, 如果愿意可以随时删除 对所有没有的事务(Ti 或更晚), 执行undo(Ti ) (仅当立即更新数据库时才如此) 正向扫描日志，对所有有的事务(Ti 或更晚), 执行 redo(Ti),咋溅泛镐卞楼耽伊楷起狄姐绊霍啸陷拣似肄蝉妆卞茎莫宠泥桌踩誊蹦捉札恢复系统恢复系统,检查点的例子,T1 可以忽略 (由于检查点,
17、 其更新已经输出到磁盘) T2 和 T3 重做 T4 取消,Tc,Tf,T1,T2,T3,T4,检查点,系统故障,朱图剿娩侧邀泌近徊笑弄墅瞎硕柔脏沪险级诬浑冉莫摘花稠酿琉甸抹胃疵恢复系统恢复系统,影子页面（Shadow Paging）,Idea 保持真身和影子，影子在非易逝内存 事务前留影，事务中影子不被修改 事务成功，则影子与时俱进 事务失败，则恢复到影子 技巧 影子不是数据页面的副本，只要页面指针表的副本,伟巳殃师腊乡妹锣钾沼仟妒萨劣提遥斯爬裂盒溃柯测鹃硷尾甲无胺絮粳藉恢复系统恢复系统,Sample Page Table,肩驳鞋轨忌粗天绝七隔蔗酞敏疾棠都诉簿券粘蛆因鲁沾殷结运馅秉跳笑厨恢复
18、系统恢复系统,Example of Shadow Paging,Shadow and current page tables after write to page 4,豁谣桅记蹋件旭山宅硷蓖扛由惠立垦淫禽减马器煮惦斜饺纵凸屿鳞毒芜邹恢复系统恢复系统,Shadow Paging,To commit a transaction :事务提交时 1. Flush 变动的值块到磁盘 2. Output current page table to disk 当前表写盘 3. Make the current page table the new shadow page table, as follows
19、: keep a pointer to the shadow page table at a fixed (known) location on disk to make the current page table the new shadow page table, simply update the pointer to point to current page table on disk,申刁湖抓市涵醚川色肌便呜碴糕铜滨栈姑树粤六胺足荐末诉军束霸盐匣家恢复系统恢复系统,Shadow Paging,Once pointer to shadow page table has been w
20、ritten, transaction is committed No recovery is needed after a crash new transactions can start right away, using the shadow page table 出错后复旧 pCurrPag= pShadow Pages not pointed to from current/shadow page table should be freed (garbage collected)释放不用的指针,旅返绘冷符篇艘冉戮盾旅披染精成瓢任诬譬申庶缕勒刮找疤瘁唱蟹屈烤辱恢复系统恢复系统,Show
21、 Paging(11/4),Advantages优点 no overhead of writing log records(快) recovery is trivial(易恢复),科么吸湍伺治迎纽豺吨联缠类芯棉苛戒阿常望宪箱藤羔擞友顶交秸熄渡婴恢复系统恢复系统,Show Paging,Disadvantages :缺点 Copying the entire page table is very expensive复制原指针表费时 Can be reduced by using a page table structured like a B+-tree No need to copy enti
22、re tree, only need to copy paths in the tree that lead to updated leaf nodes 可用B树解决，只复制路径 Commit overhead is high even with above extension 提交花销大 Need to flush every updated page, and page table Data gets fragmented related pages get separated on disk磁盘上数据不连续 After every transaction completion, the
23、database pages containing old versions of modified data need to be garbage collected 需要回收内存空间 Hard to extend algorithm to allow transactions to run concurrently 并发程序难写,鬃当从驻党想嚼疙卢生误方垮室馆狭午酮拢漂岂菌河帧烬去绪韩里吓宜邢恢复系统恢复系统,并发事务的恢复,对基于日志的恢复方案扩展，以允许多个事务并发执行 简化模型的3 个假定： 所有事务共享单个磁盘缓冲区和单个日志 缓冲块可以具有被一个或多个事务更新的数据项 假设使用严
24、格两阶段锁的并发控制，即未提交事务所做的更新对其他事务是不可见的 否则如果T1 更新A, 然后T2 又更新A 并提交, 最后T1 必须夭折时, 该怎样执行undo ? 日志登记与前面描述的相同 不同事务的日志记录在日志中可能交错分布 检查点技术及恢复时的操作必须改变 并发，多检查点导致复杂,朗弊泉绞仆旷母别相陡辨棚论僳贡华斌祈拿糠砂睦琶缺嚣炔徽罗猿逮冷改恢复系统恢复系统,并发事务的恢复,检查点的执行基本同前, 除了检查点日志记录现在形如 其中 L 是检查点时活跃事务列表 假设当执行检查点时没有正在进行的更新操作 (以后对此可放宽) 当系统从崩溃恢复时, 首先做下列动作: 初始化 undo-li
25、st 和redo-list 为空 从末尾开始反向扫描日志, 直至发现第一条 记录时停止. 对在反向扫描过程中发现的每条记录: 如果是, 将Ti 加入redo-list 如果是, 并且Ti 不在 redo-list 中, 则将Ti 加入undo-list 对L 中的每个Ti, 如果Ti 不在redo-list 中, 则将Ti 加入undo-list,都臆硕角圾闰勾吉把鸭偏形栗越浩绪脂斗狞弥谴月重棱英遵遇效履鸽讥刁恢复系统恢复系统,并发事务的恢复,至此undo-list 包含必须取消操作的未完成事务, 而redo-list 包含必须重做的已完成事务 现在恢复可以如下继续: 从最近的记录开始反向扫描
26、日志, 对undo-list 中的每个Ti 当遇到 记录时停止 扫描过程中, 对属于undo-list 中事务的每条日志记录执行undo 定位于最近的 记录 从记录开始正向扫描日志, 直至日志末尾 扫描过程中, 对属于redo-list 中事务的每条日志记录执行redo,瘁袁抱扦惫搪竿彭玫栏丽唉缉萎吾涸玻构思深砾榆柑隐亚吉甚鲁署喧妓涣恢复系统恢复系统,恢复例,对下列日志按照恢复算法的步骤走一遍:,隘槐构闯曝形迸绎归涣警园匹丘箩狞室丧丰巫滑纽颤痘坐桃儿纂含炔屎腆恢复系统恢复系统,日志记录缓冲,模型约定 日志记录缓冲: 在主存中缓冲日志记录, 而不是直接输出到稳定存储器 当缓冲区中的日志记录块满时
27、, 或者当执行日志强制(log force)操作时,将日志记录输出到稳定存储器 日志强制用来提交事务, 方法是将它的日志记录(包括提交记录)强行输出到稳定存储器 由于一次输出操作可以输出多条日志记录, 从而减少I/O 代价,拆研晚试般哺绅迟泳蚁铸秀烹夕池寓枯状缔疟及攀渝盖薄悸蓝渊爆助摆氯恢复系统恢复系统,日志记录缓冲,日志缓存的规则 日志记录按其创建次序输出到稳定存储器 仅当日志记录已经输出到稳定存储器, 事务Ti 才进入提交状态 在主存中的数据块输出到数据库之前, 所有属于该块中数据的日志记录必须已经输出到稳定存储器 这条规则称为先写日志(write-ahead logging)或WAL规则
28、 严格地说，WAL只需要输出undo信息,啸引因露厢缝履蓄桥哀徽劝亡发俗躲双绅业虐僻卿鲍绒籍据乔蹈玲胡耸懦恢复系统恢复系统,数据库缓冲,数据库维护一个数据块在内存中的缓冲区 当需要新块时, 如果缓冲区已满, 则需要将一个现有块移出缓冲区 如果所选的移出块被更新过(“脏块”), 则必须将它输出到磁盘 由于先写日志规则, 如果要将一个带有未提交更新的块输出到磁盘, 必须先将记有那些更新的取消(undo)信息的日志记录输出到稳定存储器上的日志中,磐戳忘置羊牡罪篡挥淘感醇啄辣重毛排纷坠绽服箱喻赫栖十威祝绢纠崎栏恢复系统恢复系统,数据库缓冲,当一个块输出到磁盘时, 其上不能有正在进行的更新，可以用下列方
29、法确保这一点 写数据项之前, 事务在包含数据项的块上获得排它锁 一旦完成写, 锁即可释放 这种持有时间很短的锁称为latch (插销) 在一个块输出到磁盘之前, 系统在该块上获得排他插销 确保该块上没有更新正在进行,科素嗽散饶镜唐咖碉壤绽坑腊副再吻窃较灌遥拜怕设见良告锭讥隘芬妓础恢复系统恢复系统,数据库缓冲,数据库缓冲区的实现可以是 在实际主存中为数据库保留的一个区域 在操作系统虚拟内存中 在保留的主存中实现缓冲区有下列缺点: 预先划分内存给数据库缓冲区, 限制了灵活性 需求可能改变, 尽管操作系统最清楚在什么时刻应该如何分配内存, 它却不能改变内存分配,鳃劝馋阉肿交悉暂压哇浚挂辜莽美淘庞袜弹
30、匝络巫亭狐河甩涛蓉酞臻凌周恢复系统恢复系统,数据库缓冲,数据库缓冲区可以在操作系统的虚拟内存中实现, 尽管有下列缺点: 当操作系统需要移出一个被更新过的页以便为另一页腾出空间时, 该页被写到磁盘上的交换区(swap space) 当数据库决定将缓冲页写到磁盘时, 缓冲页可能在交换区中, 于是可能必须从磁盘上的交换区读入该页再输出到磁盘上的数据库中, 导致一次多余的I/O! 称为dual paging 问题 当换出数据库缓冲页时, 理想的情况是操作系统将控制交给数据库, 由数据库输出该页到数据库中而不是交换区中 (首先确保输出日志记录) 因此Dual paging 被避免, 但通常的操作系统不支
31、持此功能 缺点：间接管理，有extra I/O!,雨凸坏拟径遁恨喜毙喧瘦薛援证腑翅袭铁弧摔炳掏键渐兼枉铡址蔗疆禾露恢复系统恢复系统,非易失性存储器丢失信息的故障,到目前为止我们都假定非易失性存储器不会丢失信息 使用类似检查点的技术来处理非易失性存储器的丢失信息 周期性地转储(dump)数据库的全部内容到稳定存储器 转储过程中不能有活跃事务：必须有一个类似于检查点的过程 输出当前在主存中的所有日志记录到稳定存储器 输出所有缓冲块到磁盘 复制数据库内容到稳定存储器 输出记录到稳定存储器的日志中 从磁盘故障恢复时 从最近的转储恢复数据库 查看日志并重做所有在转储后提交的事务 可以扩展以允许转储过程中
32、有活跃事务:称为模糊转储(fuzzy dump)或联机转储(online dump),滴勋诛樱嘘赃彰旺绪屯勘挽短摆视现耐斤档惩雁嘲辰贾张嚼威邀庭障屑净恢复系统恢复系统,Advanced Recovery Algorithm,卓堤滨胸压舍匙舔妒屎杆蜒赡敞贺烧巾舵讹钮奇奶井影建脚嫂吃密艳墟级恢复系统恢复系统,Advanced Recovery Techniques,Support high-concurrency locking techniques, such as those used for B+-tree concurrency control支持并行B-树 Operations like
33、 B+-tree insertions and deletions release locks early They cannot be undone by restoring old values (physical undo), since once a lock is released, other transactions may have updated the B+-tree. 简单的物理恢复不能复旧，因为其他事务可能干扰 Instead, insertions (resp. deletions) are undone by executing a deletion (resp.
34、insertion) operation (known as logical undo) 因此，采用逻辑复旧,颧焦傈叹于烫漳滴鸣尾汗崭哇挂磅诡篮医雄吐浚芒扣乾昧厄赚桌氮烹捅件恢复系统恢复系统,Advanced Recovery Techniques,For such operations, undo log records should contain the undo operation to be executed called logical undo logging(逻辑撤消日志) in contrast to physical undo logging(物理撤消日志),倔编硼蓑菲卸西
35、耀艾策湍鸭幌垛锄却滔尚区擒驶素肩谴谷馅摧湖辨浚漱戏恢复系统恢复系统,Advanced Recovery Techniques,Redo information is logged physically (that is, new value for each write) even for such operations Logical redo is very complicated， since database state on disk may not be “operation consistent” 由于磁盘上的数据库状态可能不是”操作一致的”，故逻辑重做比物理重做复杂的多,腺幕宦
36、末徘八斯籽喳逻发肠馆吗浦诌氖秀菇蒸葬炽伸缄晤淬奴查乃陛余披恢复系统恢复系统,Advanced Recovery Techniques,Operation logging is done as follows: When operation starts, log ，Here Oj is a unique identifier of the operation instance While operation is executing, normal log records with physical redo and physical undo information are logged W
37、hen operation completes, is logged, where U contains information needed to perform a logical undo U中包含完成逻辑撤消所需要的信息,亮展梁稼敝蜗彰寥结冲鹿灯郡烽夯岸但夯谣轿南他街询臂汲琼牟冈忧吃炬恢复系统恢复系统,Advanced Recovery Techniques,If crash/rollback occurs after the operation completes: the operation-end log record is found, and in this case log
38、ical undo is performed using undo information U physical undo information for the operation is ignored(忽略) Redo of operation (after crash) still uses physical redo information,朴绢串萍举耕前岔袱哇阻煽权部而利跌理涪濒并引仍圈忙弗墟舞婴福撤等恢复系统恢复系统,Advanced Recovery Techniques,Rollback of transaction Ti is done as follows: Scan th
39、e log backwards If a log record is found, perform the undo and log a special redo-only log record . If a record is found Rollback the operation logically using the undo information U Updates performed during rollback are logged just like during normal operation execution At the end of the operation
40、rollback, instead of logging an operation-end record, generate a record Skip all preceding log records for Ti until the record is found,饭艳畏瘸醉汽洲苔谩血吐杜盾员息蓄由狭铁桓隆铲缝蟹及脓溃损乘矛饺傈恢复系统恢复系统,Advanced Recovery Techniques,If a redo-only record is found ignore it If a record is found: skip all preceding log records
41、for Ti until the record is found Stop the scan when the record is found Add a record to the log,卞骋夷揭套射坏该朽臆骆莉往构掳预醛铀碳绝孝绢奎朋公嫁崎慕嫉哮旦苍恢复系统恢复系统,Advanced Recovery Techniques,Some points to note: Cases 3 and 4 above can occur only if the database crashes while a transaction is being rolled back 当事务回滚期间发生系统崩溃
42、导致Cases 3 and 4 出现 Skipping of log records as in case 4 is important to prevent multiple rollback of the same operation 避免同一个操作被多次撤消,授创艰室鉴兴抠描棵傲夜妙琴敌蒙绣猪堕伊仆麻桔芝糟踏盆蹭饲导蠕犬斌恢复系统恢复系统,Advanced Recovery Techniques,The following actions are taken when recovering from system crash Scan log forward from last reco
43、rd Repeat history by physically redoing all updates of all transactions Create an undo-list during the scan as follows undo-list is set to L initially Whenever is found Ti is added to undo-list Whenever or is found, Ti is deleted from undo-list This brings database to state as of crash, with committ
44、ed as well as uncommitted transactions having been redone Now undo-list contains transactions that are incomplete, that is, have neither committed nor been fully rolled back,旦淖龄豫性萤择矣松咸婴识电烧甜芽吞皿评骸迪盅沿没俩背局砖篮菱沉禁恢复系统恢复系统,Advanced Recovery Techniques,Scan log backwards, performing undo on log records of tr
45、ansactions found in undo-list Transactions are rolled back as described earlier When is found for a transaction Ti in undo-list, write a log record Stop scan when records have been found for all Ti in undo-list This undoes the effects of incomplete transactions (those with neither commit nor abort l
46、og records) Recovery is now complete,讨咎峻桌蛾狡帛吭郝弟修直缕禄又蚤丁泻梗允瘁弊纲昂阴铃羔顶缺做陪仑恢复系统恢复系统,Advanced Recovery Techniques,Checkpointing is done as follows: Output all log records in memory to stable storage Output all modified buffer blocks to stable storage Output a record to log on stable storage Transactions ar
47、e not allowed to perform any actions while checkpointing is in progress Fuzzy checkpointing allows transactions to progress while the most time consuming parts of checkpointing are in progress Performed as described on next slide,抑恭浆挤玲努赡烛坎俐挡仆诣师柄云股剔菌早浅挥叮蓝弓锹惶锣拌肛鹿赶恢复系统恢复系统,Advanced Recovery Techniques,
48、Fuzzy checkpointing is done as follows: Temporarily stop all updates by transactions Write a log record and force log to stable storage Note list M of modified buffer blocks Now permit transactions to proceed with their actions Output all modified buffer blocks in list M to disk blocks should not be
49、 updated while being output Follow WAL: all log records pertaining to a block must be output before the block is output Store a pointer to the checkpoint record in a fixed position last_checkpoint on disk,袭硬始蒙恨砾英碱缴氧驹宠驻哨屠豢诅廷刀区莎齿惭晓疗海辆捶杯岗婶眺恢复系统恢复系统,Advanced Recovery Techniques,When recovering using a fuzzy checkpoint, start scan from the checkpoint record pointed to by last_checkpoint Log records before last_checkpoint have their updates reflected in database on disk, and need not be redone Incomplete checkpoints, where system had cr