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

《毕业设计（论文）-基于iSCSI的重复数据删除系统的设计与实现.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-基于iSCSI的重复数据删除系统的设计与实现.doc（42页珍藏版）》请在三一文库上搜索。

1、I 摘 要 信息化的快速发展致使数据量与日俱增，简单的存储这些数据对企业而言并不 是最佳的解决方案存储需要投入成本，大量的文件最终将会加重企业数据备份 以及灾难恢复系统的负担。企业与其不断的扩充磁盘容量来应对数据量的增加，还 不如转向数据删除技术，以存储更少的数据。近年来新兴的重复数据删除技术就是 减少存储空间的有效方式之一。 通过对重复数据删除技术的深入研究，提出了一种基于 iSCSI 平台的重复数据 删除存储系统。该系统实现了 LBA 映射、指纹计算、指纹检索和指纹索引表管理等 功能。通过 LBA 映射表的组织和管理，实现了重复数据删除前后数据块逻辑地址的 转化和对应关系；指纹计算模块中采

2、用基于散列的 SHA-1 算法，实现了将 4KB 数据 块转化为 160 位摘要值的过程；指纹检索和指纹索引表的管理采用三级索引结构， 实现了指纹的精确定位和快速查找。为了弥补重复数据删除带来的系统性能的损失， 针对重复数据删除功能中指纹检索性能瓶颈进行了优化，提出了基于布鲁姆过滤的 指纹检索算法，大量的指纹检索请求被过滤掉，从而提高检索效率。 对系统性能、重复数据删除压缩比和检索过滤算法的效果进行了相关测试。分 别测试了标准 iSCSI 和加入重复数据删除模块后的 iSCSI 系统的性能，结果表明，加 入重复数据删除之后，虽然系统性能有所下降，但是下降的幅度还是预期的范围之 内；对重复数据删

3、除压缩比进行了测试，测试结果表明压缩效果的好坏与应用环境 密切相关，当应用于那些信息重复度较高的环境如备份存储系统、归档存储系统等 时，具有较好的压缩效果；最后对检索过滤算法进行了测试，测试出的过滤率和误 判率都可以达到预期效果。 关键词关键词：重复数据删除，指纹检索优化，存储性能 II Abstract Resulted in the rapid development of information technology increasing the amount of data, simple storage of these data to enterprises is not the

4、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 t

5、o 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 fi

6、ngerprint 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 val

7、ue 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 per

8、formance 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 ra

9、tio 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 wer

10、e 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 III higher degree of backup storage systems, archival storage systems, etc., and has good compression effect; Finally, the sear

11、ch 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 IV 目 录 摘摘 要要 .I ABSTRACT .II 目目 录录.IV 1绪绪 论论1 1.1课题背景.1 1.2课题研究目的及意义.2 1.3国内外发展现状.2 1.4课题的主要研究工作.4 1

12、.5课题的来源.5 2系统关键技术概述系统关键技术概述 .6 2.1ISCSI 平台简介.6 2.2重复数据简介.7 2.3重复数据删除的基本原理 .8 2.4数据处理粒度分析.9 2.5BLOOM FILTER 算法 10 2.6本章小结.13 3重复数据删除方案设计重复数据删除方案设计14 3.1系统功能需求.14 3.2系统总体设计.14 3.3LBA 映射表16 3.4指纹计算模块.16 3.5指纹管理和检索模块.17 3.6基于 BLOOM FILTER 算法的指纹检索优化19 V 3.7本章小结.20 4重复数据删除系统实现重复数据删除系统实现21 4.1LBA 映射表实现21 4

13、.2指纹计算模块实现.22 4.3指纹索引表的建立与指纹检索 .22 4.4BLOOM FILTER 过滤算法的实现.23 4.5处理流程分析.24 4.6本章小结.27 5系统测试与分析系统测试与分析.28 5.1测试环境介绍.28 5.2测试结果及分析.28 5.3本章小结.32 6总结与展望总结与展望.33 6.1总结.33 6.2未来展望.33 致致 谢谢.35 参考文献参考文献.36 1 1绪 论 本章首先介绍了当前存储系统面临的挑战和技术发展趋势，然后简述了本论文 研究的目的及意义，接着分析了重复数据删除技术的发展现状，介绍了国内外在重 复数据删除领域的相关研究工作，最后对本文的主

14、要研究内容及课题来源作了具体 说明。 1.1课题背景 随着信息化时代的推进，各企事业单位的信息数据量也不断增长，存储管理员 不断努力地处理日益激增的数据，比如，文本、声频、视频、图像，还有不断增加 的大容量邮件附件。然而存储这些数据对企业而言并不是最佳的解决方案存储 需要投入成本，大量的文件最终将会加重企业数据备份以及灾难恢复系统的负担。 企业与其寻求更多的存储数据的不同方式，还不如转向数据删除技术，以存储更少 的数据。 近年来新兴的重复数据删除技术1就是减少存储空间的一种方式，它通过识别和 消除数据环境中的冗余数据，确保只将单一的数据保存在存储介质中，从而节省了 大量的存储空间，降低了存储成

15、本。这意味着只需要更少的磁盘和更低频率的磁盘 采购。更有效地利用磁盘空间，就能够延长磁盘保存期限，这样，提供了更好的恢 复时间目标，更长的备份时间。同时，重复数据删除还可以缩减必须通过无线网络 传送来实现远程备份、复制和灾难恢复的数据2。这样不仅显著提高现有磁盘存储空 间的有效容量，从而使保护数据所需的物理磁盘数量更少，还有助于企业对数据的 维护管理。这便可以帮助企业减轻硬件投资和后期维护所带来的经济压力。 由于重复数据删除技术可使一些因存储容量需求巨大而成本高的数据管理和保 护方案变得经济可行，因此，在工业领域，重复数据删除技术在数据保护和归档留 存领域得到了应用。当前，在学术研究领域，重复

16、数据删除技术也是研究的热点之 一。 2 本课题的研究中，在基本的 iSCSI 平台中加入重复数据删除技术，数据存储之 前先进行去重处理。为了弥补重复数据删除带来的性能损失，利用过滤技术对数据 检索模块进行了优化，提高检索性能。 1.2课题研究目的及意义 重复数据删除技术通过有效地减少数据，消除备份成为减低数据存储成本的重 要技术，成为大家关注的焦点。在一个完整的备份工作中往往会存在大量的重复数 据，如果所有的数据不加处理的进行备份，那么这种备份开销是巨大的，更何况很 多情况下数据会备份好几份。在使用磁带作为存储介质的系统中，这种完全备份还 是可以接受的；但是在磁盘系统中，完全备份会消耗大量的磁

17、盘空间，使成本增加。 这种开销多数情况下是企业不愿意去承受的。将重复数据删除技术应用于备份系统 中带来的优势就很明显了： （1）减少备份容量需求，节约成本。研究表明，这种容量缩减幅度一般保持在 10-20 倍，在这个幅度中实现的磁盘容量需求减缩将为用户带来强有力的成本节约， 包括：更小的磁盘、更低的能耗和冷却成本。 （2） “释放”容量意味着以更少的介质管理，完成更多的备份数据，获取更长 的数据保留时间。 （3）重复数据删除改善恢复时间目标（RTO）和可靠性。用户备份到磁盘的数 据越多，就越能满足 RTO 需求，重复数据删除技术使客户在磁盘上备份更多的数据， 保留更长的时间，从而提高 RTO。

18、 通过重复数据删除技术，所有到来的数据请求都要先进行检索，如果发现该数 据已经存在，则只进行相关的映射处理，而不再重复存储。这样就可以保证没有重 复数据，从而降低存储消耗，降低成本。 1.3国内外发展现状 当前国际上的各大存储厂商均开始在自己的存储系统中开始应用重复数据删除 3 技术，比如 EMC, NetApp, DataDomain 等。目前比较成熟的产品中，重复数据删除 技术一般是用于备份和归档系统；用于主存储系统和分布式系统中的还相当少。国 内的存储厂商如华赛、H3C 等公司，也开始了重复数据删除方面的研究，并已申请 了相关专利。 目前，市场上提供重复数据删除的厂商基本上可以分为两个阵

19、营：In-line（带内） 重复数据删除和 Post-process（带外）重复数据删除。In-line 重复数据删除是指数据 保存到存储系统之前就进行重复数据删除，这样做的优势在于备份过程只需进行一 次。Post-process 重复数据删除是指在数据备份处理之后才进行重复数据删除，它的 优势在于我们无需担心由于重复数据处理使 CPU 负担加重而导致备份服务器和存储 目标之间出现瓶颈。 重复数据删除技术大致分为两个方向，一方面是数据备份领域，另一方面是基 础存储领域。从目前市场情况来看大部分应用主要还是在备份领域，重复数据删除 技术通过识别和消除数据环境中的冗余数据，从而大大减少需要保护的数

20、据量，确 保同样的数据信息只被保存一次，这样不仅显著提高现有磁盘存储空间的有效容量， 从而使保护数据所需的物理磁盘数量更少，还有助于企业对数据的维护管理。这便 可以帮助企业减轻硬件投资和后期维护所带来的经济压力。 随着数字信息的爆炸式增长，所存在的重复数据越来越多，造成了存储资源的 极大浪费。重复数据消除技术的出现在很大程度上缓解了该问题，该技术也得到了 越来越广泛的认可。目前重复数据删除技术在工业上主要应用于三个方面：数据备 份系统、归档存储系统和远程灾备系统。为了满足用户的需求，备份设备已渐渐从 传统的磁带库过渡到磁盘设备，但是考虑到成本不可能为磁盘设备无限扩容，而随 着数据量的不断增加，

21、所有备份的数据越来越多，面临容量膨胀的压力，重复数据 删除技术的出现，为最小化存储容量找到有效的方法。 由于参考数据的数量不断增长，而法规遵从要求数据在线保留的时间更长，并 且由于高性能需求需要采用磁盘进行归档，因此，企业一旦真正开始进行数据的归 档存储就面临成本问题，重复数据删除技术通过消除冗余实现高效率的归档存储， 从而实现最低的成本，目前，归档存储系统的重复数据删除技术主要是基于 Hash 的 方法，产品的销售理念是以内容寻址存储(CAS)技术为主，分为纯软件和存储系统两 4 类。在远程灾备系统中，需要将大量的数据迁移到异地的系统中，随着数据量的不 断增长，数据传输的压力越来越大，通过重

22、复数据删除技术在数据传输前检测并删 除重复的数据，可以有效地减少传输的数据量，提高数据传输速度，例如飞康的 MicroScan 软件就采用了该技术。 重复数据删除技术正在不断发展，因此，可以预计其应用也会不断拓展，用户 将在多种应用环境中可获得重复数据删除带来的成本效益，这些应用环境不仅只是 包括备份和归档，而且将覆盖其它存储应用、网络应用和桌面应用中。 1.4课题的主要研究工作 本论文研究的主要内容有以下几个方面： （1）重复数据删除技术的设计与实现。通过分析重复数据删除的一般流程，实 现了重复数据删除模块的基本功能，包括 LBA 映射表的管理、指纹计算以及指纹索 引表的建立与管理。 （2）

23、重复数据删除中指纹检索优化设计与实现。指纹检索过程是重复数据删除 技术中的一大瓶颈，本系统通过基于 Bloom Filter 算法的检索过滤技术的实现，极大 的提高了指纹检索的性能。 本论文内容组织如下： 第一章对重复数据删除技术的相关背景知识做了简单的介绍，对课题研究的目 的、意义以及国内外研究发展状况做了简要的描述。 第二章详细介绍了重复数据删除系统的总体设计。首先阐述了重复数据删除技 术的基本原理和系统的总体设计框架，然后对各个功能模块分别进行介绍，包括 LBA 映射表、指纹计算模块和指纹检索模块。 第三章描述了重复数据删除系统的具体实现过程。首先分模块详述了各个模块 的实现方案，然后重

24、点对检索优化算法部分的设计和实现进行了说明，最后分析了 系统的处理流程。 第四章对重复数据删除系统各方面的性能进行测试。 第五章总结目前所做的工作并展望未来的研究工作。 5 1.5课题的来源 本课题受国家 973 重大基础研究计划 “高效能存储系统组建方法研究” （项目 编号：2011CB302300）资助。 6 2系统关键技术概述 目前国内外已经在很多平台上实现了重复数据删除技术，在本文的研究中，是 基于 iSCSI 平台实现的。本章首先介绍了 iSCSI 存储平台的相关知识，然后介绍了重 复数据删除技术，最后就 Bloom Filter 算法的背景、算法基本原理和误判率作了简要 分析。 2

25、.1iSCSI 平台简介 iSCSI3(互联网小型计算机系统接口)是一种在 Internet 协议网络上4，特别是以 太网上进行数据块传输的标准。它是由 Cisco 和 IBM 两家发起的，并且得到了 IP 存 储技术拥护者的大力支持。是一个供硬件设备使用的可以在 IP 协议上层运行的 SCSI 指令集。简单地说，iSCSI 可以实现在 IP 网络上运行 SCSI 协议，使其能够在诸如高 速千兆以太网上进行路由选择。 iSCSI 的主要功能是在 TCP/IP 网络上的主机系统（启动器 initiator）和存储设备 （目标器 target）之间进行大量数据的封装和可靠传输过程。其工作流程如图

26、2. 1 所 示： 当客户端发出一个数据、文件或应用程序的请求后，操作系统就会根据客户端 请求的内容生成一个 SCSI 命令和数据请求，SCSI 命令和数据请求通过封装后会加 上一个信息包标题，并通过以太网传输到接收端；当接收端接收到这个信息包后， 会对信息包进行解包，分离出的 SCSI 命令与数据，而分离出来的 SCSI 命令和数据 将会传输给存储设备，当完成一次上述流程后，数据又会被返回到客户端，以响应 客户端 iSCSI 的请求。 7 含iSCSI控制单 元的服务器 iSCSIIP数据 存储设备或SANiSCSIIP数据 IP网络 图 2. 1 iSCSI 工作流程图 作为一种基于网络的

27、数据存储技术，iSCSI 具有很多优点： （1）硬件成本低廉。基于 iSCSI 技术的适配卡、交换机和缆线这些产品的价格 相对较低，而且 iSCSI 可以在现有的网络上直接安装，并不需要更改企业的网络体 系，这样可以最大程序的节约投入。 （2）操作简单。此技术主要是通过 IP 网络实现存储资源共享，只需要现有的 网络功能即可管理，其设置也非常简单。 （3）扩充性强。由于 iSCSI 存储系统可以直接在现有的网络系统中进行组建， 并不需要改变网络体系，加上运用交换机来连接存储设备，对于需要增加存储空间 的企业用户来说，只需要增加存储设备就可完全满足，因此，iSCSI 存储系统的可扩 展性高。 此

28、外，iSCSI 技术维护方便、传输速度快、突破距离限制等等，这些优势使得该 技术在各方面的应用越来越广泛。本文的研究工作也是以 iSCSI 为基础平台而展开 的。 2.2重复数据简介 相同的数据在存储系统中反复存储了多次，这样的数据就可以简单的理解为是 重复数据，也叫做冗余数据。重复数据在很多地方都存在，比如，备份系统由于其 系统本身的特点就决定了总是存在大量的冗余数据。在不同用户的个人电脑上也会 8 有很多数据是相同的，像操作系统文件、office 文件等等。 大部分网络上的重复数据量大到令人吃惊，如果不加于处理的话，随着网络上 信息量的不断增加，可能会造成磁盘空间严重不足，而且我们会发现磁

29、盘中存储的 数据大多都是重复的，所以我们必须想个办法解决重复数据的问题。 2.3重复数据删除的基本原理 重复数据删除8，也被称为智能数据压缩或单一实例存储。它是一种可以减小数 据存储需求的手段。重复数据删除的处理过程是通过删除冗余数据，确保实际上只 有第一个单一实例数据被存储。而被删除的重复数据将由一个指向元数据的指针所 代替。这样就可以大大节省存储开销，降低成本。 获取待存储的数据流 （文件或者数据） 利用某种算法计算出获取 到的数据的指纹 比对计算出的数据指纹与 指纹库中的指纹 根据比对结果进行重复 数据删除操作 图 2. 2 重复数据删除基本流程 如图 2. 2 所示，重复数据删除的一般

30、分为以下四个流程： （1）获取待存储的数据流。重复数据删除可以对文件、数据块或者位进行操作。 所以这个数据流有可能是整个文件，也有可能是数据块。分别对应于文件级重复数 据删除和块级重复数据删除。 （2）计算出获取到的数据的指纹值。在重复数据删除系统中，通常都会对数据 进行标识，一般采用数据指纹来作为唯一的标识。获取指纹值的算法常采用 MD5、SHA-1910等散列算法。 （3）将计算出的数据指纹值与指纹库中的值进行比对。以指纹值去检索指纹库， 查找该指纹值是否在已有的指纹库中。 9 （4）根据比对结果进行重复数据删除操作。如果数据指纹值在指纹库中，说明 该数据流已存在，只需要保存一个指向元数据

31、的指针即可；如果没有找到相同的指 纹，说明该数据流不存在，那么要将该指纹加入到指纹库中，同时要存储该数据流。 基本上重复数据删除的流程就是这样，但是在不同的系统中，具体的流程要比 这个复杂一些。在本文的研究中，采用的是基于 iSCSI 的重复数据删除方式，整个 系统在 iSCSI 平台上实现，获取的数据流会被分为固定大小（4KB）的数据块，然后 利用 SHA-1 散列算法计算出各个数据块的指纹值，接着以指纹值为关键字进行检索， 根据检索结果进行相应的处理。 2.4数据处理粒度分析 按照数据处理粒度来划分，重复数据删除技术包括文件级重复数据删除、块级 重复数据删除两种11。尽管结果存在差异，但判

32、断文件或块是否唯一都能带来好处。 两者的差异在于减少的数据容量不同，判断重复数据所需的时间不同。 文件级重复数据删除技术通常也称为单实例存储(SIS)，根据索引检查需要备份 或归档的文件的属性，并与已存储的文件进行比较。如果没有相同文件，就将其存 储，并更新索引；否则，仅存入指针，指向已存在的文件。因此，同一文件只保存 了一个实例，随后的副本都以指针替代，而指针指向原始文件。块级重复数据删除 技术将数据流分割成块，检查数据块，并将这些部分与之前存储的信息予以比较， 检查是否存在冗余。同样，如果存在相同数据块，就增加一个引用指针；否则，就 将其存储。 文件级和块级各有各的优缺点。文件级重复数据删

33、除的索引非常小，在判断重 复数据和检索时所花费的时间少。由于索引小、比较次数少，文件级删除技术所需 的处理负荷较低，对恢复时间的影响较少。但是当文件内部发生一点小变化，那么 整个文件都必须重新存储，而且以文件为基本单位进行重复数据删除时，重复率低， 所以压缩比相对较低。块级重复数据删除中数据要分块处理，因而会花大量的精力 去索引和管理各块数据，检测重复数据时的匹配工作也是比较大的。但通过将文件 10 中的数据分块处理，可以大大提高数据的重复率，数据压缩比会是文件级的好几倍， 可以更好的实现重复数据删除。 不管数据流是文件级的还是块级的，在标准 iSCSI 平台中，最终都是被分成一 页一页的数据

34、来进行处理的，也就是说，iSCSI 平台自动完成了数据分块的操作，所 以为了不与平台本身的结构起冲突，基于 iSCSI 的重复数据删除系统我们也选择按 块级来处理。 不同的重复数据删除系统检查的数据块大小各不相同，通常情况下分为两种， 变长块和定长块。由于变长块处理起来比较繁琐，所以在本文研究中采用定长块的 方式。固定块的大小可能为 4KB、8KB 或者 64KB 等等，区别在于数据块大小越小， 被判定为冗余的几率越大。这就意味着消除的冗余更多，存储的数据更少。但显而 易见的，数据块大小越小，文件被分得的数据块数量就越庞大，这也意味着要花更 多的空间去管理块结构，判断重复的过程消耗更多的时间。

35、在本论文研究中选择的 块大小是 4KB。将数据流分成一块一块的数据，每一块的数据大小为 4KB，块大小 比较小，以期望可以获得更高的去重率。在数据管理和重复数据比对的过程中，希 望可以通过利用一些比较高效的方式来缓解这一部分的缺陷，同时也可以采取一些 优化措施来避免这一部分成为系统瓶颈。 2.5BLOOM FILTER 算法 2.5.1 算法背景 Bloom Filter1213是一种空间效率很高的随机数据结构，它利用位数组很简洁地 表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效是有 一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的

36、 元素误认为属于这个集合（false positive） 。因此，Bloom Filter 不适合那些“零错误” 的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter 通过极少的错误换取 了存储空间的极大节省。 11 2.5.2 算法基本原理 Bloom 过滤器14对集合采用一个位串表示，并支持元素的哈希查找。既能表示 集合，支持集合元素查询，又能有效地过滤掉不属于集合的元素。其算法结构的实 质是将集合中的元素通过 k 个哈希函数映射到位串向量中。近年来 Bloom Filter 算法 在实际中的应用越来越广泛，关于这种算法的相关研究工作也备受关注。标准的 Bloom Filt

37、er 算法的工作原理如下：如图 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，那 么只有第一次会起作用，后面几次将没有任何效果。 集合外 A B C D 集合内 E F G H h1(x) h2(x) h3(x) hk(x) 0 1 1 0 0 0 1

38、0 0 0 0 . . . 1 0 向量V k个哈希函数 图 2.1 Bloom Filter 算法原理图 Bloom Filter 算法主要包含两个操作：插入操作和查询操作。元素插入操作就是 将元素插入到集合，完成元素到 Bloom 过滤器的向量表示；元素的查询操作就是利 用 Bloom 判断元素是否在集合中。Bloom 过滤器在使用前必须初始化，即将 V 向量 12 的各位初始化为 0。 集合中元素的插入过程就是元素到向量的映射过程。元素插入操作如图 2.2 所 示： 1）计算元素 x 的 k 个哈希地址，即 h1(x), h2(x),.,hk(x)。 2）将 Bloom 过滤器向量中对应

39、位置置 1，即 Vh1(x) = Vh2(x) = =Vhk(x) = 1。 x x 000100010100010 h h1 1( (x x) )h h2 2( (x x) ) h h3 3( (x x) )h hk k( (x x) ) 图 2.2 元素插入过程示意图 元素查询操作如图 2.3 所示，基本上是插入操作的反过程，也分为两步： 1）计算出元素 x 的 k 个哈希地址。 2）检查 Bloom 过滤器向量中对应位置上的值是否为 1。它们只要有一个是 0，x 必不在集合中。如果全为 1，则 x 可能在集合中，但不一定。此时就出现了误 判，即将不属于集合的元素误判为属于集合中。由于算法

40、本身的缺陷，这种误判是 始终存在的。 a a 000100010100010 h h1 1( (x x) )h h2 2( (x x) ) h h3 3( (x x) )h hk k( (x x) ) b bc cd d 图 2.3 元素查询过程示意图 13 2.5.3 算法误判率 Bloom 过滤器作为一种支持集合查询的数据结构，在达到其高效、简洁的表示 集合效果的同时，却存在某元素不属于数据集合而被指称属于该数据集合的可能性。 可以通过数据模型来估算误判率的大小。假设哈希函数取值服从均匀分布，则当集 合中所有元素都映射完毕后，V 向量任意一位为 0 的概率: / 1 (1)kn kn m

41、pe m (2.1) 在发生误判时，要求 k 个哈希函数计算得出的位都不为 0，则其概率为 (2.2) / (1) kn mk pe 由公式 2.2 可以看出，误判率的大小和 n/m 的值相关。对公式 2.2 求偏导，可以 得到误判率最小时 k，m，n 三者之间的关系，如公式 2.3： (2.3) ln2 m k n 一般情况下，可以固定集合总元素个数 n 和误判率 p 这两个参数，然后就可以 根据公式（2.2）和公式（2.3）来计 k 值和 m 值。网上有提供的专门的计算器 （Bloom Filter Calculator） ，可以输入 n 和 p，计算出 k 和 m。 2.6 本章小结 本

42、章首先介绍了 iSCSI 存储平台的相关知识，然后介绍了重复数据删除技术， 分别就重复数据删除的基本原理以及重复数据删除的处理粒度问题作了说明，最后 介绍了 Bloom Filter 算法，包括该算法的背景、算法基本原理和误判率分析。 14 3重复数据删除方案设计 上一章我们已经分别讨论了 iSCSI 平台工作流程、重复数据删除技术的基本原 理、数据处理粒度以及布鲁姆算法，基于这些理论背景，我们将设计实现一个基于 iSCSI 平台的重复数据删除系统。该系统是在标准 iSCSI 协议的基础上，加入重复数 据删除模块来实现的。本章主要介绍了系统的总体设计，并简要说明 LBA 映射表、 指纹计算、指

43、纹管理和检索等各模块的功能，然后介绍了基于 Bloom Filter 算法的指 纹检索优化设计。 3.1 系统功能需求 本研究要实现的是基于 iSCSI 平台的重复数据删除系统，具有以下几个方面的 功能需求和性能要求： （1）搭建基于 iSCSI 平台下的存储系统。 （2）重复数据删除模块功能的实现。要实现重复数据删除的基本流程，完成数 据指纹的计算、指纹表的建立与管理、指纹检索等基本功能。 （3）实现对指纹检索模块的优化。当存储的数据量较大时，那么相应的指纹库 也会很庞大，在进行指纹检索时就需要消耗较长的时间，会成为整个系统的性能瓶 颈所在。为了提高检索性能，我们可以在检索之前先采用基于 B

44、loom Filter 算法的索 引检索过滤技术对指纹进行过滤，这样可以极大的提高检索性能。 3.2 系统总体设计 整个系统采用 iSCSI 启动器作为客户端，iSCSI 目标器作为服务器端，重复数据 删除模块就嵌在 iSCSI 目标器代码中。如图 3.1 所示，重复数据删除模块主要包括 LBA 映射表、指纹计算、指纹检索几个功能模块和检索性能优化部分。 15 客户端 (iSCSI initiator) 客户端 (iSCSI initiator) 客户端 (iSCSI initiator) 交换机 (switch) iSCSI LBA映射表 指纹计算模块 指纹索引表的建立与 指纹检索模块 重复

45、数据删除模块 存储设备 (Disk) 指纹检索过滤 性能优化 图 3.1 重复数据删除系统总体设计图 系统总体基本功能实现包括以下几个子模块： （1）LBA 映射表。用来记录重复数据删除前请求的 LBA 与重复数据删除之后 的 LBA 的映射关系，由于重复数据的存在，去重前几个不同的 LBA 去重后有可能 对应同一个 LBA。 （2）指纹计算模块。利用基于散列的 SHA-1 算法计算出数据块的指纹值，4KB 的数据页对应唯一的一个 160bit 的指纹值。 （3）指纹索引表的建立与指纹检索模块。本系统中指纹索引表的建立采用多级 索引的方式，指纹的检索也是采用多级检索的方式。在进行指纹检索之前，

46、先利用 基于 bloom filter 算法的过滤技术对指纹值进行过滤处理，过滤掉部分指纹检索请求 16 从而提高检索性能。将过滤掉的那部分指纹加入到摘要向量中，对剩下的指纹值再 进行指纹检索。 3.3LBA 映射表 在磁盘设备中，每个存储单元都会有一个标识位置的逻辑地址即 LBA，当数据 被存储到磁盘设备后，都会记录下该数据被存储在哪个地址单元中以便后来对数据 进行读写操作。在标准的 iSCSI 平台中，用户对数据进行 I/O 操作时，都是对真实磁 盘空间进行操作，所以只需要记录下数据存储的位置即可。但加入重复数据删除模 块之后，重复数据只会在磁盘中存储一遍，用户对重复数据的操作会被定位到同

47、一 个逻辑地址单元。也就是说用户请求处理的 LBA 不再是真实磁盘的 LBA，这中间会 进行映射处理，将用户请求的 LBA 转化为对应磁盘的 LBA。 LBA 映射表结构是重复数据删除系统涉及到的核心数据结构，该结构需要将上 层模块中的请求地址 LBA_U 映射到下层提供的某个 LBA_L 之上，对于包含有相同 数据的不同 LBA_U 需映射到同一个 LBA_L 上。 3.4 指纹计算模块 新到来的数据流被划分为一个个的 4KB 的数据块，要判断这些数据块是否是重 复数据，如果不加任何处理，那么最直接的方法就是一个字节一个字节的去和其他 已经存储的数据块去比对。大家可以想象一下，这样处理效率是

48、极低的，低到重复 数据删除模块失去了存在的意义。为了提高效率简化操作，我们必须想办法来简化 数据块。 类比人的识别，通常情况下，人与人的指纹是不一样的，因此我们可以用指纹 来识别和标记某个人。数据块也一样，我们可以通过某种方式，将数据块转变成数 据指纹，用该指纹来唯一标记这个数据块。数据指纹通常是一个哈希值，对哈希值 的比对就要比数据块的比对要简单快捷得多。 一般采用哈希散列算法来计算数据指纹，比如 SHA-1 算法、MD5 算法等等。在 17 本论文的设计中，哈希算法是作为一个独立的模块存在的，这样就便于替换不同的 算法。在本系统中，采用的是 SHA-1 算法来计算数据指纹。SHA(Secu

49、re Hash Algorithm)全称为安全散列算法，由一系列密码散列函数组成。SHA-1 为较早的一种 散列算法，可以从最大 264 位的原数据中产生 160bit 的摘要值，来对原数据进行唯 一性标识。也就是说，在本系统中，4KB 的数据块经由指纹计算模块后产生出 160bit 的指纹值，用此值来作为原数据块的标识。 SHA-1 算法在标准 RFC 文档中有详细的说明，并且提供了标准的实现代码，系 统中直接使用了此代码，具体的算法原理在此不再详述。 3.5 指纹管理和检索模块 3.5.1 指纹索引表的组织与建立 指纹索引表是整个重复数据删除模块的核心元数据管理部分，经过重复数据删 除后的每个数据块都是单一实例数据块，每一个单一实例数据块都对应一个指纹索 引节点。合理的组织和管理这些索引节点，是重复数据删除模块设计的关键问题， 也决定了指纹检索的方式和效率。 4KB 大小的数据块通过 SHA-1 散列算法得到的指纹值为 160bit，直接通过这 160bit 值来进行全哈希显然是不可行的。为此，在本系统中，采用了多级索引表组织 方式，即取 160bit 指纹值中的前 24bit 值共 3 个字节作为多级索引关键字。将三个字 节分别设为 key