（计算机应用技术专业论文）面向闪存的缓冲区管理算法研究.pdf

摘要 摘要 闪存作为一种新型的固态存储介质，由于具有体积小、重量轻、非易失、高 速、高抗震、低功耗等优良特性，近年来已经被广泛应用于各种嵌入式系统和便 携式设备。闪存的独特物理特性对数据管理技术提出了新的挑战，例如闪存存储 管理、闪存数据索引、面向闪存的缓冲区管理等。其中，缓冲区管理作为提高闪 存存取性能的一种重要且非常有效的手段，近年来已成为闪存数据管理领域的一 个研究热点。 然而，目前已有的缓冲区置换策略大多针对的是传统的磁盘存储系统，没有 考虑闪存不同于磁盘的特性，只着眼于提高缓冲区的命中率，如果直接它们应用 在闪存上，闪存的总访问开销会非常大。因此，针对闪存的特性，研究高效的缓 冲区置换策略对降低闪存的访问开销具有重要意义。 本论文首先对目前已有的基于闪存的缓冲区管理算法进行了总结，然后分析 了基于闪存的缓冲区管理的关键问题，并重点研究了缓冲区置换策略，最后提出 了相应的解决方法。具体而言，本文的主要工作有： ( 1 ) 提出了一种新型的面向闪存系统的缓冲区置换算法c c f l r u 。该算法 使用双l r u 链表维护缓冲区中的数据，其中，一个混合l r u 链表维护缓冲区中 的脏数据页和热的干净数据页，而另一个冷的干净l r u 链表只维护缓冲区中的 冷的干净数据页。当缓冲区空间不足时，优先置换出冷的干净l r u 链表中最近 最少访问的干净数据页，否则当冷的干净链表为空时置换出混合的l r u 链表中 冷的脏数据页。利用这一策略，c c f l r u 算法可以有效地解决缓冲区一次性扫 描式访问污染问题，减少了闪存的写操作；此外，算法在减少闪存的写操作同时 还保持了较高的命中率，从而提高了闪存的访问性能。 ( 2 ) 针对置换算法c c f l r u 中出现的o 1 跃变问题，本文对置换算法 c c f l r u 进行了改进，提出了可控的冷干净数据页优先置换算法c c c f l r u 。 与置换算法c c f l r u 不同的是，该算法对缓冲区中的冷的干净l r u 链表的长 度做了限制，规定冷的干净l r u 链表的长度不能小于m i n c c l ，否则将从混合 的l r u 链表中选择冷的脏数据页置换出去。相对于c c f l r u 而言，c c c f l r u 算法可以防止初始加载到缓冲区中并即将会被频繁访问的干净数据页很快被置 换出去，在增加少量闪存写操作的同时较大幅度地提高了缓冲区的命中率。 关键词：闪存缓冲区置换算法闪存数据库l r u a b s t r a c t a b s t r a c t a san o v e ls o l i d - s t a t es t o r a g em e d i u m ，f l a s hm e m o r yh a sb e e nw i d e l y u s e da ss t o r a g em e d i u mf o re 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 si nr e c e n t y e a r s ，d u et oi t ss p e c i f i cc h a r a c t e r i s t i c s ，s u c ha ss m a l ls i z e ，l i g h t w e i g h t ， n o n v o l a t i l e ，h i g hs p e e d ，s h o c k r e s i s t a n c e ，a n dl e s se n e r g yc o n s u m p t i o n m e a n w h i l e ，t h o s es p e c i f i cc h a r a c t e r i s t i c so ff l a s hm e m o r ya l s oi n t r o d u c en e w c h a l l e n g e st ot h ed a t am a n a g e m e n tt e c h n o l o g i e s al o to fi s s u e si nt h ed a t a m a n a g e m e n ta r e an o ws h o u l db er e c o n s i d e r e d ，i fw eu s ef l a s hm e m o r ya st h e d a t as t o r a g ed e v i c e s t h o s ei s s u e si n c l u d ef l a s h b a s e ds t o r a g em a n a g e m e n t ， f l a s h - a w a r ei n d e xm a n a g e m e n t ，f l a s h - a w a r eb u f f e rm a n a g e m e n t ，a n ds oo n a m o n gt h e m ，b u f f e rm a n a g e m e n th a sb e e nah o tt o p i ci nt h ef i e l do f f l a s h - b a s e dd a t a b a s ei nr e c e n ty e a r s ，b e c a u s ei ti sa ni m p o r t a n ta n dv e r y e f f e c t i v em e t h o df o ri m p r o v i n gt h ei op e r f o r m a n c eo ff l a s h b a s e dd a t a b a s e s y s t e m s h o w e v e r ，p r e v i o u sb u f f e rm a n a g e m e n ta l g o r i t h m sa r em o s t l yd e s i g n e df o r m a g n e t i cd i s ks t o r a g e ，a n dd on o tc o n s i d e rt h ec h a r a c t e r i s t i c so ff l a s hm e m o r y ， w h i c ha r em u c hd i f f e r e n tf r o mt h o s eo fm a g n e t i cd i s k i fw ed i r e c t l yu s et h o s e a l g o r i t h m si nf l a s h - b a s e dd a t a b a s es y s t e m s ，t h et o t a lc o s t sf o ra c c e s s i n gf l a s h m e m o r ym a yb ev e r yh i g h ，a st h e yo n l yf o c u so nt h eh i tc o u n to ft h eb u f f e r a n dn e g l e c tt h ew r i t ec o s t sw h e nr e p l a c i n gb u f f e rf r a m e s t h er e a s o nt o i n t r o d u c ew r i t ec o s t si n t ob u f f e rr e p l a c e m e n ta l g o r i t h m si st h a tt h ep a g e w r i t e l a t e n c yi nf l a s hd e v i c e si sm u c hh i g h e rt h a np a g e - r e a dc o s t s s o ，i ti sv e r y i m p o r t a n tt os t u d ya ne f f e c t i v ef l a s h a w a r eb u f f e rr e p l a c e m e n tp o l i c yt o i m p r o v et h eb u f f e rm a n a g e m e n tp e r f o r m a n c ei nf l a s h - b a s e dd a t a b a s es y s t e m s i nt h i sd i s s e r t a t i o n ，w ef i r s tr e v i e wt h ee x i s t i n gb u f f e rm a n a g e m e n ta l g o r i t h m s f o rf l a s hm e m o r y , a n dt h e n a n a l y z et h ek e yc h a l l e n g e s o ff l a s h a w a r eb u f f e r m a n a g e m e n t f i n a l l y , an e wf l a s h - a w a r e b u f f e rr e p l a c e m e n t a l g o r i t h m c a l l e d c c f - l r ui sp r e s e n t e d w ea l s op r o p o s ea ni m p r o v e dv e r s i o no fc c f l r u ，w h i c hi s c a l l e dc c c f - l r u ，t os o l v et h ep r o b l e m si nc c f l r u t h em a i nr e s e a r c hw o r ko f t h i sd i s s e r t a t i o nc a l lb es u m m a r i z e da sf o l l o w s ： 1 w ep r o p o s ean o v e lb u f f e rr e p l a c e m e n ta l g o r i t h mf o rf l a s h - m e m o r y - b a s e d s y s t e m s ，c a l l e dc c f l r u t h en e wa l g o r i t h mu s e st w ol r ul i s t st om a i n t a i nt h e i l i a b s t r a = t b u f f e rp a g e s ，w h e r eac o l d c l e a nl r ul i s ts t o r e st h ec o l dc l e a np a g e s ，a n dam i x e d l r ul i s tp l a c e sd i r t yp a g e sa n dh o tc l e a np a g e s w h e nt h eb u f f e rs p a c ei si n s u f f i c i e n t ， i tf i r s te v i c t st h el r u p a g ei nt h ec o l dc l e a nl i s t ，o re v i c t st h ec o l dd i r t yp a g ei nt h e m i x e dl r ul i s ti nc a s et h a tt h ec o l dc l e a nl i s ti s e m p t y u s i n gt h i ss t r a t e g y , r e p l a c e m e n ta l g o r i t h mc c f - l r uc a ne f f e c t i v e l yp r e v e n tc l e a np a g ea c c e s s e do n l y o n c er e c e n t l yf r o mp o l l u t i n gt h eb u f f e r a n dt h u sr e d u c e st h en u m b e ro ff l a s hw r i t e o p e r a t i o n ；m o r e o v e r , i tr e d u c e st h en u m b e ro ff l a s hw r i t eo p e r a t i o n sa sw e l la sh o l d s h i g h e rh i tr a t i o ，a n dt h u si m p r o v e st h ea c c e s sp e r f o r m a n c eo ff l a s hm e m o r y 2 i no r d e rt os o l v et h eo lj u m p i n gp r o b l e mi nt h er e p l a c e m e n ta l g o r i t h m c c f - l r u ，w ei m p r o v et h ec c f l r ua l g o r i t h ma n dp r o p o s ean e wr e p l a c e m e n t a l g o r i t h mc a l l e dc c c f l r u u n l i k er e p l a c e m e n ta l g o r i t h mc c f - l r u ，r e p l a c e m e n t a l g o r i t h mc c c f - l r ul i m i t st h el e n g t ho fc o l dc l e a nl r ul i s ti nt h eb u f f e r , a n d s t i p u l a t e st h a ti t sl e n g t hi sn o tl e s st h a nm i n c c l ，o t h e r w i s ei ts e l e c t st h ec o l dd i r t y p a g e sf r o mt h em i x e dl i ul i s ta sv i c t i m c o m p a r e d 谢n lc c f l r u ，c c c f l r uc a n k e e pi nt h eb u f f e rt h ec l e a np a g e sw h i c ha r ei n i t i a l l yl o a d e di n t ob u f f e ra n dw i l lb e f r e q u e n t l ya c c e s s e d ，n l ec c c f - l r ui n t r o d u c e sas m a l ln u m b e ro ff l a s hw r i t e o p e r a t i o n sb u ts i g n i f i c a n t l yi m p r o v e st h eh i tr a t i o ，a n dt h u sc a ni m p r o v et h eo v e r a l l p e r f o r m a n c eo f f l a s h - b a s e dd a t a b a s es y s t e m s k e yw o r d s ：f l a s hm e m o r y , b u f f e rr e p l a c e m e n ta l g o r i t h m ，f l a s h - b a s e dd a t a b a s e ， l r u i v 图目录 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图目录 o c z2 5 0 g b 闪存固态硬盘3 n a n d 型闪存存储系统1 2 缓冲区管理算法c f l r u 的一个例子1 3 缓冲区管理算法d l c f l r u e 的一个例子1 4 缓冲区管理算法l r u w s r 的一个例子1 5 f a b 的缓冲区链表结构1 6 c l c 的缓冲区链表的结构1 8 c c f l r u 维护的混合l r u 链表和冷的干净l r u 链表2 3 c c f l r u 置换策略的伪代码2 4 模拟测试负载下不同缓冲区置换算法的命中率2 7 模拟测试负载下不同缓冲区置换算法的闪存写次数2 9 模拟测试负载下不同缓冲区置换算法的i o 总延迟3 0 模拟测试负载下不同缓冲区置换算法的运行时间3 2 o l t p 测试负载下不同缓冲区置换算法的命中率3 3 o l t p 测试负载下不同缓冲区置换算法的闪存写次数3 4 o l t p 测试负载下不同缓冲区置换算法的i o 总延迟3 4 o l t p 测试负载下不同缓冲区置换算法的运行时间3 5 c c c f l r u 维护的混合l r u 链表和冷的干净l r u 链表3 9 c c c f l r u 置换策略的伪代码4 0 o l t p 测试负载下两种缓冲区置换算法的命中率4 2 o l t p 测试负载下两种缓冲区置换算法的闪存写次数4 3 o l t p 测试负载下不同缓冲区置换算法的i 0 总延迟4 4 o l t p 测试负载下不同缓冲区置换算法的运行时间4 5 c c c f - l r u 在0 【取值区间为 0 ，1 】时运行时间的变化情况4 6 c c c f - l r u 在伐取值区间为 0 ，0 1 时运行时间的变化情况4 6 v i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰 写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了 明确的说明。 作者签名：奄k 签字日期：盈磋篁圆丝鱼 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 电断口保密( 年) 作者签名：套右 签字日期：丝嗌点叠塑里 导师签名：行诡忱 签字日期：纠! 竺 第1 章绪论 1 1引言 第1 章绪论 随着电子技术的快速发展，闪存作为一种新型的存储介质，已经被广 泛应用于嵌入式系统和航天航空等应用领域。闪存有n o r 和n a n d 两种 类型，其中n o r 型闪存容量较小，价格相对较高，通常用于存储程序， 而n a n d 型闪存容量较大，价格相对较低，通常用于存储数据。与传统的 存储介质磁盘相比，闪存具有非易失、高读写速度( 单位时间i o 数比磁 盘高1 0 倍以上：2 8 0 0l o p sv s 2 0 0i o p s ) 、低功耗( 电量消耗比磁盘低 1 5 倍左右：0 9w a t t sv s 1 4w a t t s ) 、低噪音、抗震、小巧轻便等优 点。上述这些优良特性，使得闪存成为许多存储系统的最佳选择。此外， 闪存存储介质本身还有一些独特的物理特性，如读写速度不对称、不支持 原位更新( 重写数据页之前必须先擦除其所在的块) 、数据块允许的平均 擦除次数有限等( 具体细节请参见2 1 节) 。 由于闪存和磁盘在物理结构、数据存取方式等方面均存在着显著的差 异，所以目前已有的基于磁盘的应用如文件系统等无法直接支持闪存设备。 为了解决这一问题，i n t e l 在l9 9 8 年率先提出了闪存转换层( f l a s h t r a n s l a t i o nl a y e r ，f t l ) ，通过将闪存模拟成类似于磁盘的块存储设备，屏 蔽了闪存的硬件特性，使得传统的存储管理技术可以直接用于闪存，进而 使现有的操作系统、数据库系统等应用可以直接支持闪存设备。 缓冲区管理技术是提高闪存访问性能的有效手段之一。目前，已有的 操作系统和数据库管理系统多采用l r u 等传统的缓冲区置换算法，而这些 算法大多针对的是磁盘存储系统，没有考虑到闪存读写代价不对称的特性， 虽然闪存不同于磁盘的特性大多已经被闪存转换层所屏蔽，但是闪存写代 价显著高于读代价的问题仍然存在，直接用于闪存时使得闪存的访问性能 较差。因此，针对闪存的特性，研究面向闪存的缓冲区管理方面的问题， 对提高闪存的访问性能具有重要的理论意义和应用价值。本文正是针对这 一问题展开研究。 1 2 闪存存储器 第1 章绪论 闪存是i n t e l 和东芝在2 0 世纪8 0 年代末推出的一种新型固态存储器 ( s o l i ds t a t ed i s k ) 。由于它具有高速、防震、低噪、省电、小巧便于携 带等优良特性，近年来被广泛用于各种嵌入式系统和便携式设备，如p d a 、 m p 3 、d v 、数码相机、手机、传感器等，目前已在人们的日常生活当中扮 演着重要的角色。随着闪存容量的快速增长和价格的不断下降，闪存已经 成为一种新的重要的二级存储设备，并逐渐开始作为大容量数据存储设备 应用于企业级计算环境中。 1 2 1 闪存的优缺点 与传统的磁盘相比，闪存具有以下优良的特性： ( 1 ) 小巧轻便 与磁盘精密的机械构造不同，闪存存储介质结构简单，数据读取不需 要像传统的磁盘存储器那样旋转机械磁头进行定位，因此具有体积小，重 量轻的特点，便于人们随身携带。 ( 2 ) 低功耗 由于闪存的物理构造无任何机械部分，工作时仅仅是电子运动，省去 了传统的磁盘存储器读取数据时高速的磁盘转动所消耗的大量电力，所以 闪存存储器具有能耗低、省电的特点( 电量消耗比磁盘低1 5 倍左右：0 9 w a t t sv s 1 4w a t t s ) 。随着闪存芯片生产工艺的飞速发展，闪存的耗 电量越来越低。以闪存为存储介质的m p 3 为例，s o n y 的e l0 0 系列，使用 1 节a a a 电池，其播放时间就可以达到7 0 个小时。 ( 3 ) 低噪音 与传统的磁盘存储器相比，闪存的物理结构无任何机械部分，当读取 数据时，闪存内部没有机械运动而仅仅是电子运动，因此不存在部件运行 所产生的噪声。 ( 4 ) 高抗震性 与磁盘复杂且精密的物理结构不同，闪存物理构造比较简单，其工作 时不存在机械运动而仅仅是电子运动，因而防震抗震能力极佳，即使在一 些比较恶劣的应用环境中，仍可以稳定的工作。 ( 5 ) 高读写速度 由于传统磁盘机械结构的限制，其读取一个磁盘块的时间通常是由寻 道时间、旋转延迟和传输时间等几部分组成，而闪存没有机械寻道和旋转 过程，因此其数据读写速度和磁盘相比有了显著的提高。最近几年，闪存 的制造工艺日趋成熟，业界很多厂商都推出了大容量、高性能的固态硬盘 2 第l 章绪论 产品( s o l i ds t a t ed i s k ，s s d ) 。如o c z 公司在2 0 0 9 年6 月发布的一款 25 英寸、容量为2 5 0 g b 的闪存固态硬盘o c z s s d 2 1 a p x ，如图11 所示。 该固态硬盘采用s a t a1 1 接口，据o c z 表示，o c z s s d 2 - 1 a p x 的速度比 最快的7 2 0 0 转硬盘快5 倍咀上，甚至可以达到4 0 0 0 0 转传统硬盘的速度， 其读取和写入速度分别为2 3 0 m b s 和1 6 0 m b s 。 图l 1o c z2 5 0 0 b 闪存固态硬盘 然而，目前还存在着一些制约闪存存储器应用发展的不利因素。主要 表现在以下两个方面： ( 1 ) 容量小 闪存的单芯片容量已经达到了3 2 g b ，而且目前一些厂商也已经推出 了容量达5 1 2 g b 的闪存固态硬盘但与磁盘t b 级的超大容量相比还是有 相当太的差距，限制了闪存在企业级计算环境中的应用。但最近几年来闪 存的容量一直在高速增长，基本上每年都可以翻一番，容量上的瓶颈将逐 渐缓解。据b i t m i c r o 公司方面声称，其在不久的将来将会推出一款容量高 选1 6 t b 的固态硬盘新品。 ( 2 ) 价格高 根据o a r t n c r 的研究结论，面向个人消费者的固态硬盘的成本大约2 34 5 美元o b 而普通硬盘为03 8 美元o b 。目前看来闪存的价格要高于 磁盘，但是随着闪存生产厂商的生产能力不断增强，闪存的价格也在快速 下降。i n s t a t 的调查数据表明，固态硬盘的价格每年会下降6 0 。 1 22 闪存的广泛应用 由于具有非易失、高速、高抗震性、低功耗、小巧轻便等优良特性， 闪存存储器在消费性电子产品领域获得了广泛的应用。目前最常见的电子 消费产品如数码相机、m p 3 播放器、手机、u 盘、p m p 等都采用闪存作为 第1 章绪论 存储介质。另外，随着容量的快速增长和价格的不断下降，采用闪存介质 的固态硬盘在追求节能和抗震性能的笔记本电脑领域很快得到了应用，目 前已有不少p c 生产商己采用固态硬盘作为笔记本的二级存储介质，如 s a m s u n g 的n t q 3 0 s s d 使用了3 2 g b 的固态硬盘，苹果公司的m a c b o o k a i r ( m c 2 3 4 z p a ) 使用了1 2 8 g b 的固态硬盘，东芝的d y n a b o o ks sr x 2 w a j 则使用了5 1 2 g b 的固态硬盘。随着近来上网本( n e t b o o k ) 和平板电脑的 出现，闪存在笔记本电脑领域的应用将会更加广泛。 另一方面，随着近年来闪存存储器在容量和稳定性等技术方面的突破 性发展和i t 市场对节能及虚拟化等议题的关注升高，固态硬盘在追求性能 的服务器市场也得到了快速的应用。目前，固态硬盘已经涉足企业级的应 用，e m c 、i b m 、h p 、n e t a p p 、d e l l 、h 3 c 和华为赛门铁克等厂商都竞相 将固态硬盘推广到企业级存储产品中，唯恐落后。百度是目前国内少数在 企业级存储中采用固态硬盘的用户之一，其在2 0 0 8 年宣布将旗下的上千 台服务器的硬盘全部更换为固态硬盘以提高计算速度。第一批“吃螃蟹”的 还有辽宁移动，2 0 0 9 年3 月，其将9 块14 6 g b 的固态硬盘配置到e m c s y m m e t r i xd m x 4 中，大大地缩短了客户详单查询时间。此外，2 0 0 9 年， 中银国际证券有限责任公司采用了以闪存为存储介质的e m cc l a r i i o n 网络存储系统，使整个核心交易系统的响应速度得到了大幅度地提高。一 些网络游戏公司如深圳网域也使用固态硬盘来加快服务器的访问速度，提 高服务器的负载能力。 1 3 闪存芯片 1 3 1 闪存芯片的类型 闪存主要有n o r 和n a n d 两种类型，其中n o r 型闪存容量较小，价 格相对较高，以字节为存取单位，支持代码本地运行，通常用于存储程序； 而n a n d 型闪存容量较大，价格相对较低，以数据页为存储单位，通常用 于存储数据。不同的特性使得两者分别属于不同的市场，其中，n o r 型闪 存主要用于手机、掌上电脑等需要支持代码本地运行的应用领域，而n a n d 型闪存主要用于数据存储相关的领域，如移动存储产品和各种类型的闪存 卡等。目前，n o r 型闪存的生产厂商主要有i n t e l 和s p a n s i o n ，英特尔目 前的市场份额稍高，而s p a n s i o n 则在技术上具有一定的优势，而n a n d 型闪存的生产厂商主要包括韩国的三星电子、现代电子和海力士，日本的 4 第1 章绪论 东芝，以及美国的s a n d i s k 、m i c r o n 等，其中三星公司占据的市场份额较 高。 1 3 1闪存芯片的基本工作原理 无论是n o r 型闪存还是n a n d 型闪存，它们都是闪存家族中的成员， 两者的基本数据存储方式和操作原理完全相同。闪存以单晶体管作为二进 制信号的存储单元，结构与普通的半导体晶体管和场效应管非常类似，区 别在于闪存芯片的晶体管中加入了“浮动栅”( f l o a t i n gg a t e ) 和“控制栅” ( c o n t r o lg a t e ) 。浮动栅表面被一层硅氧化物绝缘体所包覆并通过电容与 控制栅耦合，用来贮存电子；而控制栅用来将电子注入或移出浮动栅。当 负电子在控制栅的作用下被注入浮动栅时，该单晶体管的存储状态就由1 变成0 ；相反，当负电子被从浮动栅内移出后，该单晶体管的存储状态就 由0 变成1 。 闪存芯片在写入数据之前，必须将浮动栅内的负电子全部移走，使得 相关闪存块中各位的存储状态都置为1 ，即进行擦除操作。因此，只有写 入数据0 时才需要执行写入动作，即将闪存上与之对应的存储位的状态由 l 置为o 。由于闪存的擦除操作以块为单位，所以闪存块的擦除过程需要 耗费很长的时间，对于n o r 型闪存和n a n d 型闪存，擦除操作引起的开 销均不容忽视。此外，由于闪存的写入过程需要耗费较长的时间，所以不 管是n o r 型闪存还是n a n d 型闪存，其数据写入速度总是慢于读取的速 度。 1 3 2 n o r 型与n a n d 型闪存特性的比较 n o r 型闪存与n a n d 型闪存存储特性有着很大的差异，主要表现在 以下几个方面： ( 1 ) 存取接口 n o r 型闪存一般使用s r a m 接口，有足够多的地址引脚用于寻址， 可以很容易存取每一个字节，从而能够支持芯片内执行( e x e c u t ei np l a c e ， x i p ) 。而n a n d 型闪存地址线和数据线复用，使用复杂的i o 口串行地 存取数据，一般会有8 个引脚用来传送控制、地址和数据等信息。 ( 2 ) 性能 n o r 型闪存的擦除块大小通常为6 4 - - 1 2 8 k b ，擦除操作所需的时间在 数百毫秒到数秒之间；而读写操作均可以按字节或字( w o r d ，1w o r d = 2 b ) 5 第l 章绪论 进行，字节和字读写速度很快。而n a n d 型闪存的擦除块大小通常为 1 6 k b - 2 5 6 k b ，擦除操作所需的时间一般为几毫秒；读写操作均以页为单 位，页大小通常为5 1 2 b - 4 k b ，页读取时间一般为数十微秒，而页写入时 间一般为数百微秒。简单来说，n o r 型闪存的读速度较快，而n a n d 型 闪存的写和擦除速度较快。 ( 3 ) 容量和成本 由于n o r 型闪存的每个存储单元与位线相连，增加了芯片内位线的 数量，不利于存储密度的提高，因此n o r 型闪存的容量较小，一般在 1 1 6 m b y t e 左右，占据了容量在十几兆字节以下的闪存市场的大部分份额。 与n o r 型闪存相比，n a n d 型闪存往往用在几十兆、上百兆字节甚至更 大容量的产品当中。另外，由于n a n d 型闪存的单元尺寸几乎是n o r 型 闪存的一半，并且生产过程更为简单，因此n a n d 型闪存可以在给定的模 具尺寸内提供更高的存储容量，从而n a n d 型闪存的单位价格要低于n o r 型闪存。因此，n o r 型闪存主要用于程序代码或少量数据存储，而n a n d 型闪存则更多地用于大数据量存储 ( 4 ) 耐用性 由于闪存的写和擦除操作会使得存储介质氧化降解，导致芯片老化， 所以闪存并不适合频繁地擦写。在闪存芯片使用寿命方面，n a n d 型闪存 的擦除块的最大擦除次数通常能够达到一百万次左右，而n o r 型闪存的 擦除块的最大擦除次数则是十万次左右。因此，n a n d 型闪存具有较高的 可擦除次数。 ( 5 ) 可靠性 可靠性是使用闪存存储介质时需要重点考虑的一个问题，这里主要从 位交换和坏块处理这两个方面来比较n o r 型闪存和n a n d 型闪存的可靠 性。 位反转现象，是指某些情况下闪存芯片上的一个位( b i t ) 发生反转。 位反转现象在两种类型的闪存芯片上均可能出现，但出现频率很低，且 n o r 型闪存发生的概率远小于n a n d 型闪存。在使用n a n d 型闪存时， 系统往往需要使用错误探测和错误更正算法，以增强n a n d 型闪存的可靠 性。 坏块问题主要与n a n d 型闪存相关，在n a n d 型闪存的生产及使用 过程中都可能产生坏块。一旦闪存块成为坏块，将不再可靠。一般来说， n a n d 型闪存在未使用之前，其中的坏块是随机分布的，系统在使用前需 要对整个闪存存储空间进行初始化扫描，将发现的坏块标记为不可用。 6 第1 章绪论 虽然n o r 型闪存和n a n d 型闪存在很多特性上有较大的差异，但是 这两种类型的闪存芯片也存在着一些共同特性，如不支持原位更新，重写 前需要进行块擦除操作，闪存的写操作和擦除操作代价都显著高于读操作， 块的可擦除次数都有限等。 1 4 基于闪存的缓冲区管理 缓冲区管理是提高闪存访问性能的有效手段之一，也是计算机领域一 个非常重要的研究主题。现在很多缓冲区置换策略，如l r u 、l r u k 、l i r s 、 f b r 、a r c 等( d i n ge ta l2 0 0 5 ；m e g i d d oa n dm o d h a2 0 0 3 ；j i a n ga n dz h a n g 2 0 0 2 ；l e ee ta l2 0 01 ；o n e i le ta l19 9 3 ；r o b i n s o na n dd e v a r a k o n d al9 9 0 ) ，已 被广泛地用于操作系统、数据库系统以及存储系统中。但这些缓冲区置换 策略大多都是针对磁盘，主要着眼于提高数据在缓冲区中的命中率，而闪 存的读写代价不对称的特性则决定了其必须采用不同于一般磁盘存储的 缓冲区置换策略，需要对读写操作加以区分，在保证缓冲区命中率的同时， 尽可能地减少写操作。除此之外，由于闪存的随机写代价要远远高于闪存 的连续写代价( 一般是十倍以上) ，所以尽可能增加连续写的概率也成为 提高闪存访问性能一种手段。总而言之，减少闪存的随机写操作已经成为 提高闪存访问性能的一种重要手段。目前，已经有了一些科研机构做了相 关的研究，根据应用环境的不同，研究方向大致可以分为以下两类： ( 1 ) 基于s s d 的缓冲区管理算法的研究。这类缓冲区算法主要是考 虑闪存的读写代价的不对称性以及数据的访问频率，在保证缓冲区命中率 的同时，尽可能减少闪存的写操作，从而达到提高闪存访问性能的目的。 目前，已有的缓冲区算法包括c f l r u 、l r u w s r 和l i r s w s r 等( j u n ge t a l2 0 0 7 ；y ie ta l2 0 0 9 ) ，其中最著名是c f l r u 算法。 ( 2 ) s s d 内部的缓冲区管理算法的研究。与第一类缓冲区算法不同 的是，s s d 内部的缓冲区算法主要是只针对写缓冲，利用闪存连续写代价 明显低于随机写的特点，将具有连续特性的数据页进行聚簇，然后一次性 置换出去。该类算法在尽可能减少置换次数的同时，尽可能提高聚簇的置 换粒度，从而达到提高闪存访问性能的特性。目前，已有的缓冲区算法包 括f a b 、b p l r u 、r e f ( s e oa n ds h i n2 0 0 8 ) 和c l c 等。 1 5 本文的主要工作 7 第1 章绪论 缓冲区管理是提高闪存访存性能的一种重要且非常有效的手段，对降 低闪存的访问开销具有重要意义。目前已有的缓冲区置换策略没有考虑闪 存不同于磁盘的特性，只着眼于提高缓冲区的命中率，如果直接它们应用 在闪存上，闪存的总访问开销可能会非常大，但如果只着眼于减少写操作， 又有可能会大幅度降低缓冲区的命中率，产生过多的读操作，降低闪存的 访问性能。针对目前存在的这些问题，本文将结合缓冲区中数据的访问特 性和闪存读写代价不对称的特性，研究高效的针对闪存的缓冲区置换策略， 在保证数据命中率的同时，尽可能提高置换策略的整体i o 性能。具体地 来说，本文在设计缓冲区置换策略时，不仅考虑缓冲区中数据的访问频率， 还考虑闪存写代价高于读代价的特性，对缓冲区中的数据页进行分类并给 出各类数据页置换代价的关系，当发生置换时，优先置换出缓冲区中置换 代价最小的数据页，以达到在降低闪存访问开销的同时保证较高命中率的 目的。 本文的主要工作可归纳为如下几点： ( 1 ) 提出了一种新型的面向闪存系统的缓冲区置换算法c c f l r u 。 该算法使用双l r u 链表维护缓冲区中的数据，其中，一个混合l r u 链表 维护缓冲区中的脏数据页和热的干净数据页，而另一个冷的干净l r u 链表 只维护缓冲区中的冷的干净数据页。当缓冲区空间不足时，优先置换出冷 的干净l r u 链表中最近最少访问的干净数据页，否则当冷的干净链表为空 时置换出混合的l r u 链表中冷的脏数据页。利用这一策略，c c f l r u 算 法可以有效地解决缓冲区一次性扫描式访问污染问题，减少了闪存的写操 作；此外，算法在减少闪存的写操作同时还保持了较高的命中率，从而提 高了闪存的访问性能。 ( 2 ) 针对置换算法c c f l r u 中出现的0 1 跃变问题，本文对置换算 法c c f - l r u 进行了改进，提出了可控的冷干净数据页优先置换算法 c c c f - l r u 。与置换算法c c f l r u 不同的是，该算法对缓冲区中的冷的 干净l r u 链表的长度做了限制，规定冷的干净l r u 链表的长度不能小于 m i n c c l ，否则将从混合的l r u 链表中选择冷的脏数据页置换出去。相对 于c c f - l r u 而言，c c c f - l r u 算法可以防止初始加载到缓冲区中并即将 会被频繁访问的干净数据页很快被置换出去，在增加少量闪存写操作的同 时较大幅度地提高了缓冲区的命中率。 1 6 论文的组织结构 8 第1 章绪论 本文共分为五章，各部分的内容组织如下： 第一章首先介绍了本文的课题背景及研究意义，然后具体介绍了闪存 的存储特性及其在多个领域的应用，随后又介绍了n o r 和n a n d 两种类 型的闪存芯片，并分析比较了这两种类型闪存芯片的器件特性的异同，接 着简单地概述了面向闪存的缓冲区管理的研究现状，最后是本文的研究内 容和创新之处。 第二章首先介绍闪存的硬件特性和n a n d 型闪存存储系统，然后具体 分析了目前已有的基于闪存的缓冲区管理算法，并提出研究中的一些关键 问题。 第三章针对已有的基于闪存的缓冲区管理算法的不足，结合闪存读写 代价不对称性和数据访问频率，提出了冷干净数据页优先置换算法。该算 法根据缓冲区中数据的访问频率将数据分为冷的干净数据页、冷的脏数据 页、热的干净数据页和热的脏数据页，并采用双缓冲链表维护缓冲区中的 数据。通过优先置换出缓冲区中冷的干净数据页，尤其是最近一段时间内 只访问一次的数据页，在保证缓冲区命中率的同时，有效地减少了闪存的 写操作，从而获得了较好的访问性能，最后通过实验验证了算法的性能。 第四章主要是针对冷的干净数据页优先置换算法中存在的0 1 跃变问 题，提出了自适应的冷的干净数页优先置换算法。该算法在原算法的基础 上采用m i n c c l 机制，通过限定冷的干净数据页链表的最小长度，有效地 解决了o 1 跃变问题，使原算法性能得到了提高，最后通过实验验证了新 算法的性能。 第五章对本文的工作做了总结性的回顾，并给出了未来的工作方向。 9 第2 章基于闪存的缓冲区管理研究现状 第2 章基于闪存的缓冲区管理研究现状 2 1闪存特性和闪存存储系统 闪存是一种e e p r o m ( 非易失的存储介质) ，根据物理构造的不同， 闪存一般分为n o r 和n a n d 两种类型。与n o r 型闪存相比，n a n d 型 闪存的容量较更大、价格更低、写擦除速度更快，适合做大容量存储设备， 从而获得了更广泛的应用。近几年，国内外基于闪存的缓冲区管理研究多 是针对n a n d 型闪存，本论文也主要针对n a n d 型闪存进行研究。 与硬盘相比，n a n d 型闪存具有以下特性： ( 1 ) 闪存存储设备由尺寸大小固定的块组成，而每个块又由基本的 存储单元页构成，形成块、页式的组织结构，无机械延迟，即没有寻道时 间和旋转时间； ( 2 ) 不支持原位更新，对存储区的重复写操作之前必须进行擦除操 作，由于原位更新代价过大，所以一般采用换位更新方式； ( 3 ) 有三种基本操作，分别为页读写和块擦除操作，其中，读写擦 除速度存在较大差异，读操作速度明显高于写操作，而擦除操作则更慢， 如表2 1 所示，写操作时间是读操作时间的l o 倍左右，擦除操作时间是写 操作时间的7 5 倍左右；