毕业设计论文基于iSCSI的重复数据删除系统的设计与实现.doc

摘 要信息化的快速发展致使数据量与日俱增，简单的存储这些数据对企业而言并不是最佳的解决方案存储需要投入成本，大量的文件最终将会加重企业数据备份以及灾难恢复系统的负担。企业与其不断的扩充磁盘容量来应对数据量的增加，还不如转向数据删除技术，以存储更少的数据。近年来新兴的重复数据删除技术就是减少存储空间的有效方式之一。通过对重复数据删除技术的深入研究，提出了一种基于iSCSI平台的重复数据删除存储系统。该系统实现了LBA映射、指纹计算、指纹检索和指纹索引表管理等功能。通过LBA映射表的组织和管理，实现了重复数据删除前后数据块逻辑地址的转化和对应关系；指纹计算模块中采用基于散列的SHA-1算法，实现了将4KB数据块转化为160位摘要值的过程；指纹检索和指纹索引表的管理采用三级索引结构，实现了指纹的精确定位和快速查找。为了弥补重复数据删除带来的系统性能的损失，针对重复数据删除功能中指纹检索性能瓶颈进行了优化，提出了基于布鲁姆过滤的指纹检索算法，大量的指纹检索请求被过滤掉，从而提高检索效率。对系统性能、重复数据删除压缩比和检索过滤算法的效果进行了相关测试。分别测试了标准iSCSI和加入重复数据删除模块后的iSCSI系统的性能，结果表明，加入重复数据删除之后，虽然系统性能有所下降，但是下降的幅度还是预期的范围之内；对重复数据删除压缩比进行了测试，测试结果表明压缩效果的好坏与应用环境密切相关，当应用于那些信息重复度较高的环境如备份存储系统、归档存储系统等时，具有较好的压缩效果；最后对检索过滤算法进行了测试，测试出的过滤率和误判率都可以达到预期效果。关键词：重复数据删除，指纹检索优化，存储性能AbstractResulted in the rapid development of information technology increasing the amount of data, simple storage of these data to enterprises is not the best solution - storage needs input costs, a large number of documents that will ultimately increase the enterprise data backup and disaster recovery burden. Compared to expand disk capacity to respond to the increase in the amount of data, companies might as well turn to remove the technical data to store less data.In recent years, new data deduplication technology is one of effective way to reduce storage space.Data de-duplication technology by further research, a platform based on iSCSI deduplication storage systems. This system has LBA mapping, fingerprint calculation, fingerprints and fingerprint search index table management. LBA mapping table by the organization and management, and data de-duplication before data blocks the conversion of logical address and correspondence; fingerprint calculation module based on SHA-1 hash algorithm, implemented into the 4KB block 160 Summary value of the process; fingerprints and fingerprint index table to retrieve the management of all three index structure is used to achieve precise positioning and fast fingerprint search. To make up for deduplication performance caused the loss of data deduplication feature for fingerprint retrieval performance bottlenecks, for a special algorithm optimization, proposed fingerprint retrieval based on Bloom filter filtering algorithm to filter out a large number of fingerprint retrieval request, thereby enhancing the efficiency of retrieval. On system performance, data deduplication, compression ratio and the effect of filtering algorithms to retrieve the relevant tests. ISCSI and standard were tested by adding data deduplication module of the iSCSI system performance, results show that adding data deduplication, the system performance has declined; on data deduplication compression ratio were tested, the test results show that good compression bad environment is closely related with the application, when applied to repeat that information environment such as a higher degree of backup storage systems, archival storage systems, etc., and has good compression effect; Finally, the search filter algorithm has been tested, tested the filtration rate and false positive rate can achieve the desired results. Keywords: De-duplication, Fingerprint search optimization, Storage Performance目 录摘 要IABSTRACTII目 录IV1绪 论11.1课题背景11.2课题研究目的及意义21.3国内外发展现状21.4课题的主要研究工作41.5课题的来源52系统关键技术概述62.1iSCSI平台简介62.2重复数据简介72.3重复数据删除的基本原理82.4数据处理粒度分析92.5BLOOM FILTER算法102.6本章小结133重复数据删除方案设计143.1系统功能需求143.2系统总体设计143.3LBA映射表163.4指纹计算模块163.5指纹管理和检索模块173.6基于BLOOM FILTER算法的指纹检索优化193.7本章小结204重复数据删除系统实现214.1LBA映射表实现214.2指纹计算模块实现224.3指纹索引表的建立与指纹检索224.4BLOOM FILTER过滤算法的实现234.5处理流程分析244.6本章小结275系统测试与分析285.1测试环境介绍285.2测试结果及分析285.3本章小结326总结与展望336.1总结336.2未来展望33致 谢35参考文献36371 绪 论本章首先介绍了当前存储系统面临的挑战和技术发展趋势，然后简述了本论文研究的目的及意义，接着分析了重复数据删除技术的发展现状，介绍了国内外在重复数据删除领域的相关研究工作，最后对本文的主要研究内容及课题来源作了具体说明。1.1 课题背景随着信息化时代的推进，各企事业单位的信息数据量也不断增长，存储管理员不断努力地处理日益激增的数据，比如，文本、声频、视频、图像，还有不断增加的大容量邮件附件。然而存储这些数据对企业而言并不是最佳的解决方案存储需要投入成本，大量的文件最终将会加重企业数据备份以及灾难恢复系统的负担。企业与其寻求更多的存储数据的不同方式，还不如转向数据删除技术，以存储更少的数据。近年来新兴的重复数据删除技术1就是减少存储空间的一种方式，它通过识别和消除数据环境中的冗余数据，确保只将单一的数据保存在存储介质中，从而节省了大量的存储空间，降低了存储成本。这意味着只需要更少的磁盘和更低频率的磁盘采购。更有效地利用磁盘空间，就能够延长磁盘保存期限，这样，提供了更好的恢复时间目标，更长的备份时间。同时，重复数据删除还可以缩减必须通过无线网络传送来实现远程备份、复制和灾难恢复的数据2。这样不仅显著提高现有磁盘存储空间的有效容量，从而使保护数据所需的物理磁盘数量更少，还有助于企业对数据的维护管理。这便可以帮助企业减轻硬件投资和后期维护所带来的经济压力。由于重复数据删除技术可使一些因存储容量需求巨大而成本高的数据管理和保护方案变得经济可行，因此，在工业领域，重复数据删除技术在数据保护和归档留存领域得到了应用。当前，在学术研究领域，重复数据删除技术也是研究的热点之一。本课题的研究中，在基本的iSCSI平台中加入重复数据删除技术，数据存储之前先进行去重处理。为了弥补重复数据删除带来的性能损失，利用过滤技术对数据检索模块进行了优化，提高检索性能。1.2 课题研究目的及意义重复数据删除技术通过有效地减少数据，消除备份成为减低数据存储成本的重要技术，成为大家关注的焦点。在一个完整的备份工作中往往会存在大量的重复数据，如果所有的数据不加处理的进行备份，那么这种备份开销是巨大的，更何况很多情况下数据会备份好几份。在使用磁带作为存储介质的系统中，这种完全备份还是可以接受的；但是在磁盘系统中，完全备份会消耗大量的磁盘空间，使成本增加。这种开销多数情况下是企业不愿意去承受的。将重复数据删除技术应用于备份系统中带来的优势就很明显了：（1）减少备份容量需求，节约成本。研究表明，这种容量缩减幅度一般保持在10-20倍，在这个幅度中实现的磁盘容量需求减缩将为用户带来强有力的成本节约，包括：更小的磁盘、更低的能耗和冷却成本。（2）“释放”容量意味着以更少的介质管理，完成更多的备份数据，获取更长的数据保留时间。（3）重复数据删除改善恢复时间目标（RTO）和可靠性。用户备份到磁盘的数据越多，就越能满足RTO需求，重复数据删除技术使客户在磁盘上备份更多的数据，保留更长的时间，从而提高RTO。通过重复数据删除技术，所有到来的数据请求都要先进行检索，如果发现该数据已经存在，则只进行相关的映射处理，而不再重复存储。这样就可以保证没有重复数据，从而降低存储消耗，降低成本。1.3 国内外发展现状当前国际上的各大存储厂商均开始在自己的存储系统中开始应用重复数据删除技术，比如EMC, NetApp, DataDomain等。目前比较成熟的产品中，重复数据删除技术一般是用于备份和归档系统；用于主存储系统和分布式系统中的还相当少。国内的存储厂商如华赛、H3C等公司，也开始了重复数据删除方面的研究，并已申请了相关专利。目前，市场上提供重复数据删除的厂商基本上可以分为两个阵营：In-line（带内）重复数据删除和Post-process（带外）重复数据删除。In-line重复数据删除是指数据保存到存储系统之前就进行重复数据删除，这样做的优势在于备份过程只需进行一次。Post-process重复数据删除是指在数据备份处理之后才进行重复数据删除，它的优势在于我们无需担心由于重复数据处理使CPU负担加重而导致备份服务器和存储目标之间出现瓶颈。重复数据删除技术大致分为两个方向，一方面是数据备份领域，另一方面是基础存储领域。从目前市场情况来看大部分应用主要还是在备份领域，重复数据删除技术通过识别和消除数据环境中的冗余数据，从而大大减少需要保护的数据量，确保同样的数据信息只被保存一次，这样不仅显著提高现有磁盘存储空间的有效容量，从而使保护数据所需的物理磁盘数量更少，还有助于企业对数据的维护管理。这便可以帮助企业减轻硬件投资和后期维护所带来的经济压力。随着数字信息的爆炸式增长，所存在的重复数据越来越多，造成了存储资源的极大浪费。重复数据消除技术的出现在很大程度上缓解了该问题，该技术也得到了越来越广泛的认可。目前重复数据删除技术在工业上主要应用于三个方面：数据备份系统、归档存储系统和远程灾备系统。为了满足用户的需求，备份设备已渐渐从传统的磁带库过渡到磁盘设备，但是考虑到成本不可能为磁盘设备无限扩容，而随着数据量的不断增加，所有备份的数据越来越多，面临容量膨胀的压力，重复数据删除技术的出现，为最小化存储容量找到有效的方法。由于参考数据的数量不断增长，而法规遵从要求数据在线保留的时间更长，并且由于高性能需求需要采用磁盘进行归档，因此，企业一旦真正开始进行数据的归档存储就面临成本问题，重复数据删除技术通过消除冗余实现高效率的归档存储，从而实现最低的成本，目前，归档存储系统的重复数据删除技术主要是基于Hash的方法，产品的销售理念是以内容寻址存储(CAS)技术为主，分为纯软件和存储系统两类。在远程灾备系统中，需要将大量的数据迁移到异地的系统中，随着数据量的不断增长，数据传输的压力越来越大，通过重复数据删除技术在数据传输前检测并删除重复的数据，可以有效地减少传输的数据量，提高数据传输速度，例如飞康的MicroScan软件就采用了该技术。重复数据删除技术正在不断发展，因此，可以预计其应用也会不断拓展，用户将在多种应用环境中可获得重复数据删除带来的成本效益，这些应用环境不仅只是包括备份和归档，而且将覆盖其它存储应用、网络应用和桌面应用中。1.4 课题的主要研究工作本论文研究的主要内容有以下几个方面：（1）重复数据删除技术的设计与实现。通过分析重复数据删除的一般流程，实现了重复数据删除模块的基本功能，包括LBA映射表的管理、指纹计算以及指纹索引表的建立与管理。（2）重复数据删除中指纹检索优化设计与实现。指纹检索过程是重复数据删除技术中的一大瓶颈，本系统通过基于Bloom Filter算法的检索过滤技术的实现，极大的提高了指纹检索的性能。本论文内容组织如下：第一章对重复数据删除技术的相关背景知识做了简单的介绍，对课题研究的目的、意义以及国内外研究发展状况做了简要的描述。第二章详细介绍了重复数据删除系统的总体设计。首先阐述了重复数据删除技术的基本原理和系统的总体设计框架，然后对各个功能模块分别进行介绍，包括LBA映射表、指纹计算模块和指纹检索模块。第三章描述了重复数据删除系统的具体实现过程。首先分模块详述了各个模块的实现方案，然后重点对检索优化算法部分的设计和实现进行了说明，最后分析了系统的处理流程。第四章对重复数据删除系统各方面的性能进行测试。第五章总结目前所做的工作并展望未来的研究工作。1.5 课题的来源本课题受国家973重大基础研究计划 “高效能存储系统组建方法研究”（项目编号：2011CB302300）资助。2 系统关键技术概述目前国内外已经在很多平台上实现了重复数据删除技术，在本文的研究中，是基于iSCSI平台实现的。本章首先介绍了iSCSI存储平台的相关知识，然后介绍了重复数据删除技术，最后就Bloom Filter算法的背景、算法基本原理和误判率作了简要分析。2.1 iSCSI平台简介iSCSI3(互联网小型计算机系统接口)是一种在Internet协议网络上4，特别是以太网上进行数据块传输的标准。它是由Cisco和IBM两家发起的，并且得到了IP存储技术拥护者的大力支持。是一个供硬件设备使用的可以在IP协议上层运行的SCSI指令集。简单地说，iSCSI可以实现在IP网络上运行SCSI协议，使其能够在诸如高速千兆以太网上进行路由选择。iSCSI的主要功能是在TCP/IP网络上的主机系统（启动器initiator）和存储设备（目标器target）之间进行大量数据的封装和可靠传输过程。其工作流程如图2. 1所示：当客户端发出一个数据、文件或应用程序的请求后，操作系统就会根据客户端请求的内容生成一个SCSI命令和数据请求，SCSI命令和数据请求通过封装后会加上一个信息包标题，并通过以太网传输到接收端；当接收端接收到这个信息包后，会对信息包进行解包，分离出的SCSI命令与数据，而分离出来的SCSI命令和数据将会传输给存储设备，当完成一次上述流程后，数据又会被返回到客户端，以响应客户端iSCSI的请求。图2. 1 iSCSI工作流程图作为一种基于网络的数据存储技术，iSCSI具有很多优点：（1）硬件成本低廉。基于iSCSI技术的适配卡、交换机和缆线这些产品的价格相对较低，而且iSCSI可以在现有的网络上直接安装，并不需要更改企业的网络体系，这样可以最大程序的节约投入。（2）操作简单。此技术主要是通过IP网络实现存储资源共享，只需要现有的网络功能即可管理，其设置也非常简单。（3）扩充性强。由于iSCSI存储系统可以直接在现有的网络系统中进行组建，并不需要改变网络体系，加上运用交换机来连接存储设备，对于需要增加存储空间的企业用户来说，只需要增加存储设备就可完全满足，因此，iSCSI存储系统的可扩展性高。此外，iSCSI技术维护方便、传输速度快、突破距离限制等等，这些优势使得该技术在各方面的应用越来越广泛。本文的研究工作也是以iSCSI为基础平台而展开的。2.2 重复数据简介相同的数据在存储系统中反复存储了多次，这样的数据就可以简单的理解为是重复数据，也叫做冗余数据。重复数据在很多地方都存在，比如，备份系统由于其系统本身的特点就决定了总是存在大量的冗余数据。在不同用户的个人电脑上也会有很多数据是相同的，像操作系统文件、office文件等等。大部分网络上的重复数据量大到令人吃惊，如果不加于处理的话，随着网络上信息量的不断增加，可能会造成磁盘空间严重不足，而且我们会发现磁盘中存储的数据大多都是重复的，所以我们必须想个办法解决重复数据的问题。2.3 重复数据删除的基本原理重复数据删除8，也被称为智能数据压缩或单一实例存储。它是一种可以减小数据存储需求的手段。重复数据删除的处理过程是通过删除冗余数据，确保实际上只有第一个单一实例数据被存储。而被删除的重复数据将由一个指向元数据的指针所代替。这样就可以大大节省存储开销，降低成本。图2. 2重复数据删除基本流程如图2. 2所示，重复数据删除的一般分为以下四个流程：（1）获取待存储的数据流。重复数据删除可以对文件、数据块或者位进行操作。所以这个数据流有可能是整个文件，也有可能是数据块。分别对应于文件级重复数据删除和块级重复数据删除。（2）计算出获取到的数据的指纹值。在重复数据删除系统中，通常都会对数据进行标识，一般采用数据指纹来作为唯一的标识。获取指纹值的算法常采用MD5、SHA-1910等散列算法。（3）将计算出的数据指纹值与指纹库中的值进行比对。以指纹值去检索指纹库，查找该指纹值是否在已有的指纹库中。（4）根据比对结果进行重复数据删除操作。如果数据指纹值在指纹库中，说明该数据流已存在，只需要保存一个指向元数据的指针即可；如果没有找到相同的指纹，说明该数据流不存在，那么要将该指纹加入到指纹库中，同时要存储该数据流。基本上重复数据删除的流程就是这样，但是在不同的系统中，具体的流程要比这个复杂一些。在本文的研究中，采用的是基于iSCSI的重复数据删除方式，整个系统在iSCSI平台上实现，获取的数据流会被分为固定大小（4KB）的数据块，然后利用SHA-1散列算法计算出各个数据块的指纹值，接着以指纹值为关键字进行检索，根据检索结果进行相应的处理。2.4 数据处理粒度分析按照数据处理粒度来划分，重复数据删除技术包括文件级重复数据删除、块级重复数据删除两种11。尽管结果存在差异，但判断文件或块是否唯一都能带来好处。两者的差异在于减少的数据容量不同，判断重复数据所需的时间不同。文件级重复数据删除技术通常也称为单实例存储(SIS)，根据索引检查需要备份或归档的文件的属性，并与已存储的文件进行比较。如果没有相同文件，就将其存储，并更新索引；否则，仅存入指针，指向已存在的文件。因此，同一文件只保存了一个实例，随后的副本都以指针替代，而指针指向原始文件。块级重复数据删除技术将数据流分割成块，检查数据块，并将这些部分与之前存储的信息予以比较，检查是否存在冗余。同样，如果存在相同数据块，就增加一个引用指针；否则，就将其存储。文件级和块级各有各的优缺点。文件级重复数据删除的索引非常小，在判断重复数据和检索时所花费的时间少。由于索引小、比较次数少，文件级删除技术所需的处理负荷较低，对恢复时间的影响较少。但是当文件内部发生一点小变化，那么整个文件都必须重新存储，而且以文件为基本单位进行重复数据删除时，重复率低，所以压缩比相对较低。块级重复数据删除中数据要分块处理，因而会花大量的精力去索引和管理各块数据，检测重复数据时的匹配工作也是比较大的。但通过将文件中的数据分块处理，可以大大提高数据的重复率，数据压缩比会是文件级的好几倍，可以更好的实现重复数据删除。不管数据流是文件级的还是块级的，在标准iSCSI平台中，最终都是被分成一页一页的数据来进行处理的，也就是说，iSCSI平台自动完成了数据分块的操作，所以为了不与平台本身的结构起冲突，基于iSCSI的重复数据删除系统我们也选择按块级来处理。不同的重复数据删除系统检查的数据块大小各不相同，通常情况下分为两种，变长块和定长块。由于变长块处理起来比较繁琐，所以在本文研究中采用定长块的方式。固定块的大小可能为4KB、8KB或者64KB等等，区别在于数据块大小越小，被判定为冗余的几率越大。这就意味着消除的冗余更多，存储的数据更少。但显而易见的，数据块大小越小，文件被分得的数据块数量就越庞大，这也意味着要花更多的空间去管理块结构，判断重复的过程消耗更多的时间。在本论文研究中选择的块大小是4KB。将数据流分成一块一块的数据，每一块的数据大小为4KB，块大小比较小，以期望可以获得更高的去重率。在数据管理和重复数据比对的过程中，希望可以通过利用一些比较高效的方式来缓解这一部分的缺陷，同时也可以采取一些优化措施来避免这一部分成为系统瓶颈。2.5 BLOOM FILTER算法2.5.1 算法背景Bloom Filter1213是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。2.5.2 算法基本原理Bloom过滤器14对集合采用一个位串表示，并支持元素的哈希查找。既能表示集合，支持集合元素查询，又能有效地过滤掉不属于集合的元素。其算法结构的实质是将集合中的元素通过k 个哈希函数映射到位串向量中。近年来Bloom Filter算法在实际中的应用越来越广泛，关于这种算法的相关研究工作也备受关注。标准的Bloom Filter算法的工作原理如下：如图 2.1所示，数据集合S=s1,s2,sn共有n 个元素通过k 个哈希函数h1,h2,hk 映射到长度为m 的位串向量V 中。通常, Bloom过滤器表示的汇总信息就是向量V。每一个哈希函数相互独立且函数的取值范围为0,1,2,m1。初始状态下，向量中的每个位都为0，对任意一个元素，第i个哈希函数映射的位置h（i）就会被置为1。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。图 2.1 Bloom Filter算法原理图Bloom Filter算法主要包含两个操作：插入操作和查询操作。元素插入操作就是将元素插入到集合，完成元素到Bloom过滤器的向量表示；元素的查询操作就是利用Bloom判断元素是否在集合中。Bloom过滤器在使用前必须初始化，即将V 向量的各位初始化为0。集合中元素的插入过程就是元素到向量的映射过程。元素插入操作如图 2.2所示：1）计算元素x的k个哈希地址，即h1(x), h2(x),.,hk(x)。2）将Bloom过滤器向量中对应位置置1，即Vh1(x) = Vh2(x) = =Vhk(x) = 1。图 2.2 元素插入过程示意图元素查询操作如图 2.3所示，基本上是插入操作的反过程，也分为两步：1）计算出元素x的k个哈希地址。2）检查Bloom过滤器向量中对应位置上的值是否为1。它们只要有一个是0，x必不在集合中。如果全为1，则x可能在集合中，但不一定。此时就出现了误判，即将不属于集合的元素误判为属于集合中。由于算法本身的缺陷，这种误判是始终存在的。图 2.3 元素查询过程示意图2.5.3 算法误判率Bloom过滤器作为一种支持集合查询的数据结构，在达到其高效、简洁的表示集合效果的同时，却存在某元素不属于数据集合而被指称属于该数据集合的可能性。可以通过数据模型来估算误判率的大小。假设哈希函数取值服从均匀分布，则当集合中所有元素都映射完毕后，V 向量任意一位为0 的概率: (2.1)在发生误判时，要求k个哈希函数计算得出的位都不为0，则其概率为 (2.2)由公式2.2可以看出，误判率的大小和n/m的值相关。对公式2.2求偏导，可以得到误判率最小时k，m，n三者之间的关系，如公式2.3： (2.3)一般情况下，可以固定集合总元素个数n和误判率p这两个参数，然后就可以根据公式（2.2）和公式（2.3）来计k值和m值。网上有提供的专门的计算器（Bloom Filter Calculator），可以输入n和p，计算出k和m。2.6 本章小结本章首先介绍了iSCSI存储平台的相关知识，然后介绍了重复数据删除技术，分别就重复数据删除的基本原理以及重复数据删除的处理粒度问题作了说明，最后介绍了Bloom Filter算法，包括该算法的背景、算法基本原理和误判率分析。3 重复数据删除方案设计上一章我们已经分别讨论了iSCSI平台工作流程、重复数据删除技术的基本原理、数据处理粒度以及布鲁姆算法，基于这些理论背景，我们将设计实现一个基于iSCSI平台的重复数据删除系统。该系统是在标准iSCSI协议的基础上，加入重复数据删除模块来实现的。本章主要介绍了系统的总体设计，并简要说明LBA映射表、指纹计算、指纹管理和检索等各模块的功能，然后介绍了基于Bloom Filter算法的指纹检索优化设计。3.1 系统功能需求本研究要实现的是基于iSCSI平台的重复数据删除系统，具有以下几个方面的功能需求和性能要求：（1）搭建基于iSCSI平台下的存储系统。（2）重复数据删除模块功能的实现。要实现重复数据删除的基本流程，完成数据指纹的计算、指纹表的建立与管理、指纹检索等基本功能。（3）实现对指纹检索模块的优化。当存储的数据量较大时，那么相应的指纹库也会很庞大，在进行指纹检索时就需要消耗较长的时间，会成为整个系统的性能瓶颈所在。为了提高检索性能，我们可以在检索之前先采用基于Bloom Filter算法的索引检索过滤技术对指纹进行过滤，这样可以极大的提高检索性能。3.2 系统总体设计整个系统采用iSCSI启动器作为客户端，iSCSI目标器作为服务器端，重复数据删除模块就嵌在iSCSI目标器代码中。如图 3.1所示，重复数据删除模块主要包括LBA映射表、指纹计算、指纹检索几个功能模块和检索性能优化部分。图 3.1重复数据删除系统总体设计图系统总体基本功能实现包括以下几个子模块：（1）LBA映射表。用来记录重复数据删除前请求的LBA与重复数据删除之后的LBA的映射关系，由于重复数据的存在，去重前几个不同的LBA去重后有可能对应同一个LBA。（2）指纹计算模块。利用基于散列的SHA-1算法计算出数据块的指纹值，4KB的数据页对应唯一的一个160bit的指纹值。（3）指纹索引表的建立与指纹检索模块。本系统中指纹索引表的建立采用多级索引的方式，指纹的检索也是采用多级检索的方式。在进行指纹检索之前，先利用基于bloom filter算法的过滤技术对指纹值进行过滤处理，过滤掉部分指纹检索请求从而提高检索性能。将过滤掉的那部分指纹加入到摘要向量中，对剩下的指纹值再进行指纹检索。3.3 LBA映射表在磁盘设备中，每个存储单元都会有一个标识位置的逻辑地址即LBA，当数据被存储到磁盘设备后，都会记录下该数据被存储在哪个地址单元中以便后来对数据进行读写操作。在标准的iSCSI平台中，用户对数据进行I/O操作时，都是对真实磁盘空间进行操作，所以只需要记录下数据存储的位置即可。但加入重复数据删除模块之后，重复数据只会在磁盘中存储一遍，用户对重复数据的操作会被定位到同一个逻辑地址单元。也就是说用户请求处理的LBA不再是真实磁盘的LBA，这中间会进行映射处理，将用户请求的LBA转化为对应磁盘的LBA。LBA映射表结构是重复数据删除系统涉及到的核心数据结构，该结构需要将上层模块中的请求地址LBA_U映射到下层提供的某个LBA_L之上，对于包含有相同数据的不同LBA_U需映射到同一个LBA_L上。3.4 指纹计算模块新到来的数据流被划分为一个个的4KB的数据块，要判断这些数据块是否是重复数据，如果不加任何处理，那么最直接的方法就是一个字节一个字节的去和其他已经存储的数据块去比对。大家可以想象一下，这样处理效率是极低的，低到重复数据删除模块失去了存在的意义。为了提高效率简化操作，我们必须想办法来简化数据块。类比人的识别，通常情况下，人与人的指纹是不一样的，因此我们可以用指纹来识别和标记某个人。数据块也一样，我们可以通过某种方式，将数据块转变成数据指纹，用该指纹来唯一标记这个数据块。数据指纹通常是一个哈希值，对哈希值的比对就要比数据块的比对要简单快捷得多。一般采用哈希散列算法来计算数据指纹，比如SHA-1算法、MD5算法等等。在本论文的设计中，哈希算法是作为一个独立的模块存在的，这样就便于替换不同的算法。在本系统中，采用的是SHA-1算法来计算数据指纹。SHA(Secure Hash Algorithm)全称为安全散列算法，由一系列密码散列函数组成。SHA-1为较早的一种散列算法，可以从最大264位的原数据中产生160bit的摘要值，来对原数据进行唯一性标识。也就是说，在本系统中，4KB的数据块经由指纹计算模块后产生出160bit的指纹值，用此值来作为原数据块的标识。SHA-1算法在标准RFC文档中有详细的说明，并且提供了标准的实现代码，系统中直接使用了此代码，具体的算法原理在此不再详述。3.5 指纹管理和检索模块3.5.1 指纹索引表的组织与建立指纹索引表是整个重复数据删除模块的核心元数据管理部分，经过重复数据删除后的每个数据块都是单一实例数据块，每一个单一实例数据块都对应一个指纹索引节点。合理的组织和管理这些索引节点，是重复数据删除模块设计的关键问题，也决定了指纹检索的方式和效率。4KB大小的数据块通过SHA-1散列算法得到的指纹值为160bit，直接通过这160bit值来进行全哈希显然是不可行的。为此，在本系统中，采用了多级索引表组织方式，即取160bit指纹值中的前24bit值共3个字节作为多级索引关键字。将三个字节分别设为key1、key2 、key3，则每个key的取值都在0255，通过这三个key值可以建立三级索引表，key1、key2 、key3分别作为三级索引的关键字，每级索引最多有256个关键字，最后一级索引后挂接的便是指纹索引节点。指纹索引表结构如图 3.2所示。三级索引表的每个索引节点只用一个指针记录即可，即每个节点需要占用4个字节的空间，整个三级索引表一共有1 + 256 + 2562 + 2563 个节点，通过计算可以得到共占用约64MB内存，这种程度是可以接受的。图 3.2 三级索引表结构图3.5.2 指纹检索流程分析指纹检索就是确定待检索的指纹值是否存在于指纹索引表中。根据指纹索引表的组织方式，可以确定指纹检索也采用三级检索的方式，其基本流程如下：图 3.3 指纹检索流程由指纹检索流程可以看出，假设N为三级索引后某一个指纹索引链表的平均长度，指纹检索的算法复杂度为O（3 +N）。由于SHA-1算法的高散列性，可以预见到经过三级索引后，所有的指纹索引节点将较为均匀的分配到整个链表上，即N的离散性较低，这样就可以保证每一次的指纹检索其算法复杂度相当。3.6 基于BLOOM FILTER算法的指纹检索优化3.6.1 重复数据删除检索性能瓶颈重复数据删除技术的应用必然会对存储系统的性能造成一定的影响。主要的性能损耗出现在指纹检索模块中，随着数据量的不断增加，指纹索引表会变得越来越庞大，大量的元数据会使指纹数据检索成为系统的瓶颈。基于SHA-1算法的数据指纹计算模块会为每一页4KB的数据块产生160bit的指纹值。当指纹索引节点不断增加，对指纹的索引和对指纹值的比对都将消耗更长的时间。为了避免指纹索引成为瓶颈，本系统中采用了三级索引结构来管理和检索数据指纹，这样可以有效地减小指纹检索算法的时间复杂度。除了优化索引表的结构之外，我们还可以在检索之前先判断该数据指纹需不需要进行检索，如果我们事先能判定出该数据指纹值一定在或者一定不在指纹索引表中，那么我们就可以省去指纹检索的过程，从而可以提高检索效率。在本系统中，我们采用的是基于Bloom Filter算法的检索过滤技术，