（计算机应用技术专业论文）混合结构闪存索引研究.pdf

摘要 摘要 闪存作为一种新型的非易失存储介质，诞生于2 0 世纪8 0 年代末，具 有高速、抗震、功耗低以及小巧轻便等优良特性。而且闪存作为一种纯电 子设备，能够克服传统的机械设备所造成的一些缺陷，可以解决传统磁盘 i o 操作中的机械延迟。因此，闪存的用途越来越广泛，从最初局限于嵌 入式系统和便携式设备发展到现在已经开始作为一种二级存储设备( 固态 硬盘) 应用于计算机系统中，并逐渐应用到企业级计算环境中。 数据库作为应用广泛的数据管理工具，随着固态硬盘作为二级存储设 备，数据库管理系统将不可避免的需要移植到固态硬盘上。由于固态硬盘 具有许多与磁盘显著不同的特性，如果直接利用传统的数据库技术会使得 其性能( 特别是更新性能) 不能获得相应于闪存和磁盘i o 性价比值而带 来的提高。在某些情况下，甚至会获得比磁盘上还差的性能。而索引结构 是有效组织数据库中的数据、提高数据库查询性能的关键技术之一，是数 据库中必不可少的结构之一。因此，研究基于闪存的索引管理技术具有重 要的理论意义和应用价值。 传统的索引研究并没有考虑闪存的特殊的i o 特性，因此直接将其移 植到闪存上将会导致其性能低下，特别是更新性能。目前基于闪存的索引结 构也没有很好的解决这个问题，因此，本论文中将提出一种混合结构的闪 存索引结构，称之为h a s h t r e e 。它结合了树类索引和哈希类索引的优点， 从而能够在保证索引查询性能的基础上获得较好的更新性能。h a s h t r e e 通 过哈希策略将索引记录散列到多个桶中，然后将每个桶中的索引记录组织 成f t r e e 的树结构形式。 论文的主要贡献包括以下几个方面： ( 1 ) 提出了一种混合结构的索引结构h a s h t r e e ； ( 2 ) 在h a s h t r e e 中引入调节机制，这样可以通过调节h a s h t r e e 的参 数来在索引的更新性能和查询性能之间得到一个满足要求的折中； ( 3 ) 分析了h a s h t r e e 的更新代价并讨论了h a s h t r e e 在不同s s d 下 取得较好性能的策略。 关键词：闪存；固态硬盘；索引管理；混合结构 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 e wn o v e ls o l i d s t a t e s t o r a g em e d i u ma n df i r s t a p p e a r e di n 19 8 0 s f l a s hm e m o r yh a ss o m es u p e r i o rf e a t u r e s ，s u c ha sh i g h s p e e d ，s h o c kr e s i s t a n c e ，l o wp o w e rc o n s u m p t i o n ，a n ds m a l ls i z e f l a sm e m o r y i sap u r ee l e c t r i c a ld e v i c e ，a n dt h e ni tc a no v e r c o m ed r a w b a c kc a u s e db yt h e m e c h a n i c a lm o v i n gp a r ti nm a g n e t i cd i s k s i nr e c e n ty e a r s ，f l a s hm e m o r yi s w i d e l yu s e d ，i tn o tb el i m i t e di nt h ee 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 ， b u tan e wi m p o r t a n ts e c o n d a r ys t o r a g ed e v i c e ( s s d ，s o i l ds t a t ed r i v e ) ，a n dh a s b e e na p p l i e di ne n t e r p r i s ec o m p u t i n ge n v i r o n m e n t m a n a g i n gd a t aw i t hd a t a b a s ei saw i d e l yu s e dt e c h n i q u e ，a n dw i t ht h e w i d e l yu s e do fs s da ss t o r a g ed e v i c e s ，t h ed b m s w i l lb em i g r a t e dt os s d i n e l u c t a b i l i t y b u t d u et ot h ed i s t i n c tc h a r a c t e r i s t i c so fs s d ，d i r e c t l y t 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 cd i s kb a s e dd a t a b a s et e c h n i q u et os s dc o u l d n o tf u l l yp l a yt h ep e r f o r m a n c ea d v a n t a g e so ff l a s hm e m o r y i ns o m es i t u a t i o n ， t h ep e r f o r m a n c ee v e np o o rt h a nm a g n e t i cd is k t h ei n d e xs t r u c t u r ei so n eo f t h ek e yt e c h n o l o g i e st oi m p r o v eq u e r yp e r f o r m a n c eo fd a t a b a s e ，w h i c hi sa e s s e n t i a ls t r u c t u r eo ft h ed a t a b a s e t h e r e f o r e ，r e s e a r c h i n go nt h ep r o b l e m si n i n d e xm a n a g e m e n th a si m p o r t a n tt h e o r e t i cs i g n i f i c a n c ea n dv a l u e t r a d i t i o n a li n d e xs t r u c t u r e sd on o tt a k et h ef l a s hi oc h a r a c t e r i s t i c si n t o a c c o u n ta n d ，t h e r e f o r e ，w i l lc a u s ep o o rp e r f o r m a n c e ，e s p e c i a l l yp o o ru p d a t e p e r f o r m a n c e t oa d d r e s st h i sp r o b l e m ，w ep r e s e n t an e wh y b r i di n d e x s t r u c t u r ef o rf l a s hd i s k si nt h i sp a p e r ，w h i c hi sc a l l e dh a s h t r e e h a s h t r e e a i m sa tg e t t i n gb e t t e ru p d a t ep e r f o r m a n c ew h i l ek e e p i n gr e l a t i v e l yh i g hs e a r c h e f f i c i e n c y ，w h i c hc o m b i n e st h ea d v a n t a g eo ft r e es t r u c t u r a li n d e xa n dh a s h s t r u c t u r a li n d e x t h eh a s h t r e eu s e sah a s h b a s e di n d e xt os p l i tt h ei n d e x e d r e c o r d si n t os e v e r a lb u c k e t s ，a n dt h e nw ed e v e l o pan e wt r e es t r u c t u r en a m e d f t r e et oo r g a n i z et h er e c o r d si ne a c hb u c k e t t h em a i nc o n t r i b u t i o n so ft h ep a p e ra r 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 eah y b r i di n d e xs t r u c t u r ef o rf l a s hd i s k s ，c a l l e dh a s h t r e e i i i a b s t r a c t ( 2 ) w ei n t r o d u c eat u n i n gm e c h a n i s mi n t ot h eh a s h t r e es ot h a tw ec a n o b t a i n a p p r o p r i a t e t r a d e - o f fb e t w e e ns e a r c h p e r f o r m a n c e a n du p d a t e p e r f o r m a n c e ( 3 ) w ea n a l y z et h eu p d a t ec o s to fh a s h t r e ea n dd i s c u s ss t r a t e g i e st og e t o p t i m a lp e r f o r m a n c eo v e rd i f f e r e n ts s d s k e yw o r d s ：f l a s hm e m o r y ；s s d ；i n d e xm a n a g e m e n t ；h y b r i ds t r u c t u r e i v 图目录 图目录 图1 1 s l cv s m l c 3 图1 2n a n d 型闪存芯片的结构4 图1 3闪存存储系统架构7 图1 4 各种闪存文件系统的比较。8 图1 5f t l 中各种模式映射示意图9 图2 1 基于闪存的索引关系图1 5 图2 2b f t l 的索引结构1 9 图2 3结点转换表示意图2 0 图2 4i b s f 的索引结构2 0 图2 5f d t r e e 的索引结构。2 1 图3 1读写粒度为2 k b 和5 1 2 k b 时，随机读、随机写、连续读和连续写的带 宽比较2 4 图3 2h a s h t r e e 的索引结构2 6 图3 3实验结构图3 3 图3 4h a s h t r e e 参数对性能的影响3 4 图3 5 均匀负载下三种索引的性能比较3 5 图3 6 均匀负载下三神索引的整体性能比较3 6 图3 7 不均匀负载下三种索引的整体性能比较3 7 图4 1三种s s d 的带宽比较( r n d r d 、s e q r d 、r n d w r 和s e q - w r 分别 代表随机读、顺序读、随机写和顺序写) 4 0 v i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：恤 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 母么开口保密( 年) 作者签名： 堑 虹 导师签名： 签字日期：竺! ! ：至签字日期：2 亟二! ：! 鱼至 第1 章绪论 1 1引言 第1 章绪论 闪存( f l a s hm e m o r y ) 诞生于2 0 世纪8 0 年代末，作为一种新型的非 易失存储介质，具有高速、抗震、功耗低以及小巧轻便等优良特性。闪存 作为一种纯电子设备，能够解决传统磁盘i o 操作中的机械延迟。因此， 闪存的用途越来越广泛，已经从最初局限于嵌入式系统和便携式设备( 如 m p 3 、p d a 、p m p 、h p c 、d c 、d v 、手机、u 盘等) ，发展到现在已经 开始作为一种二级存储设备( 固态硬盘) 应用于计算机系统中，并逐渐应 用到企业级计算环境中。随着闪存制造工艺的发展，闪存的容量逐渐增大， 使得目前的固态硬盘的容量也随着增长，目前市场上已经出现t b 级的固 态硬盘产品。 数据库作为应用广泛的数据管理工具，随着闪存取代磁盘作为二级存 储设备，数据库不可避免的需要移植到闪存上。但是由于闪存的硬件特性 使得其具有某些特有的限制，比如闪存的读写速度呈现不对称性、n a n d 闪存中由于原位更新代价过大一般采取换位更新以及闪存中每个页都具 有擦除次数的限制等，如果直接利用传统的数据库技术会使得其性能( 特 别是更新性能) 不能获得相应于闪存和磁盘i o 性价比值而带来的提高 ( l e eswe ta l2 0 0 7 ) 。在某些情况下，甚至会获得比磁盘上还差的性能。 因此，建立以闪存为二级存储设备的数据库管理系统( f l a s h b a s e dd b m s ， 闪存数据库) 是目前闪存数据管理研究的主流研究方向。 索引结构是有效组织数据库中的数据、提高数据库查询性能的关键技 术之一，因此索引是数据库中必不可少的结构之一。将基于磁盘的传统索 引技术直接应用到闪存上并不能充分发挥闪存的优势，会使得索引的更新 性能低下，同时会直接影响闪存寿命。因此，本文将研究适合闪存物理特 性的高效索引结构。 在本章剩余部分安排如下：1 2 节将介绍闪存及固态硬盘的物理特性， 1 3 节介绍闪存数据管理的研究方向，1 4 节简单介绍本文的主要工作，1 5 节介绍本文的结构的章节安排。 第1 章绪论 1 2 闪存及固态硬盘 1 2 1 闪存芯片及物理特性 目前市场上闪存存储器中采用的闪存芯片主要有两种类型，即n o r 型闪存芯片和n a n d 型闪存芯片。美国的i n t e l 公司于1 9 8 8 年首先开发出 了n o r 闪存技术，由于n o r 芯片简单易编程并且支持单字节的独立读写， 于是很快广泛应用于嵌入式系统，从而改变了e p r o m 和e e p r o m 一统天 下的局面。紧接着，在1 9 9 0 年左右，日本的东芝公司提出了n a n d 型闪 存芯片结构，n a n d 型芯片将读写接口由n o r 型芯片的字节型改为按块 存储( n a n d 型闪存芯片的读写单位为一个页( p a g e ，类似于磁盘的扇区) ) ， 具有类似与磁盘的块设备接口。n a n d 型闪存芯片的存储单元结构特征使 得其拥有更高的存储密度( n o r 型芯片的存储单元要比n a n d 大2 5 倍) ， 因此相应地降低了存储成本。 n a n d 芯片的存储单元主要分为两类：s l c ( s i n g l el a y e rc e l l ) 和 m l c ( m u l t i l e v e lc e l l ) ，如图1 1 所示( m a r c oa 。a ，s a n v i d oe ta l2 0 0 8 ) 。 s l c 的特点是成本高、容量小、速度快，而m l c 的特点是容量大成本低， 但是速度慢。2 0 0 6 年，第一块2 - b i tm l c 芯片( 2 xm l c ，即一个存储单 元可以存储2 b i t 数据) 问世，同时3 x 和4 xm l c 芯片也相继出现。图1 1 左半图是s l c 芯片单元电压分布示意图，s l c 只有两个电压符，因为它只 有两个状态( 0 或1 ) 。所以从s l c 芯片中读取数据，只需要和一个电压 阈值进行比较，但是在2 xm l c 芯片中( 图1 1 右半图所示) 有四个状态 ( 0 0 ，0 1 ，1 0 ，1 1 ) ，所以存在三个电压阂值( 对于4 xm l c 芯片有1 5 个电压阈值) 。同时，由于每个m l c 存储单元中存放的数据较多，结构 相对复杂，出错的几率也相应增加，因此必须利用校验码( e r r o r c o r r e c t i n g c o d e s ，e c c s ) 进行错误修正，这个动作导致其性能大幅落后于结构简单的 s l c 闪存。此外，s l c 闪存的优点是擦除次数高达1 0 0 0 0 0 次，比m l c 闪 存高出1 0 倍。所以，为了保证m l c 的寿命，控制芯片通过磨损均衡算法， 使得每个存储单元的写入次数可以平均分摊，达到1 0 0 万小时故障间隔时 间( m t b f ) 。 2 第l 章绪论 雌从 围1 1s l cv sm l c n a n d 闪存是由一系列独立的闪存块( b l o c k ，又称擦除块) 组成的( 如 图12 所示( m a r c o aase ta l2 0 0 8 ) ) ，而块也是闪存进行擦除操作的 最小单元。对块进行擦除操作通常耗时较长，s l c 设备一般需要i5 - 2 m s ； 而在m l c 设备中通常时间更长，一般为3 m s 左右。每个闪存块包含固定 数目的页( p a g e ) ，s l c 的每个块中通常有6 4 个页，而m l c 一般为1 2 8 。 s l c 中每个页的大小为2 k b ，而2 x m l c 中页大小可以达到4 k b 。每个页 都有一定的附加空间( s p a r ea r e a ，s l c 为6 4 b y t e s ，m l c 为2 1 8 b y t c s ) ， 存储管理系统可以在附加空间中存储数据校验码、时间戳以及一些元数据 等信息。n o r 和n a n d 闪存的数据存取性能总结如表1l 所示 表1 in o r 闪存与n a n d 闪存的数据存取性能对比 类型 模式读 写 擦除 单位 w o r d ( 2 8 ) w o r d 犯b 1 b l o c k ( 6 4 r m ) n o r 速度9 9 s 7 0 0 m s 单位 p a g e ( 2 k b )p a g e ( 2 k s ) s l c n a n d0 2 s k b ) 速度 2 5 p s 单位 p a g e “k b )p a g e ( 4 k b ) ( 5 1 2 k b ) 伫x m l c )速度 5 0 p s 与传统磁盘相比较，n a n d 型闪存苍片特有的物理特性可以总结如下： i ) 无机械延迟，即没有寻道时间和旋转时间； 2 )读操作，写操作，擦除操作的速度呈现不对称性，读操作明显快于 写操作和擦除操作，而擦除操作是所有操作中速度最慢的： 3 )由于闪存的写操作的操作页面的状态必须为已擦除。因此在 n a n d 闪存中，原位更新代价过大，一般采取换位更新； 4 )n a n d 闪存块具有擦除次数的限制，当块的擦除次数超过限制 后将成为坏块，变得不再可靠。 第1 章绪论 掣 ls 呻一 h h l $ 1 m r 一 卜 。 ：a j 叫一- 二 。叠| i i 一 i厂 l 圈1 2n a n d 型c 日存芯片韵结构 闪存已经在电子消费产品领域获得了广泛的应用，如m p 3 、p d a 、p m p 、 h p c 、d c 、d v 、手机、u 盘等诸多产品都将闪存作为其存储设备，最近 闪存豹应用也逐渐向个人电脑和企业计算环境下发展。固态硬盘是闪存作 为存储用途的一种常见的产品形式，目前应用非常广泛，并且有取代磁盘 作为一种新的二级存储设备的趋势。 122 固态硬盘 固态硬盘是闪存用作存储用途的一个非常常见的产品形式，与磁盘区 别较大。磁盘主要是由用来保存数据的磁介质和磁头组成，通过磁头的转 动来完成数据的读写操作；而固态硬盘则完全不同，没有任何的机械部分， 因此固态硬盘相对于磁盘有较好的访问延迟。这使得固态硬盘能够像磁盘 取代磁带一样来取代磁盘作为一种新的二级存储设备，特别是在数据密集 型的环境下，比如数据库以及企业计算环境。固态硬盘相对于磁盘有根多 优良的特性，主要表现在阻下几个方面： ( 1 ) 高速 相对干磁盘而言，固态硬盘没有机械寻道和旋转过程，因此数据读写 速度都有了显著的提高。最近几年，随着闪存的制造工艺的发展，很多厂 商都推出了高性能、大容量的固态硬盘产品。如2 0 0 9 年o c z 推出的一款 v e r t e x 系列的2 5 6 g 的固态硬盘，读取和写入速度分别能达到2 5 0 m b s 和 第1 章绪论 1 6 0 m b s 。 ( 2 ) 抗震 由于固态硬盘内部不存在任何机械活动部件，不会发生机械故障，也 不怕碰撞、冲击、振动。这样即使在高速移动甚至伴随翻转倾斜的情况下 也不会影响到正常使用，而且在笔记本电脑发生意外掉落或与硬物碰撞时 能够将数据丢失的可能性降到最小。因此可以在恶劣环境下稳定地工作。 ( 3 ) 体积小，重量轻 由于固态硬盘内部不存在类似于磁头的机械设备，数据读取不需要像 传统的磁盘存储器那样旋转机械磁头，因此具有体积小，重量轻的特点。 ( 4 ) 低功耗 由于没有磁头等机械部件的运动，闪存在节能省电方面优势突出。如 o c zv e r t e x 系列2 5 6 g 的固态硬盘工作时的功耗为2 w ，空闲时的耗电量 仅有0 5 w 。 虽然各款固态硬盘都具有以上各种优良特性，但是不同的固态硬盘之 间的读写性能差异还是很大，主要取决于底层闪存芯片的类型( s l c 还是 m l c ) 和控制总线上并行的级别。市场上第一代的s a t a 接口的固态硬盘 虽然有较好的读写延迟，但是没有很好的读写吞吐量( 特别是随机写入吞 吐量，小于2 0 m b s ) 。因此第二代的固态硬盘产品着力于提高读写吞吐 量的问题，将随机写入吞吐量提高到4 0 m b s 一2 5 0 m b s ( 取决于固态硬盘 的价格) 。我们将第一代的固态硬盘产品称为低端固态硬盘 ( 1 0 w p e r f o r m a n c es s d ) ，而相应将价格较高的第二代固态硬盘称为高端 固态硬盘( h i g h p e r f o r m a n c es s d ) 。显而易见的是，高端固态硬盘虽然性 能优于低端产品，但是价格也远高于低端固态硬盘。 固态之间性能存在一定的差异性，因此在基于固态硬盘研究的算法中 必须考虑这种差异性。比如，固态硬盘相对于磁盘有一个显著的i o 特性， 那就是连续写性能优于随机写性能，但是连续写性能和随机写性能之间差 异的大小则完全由固态硬盘本身决定。因此，如果算法中利用了相关特性 的话，则必须考虑这样差异性对算法性能的影响。 1 3闪存数据管理 1 3 1概述 在传统的存储体系结构中，内存位于磁盘之上，但是磁盘和内存之间 第1 章绪论 的性能和价格存在巨大的差异。固态硬盘作为一种持久性存储设备，由于 其访问速度要比磁盘快，因此将固态硬盘作为的一种新的二级存储设备能 够减小这种差距。随着固态硬盘取代磁盘作为一种新的二级存储设备，基 于闪存的数据管理问题将是提高系统性能的关键。 目前基于闪存的数据管理的研究领域主要涉及存储管理、索引管理、 缓冲区管理等方面。从体系结构来看( 如图1 3 所示) ，闪存的索引管理 位于存储管理之上，设计系统的索引结构时需要考虑系统存储管理的实现 方法。因此，接下来将介绍目前闪存存储管理的相关研究方法和研究现状。 1 3 2 闪存存储管理 闪存存储管理的主要目的是为上层应用提供硬件抽象，目前闪存的存 储管理主要有两类方法：一类是在传统文件系统( 如e x t 2 、f a t 以及n t f s 等) 和闪存之间加入闪存转换层( f t l ，f l a s ht r a n s l a t i o nl a y e r ) ，从而屏 蔽闪存器件特征，使得闪存具有与磁盘类似的i 0 接口。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 e 2 0 0 1 ) 、y a f f s ( a l e p hol2 0 0 2 ) 和c f f s ( s e u n gh l2 0 0 6 ) 等。 两类方法各有利弊，f t l 方法虽然实现简单，但是由于上层文件系统 并没有针对闪存进行任何优化( 比如f t l 不能识别操作系统的删除操作 ( s a ikme ta l2 0 0 9 ) ) ，从而影响了存储管理系统的性能。针对闪存优 化的文件系统则能非常好的利用闪存各种物理的特性，从而使闪存能取得 较好的读写性能，但是实现较为复杂。 6 第l 章绪论 i n d e xs n l l c t u r e 彗簧里禽 弋夕弋夕 么 么、 ( f l a s ht r a n s l a t i o nl a y e r 一一耻飞。7。7 f l a s hd r i v e r f l a s hm e m o r y o n t 图1 3 闪存存储系统架构 ( 1 ) 闪存文件系统 j f f s ( j o u r n a l i n gf l a s hf i l es y s t e m ) ( w o o d h o u s e2 0 0 1 ) 结合闪存的特 殊属性，对传统的日志文件系统( 1 0 9 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 m e ta 1 19 9 2 ) ) 进行了简化，是一种纯日志文件系统。日志文件系统的主要 的设计思想就是管理文件系统的变化。j f f s 2 是目前比较稳定的j f f s 版 本，j f f s 2 中写操作以结点为单位，而结点通常由一些文件数据、索引节 点编号、在文件中的逻辑偏移、数据长度以及版本号组成。因此j f f s 2 的 写操作简单并且速度较快，但是进行文件读操作时需要寻找与该文件相关 的所有节点并进行重构。j f f s 2 在挂载时需要扫描所有闪存空间并在内存 中构建文件系统的元数据。因此，启动时间将随着闪存空间大小线性增长， 并且内存占用也线性增长，所以，j f f s 2 扩展性不强，不适用于容量较大 的n a n d 芯片。为了解决j f f s 2 中存在的问题，y a f f s ( y e ta n o t h e rf l a s h f i l es y s t e m ( a l e p hol2 0 0 2 ) ) 作为另外一种基于闪存的文件系统在启动 时间和内存占用上都有明显改进。y a f f s 中每个文件都有一个专门的页面 来存放文件头，并且利用闪存页中的剩余空间( s p a r es p a c e ) 来存储文件 系统相关内容。因此，y a f f s 在启动时只需要扫描部分闪存页以及所有闪 存页的剩余空间，启动时间相对j f f s 2 减少较多。 7 第1 章绪论 嚣；嚣钝i c 钎“舶晰”。0 7 i ! ，制1 ，蹙， 固1 4 各种闲存文件系统的比较 c f f s ( s e u n ghl2 0 0 6 ) 中则考虑了文件系统的特性，比如文件系统 中元数据和文件数据之间的不同特性等( 文件系统的元数据大小较小且经 常修改和访问) ，因此将文件系统中的元数据和文件数据在闪存上分开存 储，从而在一定程度上实现冷热聚类存储( 文件系统的元数据由于经常访 问，因此相对较热) ：并且c f f s 在每个i n o d e 结点中存储所有的所有记 录，从而减少闪存页的扫描操作。在p f f s ( y o u n g w o op2 0 0 8 ) 中则引入 新的硬件p r a m ( p h a s e c h a n g er a m ) 与闪存组成混合存储系统系统，通 过p r a m 来存储文件系统的元数据。p r a m 作为下一代存储设备，具有支 持字节写操作并且访问读写速度比闪存更快的优点。因此，p f f s 在启动阶 段不需要进行任何闪存负扫描操作，并且内存占用也非常低。 各种闪存文件系统( j f f s 、y a f f s 、c f f s 和p f f s ) 执行文件访问操 作的步骤及扫描区域的比较如图14 所示( k y u i lpe ta l2 0 0 8 ) 。 ( 2 ) 闪存转换层 调存的特殊硬件特征，也就是闪存页在重写前必须擦除其所在的整个 块( e r a s e b e f o r e w r i t e ) ，使得其需要闪存转换屠( f t l ) 掩饰闪存的异地 更新特性，从而使闪存具有与磁盘类似的i o 接口。f t l 层主要包含三个 主要功能：地址映射( a d d r e s st r a n s l a t i o n ) 、空闻分配( s p a c ea l l o c a t i o n ) 和垃圾回收( g a r b a g ec o l l e c t i o n ) 。 第1 章绪论 p 均- l 吼自b c - ( a ) p a g e l e v e lf t ls c h e m e( b ) b l o c k l e v e lf t ls c h e m e ( c ) h y b r i df t lsc h e m e 图1 5f t l 中各种模式映射示意图 闪存转换层中的三个部分中对其性能影响最大的是地址映射，地址映 射在上层文件系统中的逻辑地址和底层闪存的物理地址之间建立映射关 系。地址映射方法主要可以分为三类：页级地址映射( 如图2 3( a ) 所 示) 、块级地址映射( 如图2 3( a ) 所示) 和混合型地址映射( 如图2 3 ( a ) 所示) ( a a y u s hg e ta l2 0 0 8 ) 。在页级映射中( a m i rb1 9 9 5 ) ，每 一个逻辑地址都独立映射到一个物理地址上。在这种情况下进行写操作 时，f t l 首先选取一个可用的物理闪存页，并将数据写入该页中，同时改 变映射表的映射关系将逻辑页映射到新的物理页上。如果f t l 在上述过程 中找不到空闲页，则需要执行垃圾回收操作。页级地址映射技术的优点是 底层写操作实现简单，缺点是地址转换表较大，存在内存消耗问题。为了 解决内存消耗问题，块级映射技术应用而生( a m i rb1 9 9 9 ；t a k a y u k is 1 9 9 9 ) 。块级映射技术的主要思想是在逻辑块和物理块之间建立映射关系， 同时逻辑块和物理块中相应的闪存页需要一一对应，也就是说具有相同的 偏移。显然，块级映射技术大大较少了地址转换表的内存占用，但是如果 需要对块中的某个页中重复执行写操作的话，则每次重复写操作都需要擦 9 第1 章绪论 除并重写整个块，会带来非常高的拷贝和擦除代价。而混合型映射技术 ( j e s u n gk e ta l2 0 0 2 ；s ejke ta l2 0 0 8 ) 则综合了页级映射技术和块级映 射技术的优点，首先利用块级映射技术获取相应的物理块地址，然后再利 用页级映射技术在该物理块中获取一个空闲的物理页。混合型映射技术既 解决了页级映射技术中内存占用的问题，同时由于采用了块内页级映射技 术使得其拷贝和擦除代价大大降低。 1 3 3闪存索引管理 索引结构作为有效组织系统中的数据、提高系统的查询性能的关键技 术之一，是数据管理系统中必不可少的结构。 闪存具有读写速度不对称性( 读快写慢) 、不可重复写( 异地更新) 以及擦除次数有限等特点，从而为基于闪存的高效索引的设计带来了很多 新的挑战。传统的索引结构并没有考虑闪存的i o 特性，所以直接将传统 索引移植到闪存上，肯定无法充分的利用闪存高性能的特点。比如，当我 们使用传统的索引方法更新一个键值时至少需要重写一个闪存页( 因为闪 存写操作的最小单元为一个页) ，很显然会使得索引更新性能低下，同时 这种更新方法会带来大量的擦除操作，而这种擦除操作的增加会直接影响 到闪存寿命。由此可见，基于闪存的索引结构必须要考虑闪存读写操作的 不对称性以及擦除次数限制等特性，并且需要尽量的减少索引结点更新时 所引起的写操作和擦除操作。 目前闪存作为存储用途的主要产品形式是固态硬盘，而固态硬盘作为 一种闪存的封装形式，虽然具有闪存芯片的一些物理特性，比如读写具有 不对称性以及擦除次数限制等，但是固态硬盘也有自身的一些物理特性。 因此，考虑应用于固态硬盘环境的索引结构时，还需要考虑固态硬盘所具 有的i o 特性，比如固态硬盘的连续写性能优于随机写性能等。由于固态 硬盘应用范围广泛，针对固态硬盘优化的闪存索引结构也是目前研究的趋 势。 1 4 本文的工作 为了解决上面提到的问题，已有不少研究者提出各种基于闪存和固态 硬盘的索引结构，在总结已有的基于闪存的索引结构的创新点以及其存在 的问题后，本论文将提出一种新的更加高效的针对固态硬盘优化的索引结 构，索引设计中结合哈希类索引和树类索引的优点，使其能够更好的适应 1 0 第1 章绪论 各种工作负载，并且讨论其高效应用于目前市场上已有的低端、中端以及 高端固态硬盘上的的策略。 1 5 本文的组织 本文余下部分的组织结构如下： 第二章首先简单介绍目前闪存索引研究的概况，然后重点介绍几种写 优化闪存索引的结构和其优缺点。 第三章针对固态硬盘的i o 特性以及目前基于固态硬盘的索引结构存 在的问题，提出结合树类索引和哈希类索引特性的混合结构索引 h a s h t r e e 。h a s h t r e e 通过哈希策略和可变参数厂使得f t r e e 变小，从而使 得f t r e e 进行合并操作时写操作数变少。而且，h a s h t r e e 中通过临界高度 控制f t r e e 的高度从而获得较好的查询性能。实验中比较了h a s h t r e e 和 b f t l 以及f d t r e e 的性能，并对实验结构进行了具体分析。 第四章分析了h a s h t r e e 索引的更新代价，并在此基础上对h a s h t r e e 在各种固态硬盘上通用性的问题展开了相关研究和分析。 第五章对本文所做的工作进行了总结，并展望了未来的研究方向。 第2 章基于闪存的索引管理 2 1 引言 第2 章基于闪存的索引管理 闪速存储器( f l a s hm e m o r y ，简称闪存) 诞生于2 0 世纪8 0 年代末， 由于它具有高速、低功耗、抗震、小巧轻便等优良特征，已经在嵌入式系 统以及便携设备中取得广泛应用，并且应用范围有向笔记本电脑以及企业 级计算环境延伸的趋势。闪存作为一种新型的电子存储设备，具有较高的 访问速度和无机械延迟的特性，使得它成为替代磁盘的首选存储介质。图 灵奖得主j i mg r a y 在2 0 0 6 年就明确提出“就像磁盘取代磁带一样，闪存 将会取代磁盘”( j i mg r a y2 0 0 6 ) 。 随着固态硬盘取代磁盘作为一种新的二级存储设备，数据库管理系统 将不可避免的移植到固态硬盘上，而索引结构作为有效组织数据库中的数 据、提高数据库的查询性能的关键技术之一，是数据库中必不可少的结构。 如果将基于磁盘的传统索引技术直接应用到闪存上并不能充分发挥闪存 的优势。崔斌等( 2 0 0 9 ) 通过实验发现b + 树索引结构在未针对闪存优化的 情况下，基于闪存的b + 树索引更新操作已经略快于磁盘，因此b + 树索引 结构针对闪存的特性进行优化后性能应该有非常大的提升空间。 本章接下来首先简单介绍目前闪存索引研究的概况，然后重点介绍几 种写优化闪存索引的结构和其优缺点。 2 2基于闪存的索引管理 索引管理在体系结构上位于存储管理之上，因此存储管理所采用的方 式( 文件系统或者f t l ) 将直接影响索引结构设计。目前，基于闪存的索 引研究从存储管理的角度大致可以分为两大类：一类是底层存储管理采用 闪存转换层，此时f t l 屏蔽了闪存的硬件特性，f t l 中通过地址映射在闪 存物理地址和上层应用程序的逻辑地址之间建立映射，因此上层应用程序 不能直接管理闪存的物理地址，也就是说这种情况下只能在逻辑地址上建 立索引；而另一类是底层存储管理采用闪存文件系统，此时上层应用程序 可以通过文件系统管理闪存的物理地址，因此这种情况下可以在闪存物理 地址上建立索引。前一种方法可以不用考虑闪存底层的存储管理部分，直 接在闪存转换层上考虑索引的设计，而目前固态硬盘作为闪存的应用产品 1 3 第2 章基于闪存的索引管理 形式，已经将闪存转换层固化在硬件层上，使得其能够在目前的操作系统 下像磁盘一样直接应用。因此，考虑将固态硬盘作为存储设备来建立索引 的话，只能利用前一种方法考虑在逻辑地址上建立索引；而后一种方法则 主要应用于闪存文件系统内部或者缺少闪存转换层和文件系统支持的环 境下。基于闪存的索引关系图如图2 1 所示。 2 2 1基于物理地址的闪存索引 当考虑在物理地址上建立索引时，则需要考虑存储方面的细节问题。 由于这类索引结构的应用范围具有很大的局限性，目前这类索引研究并不 多见。这类闪存索引结构主要是利用闪存芯片的物理特性( 如读写擦除 操作的粒度等) 来减少索引操作的代价。 韩国科学技术院( k a i s t ) 的k a n gd e ta l ( 2 0 0 7 ) 提出了“t r e e 索引 结构，主要是针对b 树索引中叶结点更新所引起的所在路径上所有索引结 点的级联更新问题( 主要是由闪存的换位更新造成) 。p t r e e 索引中将b 树一条路径上所有的索引结点存储到同一个物理闪存页中，由于闪存的写 操作粒度为页，所以一定程度上避免了结点的级联更新，从而提高了索引 的更新性能。但是t r e e 的结点大小由闪存页面大小和结点所在层次决 定，且闪存中可能存储结点的多个版本，导致空间利用率不高，同时“t r e e 不能支持范围查询。 韩国成均馆大学的g a p j o on a 等人利用i p l 存储方法存储b + 树索引从 而提出了i p lb + t r e e ( n agje ta l2 0 0 9 a ) ，i p l 的主要思想是将数据页 和其相关的日志存储在同一个块中，i p lb + t r e e 就是利用i p l 思想来提高 b + t r e e 的更新性能。随后作者又对i p lb + t r e e 进行改进，提出了d i p l b + t r e e 索引结构( n agje ta l2 0 0 9 b ) ，主要是解决i p lb + t r e e 中出现 结点分裂操作时由于产生日志过多导致日志经常溢出的问题，因此，在 d i p lb + t r e e 中通过动态调整日志区域的大小来解决日志频繁溢出的问 题，从而进一步提高b + 树索引在闪存上的更新效率。 1 4 第2 章基于闪存的索引管理 i d y n a m i ch a s h ；! l! ： ，：s e n s o r - b a s e di n d e x ；： i 哈希类索引；! ，。- 一- _ | 一一_ ，。一一_ ： ，i ，一一- 一 - i l ；b f t l i b s f! l 、 i ! f l a s hd b ；! 。、 ；：l a z yu p d a t eb + - t r e e i 、 ：i f t r e e 一，c h c 1 h e ；： ，：f d t r c e树炎索弓i ；： f l a s h i i b a s e d 一；：犟予逻辑地址的闪存索弓i ： i n d e x 、- - - - l ； ：r 一一一一一一一一一一一一一一一一