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

部字节数组的哈希值。因为每个字节的数值最多有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通过采用客户端相关的冗余数据删除技术，可提高对存储资源以及网络资源的利用率，降低运营成本，提高可扩展性以及整体性能。