基于数据去重的广域网络传输优化系统研究
2016-11-03时立锋刘海客包翰榕
时立锋 刘海客 包翰榕
【摘要】 信息技术不断的更新和发展推动全球进入大数据时代。传统型广域网传输方案伴随通信量的急剧增长已经很难满足用户的数据传输要求。面对广域网遇到的现状，主要研究了一种数据去重算法，并将其用于广域网优化系统中。重点研究了数据分块算法，采用一种新型的滑动块检测技术，并利用时间淘汰算法选出重复的数据块，从而提高重复数据削减率，可以有效节约网络带宽并加快广域网传输速率。
【关键词】 数据去重 数据分块算法 广域网优化 时间淘汰算法
随着信息技术产业的飞速发展，当前已涌现出各种新型网络应用，致使广域网上的带宽流量迅猛增加，网络也因此出现带宽紧缺、延时高等问题。
面对上述问题，广域网加速随即成为讨论的热点。数据去重技术脱颖而出，它能够对网络中的数据实施全面的、不间断的重复数据检测，而且其压缩效率明显优于传统概念的压缩技术。调查显示，广域网中有接近60%的流量数据都是重复的[1]。例如，网络中同一文件可能在某些时间段内分发给多个人，因此便造成相同数据反复传送[2]。邮件群发也会导致大量冗余[3]；互联网上的web页面同样也会造成大量重复数据[4]。在广域网流量中约48%的网页内容几乎相同[5]；如果能在广域网加速系统中结合去重技术，将极大限度提升整个带宽的利用率。
在这个以用户体验为主导的时代，去重优化系统能够为个人和企业提供优质的网络体验。其原理是：采用数据去重技术对TCP流进行去重处理，采用双向缓存存储字段，并以非常小的代价消除重复数据，确保冗余流量不会重复发送，该方法有效减少了不必要的带宽浪费，此举可以达到提高传输速率和带宽利用的目的。通常情况下，广域网加速系统会同时部署在客户端和服务端，因此可以保证对通过的TCP流进行双向数据优化。系统示意图如图1所示。
数据去重系统一般由TCP透明代理和去重处理两部分构成。TCP透明代理的主要功能是截取数据流交给去重模块，处理完冗余后再将去重之后的数据进行发送，另外一端数据去重系统负责将接收的数据作还原处理。
目前，思科已经率先在网络优化领域展开了研究工作。它推出一款名为WAAS设备，在传输协议环境内消除重复数据并采用双向模式，有效地消除了网络中的冗余流量，为其它应用预留出更多的空间。
一、数据去重原理和方法
1.1 数据去重的定义及分类
数据去重是一种消除重复数据[6]的方法，又称之为智能压缩、单实例存储或冗余数据删除[7]，根据粗粒度消除冗余，此技术不仅支持文件级去重功能，而且对数据块也能起到很好去重效果。
第一类：相同数据检测技术：完全文件检测技术使用hash算法以整个文件为单元进行去重处理；数据块级重复数据去重技术通常采用固定快算法[8]、基于内容的边长分块算法[9]、滑动块检测技术[10]来分析查找出重复的数据块。
第二类：相似数据检测技术：该技术一般采用模式匹配技术、shingle技术[11]以及bloom filter技术[12]寻找出数据的相似点，然后对相似部分使用delta编码技术[13]实现编码压缩。
1.2 数据去重的原理及流程
数据去重的原理是利用算法查找数据流中的重复数据，随后用短小标签来替代那些重复值，以此避免大量相同数据反复传送于网络中，从而可以提升带宽利用效率。数据去重基本流程如图2所示。
图2中数据去重技术主要分为三步：
（1）协议栈将符合规则的数据流传送到数据去重模块中，并采用适当的数据块划分算法处理数据流。常用的数据块划分算法有固定分块算法、可变分块算法、滑动块检测技术。
（2）当数据流被划分成数据块之后，就需要判断其是不是重复数据块了，为了解决这个问题，可以利用hash值来作为区别不同数据块的指纹。通常使用SHA-1、MD5等函数来计算数据块hash值。
（3）通过计算数据块的hash值去搜索数据指纹库，如果在数据指纹库中匹配到该指纹，则需要对该数据块进行去重操作。反之，则需要将此数据块对应的指纹添加到数据指纹库中，与此同时记录该数据块。
二、数据去重关键技术的研究与改进
2.1 数据块划分算法
（1）固定分块检测算法
固定分块检测技术是一种用于处理数据块级的简单重复检测技术，它采用预设的固定分块将原始数据集切分为等长且互不重叠的数据块，然后再计算其每个数据块的指纹值。
（2）基于内容的变长分块（CDC）检测算法
变长分块检测机制则按照数据所包含的内容来确定块长。该方法采用滑动块窗口的方式读取数据流，然后将窗口内数据块通过Rabin滚动哈希算法计算其特征值，假如特征值未能满足设定要求，则将窗口向后偏移一字节，以此类推，直到特征值满足设定的要求，此时将上一个分块的边界到窗口右边沿所包括的数据作为一个新的分块。
（3）滑动块检测算法
滑动块检测技术[14]则有效利用上述两种算法的特点，该算法采用固定大小的滑动窗口来读取数据流，并使用弱hash算法计算窗口内数据块的指纹，如果在数据指纹库中匹配，则再次计算此数据块的强hash指纹值并在数据指纹库中匹配，匹配成功则认为滑动窗口内所有的数据内容为一个有效数据块，否则将窗口向后挪动一个字节重新利用弱hash算法计算。如果滑过一个块大小的距离依然没能找到对应的指纹，则认定此滑动窗口内的数据为一个数据块边界。
2.2 改进的滑动块检测算法
即使滑动块检测算法是一种结合弱hash校验和强hash校验分块算法，不过该方法依然无法百分百保证准确性。有可能弱hash和强hash同时发生碰撞导致发送了错误的索引，从而引起数据传输错误。针对该问题我们提出了一种新的方法。在滑动块检测算法的基础上，将原来计算滑动窗口内数据指纹的弱hash算法，用滚动哈希算法来替换。而二次匹配数据指纹的强hash算法，利用逐个字节比较的方法进行替换，这样就可以避0免将两个不同的数据块划分为重复数据块而发送错误的数据块索引，引起的传输错误问题。
2.3 数据块指纹及其检索
数据指纹如果能作为数据块的唯一标识将可以很好地用于检索方面。而目前比较适合计算数据指纹的是hash算法。hash算法以不定长度的数据作为入参，然后利用hash函数计算出定长的输出值，该输出就是hash值，或称之为数据指纹。Hash算法的数学表达式为key=hash（content），主要的hash算法有MD5、sha-1等。
对于大存储容量的数据去重系统来说，寻找一个数量巨大的指纹库，性能往往会成为一种制约。不过Hash以O（1）的时间复杂度超过其它诸多信息检索方式成为广泛认可的高性能查找算法。
三、基于数据去重的广域网加速优化系统的设计与实现
3.1 方案设计与实现
广域网数据优化系统是一个对等的双边系统，系统两端同时支持数据压缩和恢复功能。如图3所示，该系统主要由TCP透明代理和数据去重两部分构成，工作过程中需要先确认收发两端是否部署了该系统，如果存在，则对TCP流进行数据去重优化；否则，不做任何处理将该TCP报文转发出去。数据发送时，TCP透明代理模块将符合规则的TCP数据流截取下来，随后进行重组，当满足一定条件时，就将该数据段交付给去重模块处理，最终将处理过的新数据发到广域网上；接收端，TCP透明代理监测数据流中的索引号，当发现有重复数据的索引值时则将其发送给去重模块进行还原，最终将还原后的数据送往目的端。对于客户端而言，整个过程无需进行任何配置操作，Linux操作系统提供的netfilter框架可以很好地实现代理功能。数据经过广域网数据去重优化系统时协议栈会自动将符合规则的数据报文截获并交给自定义的用户空间协议栈处理[16]。
系统工作过程中，接收线程通过IPQueue机制将符合条件的IP数据包截取并放入用户空间的预处理队列。TCP_ prep报文预处理线程主要对的数据报文的排序、重组和TCP连接管理，TCP_prep线程将预处理后的控制报文直接放入发送队列，同时将重组后的数据报文放到待处理数据队列中。Data_proc数据处理线程封装了重复数据消除模块，当待处理队列中的数据满足一定条件触发定时器时线程TCP_timer时，Data_proc作为处理数据的线程从待处理队列中读取数据并交给去重模块处理，将处理过后的数据放入发送队列中。TCP_sender发送线程读取待发送队列信息，然后根据端口和ip调用Raw Socket将这些信息发到指定的终端上，图4是报文在TCP处理中的处理流程。
3.2 改进的滑动块检测算法的实现
本系统采用改进的滑动块检测算法，改进后的滑动块检测算法（滑动窗口2KB）如图5所示。
改进的滑动块检测算法具体流程如下：
Step 1：数据分块开始时如图6所示，首先利用滚动哈希函数计算图6滑动块窗口里面2KB个字节的数据块哈希值，然后在数据指纹库里面进行索引，若未能索引到则将窗口向后挪动一个字节如图7所示，如果索引到了则把这个数据块和在数据指纹库里面索引到的hash值对应的数据块进行逐个字节比较。如果这两个数据块逐个字节比较完全一样则说明索引成功，此时我们就将滑动窗口内的字节划分数据块1，并且将前一个数据块后边界和此时滑动窗口前边界之间的数据划分为数据块2，同时还将滑动窗口向后移动2KB个字节如图8所示，如果逐个字节比较不完全一样则发生hash冲突索引失败，这说明这个数据块不是一个重复的数据块，这时需要将滑动窗口向后移动一个字节如图7所示。对于数据块2来说，如果大小小于2KB则不能将这数据块加入到数据指纹库当中，如果等于2KB则把这个数据块（segment）和其hash值一起加入到数据指纹库当中。对于1数据块，由于是重复的，所以不需要将其加入到数据指纹库当中。
Step 2：有一种特殊的情况即连续滑动了2KB个字节，此时不管滑动窗口内的数据有没有在数据指纹库里面索引成功，直接将滑动块前面的2KB个字节划分为一个数据块，并且将其hash值和数据块都加入到数据指纹库当中。
3.3 数据传输编解码协议
在TCP数据流通过去重模块之后就要开始进行广域网传输了，在传输之前需要自己制定一套编解码协议，以便收发双方可以更好的对去重后的TCP数据流进行接收和发送。
XCODEC_PIPE_OP_HELLO：主站或者小站发送的第一个数据，表示数据传输即将开始，后面跟着发送数据者的UUID，接收者收到此UUID，据此UUID找到对应的接收数据指纹库（以下都称为Cache）。
XCODEC_PIPE_OP_ASK：小站收到主站发来的索引，但是自己的Cache中没有此索引，因此不能得到真实数据，这时发送这个消息，向主站请求真实数据。这个消息中包含有此索引（hash值）。
XCODEC_PIPE_OP_LEARN：主站收到XCODEC_PIPE_OP_ASK消息后，从中解析出HASH值，从自己的Cache中取出数据，发给小站，这个数据包的格式就采用这个类型。如果主站Cache中没有此hash值，则发生致命错误，需要断开连接。
XCODEC_PIPE_OP_FRAME：正常数据都放入到FRAME中。数据也是有格式的。FRAME的最大长度是XCODEC_PIPE_MAX_FRAME，为32768。
XCODEC_MAGIC：是个标记，遇到此标记，表明随后紧挨的一个字节是一种操作类型。这种操作类型有以下几种。
操作类型：
XCODEC_OP_ESCAPE：表示这是原始数据，而且XCODEC_MAGIC本身也是原始数据的一部分。发送者，对于原始数据，在ESCAPE时，要逐个字节寻找数据中的XCODEC_MAGIC，如果找到，就在后面插入一个XCODEC_ OP_ESCAPE。
XCODEC_OP_EXTRACT：表示后面的2k数据应该存入Cache，接收者收到这种操作，需要计算后面2k数据的HASH值，并存入自己的Cache。
XCODEC_OP_BACKREF：表示后面的一个字节是个索引号，接收者需要根据此索引号在自己的window中找到对应的HASH值，再由HASH从cache中找到真实数据。
XCODEC_OP_REF：表示后面的8个字节是个HASH值，接收都需要根据此HASH值在自己的cache中找到真实数据。
如果不能依据XCODEC_OP_BACKREF找到相对应的数据，则会导致致命错误的发生。如果不能根据XCODEC_OP_ REF找到对应数据，则需要发送XCODEC_PIPE_OP_ASK向发送者要真实的数据。
3.4 数据指纹库Cache管理
Cache数据都放在内存中，基本数据结构是一个基于hash的Map
二、测试及结果分析
4.1 测试方法
评价指标：数据去重技术旨在加速收发双方的通信速度，所以可以用速度提升百分比来作为评价指标。
测试环境：采用两个普通电脑当作数据传输的收发两端，在另外两个双网卡机器上运行广域网数据优化软件，延迟为600ms，丢包率为0.005%的条件下对数据传输进行加速测试，测试网络结构图如图12。
测试方法：
4.2 测试结果及分析
从以上测试结果我们可以得出如下结论：
（1）结论1：方案一和方案二的对比可以看出广域网的延迟对于数据传输产生了很大的影响，使得传输速率下降非常明显。
（2）结论2：方案二和方案三的对比可以得出透明代理可以加速有巨大延迟的广域网的传输速度，加速效果非常明显。
（3）结论3：方案四的两次测试对比可以看出在透明代理的基础上，数据去重技术的加速效果异常明显，第一次由于数据去重的开销，速率相比透明代理有小幅下降，但是第二次的测试充分说明了数据去重对于广域网传输优化有着极大的改善，速率提升很明显。
从方案一、二、三、四的对比可以看出来透明代理和数据去重对数据传输加速都起到了很大的加速效果。尤其是数据去重功能将原来的速度提升了很多，这不但加速数据传输，而且减少了在网络上传输的数据量，减少了对带宽的占用。极大的改善了广域网络传输的环境，提升了传输速率。
五、结束语
本文首先对数据去重技术的研究背景和现况进行了介绍，然后对数据去重涉及到的关键技术进行了研究和改进，并在这些理论的基础上设计出一种带有数据去重的广域网优化加速系统。并且经过实例测试这个系统工作正常，性能达到了预期加速的目的，改善了广域网传输的环境。但还是可以在如下几个方面进行改进：
（1）对重复数据的检索是限制重复数据消除性能的瓶颈，在内存资源有限的情况下就只能存储有限的数据块和hash值，这就会引起重复数据检索成功率的降低。所以平衡数据指纹库和和内存之间的关系可以最优化检索效率，这也是以后研究的重点。
（2）两边的数据指纹库即Cache同步也是一个很大的问题，同步机制是在假设网络条件理想的情况下才可以的，但是真实的网络环境条件很差，这就为cache同步机制带来了极大的挑战，如何解决这个问题变得很迫切。
参 考 文 献
[1] Mcknight J， Asaro T， Babineau B. Digital archiving： end-user survey and market forecast 2006-2010[J]. Milford， MA， USA： Enterprise Strategy Group，2006.
[2] Santry D S， Feeley M J， Hutchinson N C， et al. Deciding when to forget in the Elephant file system[J]. In Proceedings of the 17th ACM Symposium on Operating System Principles（SOS99）. New York， USA： ACM Press，1999：1 10-123.
[3] Tolia N， Kaminsky M， Andersen D G， et al. An architecture for internet data transfer[J]. In Proceedings of the 3rd Symposium on Networked Systems Dsign and Implementation （NSDI06）.San Jose， CA，USA：USENIX Association，1006：253-266.
[4] Mogu J C， Chan Y M， Kelly T. Design， implementation， and evaluation of duplicate transfer detection in HTTP[J].In Proceedings of the 1st Conference on Symposiums on Networked Systems Design and Implementation（NSDI04）.Berkeley， USA：USENIX Association，2004：4-4.
[5] Shivakumar N， Garcia-Molina H. Finding near-replicas of documents on the Web[J]. In Proceeding of the 2nd International Workshop on the World Wide Web and Databases（WebDB99）.Berlin，Germany：Springer-Verlag，1999：204-212.
[6] 敖莉，舒继武，李明强.重复数据消除技术[J].软件学报.2010，（05）.
[7] Chuanyi Liu， Yingping Lu， Chunhui Shi， et al. ADMAD： Application Driven Metadata Aware De-duplication Arc hival Storage System[J]. Digital Object Indetifier， September 2008.29-35.
[8] Bobbarjung Dr， Jagannathan S， Dubnicki C. Improving duplicate elimination in storage systems[J]. ACM Trans. on Storage，2006，424-448.
[9] Jain N， Dahlin M， Tew ari R. Taper： Tiered approach for eliminating redundancy in replica synchronization[J]. In： Proc. Of the 4th usenix Conf. on File and Storage Technologies（FAST 2005）. Berkeley： USENIX Association，2005.
[10] Broder AZ. Identifying and filtering near-duplicate documents[J]. In： Giancarlo R， Sankof D， eds. Proc. of the 11th annual Symp. On Combinatorial Pattern Matching.London： Springer-Verlag，2000.1-10.
[11] Han B， Keleher P. Implementation and performance evaluation of fuzzy file block matching[J]. In： Proc of the 2007 USENIX Annual Technical Conf.（USENIX 2007）.Berkeley： USENIX Association，2007.199-204.
[12] Bloom BH. Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM，1970， 13（7）：422-426.
[13] Ouyang Z， Memon N， Suel T， Trendafilov D. Cluster-Based delta compression of a collection of files[J]. In：Proc. Of the 3rd Intl Conf. on Web Information Systems Enginerring. Washington： IEEE Computer Society Press，2006.257-266.
[14] Hsu W W S， Ong S. System and method for dividing data into predominantly fixed-sized chunks so that duplicate data chunks may be identified[J]. US Patent：US7281006B2.2007：23-32.
[15] Tin Thein Thwel， Ni Lar Thein. An Efficient Indexing Mechanism for Data Deduplication[J].International Conference on Current Trends in Information Technology，2009：1-15.
[16] 徐照，广域网重复数据消除方法的研究与实现[D]. 南京：南京邮电大学，2013.2
