（计算机应用技术专业论文）闪存数据库若干关键问题研究.pdf

摘要 摘要 闪存诞生于2 0 世纪8 0 年代末，是一种新型的固态存储介质，具有高 速、非易失、低功耗、高抗震、小巧轻便等特性。闪存的优良特性使得它 成为突破磁盘局限性的首选存储介质。近几年来，闪存已经被广泛应用于 各种嵌入式系统和便携式设备；同时，随着闪存容量的快速增长和价格的 不断下降，闪存已经成为一种新的重要的二级存储设备，并开始应用于企 业级计算环境中。 日益多样和复杂的应用对闪存上的数据管理提出了许多新的挑战，采 用数据库技术来管理闪存中的数据，即建立闪存数据库，成为应对闪存数 据管理方面挑战的首选途径。由于闪存具有许多与磁盘显著不同的特性， 将传统的基于磁盘的数据库技术直接移植到闪存上并不能较好地发挥闪 存的性能优势。因此，从闪存的物理特性入手，针对数据库的数据存取特 点，研究闪存数据库领域的相关问题，具有重要的理论意义和应用价值。 本论文总结了闪存数据库领域已有的研究成果，并在存储管理、索引 和事务恢复等方面展开了研究。 论文首先介绍了闪存的物理特性及其广泛应用，接着分别介绍了闪存 的两种主要类型：n o r 闪存和n a n d 闪存，并分析了两者物理特性的异 同和应用方式的差别。 索引是提高数据库性能的关键技术之一。针对已有的索引方法中系统 故障后结点转换表重建代价大的问题，论文结合n o r 闪存和n a n d 闪存 的物理特性，提出基于复合闪存存储结构的可靠b + 树索引实现方法，结 合快照和日志两种机制，实现了系统故障后索引结点转换表的快速重建。 存储管理是闪存数据库研究的基础。论文针对数据库的数据存取特 点，提出了基于分离日志的存储管理方法，提高了数据更新性能。同时， 将该方法和换位更新方法相结合，进一步提出了自适应的存储管理方法， 在提高更新性能的同时较好地兼顾了读取性能，能够适应变化的负载。 事务恢复是闪存数据库的重要组成部分。论文针对已有的闪存事务恢 复方法在运行开销和提交代价等方面的不足，提出了基于分离日志的事务 恢复方法，在减少事务提交代价的同时提供了较好的恢复性能。 摘要 本论文主要在以下几个关键问题上做出了新贡献： ( 1 ) 在复合闪存存储结构的基础上，提出了一种可靠的b + 树索引实 现方法，结合快照和日志两种机制，实现了系统故障后索引结点转换表等 关键数据结构的快速重建。 ( 2 ) 提出了自适应的闪存存储管理方法，结合了基于日志的更新方 法和换位更新方法的优点，在提高数据更新性能的同时较好地兼顾了读取 性能，能够适应变化的负载。 ( 3 ) 提出了基于分离日志的事务恢复方法，减少了事务提交代价， 并提供了较好的故障恢复性能。 关键词：闪存；闪存数据库；存储管理；索引；事务恢复 i i a b s t r a c t a b s t r a c t f l a s hm e m o r yi san o v e ls o l i d - s t a t es t o r a g em e d i u ma n df i r s ta p p e a r e di n 19 8 0 s f l a s hm e m o r yh a sm a n ya d v a n t a g e so v e rt r a d i t i o n a lm a g n e t i cd i s k s u c ha sh i g h s p e e d ，n o n - v o l a t i l i t y ，l o wp o w e rc o n s u n l p t i o n ，s h o c kr e s i s t e n c e ， a n dp o r t a b i l i t y ，s oi ti sap r e f e r r e d s t o r a g em e d i u mt o o v e r c o m et h e l i m i t a t i o n so fm a g n e t i cd i s k i nr e c e n ty e a r s ，f l a s hm e m o r yi sw i d e l yu s e di n v a r i o u se m b e d d e ds y s t e m sa n dp o r t a b l ed e v i c e s w i t ht h er a p i di n c r e a s eo f c a p a c i t ya n dd e c r e a s eo fp r i c e ， f l a s hm e m o r yb e c o m ean e wi m p o r t a n t s e c o n d a r ys t o r a g ed e v i c e ， a n dh a sb e e na p p l i e di ne n t e r p r i s e c o m p u t i n g e n v i r o n m e n t n e wc h a l l e n g e sa r ep o s e db yt h ei n c r e a s i n g l yv a r i o u sa n dc o m p l e x a p p l i c a t i o n st ot h ed a t am a n a g e m e n to nn a s hm e m o r y m a n a g i n gd a t aw i t h d a t a b a s et e c h n i q u e ，i e ，e s t a b l i s h i n gn a s h - b a s e dd b m s ，i sap r e f e r r e d a p p r o a c ht om e e tt h ec h a l l e n g e so ff l a s hd a t am a n a g e m e n t d u et ot h ed i s t i n c t c h a r a c t e r i s t i c so ff l a s hm e m o r y ，d i r e c t l yt r a n s p l a n t i n gt r a d i t i o n a lm a g n e t i c d i s kb a s e dd a t a b a s et e c h n i q u et of l a s hm e m o r yc o u l dn o t f u l l yp l a yt h e p e r f o r m a n c ea d v a n t a g e s o fn a s hm e m o r y t h e r e f o r e ，s t a r t i n g w i t ht h e c h a r a c t e r i s t i c so fn a s hm e m o r y ，r e s e a r c h i n go nt h ep r o b l e m si nf l a s h - b a s e d d b m sa c c o r d i n gt ot h ed a t aa c c e s s p a t t e r n so fd a t a b a s e ， h a si m p o r t a n t t h e o r e t i cs i g n i 6 c a n c ea n dv a l u e t h i sd i s s e r t a t i o ns u m m a r i z e dt h ee x i s t i n gr e s e a r c h e so nn a s h b a s e d d b m sa n dm a d ed e e p l ys t u d yo ns e v e r a lk e yp r o b l e m s ，i n c l u d i n gs t o r a g e m a n a g e m e n t ，i n d e xa n dt r a n s a c t i o n a lr e c o v e r y f i r s t l y ，t h ed i s s e r t a t i o ni n t r o d u c e dt h ec h a r a c t e r i s t i c sa n da p p l i c a t i o n so f n a s hm e m o r y t h e r ea r em a i n l yt w ot y p e so ff l a s hm e m o r y ，n o rf l a s ha n d n a n dn a s h t h ec h a r a c t e r i s t i c so fn o rf l a s ha n dn a n dn a s hw e r ea l s o i n t r o d u c e d ， r e s p e c t i v e l y m o r e o v e r ， ac o m p a “s o nw a sm a d eb e t w e e nt h e c h a r a c t e r i s t i c sa n da p p l i c a t i o na r e a so fn o rf l a s ha n dn a n df l a s h s e c o n d l y ，i n d e xi so n eo ft h ek e yt e c h n i q u e st oi m p r o v et h ep e r f o r m a n c e i i i a b s 仃a c t 一一 o fd a t a b a s e h o w e v e r ，i nt h ee x i s t i n gm e t h o d s ，i ti sv e r yc o s t l yt or e c o n s t r u c t t h ei n d e xn o d et r a n s l a t i o nt a b l ea f t e rs y s t e m f a i l u r e a c c o r d i n gt o t h e c h a r a c t e r i s t i c so fn o r a n dn a n df l a s hm e m o r y ，t h ed i s s e r t a t i o np r o p o s e da r e l i a b l eb + t r e ei m p l e m e n t a t i o no v e rc o m p o u n df l a s hs t o r a g ea r c h i t e c t u r e ， u s i n gb o t hs n a p s h o ta n dl o g g i n ga p p r o a c h e st o r e c o n s t r u c tt h el n d e xn o d e t r a n s l a t i o nt a b l ee f n c i e n t l ya f t e rs y s t e mf a i l u r e t h i r d l y ，s t o r a g em a n a g e m e n ti st h eb a s i so fn a s h b a s e dd b m s i nt h i s d e s s e r t a t i o n ， a n o u t p a g e1 0 9 9 i n ga p p r o a c h w a sp r o p o s e dt o r s t o r a g e m a n a g e m e n ta n dc o u l di m p r o v ed a t au p d a t ep e r f o r m a n c e s i g n i f i c a n t l y f u r t h e r m o r e ，b yc o m b i n i n gt h et w oa p p r o a c h e sf o rf l a s hd a t au p d a t e ，o u t 。p a g e l o g g i n ga p p r o a c h a n do u t - p l a c e u p d a t ea p p r o a c h ， a n a d a p t l v es t o r a g e m a n a g e m e n tw a sf - u r t h e rp r o p o s e d t h i sm e t h o dc o u l dg i v ec o n s i d e r a t i o nt o b o t hd a t au p d a t ep e r f o r m a n c ea n dd a t ar e a dp e r f b r m a n c e ，a d a p t i n gt ov a r y l n g w o r k l o a d s f i n a l l y ，t r a n s a c t i o n a lr e c o v e r yi sa ni m p o r t a n tc o m p o n e n to fn a s h - b a s e d d b m s i nt h i sd e s s e r t a t i o n ，a c c o r d i n gt ot h ed i s a d v a n t a g e so fe x i s t i n gf l a s h t r a n s a c t i o n a lr e c o v e r ym e t h o d s ， s u c ha sh i g hs y s t e mo v e r h e a da n dh i g h c o m m i tc o s t ，a no u t p a g e l o g g i n gb a s e dt r a n s a c t i o n a lr e c o v e r ym e t h o dw a s p r o p o s e d t h ep r o p o s e dm e t h o dc o u l dr e d u c et r a n s a c t i o nc o m m i tc o s t ， k e e p i n g 9 0 0 dr e c o v e r yp e r t o r m a n c e t h ec o n t r i b u t i o n so ft h ed i s s e r t a t i o na r el i s t e da sf o l l o w s ： ( 1 ) ar e l i a b l eb + 一t r e ei m p l e m e n t a t i o nw a sp r o p o s e d o v e rc o m p o u n d n a s hs t o r a g ea r c h i t e c t u r e b yc o m b i n i n gs n a p s h o ta p p r o a c hw i t hl o g g i n g a p p r o a c h ，t h ep r o p o s e dm e t h o dc o u l de f 亿i e n t l yr e c o n s t r u c tt h ei n d e xn o d e t r a n s l a t i o nt a b l ea f t e rs y s t e mf a i l u r e ( 2 ) a na d a p t i v es t o r a g em a n a g e m e n tw a sp r o p o s e df o rn a s hm e m o r y b yc o m b i n i n go u t p a g el o g g i n ga p p r o a c hw i t ho u t 。p l a c eu p d a t ea p p r o a c h ，t h e p r o p o s e dm e t h o dc o u l de n h a n c ed a t au p d a t ep e r f b r m a n c es i g n i f i c a n t l y ，g i v i n g c o n s i d e r a t i o nt od a t ar e a dp e r f b r m a n c e ，a d a p t i n gt ov a r y i n gw o r k l o a d s ( 3 ) at r a n s a c t i o n a lr e c o v e r ym e t h o d b a s e do no u t p a g e l o g g i n ga p p r o a c h w a sp r o p o s e d t h ep r o p o s e dm e t h o dc o u l dr e d u c et r a n s a c t i o nc o m m i tc o s t ， i v a b s t r a c t p r o v i d i n gg o o dr e c o v e r yp e r f b r m a n c e k e yw o r d s ：f l a s hm e m o r y ；f l a s h b a s e dd b m s ；s t o r a g em a n g e m e n t ；i n d e x ； t r a n s a c t i o n a lr e c o v e r y v 图目录 图目录 图1 1n a n d 闪存的组织结构3 图1 2 闪存垃圾回收过程示意图6 图2 1 c o r s a i rs t o r a g es o l u t i o n ss 1 2 8 固态硬盘1 8 图2 2 闪存应用示例2 0 图3 1b f t l 的体系结构2 7 图3 2结点转换表示意图2 8 图3 3r b f t l 结点转换表快照和更新日志记录流程3 0 图3 4r b f t l 的数据存储示意图3 2 图3 5 嵌入式设备的存储方案示例3 4 图3 6 系统故障后结点转换表重建时间比较3 8 图3 7 运行开销比较3 9 图3 8n o r 闪存容量对r b f t l 额外运行开销的影响4 0 图3 9 快照记录间隔对i m f t l 额外运行开销的影响4 0 图4 1i p l 空间结构示意图4 5 图4 2o p l 空间结构示意图。4 6 图4 3o p l + 的总体结构5 0 图4 4o p l + 模式转换示意图5l 图4 5o p l 、o p l + 、i p l 和f t l 的更新性能对比5 5 图4 60 p l 、o p l + 、i p l 和f t l 的综合性能对比5 7 图4 7自适应模式转换和表项压缩对性能的影响5 8 图5 1t r a n s a c t i o n a l f t l 空间结构示意图6 3 图5 2 o p l 事务恢复方法的数据流向一6 7 图5 3o p l 事务提交过程6 7 图5 4o p l 的数据存储示意图7 2 图5 5o p l + 版本转换示意图7 7 图目录 图5 6 运行开销比较，7 9 图5 7 系统日志和快照记录代价比较7 9 图5 8 快照记录间隔对o p l 系统日志记录代价的影响8 0 图5 9 快照记录间隔对o p l 恢复性能的影响8 0 x i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：盘3 整 签字日期二盟 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 鼹 蹩鳖 咄缀一黔戳 m 赫 幽 阴 黼 辫 锹 硎 俪 签 第l 章绪论 1 1引言 第1 章绪论 1 9 5 6 年，i b m 公司展示了具有现代意义的第一台硬磁盘驱动器 r a m a c ，此后磁盘迅速成为最主要的数据存储介质，给信息技术和人类 社会带来了深远的影响。然而，磁盘存在体积大、功耗高、抗震能力差、 工作温度范围窄、噪音大等缺点，无法较好地满足移动通信、数据采集、 航空航天等应用领域对数据存储的要求。同时，磁盘的机械特性限制了其 i o 速度的提高，过去2 0 年间，c p u 的速度增加了5 0 0 多倍，而磁盘的速 度却只增加了2 0 倍；低速的磁盘与高速的c p u 之间的不协调问题已经日 益严重，极大地影响了各种应用系统的性能。 在这种背景之下，闪存应运而生。闪速存储器( f l a s hm e m o r y ，简称 闪存) 诞生于2 0 世纪8 0 年代末，是一种新型的固态存储介质，具有高速、 非易失、低功耗、高抗震、小巧轻便等特性。闪存的优良特性使得它成为 突破磁盘局限性的首选存储介质。近几年来，闪存已经被广泛应用于各种 嵌入式系统和便携式设备，如个人数字助理( p d a ) 、便携式媒体播放器 ( p m p ) 、数码相机( d c ) 、手机、传感器、笔记本电脑、航空航天器等。 随着闪存制造工艺的发展，2 0 0 0 年以来，闪存的容量以每年翻一番的速度 在增长( 2 0 0 8 年已经出现了容量达1 2 8 g b 的闪存产品) ，而其单位价格 则不断下降。因此，许多研究者和业界厂商都指出闪存将成为一种新的重 要的大容量数据存储设备，并应用于企业级计算环境中( b o u g a n i me ta l 2 0 0 9 ；g r a ye ta l2 0 0 8 ；l e esw e ta 12 0 0 8 ) 。 日益广泛和复杂的应用对闪存上的数据存储和管理提出了越来越高 的要求，而已有的闪存文件系统等数据管理机制不能较好地满足复杂应用 的需求。数据库技术是目前最为主流的数据管理技术，能够有效的支持多 种复杂的应用。因此，采用数据库技术来存储和管理闪存中的数据，即建 立采用闪存作为二级存储设备的数据库系统( f l a s h - b a s e dd b m s ，闪存数 据库) ，是应对闪存数据管理方面挑战的首选途径。 第1 章绪论 目前，已经有一些数据库厂商针对嵌入式环境推出了一些支持闪存的 数据库系统产品，如i b md b 2e v e r y p l a c e ，o r a c l eb e r k e l e yd b ，s y b a s e i a n y w h e r e ，m i c r o s o f ts q ls e r v e r2 0 0 5c e 等。但实验测试和分析表明， 这些数据库系统并不能有效发挥闪存的性能( 它们一般也不被称为闪存数 据库) 。原因在于，目前主流的数据库系统都是基于磁盘的，其存储管理、 索引管理、并发控制、事务恢复、查询优化等机制也都针对磁盘特性进行 设计；然而闪存具有许多与磁盘显著不同的特性( 详见第二章) ，所以直 接将传统的数据库技术应用在闪存上会出现很多问题，不能充分发挥闪存 的性能优势( a j w a n ie ta l2 0 0 8 ；s h a he ta 12 0 0 8 ；l e esw e ta l2 0 0 8 ，2 0 0 7 b ) 。 因此，从闪存的器件特性入手，针对闪存数据库的数据存取特点，研究闪 存数据库领域的相关问题，具有重要的理论意义和应用价值。本文正是围 绕闪存数据库存储管理、索引和事务恢复等问题展开研究。 在本章以下的小节中，1 2 节介绍了闪存数据库领域的主要研究内容 和目前的主要研究成果，1 3 节简要介绍了本论文所做的主要工作，在1 4 节中介绍了本论文的结构和章节安排。 1 2 闪存数据库 1 2 1概述 闪存主要分为n o r 和n a n d 两种类型，两种闪存的物理特性均与磁 盘有着较大的差异( 详见第二章) 。n o r 闪存支持按字节读写，读取速度 快，但写入和擦除速度慢。n a n d 闪存由一系列闪存块( b l o c k ，又称擦 除块) 组成，每个闪存块包含固定数目的页( p a g e ) ，如图1 1 所示。读 写操作以页为单位，擦除操作以块为单位，写操作所需的时间远高于读操 作( 约1 0 倍) ，擦除操作则耗时更长( 读操作的5 0 2 0 0 倍) 。闪存页 在重写前必须擦除其所在的整个块( e r a s e - b e f o r e w r i t e ) ，且每个块的可 擦除次数有限( 约1 0 万次到1 0 0 万次) 。每个页都有一定的附加空间( s p a r e a r e a ，1 6 b 1 2 8 b ) ，存储管理系统可以在附加空间中存储数据校验码、 时间戳等信息。与n o r 闪存相比，n a n d 闪存具有更大的容量和更高的 写入擦除速度，适合作为大容量存储设备，目前的研究也主要针对n a n d 2 第1 章绪论 闪存。 由于闪存和磁盘的物理特性差异显著，因此磁盘上原有的数据管理方 法不能直接应用到闪存上，需要研究针对闪存的数据管理方法。早期的闪 存数据管理领域的研究主要集中在文件系统层次，考虑的应用也比较简 单。随着闪存硬件的快速发展和应用的日益复杂，闪存数据库技术受到了 国内外越来越多的关注。以麻省理工学院、首尔大学、韩国科学技术院、 台湾大学、中国科学技术大学、中国人民大学等为代表的学术界，以微软、 三星电子、东芝、i b m 、o r a c l e 等企业为代表的工业界，近年来都对闪存 数据库进行了一些研究( l i ue ta 12 0 0 9 ；c h o w d h u re ta l2 0 0 8 ；k u oe ta l2 0 0 8 ； n a t he ta l2 0 0 8 ；w e ie ta l2 0 0 8 ；x i a n ge ta l2 0 0 8 ；a n c i a u xe ta l2 0 0 7 ) 。 ， ! 5 1 2 kp a 壹e s 扣8 。1 9 2 副o c k s ) 、 b c c k = 6 4p a g e s ( 1 2 8 k 4 k jb 舛毒 1p a g 鲁2 2 k + 9 4j b y e s 1b i o c k = ( 2 k + 8 j 弓x6 4p a g e s = ( 1 2 8 k + 王kjb y l e s 1d v i c = 2 k + 6 4j 吕xs ；p a g e sx8 1 9 2b i o c k = 8 4 4 8 m b 黯 图1 1n a n d 闪存的组织结构 研究者已经提出了一些闪存数据库原型系统，主要有p i c o d b m s 、 l g e d b m s 、f l a s h d b 等。p i c o d b m s 是b o b i n e a ue ta l ( 2 0 0 1 ) 提出的一种基 于s m a n c a r d 的小型数据库系统，其结构和功能比较简单。p i c o d b m s 按 列来分解关系并采用基于指针的存储模型以降低存储的数据量，从而适应 s m a r t c a r d 资源受限的应用环境。 l g e d b m s 是k i mgje ta l ( 2 0 0 6 ) 提出的一种针对移动设备的数据库 引擎。l g e d b m s 借鉴了日志文件系统的方法直接管理n a n d 闪存空间， 并在存储管理基础上提供了一定的查询处理和恢复功能。针对应用中事务 执行频率较低且无并发的特点，l g e d b m s 将传统的影子分页技术应用到 闪存上来提供简单的事务处理和恢复功能。 f l a s h d b 是微软研究院的n a t he ta l ( 2 0 0 7 ) 提出的一个用于传感器网络 3 第l 章绪论 的数据库原型系统，该数据库系统以闪存作为存储设备，提供了存储管理、 缓冲区管理、索引和文件管理、查询处理等功能。其主要工作是提出了一 种自适应的b + 树索引实现方法，兼顾了索引的查询性能和更新性能，并 根据硬件特性和负载的变化动态地调整索引的查询和更新方式，以应对传 感器节点产品种类较多、采用的闪存类型和性能参数各不相同、应用环境 多变等问题。 总体来说，目前已有的闪存数据库研究工作仍处于起步阶段，对数据 库的高级功能涉及较少，已有的研究成果还缺乏系统性。市场上也尚未出 现商用的闪存数据库系统，虽然i b m 、o r a c l e 等厂商推出了一些支持闪存 的数据库系统产品，但它们都是将传统的基于磁盘的数据库技术简单移植 到闪存上，虽然支持一些数据库高级功能，如事务处理等，但是性能普遍 较低。 目前，闪存数据库领域的研究内容主要涉及存储管理、索引管理、并 发控制、事务恢复和查询优化等若干方面。已有的研究成果主要集中在存 储管理方面，其它方面也取得了一定的进展。本节接下来将分别介绍各个 方面的主要研究成果，由于存储管理方面的研究起步较早，且了解存储管 理方法有助于理解其它上层方法，因此，本节对存储管理方面的研究进行 了较多的介绍。 1 2 2 闪存数据库存储管理 存储管理的主要目的是为上层应用提供硬件抽象。目前闪存存储管理 主要存在两类方法，一类是闪存转换层技术( f 1 a s ht r a n s l a t i o nl a y e r ， f t l ) ，闪存转换层屏蔽了闪存的一些器件特性，将闪存模拟成类似磁盘 的块设备，从而使得已有的基于磁盘的应用如文件系统等可以直接移植到 闪存上。i n t e l ( 1 9 9 8 ) 最早提出了f t l 方法，后来的研究又对f t l 进行了 很多改进。另一类是闪存文件系统，即专门针对闪存而设计的文件系统， 如j f f s ( w o o d h o u s e2 0 0 1 ) 、y a f f s ( a l e p ho n el i m i t e d2 0 0 2 ) 等。两类方 法虽然有一些区别，但需要解决的主要问题基本上是二致的，包括空间分 配、垃圾回收、地址映射、损耗均匀、快速启动、缓冲区管理等。本节首 先简介两种代表性的存储管理方法j f f s 和f t l ，然后介绍目前在存储管 4 第l 章绪论 理的关键问题上的研究成果。 1 闪存文件系统 j f f s ( j o u m a l l i n gf l a s hf i l es y s t e m ) 是一种具有代表性的闪存文件系 统，最初由瑞典的a x i sc o m m u n i c a t i o n sa b 公司开发。j f f s 目前比较稳 定的版本是j f f s 2 ( w o o d h o u s e2 0 0 1 ) 。下面简要介绍其设计思想、垃圾回 收和损耗均匀等算法。 闪存的写操作代价显著高于读操作，因此闪存数据更新方法成为存储 管理的关键。由于闪存页在重写前必须进行擦除，故磁盘上广泛使用的原 位更新方法( i n p l a c eu p d a t e ，即覆盖写) 对于闪存来说代价很大，因此 j f f s 2 借鉴了磁盘中日志文件系统( l o g s t r u c t u r e df i l es y s t e m ，l f s ) ( r o s e n b l u me ta 1 1 9 9 2 ) 的思想，将闪存空间看成一种日志空间，使用换位 更新方法( o u t - p l a c eu p d a t e ) 处理数据的更新，即将数据的新版本写入其 它空闲页中而不覆盖原版本，写入完成后将原版本所在的闪存页( 又称闪 存物理页或物理页) 标记为过时页( 又称无效页或陈旧页) 。 由于采用了换位更新方法，闪存中可能存在同一逻辑页的多个版本， 因此j f f s 2 需要维护逻辑地址空间和闪存物理地址空间之间的关联，即地 址映射信息，记录每个逻辑页的最新版本所在的闪存页的地址( 又称物理 地址) 。j f f s 2 在闪存页附加空间中记录其对应的逻辑页的地址和版本号， 同一逻辑页的各个版本的版本号是递增的。 闪存空闲空间不足时，j f f s 2 需要回收过时页所占空间，这一过程称 为垃圾回收( g a r b a g ec o l l e c t i o n ) 。j f f s 2 在内存中维护脏数据块( 包含 过时页的闪存块) 列表、干净数据块( 只包含有效页的闪存块) 列表和空 闲块列表。垃圾回收操作的主要过程是将待回收数据块中的有效数据复制 到其它的空闲块中，然后擦除该数据块，最后再将该数据块加入空闲块列 表中，如图1 2 所示。 闪存块的擦除次数是有限的，超过限制后该块将成为坏块，不再可靠。 因此，为了延长闪存使用寿命，需要使擦除操作比较均匀的分布在各个闪 存块上，这称为损耗均匀( w e a rl e v e l l i n g ，又称磨损平衡) 。j f f s 2 在垃 圾回收过程中兼顾了损耗均匀，垃圾回收时根据系统时间产生一个伪随机 数，根据该伪随机数选择不同的块列表，然后从该列表中选出一个块进行 回收。 5 第1 章绪论 燃 ：1 8 ： _ ： ：3 1 5 ：4 s ： _ 。 ：- ： ：3 4 ：3 ： t 阑 ： ：t 6 ： ：- ：- ：- ： ：壹：2 9 ： 过顺园有颟口空白页 过时页 e 乒l 有效页li 空白页 i ：ill 图1 2 闪存垃圾回收过程示意图 有效页5 、2 9 被复 制到第3 块中，第2 块被擦除，变成空 闲块，从而释放了 第2 块中过时页所 占空间 j f f s 2 提供了比较完整的存储管理功能，但还存在着以下一些不足： ( 1 ) 加载时间过长：由于早期闪存容量很小，j f f s 2 在启动后加载文 件系统时通过扫描整个闪存存储空间来重建地址映射和文件分配信息，但 随着闪存容量的增大，启动时间越来越长，影响了系统的使用。 ( 2 ) 损耗均匀的随意性：j f f s 2 的损耗均匀策略是基于概率的，因此 难以保证确定性。 ( 3 ) 扩展性较差：j f f s 2 的启动时间和内存消耗都与其管理的闪存大 小成正比，这使得它的扩展性较差。在实际应用中，j f f s 2 一般只能用在 百兆字节大小的闪存上。 综上所述，与一般磁盘文件系统相比，j f f s 2 文件系统在设计时考虑 了闪存的特性，因此在数据更新、垃圾回收、损耗均匀等方面具有较好的 性能。然而，由于最初是针对n o r 闪存而设计的，对大容量n a n d 闪存 的支持还比较差，这一问题在j f f s 3 的设计草案( b i t y u t s k i y2 0 0 5 ) 中有所 考虑。 6 第l 章绪论 2 闪存转换层 闪存文件系统增加了运行于传统文件系统之上的应用软件的移植工 作。针对这一问题，i n t e l ( 1 9 9 8 ) 提出了闪存转换层( f l a s ht r a n s l a t i o nl a y e r ， f t l ) 的概念。f t l 通过在闪存上增加一层存储管理机制将闪存模拟成类 似磁盘的块设备，从而使得传统的数据管理方法和应用系统可以直接应用 于闪存设备上。采用f t l 后，闪存存储管理中的器件相关问题从上层的文 件系统层分离出来，便于算法的实现与验证，因此闪存存储管理领域的研 究多采用类似f t l 的方式。 采用f t l 作为闪存存储管理机制主要有两种方式，一种是由主系统直 接在闪存介质上以软件方式实现f t l ，如m e m o r ys t i c k ；另一种是在存储 设备内用硬件固件的方式实现f t l ，将存储设备模拟成块设备，如 c o m p a c tf l a s h 。前一种方式使得主系统能够根据应用特点优化存储管理方 法，取得更好的性能；后一种方式则简化了主系统的工作，便于使用。 与j f f s 等闪存文件系统类似，f t l 也采用换位更新方法，并维护地 址映射信息，闪存空闲空间不足时，通过垃圾回收释放过时页所占的空间。 近几年来，研究者对f t l 进行了很多改进，主要是在空间分配、垃圾回收、 损耗均匀和内存消耗等方面，这些工作将在本节接下来的部分介绍。 3 存储管理关键问题的研究现状 目前，国内外研究机构已经在存储管理的多个重要问题上取得了具体 的成果。 ( 1 ) 空间分配和垃圾回收 闪存空间分配和垃圾回收是存储管理的基本问题。i n t e l 提出的f t l 采用基于页的细粒度空间分配与回收策略，采用换位更新方法处理逻辑页 的更新，垃圾回收采用贪心算法及其改进，相对于j f f s 的顺序回收方法， f t l 的垃圾回收效率较高。k a w a g u c h ie ta l ( 1 9 9 5 ) 提出c o s t - b e n e f i t 策略进 行垃圾回收，该策略改进了贪心算法( 即选择包含的过时页最多的闪存块 进行回收) ，通过擦除代价评估模型选择合适的闪存块进行回收，避免了 回收包含最近过时页的擦除块，因为块中的其它页或许也会很快过时。 c h i a n ge ta l ( 1 9 9 9 ，1 9 9 7 ) 提出的c a t 策略改进了c o s t b e n e 疗t 策略的评估 模型，增加块的已擦除次数作为考虑因素，c a t 策略还兼顾了损耗均匀。 k w o ne ta l ( 2 0 0 7 a ) 提出的e f g r e e d y 策略进一步考虑了数据冷热( 即读取 7 第1 章绪论 更新频率) 的差异，在减少垃圾回收代价的同时更好地兼顾了损耗均匀。 此外，k w o n 、c h a n glp 等研究者在冷热数据鉴别、实时垃圾回收等方面 也提出了一些方法( k w o ne ta l2 0 0 7 b ；h s i e he ta l2 0 0 6 ；c h o ue ta l2 0 0 5 ：g a l e ta l2 0 0 5 a ，2 0 0 5 b ；c h a n gl pe ta l2 0 0 4 ) 。 f t l 等基于细粒度空间管理的存储管理方法具有良好的数据读取和 更新性能，空间利用率和垃圾回收效率也较高，但内存消耗较大。为了更 好地满足嵌入式系统等资源受限环境的要求，研究者提出了一些低内存消 耗的存储管理方法。k i mje ta l ( 2 0 0 2 ) 提出的n f t l 采用基于块的粗粒度 空间分配策略，有效减少了内存消耗，但闪存空间利用率和数据存取性能 下降。l e esw e ta l ( 2 0 0 7 c ) 提出的f a s t 方法在n f t l 的基础上有效提高 了空间利用率。此外，还有一些研究综合使用多种粒度管理闪存空间，一 定程度上兼顾了内存消耗和数据存取性能( k a n gju e ta 12 0 0 6 ；k i msye t a 12 0 0 6 ；w ue ta 12 0 0 6 a ；c h a n glpe ta l2 0 0 5 ) 。总体来说，基于粗粒度空 间管理的存储管理方法的内存消耗较低，但数据存取性能和空间利用率有 一定的下降。 ( 2 ) 损耗均匀 损耗均匀对于闪存的使用寿命有着决定意义。k i mhje ta l ( 1 9 9 9 ) 提 出在各擦除块之间周期性移动数据页的策略，避免某些更新频率较低的块 的擦除次数过低，从而使各块的擦除次数比较均匀。l o 绝r e ne ta l ( 2 0 0 3 ) 提出了阈值控制方法用于损耗均匀，当块之间的擦除次数差距超过阈值 时，主动回收擦除次数最少的块，以降低一定的垃圾回收效率为代价来更 好地保证损耗均匀。c h a n glp ( 2 0 0 7 ) 提出一种基于双队列的损耗均匀控制 方法，其主要