（计算机科学与技术专业论文）引入flash的多层次存储结构研究与实现.pdf

国防科学技术大学研究生院硕十学位论文 摘要 在整个计算机系统中，存储系统已成为一大瓶颈，传统的磁盘因为它巨大的 延迟越来越不能满足应用的需求。新近发展起来的f l a s h 存储介质因为延迟小、功 耗低、质量轻，能在恶劣环境下工作，受到存储界的青睐。但是目前，f l a s h 的容 量无法与磁盘相比，价格也很高，完全用f l a s h 构建存储系统是不经济的。因此， 用f l a s h 和磁盘构建混合的存储系统具有重大意义。 本研究针对大型存储系统中的i o 结点，在传统的存储器层次结构中引入 f l a s h ，构建一个混合的存储系统。整个工作分三部分。第一部分设计了一种高效 能、自适应的缓存替换策略，用来管理存储层次中的d r a m 。该策略具有常数的 时间复杂度。尽管具有一定的计算量，但是，由于该策略专用于计算资源较充足 的存储系统，增大计算量换取更高的命中率是值得的。第二部分设计了 d r a m f l a s h 二级缓存的管理策略，该策略的目的是用f l a s h 扩展d r a m 。因为 f l a s h 比d r a m 便宜，该策略实质上是用一种经济的方法增大了主存容量。第三部 分构建了混合辅存结构，这部分的工作包括设计高性能的s s d 、研究s s d 和磁盘 的协同原理、制定辅存中的数据预取机制。三个部分从上到下，涉及到混合存储 系统的各个层次，是一个完整的系统，重点研究了整个混合存储系统中各级之间 的缓存替换与预取策略。 主题词：存储系统，缓存替换，混合存储结构，$ s d ，f l a s h 第i 页 国防科学技术大学研究生院硕十学位论文 a b s t r a c t t h es t o r a g es u b s y s t e md r a g g l e sm o r ea n dm o r ei nt h ew h o l ec o m p u t e rs y s t e m b e c a u s eo ft h eh i g hl a t e n c y ，m a g n e t i cd i s k sc a n tm e e tt h ed e m a n do fa p p l i c a t i o n s g r a d u a l l y a san e ws t o r a g em e d i a ，f l a s hc a t c h sp e o p l e se y e sb yt h el o wl a t e n c ya n d e n e r g y - c o n s u m i n g h o w e v e ra tp r e s e n t ，f l a s hc a n th a sa sl a r g ec a p a c i t ya sd i s k s ，a n d w h a tm o r e ，t h ep r i c eo ff l a s hi st e nt i m e sa sd i s k s e n t e r p r i s e sc a n ta f f o r das t o r a g e s u b s y s t e mb u i l tw i t hf l a s hp u r e l y s o ，w el a u n c ho nt h eh y b r i ds t o r a g es y s t e m i n t e g r a t i n gd i s k sw i t hf l a s h t h i sr e s e a r c hp a y sa t t e n t i o nt ot h ev e r yo n ei on o d ei nal a r g e s c a l es o r a g es y s t e m w ei n s e r tf l a s hm e d i ai n t ot h em u l t i - l e v e ls t o r a g eh i e r a r c h yt ob u i l dah y b r i ds t o r a g e s y s t e m t h ew h o l ew o r kc a nb ed e v i d e di n t ot h r e ep a r t s f i r s t l y ，w ed e s i g nah i g h p e r f o r m a n c e 、a d a p t i v ec a c h er e p l a c e m e n tp o l i c yt oa d m i n i s t e rt h ed a t ai nd r a m t h e p o l i c yh a sc o n s t a n tt i m e c o m p l e x i t y a l t h o u g h ，t h ep o l i c yn e e d sa m o u n to fc a l c u l a t i o n ， a st h ep o l i c yd e d i c a t e st ot h es t o r a g es y s t e mw i t ha d e q u a t ec o m p u t i n gr e s o u r c e ，i ti s w o r t h yo ft r a d i n g s u r p l u sc o m p u t i n gr e s o u r c e 、析t hh i g h e rh i t - r a t i o s e c o n d l y w ed e s i g n am u l t i l e v e lc a c h em a n a g e m e n tp o l i c yt oe x t e n dt h ec a p a c i t yo fd r a m b yf l a s h a s t h ef l a s hi sc h e a p e rt h a nd r a m ，t h ep o l i c ym a k e sa ne c o n o m i c a lw a yt oe x p a n dt h e c a c h eo fas t o r a g es y s t e m t h et h i r dp a r tb u i l d st h eh y b r i ds t o r a g ed e v i c e 、 r i t hs s da n d d i s k s t h i sp a r to fw o r kc o n t a i n st h ed e s i g no fah i g hp e r f o r m a n c es s d 、c o l l a b o r a t i n g t h es s dw i t hd i s k sa n dt h ep r e f e t c hm e c h a n i s mi nt h eh y b r i ds t o r a g ed e v i c e t h ew o r k i n v o l v e sa l lt h eh i e r a r c h i e si nt h es t o r a g es y s t e m i ti sac o m p l e t er e s e a r c ha b o u tc a c h e r e p l a c e m e n ta n dp r e f e t c hp o l i c yi nt h eh y b r i ds t o r a g es y s t e m k e yw o r d s ：s t o r a g es y s t e m ，c a c h er e p l a c e m e n tp o l i c y ，h y b r i ds t o r a g e a r c h i t e c t u r e ，s s d ，f l a s h 第i i 页 国防科学技术大学研究生院硕十学位论文 表 目录 1 1d r a m 、f l a s h 、磁盘性能比较7 2 1t r a c e 特性分析1 7 2 2m 的取值1 9 3 1 r a m 与f l a s h 容量均取2 5 6 m 一3 0 3 2 王乙气m 与f l a s h 容量均取5 1 2 m 3 0 3 - 3r a m 与f l a s h 容量均取1 0 2 4 m 3 0 4 1 t r a c e 特性统计3 7 4 2h 值的统计5 0 4 3 顺序数据与零散数据的比例一5 1 4 4 顺序数据请求大小的分布5 6 4 5 顺序数据预取命中率5 7 第1 i i 页 表表表表表表表表表表表 国防科学技术大学研究生院硕+ 学位论文 图目录 图1 1多层次存储结构原理4 图1 2f l a s h 芯片存储单元的结构7 图1 3引入f l a s h 的多层次存储结构9 图2 1f b r 替换策略1 2 图2 22 q 替换策略13 图2 3a r c 替换策略13 图2 4s s a r c 原理图18 图2 5 两个页的紧急度1 8 图2 6 网络商店服务器上收集的t r a c e 实验结果2 0 图2 7p c 机上收集的t r a c e 实验结果2 0 图3 1m u l t i q u e u e 替换策略2 3 图3 2 二级缓存体系结构。2 6 图4 1 页表替换策略3 6 图4 2f i f o 队列占缓存大小的比例3 7 图4 3 预取度的确定3 8 图4 4 页表替换策略性能比较一3 9 图4 5 读请求队列与读请求栈4 l 图4 6 顺序编址与交叉编址一4 2 图4 7i o 调度示意图4 3 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题艮曼i 篁! 垒墨廷煎垒星达盔篮丝捡盈究皇塞理 一一一 学位论文作者签名： 窿志z 日期： 力。年，2 月z 7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：曼i 至! 垒墨塾的垒屋达壶篮结掐珏究皇塞理 学位论文作者签名： 臣圭：! 羔： 日期：劾岬年l 明2 7 日 储指导教师摊：聋眨 魄加种嗍2 7 日 国防科学技术大学研究生院硕士学位论文 1 1 1 存储发展现状 第一章绪论 1 1 研究背景 随着信息化建设的迅猛发展，计算机系统成为人类生活的基础设施。数据变 的像水和电一样，成为日常生活不可或缺的资源。人们对数据的依赖程度越来越 高。企事业单位的业务运行更是依赖于数据信息，其关键业务的数字化，使得存 储系统成为企业信息系统中最重要的组成部分。社会生活的数字化导致了数据的 爆炸式增长，据i d c 统计，2 0 0 7 年全世界共产生了2 8 1 e b 的数据，而到2 0 11 年， 数据量将达到1 8 0 0 e b ，年均增长6 0 l l 】。这些数据的7 0 来自个人数字设备，而 这类设备越来越普及，所以，总的数据量会保持持续增长。早期的计算机系统只 是把存储系统当作一个外部设备，而现在，存储已经成为i t 领域的一个重要发展 方向，拥有比计算领域更大的市场。存储终于从过去隐藏在计算和传输背后的技 术走到了前台。 1 1 1 1 存储需求 存储市场的蓬勃发展得益于社会对它同益增长的需求。石油、金融、电信、 生物技术、科学计算、数字影像、电子商务、远程医疗等行业和领域都是存储发 展的直接推动者。通过对多家企业的存储使用情况作调查发现i 引，2 0 0 7 年存储容 量在3 t b 以下的企业占5 3 1 ，在3 1 0 t b 之间的有2 1 9 ，l1 t b 以上存储容量 的企业只有1 0 ，还有部分企业的数据量没有确定。而到2 0 0 8 年，只有3 3 9 的 企业存储容量在3 t b 以下，在3 1 0 t b 之间的企业有2 7 7 ，l1 - 5 0 t b 之间的企业 有1 7 9 ，5 0 1 0 0 t b 之间的有1 0 6 ，在1 0 0 t b 以上的有9 9 。从这些比例的变 化来看，各企业数据的增长是很迅速的。在3 t b 以下比例减少1 9 2 的同时，3 1 0 t b 区间比例增加了5 8 ，1 1 t b 以上的比例增加了2 8 4 。据调查者分析，3 t b 以下 比例的减少主要还是表现在企业信息化建设的进步上。企业的发展规模不断扩大， 相应的业务系统也将得到不断的扩展，这使得数据量在短短的1 年时间里有如此 大的增幅，尤其是企业中一些非结构化数据的增长，成为数据增长的主要原因。 该调查小组还对存储需求的增长速度作了调查，发现有3 1 4 的企业认为他们每年 的数据增长在3 0 以下；有5 8 8 的企业认为其数据增长速度在3 0 1 0 0 之间；有 8 4 的企业认为其数据将大幅增长，增长在1 0 0 2 0 0 之间；还有1 4 的企业认为 数据在未来1 2 年内爆炸式增长。 当前，产生这么多数据的原因并不是数据库系统的爆炸式增长，而是那些邮 第1 页 国防科学技术大学研究生院硕士学位论文 件、文档、图片、影像等非结构化数据的人量增长。视频监控、娱乐、社交网络、 托管应用、政府存储、医疗归档等都是产生非结构化数据的大型系统。该调查小 组统计，在2 0 0 8 年，5 1 8 的企业拥有邮件服务器、即时通讯服务器，4 6 4 的企 业提供普通w e b 服务，3 5 8 的企业提供文件共享服务( w o r d 、p p t 、视频、图片 等共享) 。除了企业产生大量的非结构化数据，促使非结构化数据快速增长的更 重要因素是个人电子消费品的普及。摄像机、p d a 、手机等产生的大量流媒体信 息将占去很大的存储空间。据i d c 预测，到2 0 11 年，非结构化数据将会占用整个 存储容量的9 0 以上，其中由个人消费者自己去创建的信息又会占到7 0 以上。 总之，当今存储数据的特点是，容量呈爆炸式增长，且以不易管理的非结构 化数据为主。非结构化数据的增长不仅对存储容量提出了要求，还推动了存储技 术的革新。 1 1 1 2 存储技术 数据量的增大，各行业对存储的要求不断提高，使存储领域出现了很多技术 上的问题。据调查统计【2 j ，5 1 1 的企业出现存储设备f o 压力大，读写速度慢的 问题，2 9 6 的企业存储空间过小，2 9 2 的企业无法对存储设备进行有效地管理， 2 9 2 的企业发现数据过于分散不易管理，2 3 7 的企业无法忍受漫长的备份时间， 2 0 4 的企业因为大量空间不能有效利用而发生资源浪费，9 9 的企业抱怨存储耗 能太多。面对以上种种问题，出现了许多新的技术。 为了缓解存储系统的i o 压力，研究人员设计了高性能的磁盘驱动器，加快了 磁盘的转速。i s c s i 和f c o e ( f i b e rc h a n n e lo v e re t h e m e t ) 则试图为存储子系统提 供更快的通信协议。除此之外，还开发了新型的存储介质，如f l a s h 、p r a m ( 相变 随机存储器) 、m r a m ( 磁阻随机存储器) 、f r a m ( 铁电随机储存器) 等都具有很高的 读写性能。 为了应对存储容量的问题，磁盘存储密度越来越高，单盘容量超过l t 。企业 存储设备的使用方式从内置磁盘转化为n a s 、d a s ，并逐渐向s a n 演化。最后构 建了大型数据中心，迈向云存储。面对p b 级的存储管理，设计了大规模并行文件 系统。 针对管理复杂的问题，出现了存储虚拟化技术，包括对存储硬件的虚拟化、 互联网络的虚拟化以及在服务器操作系统级别的虚拟化。存储硬件的虚拟化技术 可以简化对于海量存储设备的管理，互联网络虚拟化简化了异构系统的构建，操 作系统的虚拟化可以实现安全隔离、错误隔离以及应用环境的隔离。最近提出了 云存储概念，所有数据存储在大型数据中心，各企业的数据管理更加容易。云存 储还能有效地利用存储资源，降低企业的运营成本。 研究发现，应用系统所保存的数据，高达6 0 是冗余的，而且随着时间的推 第2 页 国防科学技术大学研究生院硕士学位论文 移= f c 余越米越严重，最终可能要花费超过】0 倍的存储空f h j 矛u 管理成本【3 】。利用重 复数据删除技术，一方面可以优化存储空间的利用率，另一方面，可以减少在网 络中传输的数据量，降低能量消耗和网络成本。支持归档的单一实例存储、支持 快照的写时拷贝等技术，能进一步的删除冗余数据。 研究表明当前存储系统的能耗占整个数据中心i t 设备能耗的3 7 ，仅次于服 务器的能耗，在3 至5 年内存储系统运行所需的电费将超过其购置费用 4 1 。i d c 预 测2 0 0 9 年全球企业的存储能耗成本将超过2 0 亿美元【5 l 。目前，存储低能耗技术已 成为当前存储领域研究的热点。如何在尽量使性能不降低的前提下减少存储系统 的能耗是存储低能耗技术的核心问题。这方面的研究工作主要集中在内存低能耗 技术、磁盘低能耗技术、磁盘阵列低能耗管理、混合存储低能耗管理和精简存储 系统管理等几个方面。 存储系统的不断扩大，包含的磁盘越来越多，各种与磁盘相关的错误1 6 7 8 9 发生的越来越频繁。另外，分布式存储系统中各存储节点以及节点之间连接的失 败案例越来越多。存储系统面临的可靠性问题越来越严峻。为了防止大规模存储 系统中出现数据丢失或出错现象，确保存储的高可靠性，需要对存储系统的可靠 性进行研究。目前，这些研究主要集中于磁盘阵列的可靠性和分布式存储系统的 可靠性两方面。 1 1 2 主要的辅存介质 目前计算机系统中占统治地位的辅存介质是磁盘。磁盘是一种机械电子装置， 它由多个盘面和附加在盘面上的磁头组成。每个盘面表面分成5 0 0 0 到3 0 0 0 0 个同 心圆，被称为磁道。每个磁道被划分成1 0 0 到5 0 0 个扇区，扇区是最小的读写单 位，一般为5 1 2 字节。不同盘面上处在同一同心圆上的磁道构成一个柱面。磁盘 的工作原理是：当接收到读写请求时，根据读写地址启动相应的磁头，将磁头移 动到指定的柱面，接着旋转到指定的扇区，然后读取数据。这个过程要经历两次 机械延迟：寻道延迟和旋转延迟。寻道延迟一般在2 毫秒到1 2 毫秒之间，从磁盘 诞生的几十年来只有很小的改进。旋转延迟要小，若按1 0 0 0 0 r m i n 的转速计算， 平均旋转延迟为3 毫秒。而眼下，c p u 的时钟周期都在纳秒级，c p u 对磁盘的一 次数据请求需要等待百万个时钟周期，这对于i o 密集型应用来说是很难满足用户 要求的。但是，近年来，磁盘的容量增大很快，工业界努力提高盘面的面密度， 使单盘容量达到1 t ，目前磁盘仍然占据了绝对的市场份额。 磁带与磁盘采用同样的技术，作为计算机系统的一部分，其历史与磁盘一样 长，同时也具有相同的密度增长速度。磁带最突出的特点就是便宜，一般比相同 容量的磁盘便宜1 0 到1 0 0 倍。但也有很多缺点，如容易损坏、带宽低、只能进行 第3 页 国防科学技术大学研究生院硕十学位论文 秒级的顺序访问。因为具有如上特点，磁带一般用作数据归档和备份的二级存储 介质。近年来，由于磁盘的容量和价格优势越来越明显，磁盘逐渐取代磁带的功 用，使磁带的市场份额越来越小。 光盘也得到了广泛的应用。由于采用光学原理，具有很高的存储密度。光盘 容量大、价格低、便携，成为软件和流媒体发行的主要媒介。由于技术进步速度 快，而且已经出现了类似磁带机的光盘机柜，所以可以用作数据归档。光盘是磁 带的竞争对手。 以上几种主流辅存介质都含有机械装置，具有很大的启动延迟，与处理器的 速度相比落后百万倍，这就是造成“存储墙”的主要原因。辅存是整个计算机系 统的一个瓶颈。 1 1 , 3 多层次存储结构 为了缓解处理器与辅存速度差距太大的矛盾，系统研究者提出多层次存储结 构的概念。多层次存储结构的原理如图1 1 所示：在快速设备和慢速设备之间加一 级速度接近于快速设备的缓冲器，若把缓冲器和慢速设备看作一个整体，在快速 设备的视图中，这个整体的容量相当于慢速设备，而速度接近于缓冲器。一般说 来，缓冲器的价格很贵，但与慢速设备相比，缓冲器容量很小，这个整体的价格 接近于慢速设备。总之，多层次存储结构用一种经济的办法取得了高性能。 图1 1多层次存储结构原理 存储器层次结构重点关注四个问题：映射方法、查找策略、替换策略、写回 策吲j 。下面分别作简单介绍。 缓冲器只是零时地保存慢速设备的数据，映射方法确定了慢速设备与缓冲器 中地址单元的对应关系。有三种不同的映射方法：全相联、直接相联和组相联。 全相联就是慢速设备中任何单元的数据可以映射到缓冲器中的任何位置。它的优 点是映射灵活，缓存命中率高，但查找比较费时，一般用在对时间要求不高的软 第4 页 国防科学技术大学研究生院硕十学位论文 件系统中。直接柏联是指慢速设备中特定单元的数据只能映射剑缓冲器的唯一位 置，这个唯一位置一般是对慢速设备的地址求模得到。直接相联的优点是查找快， 只需要检查指定位置，但不够灵活，冲突失效率高。组相联介于直接相联和组相 联之间，这种机制将缓存划分成多个组，慢速设备特定单元的数据映射到缓存特 定的组中，然后在组内全相联映射。这种机制集成了直接相联和全相联的优点， 是一种折中策略。软件缓存一般采用全相联模式，处理器内部的硬缓存一般采用 直接相连或组相联模式。 上层的数据访问使用的是慢速设备的地址，当请求到达缓冲器时，要根据这 个地址确定是否在缓存中命中，这就是查找策略的任务。查找策略直接取决于映 射方法，如果是直接映射，则可以直接检验缓存中对应的地址；如果是全相联映 射，一般根据索引查找；如果是组相联映射，则根据慢速设备的地址确定数据在 缓存中的组，然后在组内根据索引查找。 缓存的容量小于慢速设备的容量，当缓存没有剩余空间，在新的数据从慢速 设备调换到缓存之前，需要将一些数据替换出缓存，选择淘汰哪些数据的策略就 是替换策略。简单的替换策略有随机选择、f i f o 、l r u l l 2 j 等。这部分的工作往往 还包含数据预取。 数据从快速设备写入缓存时，可以仅仅写入缓存，也可以在写入缓存的同时 写入慢速设备，前者被称为写回法，后者被称为写直达。当发生写缺失时，可以 将数据从慢速设备取到缓存，然后发生写命中，这种写策略叫按写分配；也可以 不经过缓存直接将数据写入慢速设备，这叫不按写分配。 这里以磁盘和主存这一层次为例，解释多层次存储结构的形式化描述。这一 级的映射方法是全相联映射，因为磁盘的任何单元都可以映射到主存的任何单元。 查找策略依赖于索引树，如页表、平衡树。在l i n u x 系统中，主存替换策略采用两 条队列的l r u 策略变种。因为磁盘速度太慢，c p u 写入主存的数据不能立即写到 磁盘，所以采用写回、按写分配策略。 存储器层次结构已广泛的运用于当前的存储系统，在c p u 内部已有两级缓存， c p u 与磁盘之间有d r a m ，大型存储系统上还有专门的缓存服务器。这些缓存的 速度、容量、价格各不相同，只有综合利用这些特点构建的多级存储器在速度、 容量和价格上才能满足应用的需求。本研究主要针对大型存储系统的单机结点， 其结构基础是在存储器层次结构中引入一种新的存储介质f l a s h ，所有的研究 均在d r a m f l a s h 磁盘这三个层次上展开，目的是改进整个存储器层次结构的速 度、容量和价格。由于这三个层次上的管理完全是软件行为，所以映射方法采用 最灵活的全相联映射，随之的查找策略就是索引查找，写回策略是写回法按写分 配，这些在本文的后面将不再提及，本研究的重点是层次结构上的替换策略。 第5 页 国防科学技术大学研究生院硕士学位论文 1 2 1f l a s h 的特性 1 2f l a s h 简介 f l a s h 是一种新型的半导体存储介质，它完全是一种电子装置，延迟低、体积 小、质量轻、无噪声、抗震动，其能耗只有传统硬盘的1 5 1 6 。f l a s h 首先被广泛 应用于嵌入式领域。近年来，由于制作工艺的进步，f l a s h 的容量越来越大，价格 越来越低，逐渐进入大规模存储领域。f l a s h 分n o r 和n a n d 两种类型，其中n a n d 型f l a s h 芯片成本低、容量大、存储密度高，较之n o rf l a s h 更适合大规模存储。 n a n df l a s h 分s l c 和m l c 两种类型，其中s l c 型可靠性好，m l c 型集成度高。 自2 0 0 1 年以来n a n df l a s h 芯片容量以每年翻一倍的速度递增。与此同时，n a n d f l a s h 价格也在以每年4 0 5 0 的速度递冽1 3 】。本研究只讨论n a n df l a s h ，若不 特别说明，以后提到的f l a s h 专指n a n df l a s h 。 f l a s h 的基本读写单位是页( p a g e ) ，多个页又组成块( b l o c k ) 。 页大小一般在 5 1 2 4 k 字节之间，为2 的整数次幂。每个页中都有6 4 字节的附加信息区域，该 区域可用来存放该页数据的元信息。每个块中有3 2 或6 4 个页。写入操作必须在 空白页进行，如果目标页已有数据，必须先将该页擦除，这一特性被称为“非定 点更新 ，擦除的基本单位是块。f l a s h 读性能良好，写延迟相对较大，写之前的 擦除操作比较耗时，对i o 性能有一定影响。而且每一块被擦除的次数有限，m l c 型f l a s h 擦除次数约为1 万次，s l c 型约为1 0 万次。 相对于磁盘，f l a s h 有一些固有的优势。 f l a s h 具有延迟小的特点。经过近三十年的发展，磁盘在单盘容量和读写速度 上进步很大，但其读写延迟始终没有得到显著改善，一直维持在毫秒级，这个时 间相当于c p u 时钟周期的百万倍。如果一个应用发出大量较小的随机请求，磁盘 是很难胜任的。而s l c 型f l a s h 的读延迟为2 5 微秒，远远优于磁盘。写延迟稍大， 为2 2 0 微秒，但由于写操作一般是异步的，所以对性能影响不大，这个延迟仍然 比磁盘的写延迟小一个数量级。擦除操作延迟在毫秒级，但擦除一般在后台进行， 且每次擦除一块，对读写性能的负面影响有限。 f l a s h 具有固有的并行性。目前单个f l a s h 芯片一般为2 g b ，要构建大规模存 储系统，必须将大量的芯片组织成阵列，而这些芯片间存在可观的并行性。另外， f l a s h 芯片内部也存在并行性。如图1 2 所示的f l a s h 芯片内部存储单元的结构，每 个芯片一般由若干个p l a n e 组成，每个p l a n e 包含大量的块，同一p l a n e 中的所有 块公用一个页大小的数据缓冲器。在读写数据时，数据必须先经过缓冲器，由缓 冲器等候读写延迟。不同p l a n e 中的存储单元可以并行的读写到各自的缓冲器中。 芯片间和芯片内的并行性为扩展f l a s h 的带宽提供了先决条件。 第6 页 国防科学技术大学研究生院硕十学位论文 图1 2f l a s h 芯片存储单元的结构 表1 1 【1 3 l 中对n a n df l a s h 、d r a m 和磁盘的性能进行了比较。比起d r a m ， f l a s h 的功耗要小的多，容量也大；比起磁盘，f l a s h 的读写延迟要小，尽管单片 f l a s h 带宽不如磁盘，但可通过增强并行性来弥补。总之f l a s h 的性能介于d r a m 和磁盘之间，这决定了本研究中f l a s h 在多层次存储结构中的位置和作用。 表1 1d r a m 、f l a s h 、磁盘性能比较 功耗 读延迟写延迟擦除延迟 运行空闲 1 gd d r 2 8 7 8 m w 8 0 m w 5 5 n s5 5 n sn a d r a m l g n a n d f l a s h ( s l c ) 2 7 m w 6 9 w2 5 t s2 0 0 9 s 1 5 m s h a r dd i s k 1 3 w9 3 w8 5 m s9 5 m sn a d r i v e 1 2 2f l a s h 研究现状 针对f l a s h 的以上特性，学术界主要作了以下几个方面的研究。 首先是提高f l a s h 存储体的性能，这主要体现在提高读写性能和延长寿命等方 面。c a g d a sd i r i k t l 3 】等人通过实验证明，f l a s h 芯片i o 性能的瓶颈是它的内部串行 接口而不是总线，所以提高性能的关键是增强并发。他们主张通过在芯片级采取 交叉存取技术，在系统级利用大量f l a s h 芯片构建阵列来同时提高并发度。对于 f l a s h 而言，提高随机写的性能至关重要。k i m 和a h n 利用d r a m 作为缓存提高 f l a s h 随机写的性能【i4 1 。由于数据的更新操作具有局部性，如果在f l a s h 之上加一 级d r a m 作为缓存，那么大量的更新会发生在d r a m 中，减少了对f l a s h 的写操 作，从而延长了f l a s h 的寿命。另外，隐藏擦除操作的延迟也能提高f l a s h 的读写 第7 页 国防科学技术大学研究生院硕十学位论文 性能。固态存储设备r a m s a n 5 0 0 t 1 5j 中包含1 6 g - - - - 6 4 g 的d d rd r a m ，使人量的 写操作在d r a m 中命中，就是基于上述原理。 f l a s h 上每一块被擦除的次数有限，要延长f l a s h 芯片的整体寿命，增强可靠 性，就要在所有的块之间平衡擦除次数，这种技术被称为损耗均衡( w e a r l e v e l l i n g ) 。损耗均衡的基本做法是：( 1 ) 为上层应用分配物理存储空间的时候， 优先选择擦除次数较少的块；( 2 ) 如果一个块因为写入了静态数据而长期没有被 擦除，相对于其它的块擦除次数明显偏少，可将这块静态数据迁移到其它擦除次 数较多的块中，增大该块的擦除几率。基于上面的原理，研究人员设计了很多有 效的算法【1 6 1 7 、1 8 1 9 2 0 1 。还有一些研究人员设计高效的垃圾回收机制减少对存储单 元的擦除。 针对这种新型的存储介质，研究人员设计了专用的文件系统。f l a s h 文件系统 一般采用日志结构。所谓日志结构，就是文件系统的所有数据和元数据都被封装 成日志节点保存在存储介质上。要获取数据首先要找到数据对应的同志节点，然 后根据节点的头信息提取有效数据。传统文件系统中父目录指向子目录的指针、 元数据指向数据的指针都不复存在，取而代之的是父目录或元数据指向日志节点 的指针，被指向的同志节点中含有相关的子目录或用户数据。文件系统的所有变 化都以日志形式记录下来，日志节点在存储介质上顺序写，而不是在原数据上直 接作修改，解决了f l a s h 存储介质非定点更新的问题。这种结构较适合于f l a s h 存 储介质：日志的实现方式正好适合f l a s h 的非定点更新的特性；日志的顺序写在一 定程度上弥补了f l a s h 随机写性能的不足；日志本身也提高了文件系统的可靠性。 除了上述结构差异以外，f l a s h 文件系统与磁盘文件系统至少还有两点不同： ( 1 ) f l a s h 文件系统必须有垃圾回收功能，因为在修改数据时新节点的生成意味着 旧数据失效( 成为垃圾) ，只有回收这些垃圾( 擦除存有失效数据的块，使其成 为可用的空白块) 才能有效的利用存储空间。( 2 ) f l a s h 文件系统不仅要根据元数 据定位数据，还要能够根据数据找到元数据，这是由f l a s h 的擦除操作必须以块为 基本单位引起的。在垃圾回收擦除某一块时，如果该块上还有少量的有效数据， 需要将这些数据迁移，同时修改相应的元数据，这个过程要求根据数据找到对应 的元数据。 典型的f l a s h 文件系统有j f f s x t 2 1 2 2 】、u b i f s l 2 引、l o g f s t 2 4 1 。j f f s x 主要用在 嵌入式系统中；u b i f s 和l o 西s 面向大型系统，但都处于发展阶段。f l a s h 文件系 统在大规模存储领域的广泛应用不仅有待自身的日趋成熟，还依赖于f l a s h 存储介 质的推广和相关兼容软件的积累。 除了通过f l a s h 文件系统管理f l a s h 存储体，还可以用f l a s h 芯片构建固态盘 s s d ( s o l i ds t a t ed r i v e ) 。s s d 为上层应用提供与磁盘一样的接口，可以直接利用 第8 页 国防科学技术大学研究生院硕+ 学位论文 传统磁盘领域积累的技术和大量软件产品。f l a s h 固态盘采用一个转换层f t l 2 5 】 将f l a s h 模拟成磁盘设备。f t l 主要完成以下几项功能：逻辑地址到物理地址的映 射、损耗均衡、垃圾回收。其中地址映射实现了f l a s h 芯片物理地址到上层应用逻 辑地址的转换，损耗均衡延长整个存储体的寿命，垃圾回收保证恒定的有效存储 空间。关于s s d 的介绍以后将有大篇幅展开。 1 3 引入f l a s h 的多层次存储结构 本研究通过在传统的存储系统中引入f l a s h 提高整个系统的性能。f l a s h 的读 写延迟、价格、容量均介于d r a m 和磁盘之间，所以本研究在传统存储器层次结 构的d r a m 和磁盘之间加一级f l a s h 作为缓存。如果把d r a m 和f l a s h 作为一个 整体，并在它们之间动态的交换数据，则在c p u 的视图中，如同增大了d r a m 的 容量，而这个混合缓存的价格和功耗远远优于完全由d r a m 组成的缓存。 f l a s h 与磁盘各有一定的优势。如f l a s h 随机读性能好，特别适合于存放多读 的随机数据，如元数据；磁盘顺序读写性能好，适合存放大块连续的数据。f l a s h 适合存放只读数据，而磁盘是读写对称的。结合这两者的优势会更好的提高存储 系统的性能，所以本研究在以磁盘为主的大规模辅存中加入适当的s s d 来配合磁 盘，重点改善读性能。在两种存储介质之间存在数据迁移，数据分布的总体原则 是随机数据和多读数据倾向于布局在s s d 中，顺序数据和多写数据倾向于布局在 磁盘中。 整个系统由混合的缓存和混合的辅存组成，它们之间的数据交换规则如下： 当数据由辅存转移到缓存时，处理器请求的数据和从s s d 预取的数据放在d r a m 中，从磁盘预取的数据放在f l a s h 缓存中；当数据由缓存写回到混合辅存时，要符 合上面提到的数据布局原则。总体结构如图1 3 所示，本研究重点关注d r a m 及 以下的存储层次结构，包括d r a m 、f l a s h 、s s d 、磁盘，整个系统完全由软件管 理，不关心c p u 内部的多级缓存。 图1 3引入f l a s h 的多层次存储结构 第9 页 国防科学技术大学研究生院硕+ 学位论文 1 4 课题研究的意义 目前磁盘和c p u 的速度差距越来越大，大型存储系统中c p u 经常闲置，磁盘 因为其巨大的延迟成为整个系统的一大瓶颈。新型存储介质f l a s h 具有延迟小、功 耗低、无噪声、抗振动等特点，是一种理想的存储介质。f l a s h 日益增长的市场份 额表明，它正处于应用普及阶段。可日前，f l a s h 的价格和容量仍然无法与磁盘相 比，完全取代磁盘主宰存储市场还需要时间。眼下可行的实现方案就是构建f l a s h - 磁盘混合存储系统，既发挥磁盘容量大、价格低的优势，又利用f l a s h 提高系统性 能。 本研究通过在d r a m 一磁盘层次之间引入f l a s h ，用一种经济的方法扩展了 d r a m 的容量。s s d 与磁盘相结合则降低了辅存的平均延迟，减少了功耗。这两 方面的工作对当前的大规模数据中心具有重大意义。本研究是国家自然科学基金 重大项目“大规模网络存储环境中的海量分布数据管理研究 的一部分，主要负 责提高网络存储数据中心中单机节点的i o 性能。 1 5 论文结构 本文的第一章是绪论，先介绍了研究的背景和意义，然后引出了本研究的基 本体系结构，对全文的工作做了简单的介绍。 第二章介绍了本研究的多层次存储结构中d r a m 的缓存替换策略。 第三章介绍d r a m f l a s h 组成的混合缓存，重点研究缓存和辅存之间、d r a m 和f l a s h 之间的数据替换策略。 第四章研究混合辅存的管理，首先设计一种高效的s s d 原型，然后介绍了s s d 磁盘混合辅存，最后一部分介绍了辅存到缓存的数据预取。 第五章对前面的内容进行了总结，并明确了以后的工作。 第1 0 页 国防科学技术大学研究生院硕士学位论文 第二章d r a m 中的替换策略 本章研究多级存储器层次结构的最上层d r a m 中的缓存替换策略。首先 从一些主流的替换策略入手介绍了这个经典领域的研究现状，接着对单级的缓存 替换策略的设计方法做一个总结，然后介绍本研究提出的替换策略以及相应的实 现和测试，最后一节是本章的总结。 2 1 单级缓存替换策略研究现状 处理器的速度达到纳秒级，且其速度的增长遵循摩尔定律。而作为当前主要 辅存设备的磁盘是机械电子装置，速度的提升受到宏观物理规律的限制，延迟在 豪秒级停滞不前。处理器和辅存设备之间的通信性能成为整个系统的一个瓶颈。 缓解这一矛盾的主要方法是在处理器和磁盘之间加一级速度更接近于处理器的缓 存装置。引入缓存的主要依据是处理器对数据请求的局部性：当前使用的数据在 不久的将来可能重复使用。所以将现在使用的数据寄存在缓存里，处理器下次请 求该数据时直接从缓存读取，减少了访问磁盘的几率，总体上提高了通信性能。 但是缓存价格较贵，容量有限。缓存饱和后，在新的数据进入缓存之前，必须将 其中一些数据替换出来。选择哪些数据替换出来的策略成为缓存研究的一大热点， 出现了许多实用的替换策略。 2 1 1 典型的替换策略 2 1 1 1l r u 制定缓存替换策略最重要的依据就是时间局部性，并由此导出一个简单有效 的替换策略l r u l l 2 l ，该策略总是选择最久未使用的数据淘汰出缓存。具体实现方 法是：维护一个队列，将刚刚使用过的数据放到队列头部，队列尾部就是长期没 有使用的数据，替换的时候就选择队尾的数据。这个策略因为简单有效被许多系 统采用，它维护的队列被广泛的引用为l r u 队列，后来的许多替换策略都是以它 为原型所作的改进。 2 1 1 2f b r f b r l 2 6 】维护一条l r u 队列，如图2 1 所示，但将l r u 分成三个部分：n e w 、 m i d d l e 、o l d 。每个页都记录它被引用的次数，当一页在n e w 中被访问时，引用次 数不增加；在m i d d l e 或o l d 被访问时，引用次数增加。任何被请求的页都放到队 列头部。替换时总是选择o l d 中引用次数最少的页。这种策略实现简单，屏蔽了数 据的关联访问，但很难确定n e w 、m i d d l e 、o l d 三部分的大小。 第1 i 页 国防科学技术大学研究生院硕士学位论文 * 一 一m n “目 t - 一命中增加引用 一 m 0 1 d 一 - 图2 if b r 替换燕略 2 1 1 3l r u ，k l r u 瓜矧策略主要针对数据库中的关联访问。所谓关联访问就是为了完成同 一个事务而对某一页的多次请求，如数据库中对某一条记录的“查询一更新”操作。 这种情况下，尽管有多次请求但并不说明