一种广域网环境下的分布式冗余删除存储系统

2.1 客户端

客户端是为某个应用服务开发，运行在使用该应用服务的用户的网络终端上的程序。程序通过响应用户输入并且同该应用服务进行消息交换，使用户能够使用该应用服务提供的服务。AegeanStore的客户端除了完成传统网络应用的客户端的响应用户输入、网络消息交换、身份验证、数据传输等任务之外，还要在冗余数据删除技术中，完成重要的任务：因为AegeanStore使用冗余数据删除技术的目标是减少冗余数据在网络传输时造成的浪费，所以冗余数据删除中的可变数据块划分和计算每个数据块的数字指纹等工作必须在客户端完成。在获得需要上传文件的所有数据块的数字指纹后，通过应用服务提供的网络接口，查询这些文件块是否已经在AegeanStore中存在，然后将新的数据块上传到数据块服务部分，完成数据上传过程；同时，客户端需要管理已经存储在本地的数据块的数字指纹，用于下载时减少冗余数据传输。

2.2 应用服务

应用服务是以AegeanStore提供的存储服务、开发框架和功能组件为基础，构建而成的网络应用服务。AegeanStore作为网络应用开发的基础平台，为了方便应用服务的开发，提供了应用服务的开发框架，使得应用服务的开发可以忽略网络应用中网络端口监听、工作进程派生、负载均衡和调度等问题，专心解决应用服务的事务逻辑，使应用服务的开发工作更加方便快捷。应用服务开发者只需要将自己开发的消息处理模块和消息序列化/反序列化模块注册到应用服务框架当中，即可被框架自动调用，进而提供网络应用服务。除此之外，AegeanStore还为应用服务的开发者提供用户管理、网络消息交换等常用的功能组件，从而提高在AegeanStore上开发应用服务效率，降低应用服务的开发和运营成本。

2.3 文件系统服务

文件系统服务为AegeanStore提供文件系统视图和文件管理接口。目前常用的提供公共存储服务的分布式存储系统当中，普遍使用的应用程序接口是Key/Value式的。虽然这种接口在开发应用服务时使用比较方便，但是与用户习惯的基于目录结构的文件系统式接口差异较大，导致大多数构建在Key/Value接口上的应用服务都要开发功能相似的文件系统视图。这些重复开发增加了应用服务开发的难度和成本，更重要的是，因为缺少存储系统内部信息的辅助，无法利用数据的局部性和网络的就近访问等优化技术，在Key/Value接口上构建的文件系统效率往往较低，对应用服务以及存储系统的网络和存储资源造成了严重的浪费。所以，AegeanStore为应用服务开发提供的接口是文件系统式的，以提高应用服务的开发效率，避免重复开发，并通过使用分布式B树、网络就近访问、代理访问等优化技术，提高存储系统的吞吐量。

2.4 索引服务

索引服务中存储了AegeanStore中所有数据块的数字指纹的索引，并提供网络查询索引接口，用来判断数字指纹所对应的数据块是否已经存在于AegeanStore当中。以SHA-1哈希函数计算出来的数据指纹为例，每个块的数字指纹大小为20 B，假设可变块划分算法所分的数据块的平均大小为4 kB，则索引服务中存储的数字指纹索引的数据规模为实际存储数据规模的0.5%。由于AegeanStore存储系统具有良好的可扩展性，其数据规模可以达到数百太字节甚至拍字节级，所以索引服务应该支持太字节级别的索引存储。

2.5 数据块服务

AegeanStore的数据块服务提供分布式的基于内容定位的存储系统[7]，其提供的接口是Key/Value形式的。数据块服务由接口、一跳分布式哈希表(DHT)[8]和数据块存储节点3部分组成：当用户存储数据块时，以该数据块的数字指纹作为Key进行存储；首先到一跳分布式哈希表中，查找该数字指纹，因为数字指纹由数据块的内容决定，所以，如果该数字指纹已经存在于分布式哈希表当中，说明该数据块已经存在于数据块服务当中，无需再次存储；如果不存在，将数据块存入数据块存储节点，将数字指纹和所存储的位置信息存入一跳分布式哈希表作为索引。当用户读取数据时，给出数据块的数字指纹。块存储服务从分布式哈希表中查找是否存在这个数字指纹，如果存在则根据在其中获得的数据块位置从存储节点读取相应数据块并返回给用户，否则返回空。

3 冗余删除技术的优化

将冗余数据删除技术应用于分布式存储系统将遇到两个问题。

(1)由于CDC算法开销过大，无法满足广域网环境中的分布式存储系统的客户端的异构性带来的计算性能瓶颈。

(2)由于分布式存储系统的高可扩展性，造成索引服务中数字指纹索引过大，从而带来的数字指纹索引查询的性能瓶颈。

3.1 CDC算法的优化

CDC算法中，无论在计算滑动窗口内的哈希值，还是获得数据块划分之后计算数据块的数字指纹都是计算密集型工作。在手机或上网本等运算能力较差的设备上，由于存在着性能瓶颈，制约了客户端相关的冗余数据删除技术的有效应用。

首先，在AegeanStore的客户端中，为了优化CDC算法的运行效率，在计算滑动窗口的哈希值时，采用了Rabin’s Fingerprinting[9]哈希函数进行计算。因Rabin’s Fingerprinting哈希函数具有可迭代计算的特性，滑动窗口时，只需要通过将滑动前哈希值、滑入字节值和滑出字节值进行复杂度为O(1)的计算，即可获得滑动后的窗口内部字节数组的哈希值。因为每个字节的数值最多有256种可能，可以通过预先的计算，将滑入和滑出字节相关的计算制成表格，之后，只需要通过查表和简单的位移操作和加减操作即可获得滑动后的哈希值，大大提高了CDC算法的运算效率。

其次，AegeanStore引入了双阈值双除数算法(TTTD)[10]，对CDC算法进一步优化。TTTD算法规定了数据块大小的最小值Smin。每一个可变数据块从开始到Smin的区间内的数据不需要进行哈希值计算。TTTD算法是为了对付可变数据块划分结果中数据块大小差异太大而造成的冗余删除率较差的问题，经试验证明，Smin:S约等于0.85时，可以获得最好的冗余删除率。所以使用TTTD算法可以大大降低冗余数据删除的计算开销，提高AegeanStore客户端的运行效率。

3.2 索引服务的优化

AegeanStore的索引服务通过采用3种优化方法，改进索引服务的数字指纹查询效率，以提高冗余数据删除技术在分布式存储系统中的性能。

(1)基于文件的批量数字指纹查询

AegeanStore提出了基于文件的批量数字指纹查询协议，将相同文件的数据指纹列表，连同该文件的路径、大小等元数据信息，组织到同一个文件上传请求当中。经过这样的优化，既减少了AegeanStore客户端的网络请求数，增大了每个请求的数据量，提高网络资源的利用率；并且，让索引服务一次可以处理很多个数字指纹的索引查询，增加了索引服务的吞吐量；更重要的是，使同一个文件的数据块的数字指纹之间所存在的局部性得以保持，为索引服务进行预取和缓存等进一步优化创造了条件。

(2)基于Bloom filter的快速新数据块过滤

Bloom filter[11]是一种高效的利用有限的内存空间，以一定错误肯定率为代价，用于快速的判断某一个元素是否在一个集合中的概率性数据结构。在AegeanStore的索引服务当中，使用一台性能较好、内存空间较大的服务器来运行快速新数据过滤模块。一个存于内存中的Bloom filter作为该模块的核心数据结构。当接收到由请求节点转发来的基于文件的批量数字指纹查询请求之后，将其中每一个数字指纹送到Bloom filter中进行判断其是否存在于AegeanStore当中。如果判定结果为可能存在，则将其忽略；如果为一定不存在，则将这个数字指纹标记为新数据块；将标记后的数字指纹列表，返回给请求节点；最后，当数据块被成功上传到数据块服务之后，将其对应的数字指纹加入到Bloom filter当中。

(3)基于文件局部性的缓存和预取

文件局部性是指出现在相同文件中的数据块，再次出现在相同文件中的概率会比较高。文件局部性通过使用基于文件的批量索引请求被保存到索引服务当中，与某数字指纹具有文件局部性的其他数字指纹的列表称之为局部性列表。缓存和预取节点中的缓存的数据结构提供Key/Value式的接口，同样以数字指纹作为Key，以其局部性列表作为Value。当索引查找的数字指纹列表被分配到某个缓存和预取节点后，处理流程如下：对于每一个没有被标记为新的数字指纹，首先到缓存中查找该数字指纹，如果命中，说明该数据块已经存在于AegeanStore当中，将文件的数字指纹列表和缓存中局部性列表合并，并在结果中标记该块为存在；若未命中，则到DHT中进行查找，如果命中，将DHT中存储的局部性列表加入缓存当中，完成预取工作，之后的处理和缓存命中时相同；如果未命中，即该数据块不存在于AegeanStore当中，在快速过滤模块当中出现了错误的情况。

4 结束语

本文提出了广域网环境下的分布式存储系统原型AegeanStore。AegeanStore在提供互联网上的存储服务的同时，还为网络应用的开发提供了框架和通用的功能模块，以提高网络应用开发和运营的效率，并降低其成本。分布式存储系统中普遍存在的冗余数据，不仅浪费了存储系统的资源，而且造成了存储系统的性能损失。AegeanStore通过采用客户端相关的冗余数据删除技术，可提高对存储资源以及网络资源的利用率，降低运营成本，提高可扩展性以及整体性能。

5 参考文献

[1] Amazon Simple Storage Service (Amazon S3) [EB/OL]. [2010-06-16]. http://aws.amazon.com/s3/.

[2] 敖莉, 舒继武, 李明强. 重复数据删除技术研究综述 [J]. 软件学报, 2010,21(5):916-929.

[3] Cryptographic Hash Function [EB/OL]. [2010-05-25]. http://en.wikipedia.org/wiki/Cryptographic_hash_functions.

[4] DENEHY T E, HSU W W. Duplicate Management for Reference Data [R]. Research Report. RJ 10305 (A0310-017). San Jose, CA,USA: IBM. 2003.

[5] BRODER A Z. Identifying and Filtering Near-duplicate Documents [C]//Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching(CPM’00), Jun 21-23, 2000, Montreal, Canada. Berlin, Germany: Springer-Verlag, 2000:1-10.

[6] HUNT J W, MCILLROY M C. An Algorithm for Differential File Comparison [R]. Computing Science Technical Report 41. Stanford, CA, USA: Stanford University, 1976.

[7] TOLIA N, KOZUCH M, SATYANARAYANAN M, et al. Opportunistic Use of Content-addressable Storage for Distributed File Systems [C]//Proceedings of the 2003 USENIX Annual Technical Conference (USENIX’03), Jun 9-14, 2003, San Antonio, TX,USA. Berkeley, CA, USA: USENIX Association, 2003: 127-140.

[8] GUPTA A, LISKOV B, RODRIGUES R. One Hop Lookups for Peer-to-peer Overlays [C]//Proceedings of the 9th Conference on Hot Topics in Operating Systems (HotOS’03), May 18-21, 2003, Lihue, HI,USA. Berkeley, CA, USA: USENIX Association,2003: 7-12.

[9] BRODER A Z. Some Applications of Rabin's Fingerprinting Method [M]//CAPOCELLI R, DE SANTIS A, VACCARO U. Sequences II: Methods in Communications, Security, and Computer Science. Berlin, Germany: Springer-Verlag, 1993: 143-152.

[10] ESHGHI K, TANG H K. A Framework for Analyzing and Improving Content-based Chunking Algorithms [R]. TR 2005-30. Hewlett-Packard Labs. 2009.

[11] BRODER A, MITZENMACHER M. Network Applications of Bloom Filters: A Survey [J]. Internet Mathematics, 2004,1(4): 485-509.

尹玉冰，清华大学高性能计算研究所在读硕士研究生，主要研究领域为存储系统。

孙竞，清华大学高性能计算研究所在读博士研究生，主要研究领域为分布式系统。

余宏亮，清华大学高性能计算研究所副教授、博士，主要研究领域为并行与分布式系统，曾作为主要成员参与和负责了5项国家级基金项目的研究工作，已在国内外重要学术刊物和会议上发表论文30余篇。

作者：尹玉冰　孙竞　余宏亮 来源：中兴通讯技术——2010年 第5期