闪存数据库日志技术

闪存数据库日志技术2011-04-22大纲总结基于链表的日志技术——LB-Logging基于地址的日志技术——HV-Logging研究动机及相关工作闪存的基本结构及特性闪存的优越性及广泛应用能量消耗小小巧轻便读写速度快无机械延迟高抗震性非易失性闪存闪存的基本结构2KBytes64Bytes页寄存器•闪存芯片组成–1芯片=若干块–1块=64页•闪存特性–读写速度不一致–重写之前先擦除–没有机械延迟–有限擦除次数闪存特性在闪存中，重写之前必须先擦除7异地更新DiskFlash闪存中常采取异地更新的方式来避免频繁的擦除操作大纲总结基于链表的日志技术——LB-Logging基于地址的日志技术——HV-Logging研究动机及相关工作闪存的基本结构及特性数据文件传统数据库日志文件索引文件元数据文件磁盘闪存数据库面临的挑战闪存数据库闪存HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase研究动机A.v1（T1，start）（T1，B，v’）（T2，start）将Undo日志直接应用在闪存数据库中存在的问题Undo日志HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase（T1，start）（T1，B，v’）（T2，start）（T1，A，v1）Undo日志A.v1A.v2将Undo日志直接应用在闪存数据库中存在的问题研究动机HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase（T1，start）（T1，B，v’）（T2，start）（T1，A，v1）（T1，rollback）Undo日志A.v1A.v2A.v1研究动机将Undo日志直接应用在闪存数据库中存在的问题相关工作—IPLS.W.Lee,andB.Moon.DesignofFlash-BasedDBMS:AnIn-PageLoggingApproach.SIGMOD2007数据库缓冲区in-memorydatapage(8KB)in-memorylogsector(512B)闪存logarea(8KB):16sectorsEraseunit(Block):128KB15datapages(8KBeach)….….….…………相关工作—FlashLoggingShiminChen.FlashLogging:ExploitingFlashDevicesforSynchronousLoggingPerformance.SIGMOD'09.日志缓冲区RequestqueueWorkerWorkerWorker……LSN：LogSequenceNumber闪存数据库中日志设计思路•读速度比写速度快•考虑用较多的读操作来减少写操作•随机和连续访问速度相似•可以用随机读来代替连续读•闪存要求重写之前擦除•利用天然存在的历史版本的数据无机械延迟异地更新•闪存寿命有限，不可无限制的擦除•尽量减少写操作，间接减少擦除读写速度不一致擦除次数有限将日志文件由顺序结构转变成链表结构对数据的历史版本地址记日志大纲总结基于链表的日志技术——LB-Logging基于地址的日志技术——HV-Logging研究动机及相关工作闪存的基本结构及特性HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabaseHV-Logging的主要思想Transaction_IdElementAddressListT1BeginNULLT1XP(X’)T2AP(A’)T1DNULLT1BP(B’)T1BDeleteT2YP(Y’)T1XP(X’’)T1RollbackNULL………随着事务不断地对数据库进行操作，日志管理器按顺序不断加入新的日志记录；如果一个事务的提交日志写入日志文件中，则会对该事务的所有旧版本数据标识为垃圾数据，等待FTL层的回收；恢复时，恢复管理器从日志文件的尾部向头部扫描，并且逐一按照数据历史版本的地址进行恢复日志文件记录版本地址信息而取代值信息日志文件的存储日志文件本身并不适合于使用闪存存储大量的擦除操作降低了闪存的使用寿命日志量大闪存擦除次数有限事务回滚率低日志快速失效日志文件存在磁盘上以延长闪存寿命数据文件存在闪存上以利用闪存的高速读取特性从整体上提高数据库性能！日志文件的存储实验及结果分析TPCC上的模拟实验利用TPCC标准规定的操作验证，HV-Logging可以减少一定数量的写操作，从而间接减少擦除操作，延长闪存使用寿命BerkeleyDB上的真实实验将HV-Logging实现在BerkeleyDB中，与传统数据库的UndoLog进行恢复时间的比较，验证HV-Logging可以大大缩短恢复时间HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase实验结果-TPCC0200040006000800010000120000.10.20.30.40.50.60.70.80.91users(thousand)writeopsUndoLogHV-Recovery3000次HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase实验结果-TPCC02000040000600008000010000012000012345678910users(Thousand)writeopsUndoLogHV-Recovery33000次HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase实验结果-BDB010020030040050060012345678910UpdateOps(thousand)recoverytime/msHDD(Tranditional)HDD(HV-recovery)SSD(Tranditional)SSD(HV-recovery)2~3倍HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase实验结果-BDB0200040006000800010000120001400016000102030405060708090100UpdateOps(thousand)recoverytime/msHDD(Tranditional)HDD(HV-recovery)SSD(Tranditional)SSD(HV-recovery)8倍HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabase大纲总结基于链表的日志技术——LB-Logging基于地址的日志技术——HV-Logging研究动机及相关工作闪存的基本结构及特性HV-recovery：AHighEfficientRecoveryTechniqueforFlash-basedDatabaseLB-Logging的主要思想Transaction_IdElementPre_ElementAddressListT1XBeginP(X1)→P(X2)→P(X3)T1YXP(Y1)→P(Y2)T2ABeginP(A1)T1ZYP(Z1)→P(Z2)→NULLT1CommitZNULLT2BANULL→P(B1)T2RollbackBNULL………随着事务不断地对数据库进行操作，日志管理器将日志以链表的形式存放在内存中；如果一个事务提交，则该事务的日志将一次性的全部写出到闪存中恢复时，恢复管理器从日志文件的链表结构中，准确找到该事务的所有日志，并逐一进行重做（redo）将日志文件由顺序结构转变成链表结构Algorithm1：transferincheckpointsvoidtransfer(filelogFile){boolflag＝true;blocknewBlock＝newblock();logRecordcurrent;current＝getFirstLogRecord(logFile);while(flag){if(currentisstillvalid)CopycurrenttonewBlock;current＝getNextLogRecord(logFile);if(newBlockisfull)Getanotherfreeblock;if(current＝NULL)flag＝false;}Erasetheoldlogfile;}\\得到日志文件中第一条日志记录\\复制到已申请好的干净的空闲空间中\\得到下一条日志记录\\如果申请的新日志块已写满，就再申请一块\\日志记录扫描完毕，退出循环\\擦除旧的日志记录LB-Logging的检查点合并算法实验设计•实验平台：（SSD/HDD）+BerkeleyDB•对比试验：ARIES、HV-Logging、LB-Logging•测试指标：恢复时间•测试因子：单个事务更新次数单个数据更新次数实验结果-事务更新数（1）00.20.40.60.811.21.41.61.82ARIES(HDD)HV-Logging(HDD)LB-Logging(HDD)ARIES(SSD)HV-Logging(SSD)LB-Logging(SSD)RecoveryTime/msUpdateTransactionSize实验结果-事务更新数（2）012345678ARIES(HDD)HV-Logging(HDD)LB-Logging(HDD)ARIES(SSD)HV-Logging(SSD)LB-Logging(SSD)RecoveryTime/msUpdateTransactionSize实验结果-数据更新次数01234567812345678ARIES(HDD)HV-Logging(HDD)LB-Logging(HDD)ARIES(SSD)HV-Logging(SSD)LB-Logging(SSD)AverageUpdateTimesforEachDataRecoveryTime/ms大纲总结基于链表的日志技术——LB-Logging基于地址的日志技术——HV-Logging研究动机及相关工作闪存的基本结构及特性总结•我们分析了闪存数据库中日志设计的问题，提出了一些新的解决方案。•一种是对闪存中天然存在的数据的历史版本来进行管理和利用的日志及恢复方法HV-Logging，来改进undo日志的性能，提高恢复效率。•一种是使用链表结构取代原有的顺序结构进行日志记录的LB-Logging，来改进redo日志的性能，进一步的提高恢复效率。•通过和开源数据库OracleBerkeleyDB的比较，实验结果表明我们的设计都比原来的方法有更高的恢复效率，充分说明了其优越性。Thankyou!