重复数据删除综述(3)：对系统性能的影响问题

　　3.1 减轻磁盘瓶颈技术

　　在重复数据删除系统中，为了节约成本，一些系统仅有少量的内存，因而不能支持所有的数据索引一次性地进入内存进行检测，从而导致了大量的磁盘访问。针对这种情况，一些文献给出了它们认为合理的解决办法。

　　经典文献

　　uAvoiding the disk bottleneck inthe data domain deduplication file system

　　Zhu B, Li K. In: Proc. of the 6th Usenix Conf. onFile and Storage Technologies (FAST 2008). Berkeley: USENIX Association, 2008.269–282.

　　文件描述的DDFS文件系统中用于减轻磁盘瓶颈的3种技术：摘要向量、基于流的块排列和局部性保持。应用这3种技术，实现了一个高吞吐率、低开销的相同块删除存储系统。

　　1)摘要向量技术

　　摘要向量技术用于减少在磁盘中查找不存在块的次数。摘要向量可以看作是一种处于内存中，对块索引的摘要。如果摘要向量指出一个块不在索引内，则不需要进一步查找。如果摘要向量指出这个块在块索引中，那么很有可能这个块就在块索引内，但并不是一定的。为摘要向量利用Bloom filter来实现。一个Bloom filter用一个m位向量来概括在块索引中n个块指纹值的存在信息，且Bloom filter的特点是允许错误肯定(认为一个不在集合中的元素在集合中)的存在。因为摘要向量是在内存中的数据结构，所以系统关机后，会将其写到disk上，启动后，又会从disk上读入内存中。为了处理停电和不正常的关机情况，系统会周期性地将摘要向量备份到磁盘上，并设置检查点。当恢复时，系统会载入最近备份的副本，并处理从最近一个检查点添加到系统中的数据，将其信息加入到摘要向量中。

　　2)基于流的块排列技术

　　基于流的块排列技术(stream-informed segment layout，简称SISL)为块数据和块描述符提供了更好的空间局部性，并且使局部cache缓存成为可能。SISL主要特点是针对同一个数据流，使得新数据块被存放在一起，块描述符也被存放在一起。SISL能够带来以下益处：

　　i.当同一个数据流的多个数据块被写入到同一个容器中时，在进行读取操作重建这个数据流时，可以大幅减少磁盘I/O次数，使系统达到较高的读性能。

　　ii.在同一数据流中，相邻新数据块的块描述符和压缩数据分别被线性地装入相同容器的元数据段和数据段。这种装入方法为其后相似的数据流提供了一种访问局部性，使得cache的局部缓存工作更有效。

　　iii.元数据段和数据段分开存储，而且元数据段比数据段要小得多。

　　3)局部性保持技术

　　系统利用局部性保持技术(locality preserved caching，简称LPC)来加速辨认重复块的过程。针对重复数据检测，传统的Cache并不适用于缓存指纹值、哈希值或者描述符，因为指纹值在本质上是随机的。因此，如果没有进行完全的索引访问，预言下一个块的索引位置是非常困难的，从而也导致了传统cache的命中率是非常低的。LPC的应用使得块重复局部性提高，如果一个块是重复的，那么附近的块很可能已经被缓存了。

　　实验结果表明，在重复数据删除的现实环境中，把以上3种技术结合在一起，可以省去99%的磁盘访问。这些技术对于一个双核计算机系统而言，就是利用其90%的CPU性能和一个15个磁盘的磁盘柜，即可达到100MB/s的单工流吞吐率和210MB/s的双工流吞吐率。

　　3.2 提高数据搜索速度技术

　　重复数据的检测比对过程给系统带来了巨大的时间开销。当数据的所有特征存在于1个索引中时会导致系统的可扩展性差，同时导致特征值匹配的时间开销过大，因此一些研究者提出了提高数据搜索匹配速度的关键技术：把索引分片为多个小索引，并存储在多个服务器上，增加搜索的可扩展性及可并行性。同时，当有新文档加入系统时，选择一部分分片服务器来存储它的特征;在重复数据搜索时，也只在一部分分片服务器上查询。

　　经典文献

　　uContent-Based document routingand index partitioning for scalable similarity-based searches in a largecorpus.

　　Bhagwat D, Eshghi K, Mehra P. In: Berkhin P,Caruana R, Wu XD, Gaffney S, eds. Proc. of the 13th ACM SIGKDD Int’l Conf. onKnowledge Discovery and Data Mining (KDD 2007). New York: ACM Press, 2007.105–112.

　　此文的主要目的是描述一种将文件的索引分区并且路由的方法，但文中提到了如何提取文件的相似性特征的方法。文中为了实现大数据的扩展性，将大数据的index打散到多个不同的server上，这样可以实现index的并行更新和查询。

　　它将一个文档的所有特征路由在一起，而并不把文档的每个特征独立地路由。在吸收文档时，文档路由策略用特征提取算法提取出文档的特征集，基于这些特征，选择一部分索引分片。文档被路由到这些分片上，并加入那里的索引中。在查询时，用同样的特征提取和文档路由算法选择查询的分片，在所选择的分片上查询该文档的特征，并把结果进行归并。

　　原有的路由方法(基于前缀的DHT)存在问题：假设同一个文件有多个特征，由于hash的随机性和雪崩性，各个特征之间毫无关联性。如果按照这样的key、value对分配文件特征，同一个文件的特征会被打散到不同的服务器上，这样如果查询新来的A文件与系统已有B文件的相似，可能为了查B文件的特征值访问很多个server。文中希望做到可以一次路由，一次访问就提取到某一个文件的所有特征。

　　另外，特征的索引结构中，用特征值(唯一的)作为索引结构的主键。同一个文件可以有多个特征值，同一个特征值也可以属于多个文件。

　　当一个新来的文件q查询系统中,按照与文件q的雅克比系数将相似文件排序。

　　实验结果表明，快速搜索技术解决了数据匹配中时间复杂度较高的问题，并且扩展性很好，对搜索结果的准确性和回取的影响很小。

转载：感谢您对网站平台的认可，以及对我们原创作品以及文章的青睐，非常欢迎各位朋友分享到个人站长或者朋友圈，但转载请说明文章出处。