存储系统重复数据删除技术研究综述

第41卷第1期2014年1月计算机科学ComputerScienceV01．41No．1Jan2014存储系统重复数据删除技术研究综述谢平(青海师范大学计算机学院西宁810008)(华中科技大学计算机科学与技术学院武汉430074)摘要目前企业对数据量不断增长的需求使得数据中心面临严峻的挑战。研究发现，存储系统中高达60％的数据是冗余的，如何缩减存储系统中的冗余数据受到越来越多科研人员的关注。重复数据删除技术利用CPU计算资源，通过数据块指纹对比能够有效地减少数据存储空间，已成为工业界和学术界研究的热点。在分析和总结近10年重复数据删除技术文献后，首先通过分析卷级重删系统体系结构，阐述了重删系统的原理、实现机制和 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。然后结合数据规模行为对重删系统性能的影响，重点分析和总结了重删系统的各种性能改进技术。最后对各种应用场景的重删系统进行对比分析，给出了4个需要重点研究的方向，包括基于主存储环境的重删 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 、基于分布式集群环境的重删方案、快速指纹查询优化技术以及智能数据检测技术。关键词重复数据删除，重删率，体系结构，元数据结构，I／0优化中图法分类号TP311文献标识码ASurveyoilDataDeduplicationTechniquesforStorageSystemsXIEPing(DepartmentofComputer，QinghaiNormalUniversity，Xining810008，China)(DepartmentofComputer，HuazhongUniversityofSci．andTech．，Wuhan430074，China)AbstractWiththeever-increasingdatavolumeinenterprises．theneedsofmassivedatastoragecapacitycurrentlybe—comeagrandchallengeindatacenters，andresearchingshowsthatthereareabout60％redundantdatainstoragesys—tems．Therefore，theproblemsofhighredundancyindatastoragesystemsarepaidmuchmoreattentionsbyreseat-chers．ExploitingCPUresourcetocomparethedatahlock’Sfingerprintwhichisunique，datadeduplicationtechniquescanefficientlyaccomplishdatareductioninstoragesystems，thusdatadeduplicationtechniqueshavebecomeahottopicinbothindustryandacademiafields．Basedonadequatelyanalyzingandsummarizingliteraturesondatadeduplicationtechniquesappearedinrecenttenyears，thispaperfirstpresentedtheprincipleofrepresentativedatadeduplicationsys—tems，implementationmechanismsaswellasevaluationmethodologiesafteranalyzingvolume-leveldatadeduplicationsystemarchitecture．Second，wealsofocusedonexistingdeduplicationoptimizingtechniqueswithconsiderationofboththecharacteristicsofdataandscaleofdatadeduplicationsystems．Finallyfournewresearchdirectionsweregivenasfollowsbycomparativelyanalyzingvariousapplicationscenariosofdatadeduplicationsystems，includingresearchofpri—mary-Storage-Leveldatadeduplicationapproaches，researchofdistributeddatadeduplicationschemeforclusteredstor-agesystems，researchofhighly-efficientfingerprintsearchingtechniquesandresearchofintelligentdatadetectiontech—niques．KeywordsDatadeduplication，Deduplicationratio，Systemarchitecture，Metadamstructure，I／Ooptimization1引言随着IT技术的不断发展，许多行业(in：金融、通信、互联网等)正呈现出数字化迅猛发展趋势，信息存储的应用领域越来越广泛，加之云技术、云存储的应用，企业数据中心存储需求量越来越庞大，数据量呈指数级增长，已从之前的TB级上升到PB级，甚至EB级。图灵奖获得者JimGray提出了一个新的经验定律：网络环境下每18个月产生的数据量等于有史以来数据量之和。2011年10月12日IT研究与顾问咨询公司Gartner对8个国家的1004家大型企业的最新研究结果[1]显示数据增长仍然是大型企业部署lT设施的最大挑战，47％企业将数据增长列为第一挑战，62％企业拥有扩充现有数据中心硬件容量的规划，30％企业 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 新建数据中心；随着存储规模的增大，一方面需要企业投入巨额资金购置存储容量，另一方面数据中心的运营成本也将显著增加，运营开销大约为1500美元／TB[引。如何缓解企业数据中心存储容量成本和运营成本已成为当前网络存储领域面临的严峻挑战。研究表明[3一，在应用系统所保存的数据中，高达60％的数据是冗余的，而随着时间推移，冗余数据的比例也将上升，而为了确保能够可靠而持久地保存数据，可能要花费超过10到稿日期：2013-03—23返修日期：2013—06—22本文受国家973重点基础研究发展计划(2011CB302303)资助。谢耳z(1979--)，男，博士生，副教授，主要研究方向为网络存储等，E-mail：qhnuxp@grnail．corn。·22·万方数据倍的存储空间和管理成本。因此存储系统中数据高冗余问题受到越来越多研究人员的关注，如何缩减存储系统数据存储容量已成为一个热门的研究课题，而重复数据删除技术(De-duplication)是其中一种容量优化(CapacityOptimization)技术，它通过消除存储系统中重复的数据，缩减系统中实际存储的数据或通过网络传输的数据，在备份、长期归档和数据灾难恢复等方面得到了广泛的应用。在工业界，DataDomainDDFs，IBM1Nigent，EMC的Avarma，Veritas的PureDisk以及CommVault的Shpana是比较知名的重复数据删除产品，这些产品通常可以达到20：1的重复数据删除率；同时学术界也进行了深入研究，包括美国的MIT、OSU、UC和Stanford等大学，德国的Paderbom大学，英国的剑桥大学，以及中国的CUHK、清华大学‘引、国防科大[61和华中科技大学等高校。目前主流重删系统针对备份／归档的二级存储系统，备份／归档存储系统[4]中有80％～90％的数据都是冗余的，这也是现有重删系统之所以获得如此高重删率的原因。近年来，随着虚拟化技术、专用处理器技术和新型存储介质的出现，结合实时联机重复数据处理和降低IT成本的考虑，重复数据删除技术面临新的机遇和挑战。重复数据删除作为一项应用于存储系统上的数据管理技术，有必要结合数据特征和存储规模来探讨重删技术对存储系统性能的影响，从而获取相关的性能优化技术，因此本文从重复数据删除技术工程设计与实现的角度，分析并概括了重复数据删除技术的基本原理、实现机制、现状以及发展方向。第2节介绍重复数据删除技术的概念、层次、分类体系和与重删技术相关的问题；第3节阐述重复数据删除系统的体系结构、重删系统设计中的关键操作、评价标准和数据规模分析；第4节深人探讨提升重删系统性能的各种加速技术；第5节总结和讨论工业界和学术界重删系统项目；最后结合海量存储系统负载特征的复杂性和应用场景的复杂性等特点，给出了4个重点研究方向。2重复数据删除系统介绍2．1重复数据删除技术重复数据删除技术是一种数据缩减技术(DataRedue—tion)，通常用于基于磁盘的备份系统，旨在减少存储系统中使用的存储容量。重复数据删除技术通过对源数据的对比分析，将数据中重复的数据块“去掉”，即重复的数据仅在磁盘介质上写一份，其它重复的副本建立“索引”，这样可以有效地节省备份介质。重复数据删除技术支持在已有的磁盘设备上存储更多的备份数据。因此采用重复数据删除技术可以增加保存备份数据的时间，减少数据中心设备数量及电力消耗，降低运营成本。2．2重删I／o层次分析和总结从系统结构的层次模型看，对于磁盘的一次I／0请求，首先应用层下发I／0请求，经过虚拟文件系统层，其次是文件系统层，接下来是Cache层、通用块层、I／0调度层、块设备驱动层，最后是物理块设备层，现有的重删系统主要位于应用层、文件系统层和块层实施重删检测功能，比如现有的开源重删系统Lessfs：7]和OpenDedup[83就是基于应用层，通过用户态文件系统Fuse[妇实施重删，从而避免了用户对底层的管理，显然实现容易，但与传统的Linux文件系统EXT2、EXT3和XFS相比其性能更低[7J，另外，有的重删系统也可以通过调用用户态的块设备驱动S睽汀模块D03来实现重删。基于内核态的重删系统是工业界和科研机构研究的重点，内核态则是以修改内核代码或者以模块的形式动态植入内核代码，LiveDFSEll]就是在现有的文件系统EXT3中实施的重删功能，文件系统层重删系统一般是对实际文件的内容进行分块和重删，把每个文件分为若干个块，针对每个文件块进行重删，而对文件元数据及目录不做重删，文件系统层的重删只是针对挂载了该重删功能的文件系统对应的分区才具有重删功能，因而也称为局部重删；块层重删系统I／0DeduplieationEl2]在文件系统层之下，独立于文件系统，能够支持多个文件系统，因而能够实施全局的重删，块接口层语义简单，从而使得I／0容易截获、操作和重定向，块接口是一个通用的抽象，如操作系统的块设备实现、RAD和IsCsI存储设备都是基于块接口的，因此基于块的抽象更能被移植和部署到多个平台。综上所述，重删系统所在的I／0层次从上到下的实现是从易到难，语义信息逐渐减弱，但重删性能会更好。2．3重删系统分类介绍和总结根据实施重复数据删除操作位置的不同，分为源和目标端重复数据删除；根据实施重复数据删除操作时机的不同，分为离线(Off-Line)、近线(Out-of-Line)和在线重删系统(On-Line)；根据实施重删操作粒度的不同，分为文件级和块级重删系统；根据重删系统所服务数据实体的存储与访问方式的不同，分为主存储和从存储重删系统。2．3．1基于源和目标端的重删系统在网络环境中，为了确保数据的可用性与可靠性，数据一般都会备份到远端存储节点。因而数据重删既可用于本地客户端节点(源重删系统)，也可用于远端存储节点(目标端重删系统)。在源重删系统里，副本被消除在每一个本地节点里，仅有唯一的数据通过网络传输到远端存储阵列进行存储，这种方式节省了网络带宽，在客户端安装应用程序，可以充分利用源端节点的资源；在目标端重删系统里，所有的数据都通过网络传输到远端存储节点进行识别并消除副本，这种方式的缺点是所有的数据都是通过网络传输的，因而占用了更多的网络带宽。由于多个客户端节点的数据最终都汇聚到了目标端节点，因此在目标端发现副本的概率更高，两者的结合将会提供更多的时间和资源来布置重删操作，比如，NetApp的Snapvault使用了两者的一个结合。2．3．2主存储与从存储重删系统存储系统可分为主(Primary)存储系统和从(Secondary)存储系统[1引。从存储重删主要针对归档和备份系统负载，数据具有局部性，备份是典型的批量写操作，一般通过自动化的进程处理。备份过程中，系统的性能会暂时下降，或者出现系统资源不足的情况，备份过程几乎没有读操作，多数用户并不关注数据恢复的速度，而对吞吐率敏感，因此从存储重删系统主要关注I／0吞吐率的提升。主存储系统则完全是另一种情况，数据缺乏局部性特征，数据会随时写入，主存储系统由于要及时响应客户端的请求，因此对延迟敏感。因而主存储重·23·万方数据删系统关注于如何提高I／O的平均响应时间，由于写可以采用写回操作，因此可以批量地更新写缓存，而不影响前台应用写请求的平均响应时间，但是对于读请求，必须从存储系统中读取，而且主存储系统读请求的比例一般大于75％，因此主重删系统更应该关注读请求的性能提升。2．3．3离线、近线和在线重删系统目前在线重删系统、离线重删系统和近线重删系统既可以应用于主存储系统，也可以应用于从存储系统，主要是基于不同应用场景的重删系统对性能的考虑。在线重删在数据写到存储系统之前在写路径中完成重删工作。由于重删过程在写关键路径中，因此增加写延迟，数据规模较小时，重删对系统延迟影响不大，但是当存储系统所处理的数据规模逐渐增大时，会加长重删的路径，从而会延长重删的处理时间，降低重删系统的性能。如果考虑逐个比较数据块，数据规模比较大，而且又在主存储系统环境，可以想象处理一个副本块将非常耗时。针对这个问题，有研究者提出牺牲重删率方式来提高系统的性能，如iDedup[13]只删除达到一定阈值的连续串，有效地缩短了指纹查询延迟时间，但缺点是只能实现部分重删。离线重删系统是一种后处理方式(Post-Process)，数据先存储到存储系统中然后实施重删功能，这种方式能够隐藏重删过程的延迟对用户体验的影响，因而对响应时间敏感的主存储环境可以采用这种离线的方式进行处理，这种类型的覆盖写会增加写延迟，也会增加读碎片。近线重删系统(Out-of-Line)倾向于等待系统空闲时完成对以前写数据的重删操作，是介于在线与离线之间的一种重删系统，只是其对时间要求不那么苛刻，如：DD群14]在主存储系统处于轻载或空闲时实施重删。2．3．4文件级与块级重删系统文件级重删系统也称单一实例存储SIS(SingleInstanceStore)，它以文件为粒度作为处理的对象，比如Microsoft的wss2000[16]，对于输入的任意一个文件采用Hash算法计算其指纹，并将这个指纹与已有文件的指纹库进行比配，如果相同，系统只保存一个指向原始文件的指针，而不是再一次存储到另外一个地方，适合于由小文件构成的数据集；由于不需要对数据文件再次进行分块划分，相应其划分数据的CPU开销相对低，RAM开销相对低，因而其执行高效、简单快捷。在实际工作负载中，尽管有大量的文件为小文件，但占用了绝大部分存储空间的是占少数的大文件。由于以文件为粒度的重删只能进行文件粒度的重复数据检测，不能发现文件内部以及文件之间更小粒度的重复数据，因此数据集的重删率往往不高，基于此有研究者提出了块级的重删系统。块级重删系统对输入的数据文件以块为粒度进行划分，如：DBLK[17]以4k为粒度对块进行划分，块级重删系统的数据重复检测在指纹库中的查找和匹配过程与文件级重删系统类似；与按文件粒度划分相比，由于其粒度更小，检测出重复块的概率会更高，如果在文件更新的过程中，一个大文件内部只有部分数据块发生变化，这种情况在块级重删系统中只保存发生变化的块，因而更能节省磁盘空间；相应地，以块粒度进行划分，计算开销会更大，会占用更多CPU资源，块级重删系统中其元数据表会变长，从而降低RAM的利用率，花费更多的磁盘空间·24·用于存储元数据表；在块划分的过程中有的系统按FSP算法[18]进行固定块大小划分，这种分块算法有利于减少分块在时间上的开销，由于主重删系统必须要求低延迟，因此可以考虑使用固定分块算法，这种方法的优点是简单高效，适合于更新操作少的数据集(如，图片服务器和视频服务器)，如果一个文件中的内容稍有变化，便会导致其后数据块内容与先前数据块内容稍有不同，从而不能智能地根据文件内容的变化进行调整，降低了系统重删率，因此有人提出重删系统按CDC算法[18]进行变长块划分(适合于经常更新的场合，如博客)，CDC算法是应用Rabin指纹将文件分割成长度大小不一的分块策略，主要采用滑动窗口技术(SlidingWindowTech—nique)，后来有研究者提出了Fingerdiff[19]和SlidingBlockTechnique技术[18]对其进行了进一步的改进，提高了重删率，对于大文件系统，变长块进行划分会获得更高的存储效率，但相应地会增加计算的开销。综上所述，文件划分粒度影响重删系统的性能：a)数据重删率；b)读写速度。由于每一个块都需要相同大小的元数据项，块越小，数据重删率会越高，但指纹项会越多，从而导致检索的Hash表会越长，表越长，更新将变得更越难，块的大小决定了系统的开销。划分粒度对于重删系统而言在时间开销、空间开销上是一个权衡。2．4重删与压缩的关系目前数据缩减(DataReduction)[153技术是存储系统领域非常重要的技术，包括重复数据删除技术和数据压缩技术，压缩技术的优点是非常成熟，并且易于理解，它的缺点是处理机制仅限于单个文件之内，而无法做到跨文件处理。压缩通常是针对那些存取频率不是很高的数据，这是因为数据的压缩和解压缩需要CPU进行非常密集的计算处理，计算开销较大，这样往往会影响数据的访问。目前使用专用芯片实现压缩和解压缩，有一些产品诸如Storewize公司的STN-2100和阱6000，以及OcarinaNetworks公司的EC0system，都支持在数据写入／读取过程中同步进行压缩／解压缩，如果它们能达到线速，就不会影响主存储系统的读写性能。重复数据删除采用指纹技术来处理数据块的内容，有相同Hash值的块只存储一次来实现数据的消重，在存储层使用重复数据删除技术并不意味着不再需要数据压缩等其它数据缩减技术。重复数据删除是一种补充型技术，能够与包括业界标准LZS压缩算法在内的现有数据压缩技术形成互补，以提供双重数据缩减性能。重删系统必须先实施重删而后再压缩，因为压缩会使即使非常相似的内容经压缩后变得非常不同。3重删系统结构及关键操作3．1卷级重删系统体系结构卷级重复数据删除系统体系结构如图1所示，企业级存储阵列通过高速存储网络Switch(FC／Ethemet)与多个Host连接，为Host提供物理存储资源，是一种典型的SAN存储区域网结构。为了提高存储系统的性能和可靠性，磁盘阵列上都部署有RAID5或RAⅡ)6，其可以被看作Host端的虚拟存储盘，每个Host通过LUN访问相应的存储资源。重删模块处在LUN逻辑卷层之上，共享整个物理磁盘资源，保存每个客户LUN和存储资源之间的实际分配关系，所以多个主机万方数据端的存取数据流需要在重复数据删除层汇集，实现在单一物理存储资源上的重复数据检测及其删除，从而在最终的物理存储子系统上仅保留一份数据拷贝。存储资源池和磁盘阵列模块管理实际的磁盘布局拓扑和物理存储虚拟化，物理上通过高速通道(FC或SAS)和存储区域网连接到磁盘柜中的磁盘上。图1卷级重复数据删除系统体系结构从系统结构层次关系看，重复数据删除层的重复数据处理流程分为文件／数据流的变长分块算法Chunking、块指纹哈希算法ChunkHashing、指纹查询检索FPindexing和存储元数据和唯一数据DataStoring4个阶段。如图1所示，它是一种典型的块层重删系统体系结构，重复数据删除层的顶端为IS汇-_SI访问协议层，在访问协议层以下的就是重复数据删除层中的各功能子模块，主要有Volume模块、Deduplication模块、Compression模块、GarbageCollection模块、Metadata模块、Chunk模块和Logger模块。重复数据检测的流程首先根据重删系统数据块分割算法将某个uJN卷的文件或数据流分割成若干个Chunk，并计算每一个Chunk的Hash值(也叫指纹FingerPrint，简称FP)，Deduplication模块根据生成的FP到Metadata模块中的指纹索引表(简称FPIndex表，记录了所有Chunk的FP信息)中去查找匹配，如果查找到，说明该数据块Chunk是副本，因此不用写入磁盘，代替的是通过Logger将该FP对应counter加1，如果没找到，说明该数据块是新的，可以直接写入磁盘并将该FP更新到FPIndex表中，在Metadata的地址索引表AddrIndex(保存了所有U姨与PBA的映射关系)中更新地址项。数据和元数据最终在磁盘上都是按Container大小存放的。为了进一步对数据实施缩减，都要使用某种压缩算法Compression对每一个COn-tainer实施压缩。由于数据和元数据在磁盘上都是以覆写方式存放，因此适时动态地回收不再使用的数据块(counter为0的数据块)将是非常必要的，垃圾回收技术GarbageCollec—tion将会有效地提升重删系统FP索引管理的可靠性、查询速度和可扩展性。3．2重复数据判定操作重复数据的判定技术就是将输入的数据与已有数据进行比较并消重的技术，目前通用的做法就是从输入的每个Chunk的内容中选择一个特征值即一个FP来标识它，然后将该新FP与FPhldex表中已有的FP进行比对，期望的特征值能唯一标识Chunk，该特征值一般选择抗冲突加密Hash值作为其特征，如SHA和MD5等算法；尽管有研究者因为Hash函数存在碰撞和生日悖论对此表示怀疑，但很多人认为相比于硬件出错，Hash碰撞引起的出错概率更小。该问题符合概率论中的生日悖论模型，SHA_1的两个不同数据块拥有同一Hash值的概率为1／2160；随着输入的数据块的个数逐渐增多，其Hash冲突的概率FPIRE22]会逐渐升高，定义为：——、r2FPIR=1一ExP(忐)(1)o／＼厶式中，N为输入数据块的个数，m为Hash值位数，块大小为32kB，磁盘空间1PB，FPIR为4．038×10_28，块越大其冲突率会越低，典型磁盘的位失效率最小为10-27；可见1PB数据空间Hash冲突率与磁盘位失效率相当，因此在系统中可以不考虑Hash冲突造成的影响。3．3重删流程读、写和删除操作重删系统根据I／0过程分为读、写和删除操作3个流程，其中指纹库的查询过程是重点优化步骤。由于整个哈希索引表太大而不能完全放入内存，因此有一部分会放在磁盘上，而磁盘的I／0开销太大，会严重影响性能，所以要通过合理的设计来提高内存缓冲区的命中率，从而减少对磁盘I／0的需求，同时尽量减少内存的占用，并使查找的过程尽可能快，以减少写请求的响应时间。DataCache中的数据项采用LUN+LBA直接索引，但不对每个LUN单独分配Cache空间，统一管理。3．3．1写请求首先通过哈希函数计算数据块的哈希值，然后在哈希指纹库中查询数据块是否在哈希索引表(FPlndex)中。如果哈希值不在表中，则申请新的磁盘空间来存放这个数据块，然后将数据块写入数据容器DataLog，再更新哈希索引表，把新数据块的FP到PBA的映射关系加入到哈希索引表中，再在地址索引表Addrlndex中加入L队到PBA的映射关系，并更新数据缓存、地址索引缓存和指纹索引缓存。如果哈希值在表中被查到，说明该数据块是重复的，更新计数器Counter，再在地址索引表中查找相应的PBA，并更新数据缓存、地址索引缓存和指纹索引缓存中的LBA到PBA之间的映射关系。3．3．2读请求直接在地址索引表Addrlndex中查找，找到后就在Data—Log中读取相应的数据块，并返回读取的数据块。对于部分放不进内存的地址索引表，要通过磁盘调度进入内存，再进行读取。3．3．3删除请求先在地址索引表中删除相应的映射关系，再在哈希指纹库中删除相应的映射关系，最后根据引用计数情况来确定是否去DataLog中删除相应的数据块。3．4重■系统的评价标准重删系统量化评价指标体现在3个方面：I／0吞吐率、请求的平均响应时间和重删率，下面结合图1介绍的块层重删系统量化了这3个指标。3．4．1平均响应时间重复数据删除系统是在正常读写流程中加人重删模块，·25·万方数据一方面在写入数据的过程中由于需要对重删的数据块元数据进行查找匹配，当元数据比较大时，不可能在cache中实现全命中，从而增加了额外的磁盘I／0，增加了查找延迟，因而会延长写入延迟时间；另一方面由于重删破坏了原有数据的连续性存放，多个文件共享一个唯一的副本，从而造成磁头更多来回移动，增加了读数据延迟，这些时间开销就叫做延迟时间，也叫响应时间，延迟时间一内存查询开销+磁盘查询开销。(1)写入延迟时间T赢一(k+T彦+Tr×h，+Td×(1--h，)+Taw)×N(2)瓦出：写入总延迟时间；k：数据分块对齐的时间开销；％：数据块生成的指纹时间开销；L：写数据块在内存中的查询时间开销；乃：写数据块在磁盘中的查询时间开销；以：写查询内存命中率；k：写人数据和元数据开销；N：写人数据规模。(2)读数据延迟时间k—T删×k+％×(1--h。)+瓦×W(3)了乙d：读数据总延迟时间；丁■：读数据块在内存中的查询时间开销；Taa：读数据块在磁盘中的查询时间开销；h。：读查询内存命中率；T≥：读数据和元数据开销；w：读取数据规模。3．4．2重删率重复数据删除技术实现了数据的缩减，其量化标准就是重删率[舯]，重删率的定义可以通过重删之前输入重删检测模块的字节数(BytesIn)和重删之后输出重删检测模块的字节数(BytesOut)来定义：缸一旦塑垃土地×100％(4)Bo“7ytesIn⋯。。7”、17就目前的重删系统而言，数据的重复率矗(冗余度)由数据集(DataSet)自身的特征以及具体应用场景、数据分块算法和平均数据分块大小决定；当数据规模较小时，能实现100％副本消重，这时重删率就等于重复率，但是随着数据规模的不断增大，其元数据表的长度也在增加，因而为了考虑性能等因素，不同的重删系统针对同一个数据集的重删率可能不同，为了体现重删系统消重的效率定义为重删效率，出，口1|，重删率定义如下：{协一{甘X{量f鼢采用查询优化是最关键的，很大程度上决定了重删效率，理想的情况下重删效率接近100％是最好的情况。影响重删系统重删效率有两个因素：1)系统的数据规模；2)采样算法。重删效率厶r与数据规模因子卢成反比，与采样算法因子a成正比，可表示为丘，一a伊。在相同的数据规模下，采样算法越好，FP的内存命中率就越高，重删效率就越高；在相同的采样算法的情况下，数据规模越大，其重删效率会越低。3．4．3I／O吞吐率存储介质吞吐率n毋指单位时间内传输的数据量。由于重删增加了正常的数据读写延迟时间，因此重删系统的IO吞吐率比不实施重删的系统吞吐率更低，数据集大小一定，与延迟时间瓦。，成反比，定义为：TA士=Bytesh／了k。(6)3．5重删系统数据规模分析在重删系统中随着数据规模的不断扩大，其FP查询管·26·理开销将逐渐增加，严重地影响了重删系统的性能和重删效率，重删率与workload有关系。比如100TB的数据，如果每一个数据块大小为4kB，则有100TIy4kB=25G个数据块，如果每个数据块的指纹大小为20B，则FPIndex表总共为25GX20B=500GB的容量；如果重删率为50％，则FPIndex表的大小为500GB×50％一250GB，显然不适合存放于内存，如果数据量达到PB级，则该FPIndex表还会更大。因此随着数据规模的增大，不可能将所有的FP放入内存，也不可能对每一个FP逐一查询，目前提高FP查询优化的技术主要是预取和采样两种技术[23]，其可实现指纹的快速查询匹配。如图1所示的块层重删系统，如果每一个LUN最大容量为64TB=246B，块大小为4kB=212B，则有246／212—2“个块，如果每一个块都用一位来表示，则共有234个位，即234／8=2GB的LU】忆&Lbitmap空间，如果总共有1024个LUN，则占用空间为1024×2GB=2048GB；对于IPB=250B的磁盘空间，块大小为4kB=212B，共计250．12即238个Chunk，同样每一个块都用一位来表示，则共有238个位，即238／8—32GB的PBA。bitmap空间，同理所需的PBA的字节数为5，如果考虑LBA所需字节数假设为10，为方便计算并将标志位等可能PBA所需字节数设定为6，则一个元数据项LBA—PBA共需16个字节，则需要238×16B一4TB的AddrIndex空间。综上所述，通过数据规模分析，重复数据删除技术使数据路径加长，数据量达到阈值后，逻辑地址LUNL&Lbitmap、地址映射表AddrIndex、指纹库H，hdex、物理地址P&Lbit—map都无法全部放到内存，引起查询延迟，从而导致了重删系统性能的瓶颈，因而其数据规模不可能无限地增大，而内存不变，通过规模分析得出如下结论：1)减小查找的范围，数据块小，查找范围大；块大，查找范围小，从而导致重删率降低。2)尽量减少对内存的占用，提高内存使用的效率。3)如何使操作尽可能不访问磁盘，在不得不访问磁盘的情况下，如何减小带来的时间开销。4提高重删系统性能的加速技术重删系统I／0路径上分为Chunking、ChunkHashing、FPindexing和DataStoring4个阶段，针对其中的每一个阶段既可以采用硬件加速技术又可以采用软件加速技术来提升重删系统性能；就目前现有技术而言，分块算法Chunking和ChunkHashing算法的复杂性的提高会增加CPU计算开销，所采用的算法相对成熟易实现，对算法的改进提升较难，现有的文献和资料显示可采用多核技术来加速其执行；DataStor—ing阶段一般受硬件接口性能所限制，可以采用读写性能更好的器件来提升，所有文献资料显示指纹查询检索(FPindex-ing)是加速提升的重点。为了提升系统FP索引管理的可靠性、查询速度和可扩展性，重删系统都会采用灵活的垃圾回收技术GarbageCollection、Striping技术与纠删码技术，以进一步提升系统的性能和可靠性。4．1Ⅱ．ind旺h嚷查询优化技术指纹库查询过程的优化是重点，目前针对较大数据量的内存查询优化策略，采用挖掘局部性特征的技术和位置特性(相似性技术)来减少内存的占用和磁盘I／0等等；采用FP快速判别算法Bloomfilter技术把常用的热指纹放到内存中，万方数据所做的工作都是在重复数据删除率、I／0吞吐率、响应时间之间进行平衡和折中。另外还可以根据具体数据流的特点进行优化，如DDF924]系统。4．1．1局部性技术数据重删系统随着数据规模的增加，其指纹索引表FPindex会逐渐加长，不可能全部放于内存，指纹的查询导致额外的磁盘I／0，增加了索引查询的时间。为了提高在RAM中指纹查询的命中率，降低指纹查询开销，在重删系统中提出了利用局部性技术(LocalityPreservedCaching)来提升指纹的查询优化技术，局部性技术分为空间局部性(SpatialLocali—ty)和时间局部性(TemporalLocality)。VentiE25]是最早给出在备份系统中实施重删的设计方案，现有重删系统的基本架构和功能来源于此，使用了BlockCache、Indexcache和DiskStriping3者的结合来提高写吞吐率。即使在使用8个高端SheetahSCSI磁盘的条带化后，最终的写速度为6．5Ⅷ／Sec。Cache的低命中率导致了如此低的速率，这表明对于大数据流单纯使用内存Cache局部性技术来提高随机磁盘I／O吞吐率是非常有限的。DDF924]注意到传统Cache技术存在的问题，从而在基于LPC技术的基础上又提出了SISL(Stream-InformedSegmentLayout)技术，SISL将无特征的输入备份数据整理为有特征的连续数据块，这些数据块在磁盘的物理空间上尽量连续保存，其对应的FP也是连续保存的，即相互关联的数据和元数据在存储空间上放人磁盘的同一个Container里，该Container具有自我描述，数据的压缩是针对每一容器实施的，不同的容器对应不同的数据流，当有多个数据流时，可同时打开多个容器。当容器满时才一次性地Flush到磁盘，也叫一次I／0，以避免磁盘瓶颈。正是由于SISL技术确保了输入的不同数据流在空间上保持的局部性，才使得LPC技术的命中率大为提高，SISL是确保LPC命中率提高的前提条件，因而可将两者统称为LPC技术，这种技术靠装入或逐出基于一个容器的指纹来保持局部性，即一个指纹被装入，那么该指纹所在的容器中的指纹全部都装入，反之在内存逐出一个指纹，那么该指纹所在的容器也被踢出，如果在内存中未命中，意味着在磁盘上的该指纹所包括的容器将被调入内存，进而利用LRU算法将在内存中的相应容器踢出，代替的不是根据指纹值的一个范围来装入或逐出，这个范围并不代表局部性。实验结果表明，Bloomfil—ter技术加u)C技术能够获得100MB／see吞吐率并显示磁盘的I／0在索引的查询操作中不再是瓶颈。在备份存储重删系统中LPC技术获得了较好性能，由于备份存储系统其行为是比较固定的，即备份固定目录的数据，因此数据流可以被解析为连续的、有意义的。若命中某一备份数据流的第一个Chunk，可以预见，接下来的Chunk也会和上一次的备份数据流中的下一个Chunk相同。但对于主存储系统局部性技术显然不会有太好的效果，因为主存储系统的数据流是比较随机的，缺乏局部性特征。4．1．2相似性技术相似性检测技术在目前的重删系统中被普遍采用，由于重删系统是在原有正常I／0路径的流程中加入了一个具有重删功能的模块，该模块的主要功能就是检测输入的新块是否是重复的块，在重删之初，元数据的查找比对可能非常快，但是当数据量达到TB级别时，这个查找就非常耗时了，再者内存的容量是有限的，不能完全容纳元数据，因而就会将一些元数据放人磁盘，因此增加了延迟时间；基于这种情况引入了相似性技术，相似性技术就好比将一个大范围的Chunk表缩小成一个小范围的Chunk表一样，这个小范围的Chunk表能够满足大多数的命中，比如90％的命中率，或者称为热点的Chunk表，因此这个小范围的Chunk表就能够放入内存，从而实现快速的查找比对。在比对数据块的时候只比对满足某一阈值的连续块[13|，这样在重删的时候只删除连续的数据块，这里存在一个不完全重删的问题，牺牲了重删率，但是它能够有效地提高重删系统的响应时间，这对于主重删系统是非常重要的。Sparseindexingscheme[26]在一个D2D的在线数据备份系统里使用采样指纹索引而不是整个指纹索引，从而进一步减少了重删系统的内存使用率。该方案的观点是副本数据块的长度是可连续变动的，在高概率的情况下一定范围内的采样指纹值的匹配可能代表了整个范围内的匹配，在所有的匹配范围内，一个冠军被作为重删的依据，采样率是在重删率与内存使用率之间的一个权衡。重删率的高低很大程度上由采样率来决定，选择一个合适的采样率是一个关键问题，比如有两个极端：一种是将所有的Hash值调入内存，当然都能找到，但不可能全部放人内存；另一种情况是只调入一个Hash值进入内存，显然I／0开销小，但命中率低，因而怎么采样是一个关键问题。Extreme-binE27]方法利用文件相似性，这种重删方法的主要目的是基于由小或非局部性的文件构成的非传统的备份载荷，对于每一个文件，Extreme-bin选择最小的Chunk的Hash值作为代表指纹，有相同“代表指纹”的文件被归为一个bin，bin是块级重删的基本范围，所有bin的有代表性的指纹都编入一个PrimaryIndex中，PrimaryIndex是相当小的，被放入RAM，因此对于每一个输入的文件只有一次对相应bin的磁盘访问。由于Extreme-bin的采样，每一个文件只有一个指纹，被归人相同桶的相似文件的概率很大程度上取决于它们的相似度，根据broder理论，不同文件有相同代表性指纹的概率随着文件数的增长将会降低。Fanglu等人[23]提出渐进式采样索引，典型的块被归入Segment，指纹的查询索引被采样以确保只有重要指纹才代表最大程度的存储段，也确保了整个索引适合放入主存储器。建议在采样的时候，采样的方案基于剩余的有效Memery，而不是使用整个主存储器的容量。如此的一个渐进式的采样方案能动态地改变采样率和产生更好的重删率。4．1．3BloomFilter技术BloomFilter是一种空间效率很高的随机数据结构，它利用位数组来很简洁地表示一个集合，并能判断一个元素是否属于这个集合，BloomFilter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。在最早的重删系统VentiE25]中采用传统段桶式的FPindex查询方式，但是当数据规模逐渐增大时，其FPindex不可能全部放于内存，BloomFilter技术是一种利用空间换时间的技术，因此引入BloomFilter技术可以有效提高元数据的查找速度。DI)心24]首次将BloomFilter应用于重删系统来加速指·27·万方数据纹的查找，称之为SummaryVector，其实现的过程包括3个阶段：初始化阶段、插入指纹和查询指纹阶段。DBLKEl7]在DDFS的基础上提出了MBL(MultiBloomingFilter)的思想，在主存储重删系统里，针对8TB的磁盘，每一个块为4kB，构造了1664×1664两层的BloomFiher，其占用内存空间11G，实现了150010PS的随机写速率和700IOPS的随机读速率。综上所述，采用BloomingFilter之前，FPindex体积很大，即使采用较大的Chunk，1TB原始数据对应的FPindex也要几个GB，所以FPindex无法完全保存在内存里，那么就会导致FPindex查询时频繁的I／0操作，处理能力肯定低下。而BloomingFilter的体积比完整的FPindex小很多，在DDFS[24]文中，16TB的原始数据，只需要lG的空间，那么BloomingFilter可以完全保存到内存中。但是BloomingFil—ter不是代替FPindex的查询，在DI)FS[踟中，FPindex会保存在磁盘中，BloomingFilter保存在内存中。只有那些全新的Chunk可以通过Blooming判定不存在相同的FP，从而避免了指纹查询过程中的磁盘I／0。但对非全新FP，还是需要进行FPindex的查询操作，磁盘I／O无法避免。按照D1)Fs[243给出的比率，BloomingFilter可以在FPindex查询过程中减少16％左右的磁盘I／O。MBL比起单层BloomFiher则使用更大的内存空间，也是一种空间换时间的思路，比起单层Bloomfiher其能够更快速精确地定位FPindex，从而避免读取不相关的指纹集合FPSET。目前重删系统普遍采用上述3种技术实现重复数据的删除，影响重删系统性能的关键在于索引的查找，目前加快索引查找的策略可归为采样和预取技术[2引。DDFS采用的BloomFiher技术和局部性技术能够有效地保证90％的内存命中率，但是其中存在小的随机磁盘I／O，严重地影响了磁盘的性能，针对这个小随机磁盘I／o，chunks切“铷采用Flash存储器来加快对索引的查找。4．2硬件加速技术从计算机系统结构的观点出发，除了上面基于软件角度的考虑外，重删系统流程的每一个功能部分都可以采用硬件加速技术来提升重删系统的性能。基于数据流的变长分块算法Chunking和块指纹哈希算法ChunkHashing其计算开销都比较大，延长了系统的响应时间，考虑将数据流分段实施分块和指纹哈希有利于实现上的并行性，从而提升系统的响应时间，如P-Dedupe[28]采用多核处理器或多处理器来实现重删系统的流水线和并行性有助于降低系统延迟时间，该思想的实施将会使主存储重删系统采用变长分块技术成为可能。重删流程中的指纹检索(H，iII—dexing)和保存元数据和唯一数据(DataStoring)是整个I／o优化的重点，一方面，如果不考虑RAM扩展限制，可以无限增加RAM，将所有的FP都存放于RAM中加快指纹检测过程，但是由于CPU型号和主板资源的限制，这一想法肯定不可能，目前单节点终端机RAM一般都是2G或4G，如果考虑将一个集群PC的RAM构建成RAMCloudE29]将会成倍地扩大内存，从而加快指纹查询检索时间；另一方面影响指纹检索和写入元数据及唯一数据的性能瓶颈在于磁盘I／0性能的限制，目前单磁盘的性能很难达到500个10PS，而新型的存储介质SSD(S0lidStateDisk)和PCM(PhaseChangeMemory)·28·都具有较高的IOPS数、高吞吐率和低访问延迟的特性[30,z1]，dell[32]和NETAPlD[33]企业级的单个SSD的性能能达到6k～18k个lOPS随机读性能，具有80～250MB／s的顺序读写吞吐率，随机写性能仅能达到100～140个IOPS，访问时间为0．05ms～0．5ms，正是由于SSD良好的性能，目前重删系统采用SSD来存储元数据，如Microsoft针对在线二级存储重删系统使用Flash来提升重删性能，提出的ChunkStashc34]主要是在传统的RAM与DISK之间增加一级FlashMemory，由于Flash良好的读写速度，使得元数据的查找速度得以提升。以吞吐率进行测试，结果显示：其比基于磁盘索引的重删系统快7X～60X，在磁盘阵列里可以采用RAm技术来进一步提升I／O性能。ChunkstashE34J注意到在DataDomain公司理想的情况下确保了大多数的查询发生在内存，但是这里不可避免地存在一些小的随机写磁盘I／0，由于这些随机的写磁盘I／0导致性能的降低，如果能改善随机磁盘I／o的命中率将会显著地提升整个吞吐率。因此提出了使用Flash存储器和Flash存储器感知的算法和数据结构来获得更快的索引查询操作。Flash存储器的读写性能好于SCSI磁盘而低于RAM。但是Flash的随机更新是相当低的，通过将Flash的随机更新转变为Log结构的扩展操作来克服对Flash的随机更新。评估结果显示，使用Flash磁盘能得到200MB／See的吞吐率。4．3垃圾回收技术垃圾回收技术在存储系统中用于判断某个物理块是否应该被回收，具体来讲就是维护元数据表中的物理块组的使用情况，目前主要有3种通用的思路[35]：标记和扫描技术(MarkandSweep)、基于引用计数(ReferenceCountbased)和基于时效期的技术(Exph-yTimebased)。标记和扫描技术(MarkandSweep)就是对已使用的每一个物理块进行标记，然后对所有的物理块进行扫描以回收未作标记的物理块，但是在标记阶段需要冻结元数据表从而不允许用户访问，另外标记物理块的开销也将是非常大的，不可能将其放于RAM，因此更新PBA将会导致低磁盘I／O性能。Hydrastol[36]提出只读标记与扫描(ReadOnlyMarkandSweep)，解决了标记阶段冻结系统的问题，回收是通过块引用数来实现的，其引用数的增加是定期更新的，从而使随机更新转变为顺序更新。Fanglut23]提出分组标记和扫描(GroupedMarkandSweep)机制，其主要思想是：为了避免在标记阶段处理每一个文件和扫描阶段处理每一个容器，通过使用文件管理器将备份数据流归为不同容器的不同层次，因此标记阶段仅仅标记一个组中发生改变的文件，而扫描也仅仅扫描标记阶段所处理组所在的容器，从而大大降低了标记所用时间开销，标记和扫描的工作量是随着系统载荷的变化而变化的，因而其具有可扩展性、高可靠和快速的特点。基于引用计数(ReferenceCountbased)简单来讲就是对每一个物理块使用一个计数器来记录其引用的次数，每一次创建一个新块和删除一个块时，其计数器就相应地加1或减1，每一次更新的时候检测其计数器为0，说明该块未被使用可以回收，比起标记和扫描的方式来讲避免了耗时的扫描，但系统规模比较大时，其更新的过程也会降低系统的性能。基于时效期的技术(ExpiryTimebased)通过PBA时效期的方式来替代万方数据引用计数，因而可进一步地减少更新次数，但是当覆写物理块时需要更新其时间，在垃圾回收时需要扫描所有的物理块，看其是否过期。目前有的系统可能使用的是其中的一种方式，或是两种混合以取得更好的时间和性能开销。4．4striping技术与纠舅码技术重复数据删除造成了数据在磁盘上的不连续存储，从而降低了磁盘I／0的性能，VentiE25]为了提升I／0性能最早采用了Striping技术[49|，Striping技术就是一种自动地将I／O的负载均衡到多个物理磁盘上的技术，在读数据时以并行的方式从不同的磁盘上获取数据块，从而获得非常好的性能。另外重删存储系统中数据的可靠性也是非常值得关注的，单纯地靠使用副本的机制一方面存储空间效率比较低，另一方面也不能确保数据失效时能够完整地恢复。目前提高存储系统可靠性普遍采用的是纠删码技术[蜘，如DataDomain公司的D1)斟241采用能够同时容双盘失效的RAID-6编码来纠错，现有的支持多盘容错的纠删码，如Ree&Solomon编码、Hover编码、wEA．Ⅵ’R编码和STAR编码等都可以用来提高存储系统的可靠性；虽然纠删码比起副本机制能够获得更高的空间效率，但是需要大量的CPU计算开销。目前大多数提高可靠性的方案都是单纯从副本或纠删码的角度出发考虑可靠性和性能，因此如何结合副本和纠删码两种方案来提高系统的性能和可靠性将有待进一步研究。5重捌系统分析与讨论重删系统性能主要体现在I／0吞吐率、平均响应时间和重删率3个方面，重删系统所服务数据对象的数据构成特征和规模决定了该重删系统的性能考虑，不同应用场景的重删系统总是在这3者之间权衡。表1各种重删系统的对比表1对各种重删系统进行了对比和总结，迄今为止大部分重复数据删除研究都是为了提高备份和归档等从存储系统的重删能力。Venti[25]是最早给出的在备份系统中实施重删的设计方案，由于归档和备份系统负载数据集的特点，很多数据都是冗余的，数据有明显的局部性特征，语义信息多，主要处理大数据级的流式写，对延迟不敏感，因而采用在线方式处理，但其对吞吐率比较敏感，因而可以采用CDC算法来实现变长分块以获得更高的重删率。很多 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 中提出的，包括VentiE251、刚Lo[47|、Sp