基于卫星数据缩减的传输优化技术研究与实现

田 浩，孙剑伟

基于卫星数据缩减的传输优化技术研究与实现

田 浩，孙剑伟

(华北计算技术研究所，北京 100083)

卫星应用系统领域，存在海量的大数据需要通过广域网传输，为了提高广域网传输速率，进而可以把基于卫星地面应用系统的卫星数据缩减作为切入点进行研究。卫星数据的地面传输将卫星地面接收站作为数据的原始起点，中心站或其他需要卫星数据的站点作为数据的目的站点，本课题研究的是卫星地面数据传输的加速优化技术。文中设计了一种卫星数据缩减方案，通过传统的数据压缩与现今大热的重复数据消除技术相结合。两种优化技术互相融合实现数据压缩与重复数据块消除珠联璧合，达到数据量的递减，减轻了地面站传输压力。最后设计了针对卫星数据缩减发送原型系统。

重复数据消除；数据压缩；加速平台

0 引言

地面系统负责接收卫星数据，并及时传送给应用系统。中国卫星的地面系统由北京站、三亚站、喀什站和今年刚刚建立的北极站四个地面接收站组成[1]。作者所在领域主要研究的是卫星数据地面传输性能优化和卫星应用系统研发。

数据传输应用系统其主要任务是合理调配网络资源和系统设备资源，管理数据传输队列作业，以确保卫星原始数据和快视数据能够快速、准确地传送到位于北京的地面站中心和卫星业主单位。负责在数据传输过程中结合广域网数据传输的系统优化技术和应用数据优化技术，优化传输性能。

其中利用应用层数据优化技术实现是本系统研究的重要内容，通过数据优化技术可以实现数据快速传输。通过对重要数据的快速传输，可以保证在突发自然灾害时，能够及时准确的将现场的图像影像等资料传回到指挥控制中心，指挥控制中心能够根据具体情况作出相应的救援部署工作，能够最大限度的减少生命和财产损失，为完成第一时间的救援提供重要的技术支持保障和决策分析的依据[8]。

1 重复数据消除主要技术

基于传输数据的优化主要包含卫星数据压缩[7]和重复数据消除两大技术。其中卫星数据压缩技术由于都是基于经典算法的改进，主要原理是基于数据编码的缩减，我们不在赘述。这里主要谈论重复数据消除技术这块的研究与应用。

重复数据消除技术包含许多技术实现细节，包括文件如何进行切分？数据块指纹如何计算？如何进行数据块检索？采用相同数据检测还是采用相似数据检测和差异编码技术？数据内容是否可以感知，是否需要对内容进行解析？这些都是重复数据消除（Data Deduplication）具体实现息息相关[3]。本文主要研究相同数据检测技术，基于二进制文件进行重消处理，具有更广泛的适用性。

存储系统的重复数据消除过程一般是这样的：首先将数据文件分割成一组数据块，为每个数据块计算“指纹”（Fingerprint），然后以“指纹”为关键字进行Hash查找，匹配则表示该数据块为重复数据块，仅存储数据块索引号，否则则表示该数据块是一个新的唯一块，对数据块进行存储并创建相关元信息。这样，一个物理文件在存储系统就对应一个逻辑表示，由一组FP组成的元数据。从如上过程中可以看出，重复数据消除的关键技术主要包括文件数据块切分、数据块指纹计算和数据块检索[4]。

1.1重消文件切块

本文将要采用的滑动块（Sliding Block）切分算法是最近刚刚新起的分块切分算法，其结合了定长切分和变长切分的优点，块大小固定[5]。算法主要流程：

（1）定长的窗口滑动，求其checksum。

（2）若找到相同的checksum则对两起点间的数据执行以下操作：

A: 若数据碎片大于1个窗口长度，取整数个窗口大小数据块，每个块分别计算checksum，该块视为非重复数据，存储其指纹。

B: 若数据碎片小于1个窗口长度，将其作为非重复数据存储。

（3）对于相同checksum计算数据指纹值，若指纹值不符合，则视为checksum不同，继续滑动窗口。示意图1。

图1 滑动窗口检测示意图

滑动窗口定长数据块前面的数据碎片也是一个数据块，它是变长的。如果滑动窗口移过一个块大小的距离仍无法匹配，则也认定为一个数据块边界。滑动块算法对插入和删除问题处理很高效，并且能够检测到比变长切分更多的重复数据。

1.2重消数据块指纹计算

重复数据消除技术的关键在于数据块“指纹”（Fingerprint）的生成和鉴别。数据块指纹是鉴别数据块是否重复的依据，如果不同数据块的指纹相同，就会造成内容丢失，产生不可恢复的严重后果。

数据块“指纹”（FingerPrinter）是数据块的特质，理想状态是每个不同的数据块具有唯一的指纹。卫星数据块本身往往较大，因此数据指纹的目标是期望以最小的字节空间表示（如16、32、64、128字节）来区别不同数据块。数据指纹通常是对数据块内容进行相关数学运算获得，从当前研究成果来看Hash函数比较接近与理想目标，比如MD5、SHA1、SHA-256、SHA-512、Rabin Fingerprint等[2]。然而，遗憾的是这些指纹函数都存在碰撞问题，即不同数据块可能会产生相同的数据指纹。相对来说，MD5和SHA系列Hash函数具有非常低的碰撞发生概率，因此通常被采用作为指纹计算方法。其中，MD5和SHA1是128位的，SHA-X（X表示位数）具有更低的碰撞发生概率，但同时计算量也会大大增加。实际应用中，需要在性能和数据安全性方面作权衡。另外，还可以同时使用多种Hash算法来为数据块计算指纹。

数据块指纹（FingerPrinter）通常使用Hash函数来计算获得，如MD5、SHA1、SHA-256、SHA-512等。其计算方法也就是出自密码学里的数据摘要算法，它的原理是：计算出数据块的指纹信息，用来达到给每一个不同数据块签名的目的，该数据块签名也就是指纹可以被用来进行数据块的完整性校验。从纯数学角度看，如果两个数据块指纹不同，则这两个数据块内容肯定不同。然而，如果两个数据块指纹相同，我们则不能断定这两个数据块是相同的。

针对这种问题，目前主要有两种解决路径：一是对数据指纹相同的块进行字节级完全比较。二是采用两种以上hash算法组合方式，最大可能降低碰撞产生的概率，这显然会对性能造成影响。

多数情况下由于卫星地面系统对传输速率优化的需求明显大于对本地性能的需求。作者在卫星数据传输系统中采用的就是第二种方法，为每个数据块计算两个指纹，一个弱校验值（Mark Adler的Adler-32校验）和一个强校验值MD5。弱校验值Adler-32算法由于本身设计的缘故，容易被人篡改伪造，在维护数据安全性方面较为劣势，但是由于其只需消耗很小的CPU时间，在在线实时任务压缩方面还是有很不错的应用价值。滑动窗口切分定长数据块先计算Adler-32弱校验值，如果不匹配则再计算MD5强校验值。这种方式以较小的性能代价极大地降低了碰撞产生的概率，而且通过优化，性能损失无几。

（一）弱校验值Adler-32算法流程

下面例子中先计算校验和A、B（16 bit），然后将它们组合成32位整数，以此来获得Adler-32算法校验值。A是数据流中所有字节的总和加1，B是来自每个步骤的A的各个值的总和。

在Adler-32运行的开始，A被初始化为1，B被初始化为0.以65521（小于216的最大素数）模数进行求和。字节按网络顺序（大端）存储，B占用两个最高有效字节。

该函数可以表示为：

A = 1 + D1 + D2 + ... + Dn（mod 65521）

B = （1 + D1）+（1 + D1 + D2）+ ... +（1 + D1 + D2 + ... + Dn）= n×D1 +（n-1）×D2 + （n-2）× D3 + ... + Dn + n（mod 65521）

Adler-32（D）=B×65536 + A

其中D是要计算校验值的字节串，n是D的长度。

例如：字符串“Wikipedia”的Adler-32弱校验值计算如下表：

表1 Adler-32算法计算流程表

A = 920 = 0x398

B = 4582 = 0x11e6

校验值 = 4,582 × 65, 536 + 920 = 300286872 = 0x11e60398

注意：在该示例中，模运算没有效果，因为没有值达到65521。

附Adler_32算法核心代码：

unsigned int adler32_checksum(char *buf, int len)

{

int i;

unsigned int s1, s2;

s1 = s2 = 0;

for (i = 0; i < (len - 4); i += 4) { s2 += 4 * (s1 + buf[i]) + 3 * buf[i+1] + 2 * buf[i+2] + buf[i+3] +

10 * CHAR_OFFSET;

s1 += (buf[i+0] + buf[i+1] + buf[i+2] + buf[i+3] + 4 * CHAR_OFFSET);

}

for (; i < len; i++) {

s1 += (buf[i]+CHAR_OFFSET);

s2 += s1;

}

return (s1 & 0xffff) + (s2 << 16);

}

unsigned int adler32_rolling_checksum(unsigned int csum, int len, char c1, char c2)

{

unsigned int s1, s2, s11, s22;

s1 = csum & 0xffff;

s2 = csum >> 16;

s1 -= (c1 - c2);

s2 -= (len * c1 - s1);

return (s1 & 0xffff) + (s2 << 16);

}

（二）MD5强校验值

强校验值的算法比较经典了，这里不再赘述。

（三）算法对比测试

针对上面两个经典算法做出算法测试。

测试数据集：2048 MB大小的资源三号（ZY-3）卫星高光谱图像数据，其中有各种资源三号（ZY-3）卫星数据类型包文件。

测试软硬件环境：操作系统Windows xp；框架Qt Designer 5.5.0；测试机，Intel(R) Core(TM) i7-3770 CPU @ 3.4.0 GHZ，2G RAM，128G IDE接口硬盘。

测试对比效果：

下面给出两种不同强弱校验算法的实验对比结果表：

表2 强弱校验值算法的实验对比

以上测试对比可以看出，数据块指纹的计算较快，在一般配置的计算机上使用强弱校验值算法，处理2 GB的文件只需40秒左右，对多核服务器的负载要求不是太高。在对卫星文件数据实时性要求更高的场合可以采用弱校验值Adler-32算法，而对数据安全性要求更高的场合采用强校验值MD-5算法。

1.3重消数据块检索

对于大存储容量的卫星重复数据消除系统来说，数据块数量非常庞大，尤其是数据块粒度细的情况下。因此，在这样一个大的数据指纹库中检索，性能就会成为瓶颈。信息检索方法有很多种，如动态数组、数据库、RB/B/B+/B*树、Hashtable等。哈希表（Hashtable）查找因为其时间复杂度为O（1），满足查找性能要求，重复数据消除技术中也采用它。哈希表处于内存中，会消耗大量内存资源，在设计重复数据消除技术前需要对内存需求作合理规划。根据数据块指纹长度、数据块数量（可以由存储容量和平均数据块大小估算）可以估算出内存需求量。

2 重复数据消除方案设计

研发或应用重复数据消除（Data Deduplication）技术时应该考虑各种因素，因为这些因素会直接影响其性能和效果。

重复数据消除（Data Deduplication，以下简称重消）的衡量维度主要有两个，即重复数据消除率（Deduplication Ratios）和性能。其中对何种数据进行重消，时间数据还是空间数据，全局数据还是局部数据？何时进行重消，在线还是离线？在何处进行重消，源端还是目标端？如何进行重消？实际应用重复数据消除技术时应该考虑各种因素，因为这些因素会直接影响其性能和效果。

2.1重消数据粒度的选择

对全局文件级数据还是局部块级别数据进行重消？这是首先需要考虑的因素，这直接决定着重复数据消除实现算法的选择和数据重消率。全局文件级的重消技术也称为单一实例存储（SIS，Single Instance Store），局部块级别的重消其消重粒度更小，可以达到4～24 KB之间。显然，局部块级别可以提供更高的数据消重率。作者所在的卫星数据库中，由于卫星高光谱影像数据的特点，局部范围内的数据重复率比全局范围数据要高，因此选择对局部块级别数据重消，会获得更高的投资回报率（ROI，Return On Investment）/总持有成本（TCO，Total Cost of Ownership）的需求。

对时间数据还是空间数据进行重消？随时间变化的数据，如周期性的备份、归档的卫星数据，重复数据消除技术还在备份归档领域中被广泛应用。我们的卫星数据地面传输应用系统中，绝大部分数据是基于卫星控制管理中心任务事后传输的，对其重消将比空间数据具有更高的重消率。

2.2重消时间的选择

上文已经提到过，数据重消时机分为两种情形：在线重删和离线重删。

采用在线重删模式，在数据存储到存储设备上的同时进行重复数据消除流程，在数据存储到硬盘之前，重复数据已经被去除掉了。因此实际传输或写入的数据量较少，适合通过LAN或WAN进行数据处理的存储系统，如网络备份归档和异地容灾系统。由于它需要实时进行文件切分、数据指纹计算、Hash查找，对系统资料消耗大。

采用离线重删模式，在写到存储设备的同时不进行重删处理，先把原始数据写到硬盘上，随后利用适当的时间启动后台进程对这些原始数据进行重删处理。与在线重删相比较，它对系统资料消耗少，但写入了包含重复的数据，因为需要预先存储消重前卫星数据，离线重删需要更多的硬盘数量和性能,而且需要保证有足够的时间来进行数据去重操作。这种模式适合直连存储DAS和存储区域网络SAN存储架构，数据传输不占用网络带宽[3]。

鉴于两种重删模式对宽带占用的影响，我们卫星数据传输优化方案将主要采用离线重删模式。

2.3重消地点的选择

数据重消可以在目的端（Target）或者源端（Source）进行。

目的端重消发生在目的端，数据在传输到目的端再进行重消，它不会占用源端系统资源，但占用大量网络带宽。目的端重消的优势在于它对应用程序透明，并具有良好的互操作性，不需要使用专门的API，现有应用软件不用作任何修改即可直接应用。

源端重消在数据源进行，传输的是已经重消后的数据，能够节省网络带宽，但会占用大量源端系统资源。

同上，鉴于两种地点消除模式对宽带的影响，我们卫星数据传输优化方案将主要采用源端重消模式。

3 卫星数据缩减方案设计与验证

卫星数据压缩和重复数据删除两种技术，目的都是缩减数据，差别在于数据压缩技术是数据的表达存在重复，它是基于数学里信息论的技术；而重复数据删除的实现依赖数据块的重复出现，是一种实践性技术。两种技术具有不同层面的针对性，并能够结合起来使用，从而实现更高的数据缩减比例。

图2 数据压缩与重复数据消除的结合流程图

如果同时应用数据压缩和重复数据删除技术，本文将讨论的是使用顺序的问题。

3.1缩减顺序分析

（一）先压缩，再重消

上文提过初始的卫星高光谱影像数据，冗余率是很高的。数据压缩技术本身是对数据进行重新编码，这样的预处理就可能破坏了卫星数据原生的冗余结构，再应用重复数据消除的话，由于初始的冗余结构遭到破坏，缩减效果会大打折扣。并且一般情况下，高压缩比的数据压缩算法往往比重复数据消除算法更消耗CPU时间，先进行数据压缩的话，其算法作用的数据域也就更大，卫星数据缩减总共消耗的时间也更多。

（二）先重消，再压缩

先执行重复数据删除则不同，它首先消除了冗余数据块，然后应用数据压缩对唯一副本数据块进行再次压缩。这样，两种技术的数据缩减作用得到叠加，而且数据压缩的消耗时间大大降低。

因此，作者的系统选择先应用重复数据删除技术缩减基本数据块的体积，然后再使用数据压缩技术进一步缩减数据本身结构体积。

3.2缩减效果验证

这里以Linux下数据压缩工具（gzip）和作者开发传输系统中用到的数据缩减功能（dc）来验证这个结合效果。

原始数据：ZY-3.dat，du–h查询容量为1107724 KB，约1081.8 MB。

表3 缩减顺序实验验证

经过实验可得，gzip + dc得到的ZY-3.gz.dc容量为241 MB，消耗时间为159.992(152.776+7.216)秒；dc + gzip得到的ZY-3.dc.gz容量为176 MB，消耗时间为67.572（28.890+38.682）秒。实验数据进一步验证了上述的分析，先重消后压缩，可以获得更高的数据压缩比和性能。

4 卫星数据缩减发送系统设计与实现

卫星数据缩减发送软件基于块级的重复数据删除技术，可以有效缩减数据存储容量，节省用户存储空间。它的主要特征如下：

（1）支持SB滑动块分块文件切分技术；

（2）零数据块碰撞，但损失部分性能；

（3）全局、源端、在线数据重消实现；

（4）支持数据包文件追加、删除、数据重消率统计功能；

（5）支持重消后数据压缩。

卫星数据缩减发送部件由7个子部件、22个单元构成，分别为主控部件、重复卫星数据消除部件、消除卫星数据压缩部件、数据文件传输部件、数据发送控制部件、运行日志管理部件、配置管理部件。

卫星数据缩减发送部件组成如图3所示。

卫星数据缩减发送软件采用面向对象面向对象设计方法和Qt Creator进行开发，客户端运行在Windows XP或者Win10上。

图3 卫星数据缩减发送部件图（部件图）

图4 客户端卫星数据缩减发送单元效果图一

图5 客户端卫星数据缩减发送单元效果图二

客户端卫星数据缩减发送软件实现部分效果如下图所示图4、图5所示。

[1] 杨冬, 孙剑伟. 基于令牌桶算法的卫星数据地面传输流量控制方法研究[J]. 软件, 2016, (03): 99-103.

[2] 黄志刚. 云备份中的双指纹校验与多线程传输技术研究[D]. 华中科技大学, 2011.

[3] 阳小珊, 朱立谷, 张琦琮, 郑良, 邱全伟, 汤占坤. 重复数据删除技术的存储空间利用率测评研究[J]. 计算机研究与发展, 2014, (S1): 187-194.

[4] Penna B, Tillo T, Magli E, et al. Transform coding techniques for lossy hyperspectral data compression[J]. IEEE Transactions on Geoscience and Remote Sensing, 2007, 45(5): 1408-1421.

[5] Roger R E, Cavenor M C. Lossless compression of AVIRIS images[J]. IEEE Transactions on Image Processing, 1996, 5(5): 713-719.

[6] Mielikainen J S, Kaarna A, Toivanen P J. Lossless hyperspectral image compression via linear prediction[C]//AeroSense 2002. International Society for Optics and Photonics, 2002: 600-608.

[7] 刘铁华. 基于HEVC框架的无损压缩编码算法研究[J]. 软件, 2013, 34(2): 69-72.

[8] 赵黛岩, 孙剑伟. 星地时间同步任务规划综合评价技术研究[J]. 软件, 2014, 35(1): 60-64.

Research and Implementation of Transmission Optimization Based on Satellite Data Reduction

TIAN Hao, SUN Jian-wei
(North China Institute of Computing Technology, Beijing 100083, China)

Satellite applications, there is a large amount of large data needs to be transmitted over the WAN, in order to improve the WAN transmission rate, which can be based on satellite ground applications, satellite data reduction as a starting point for research. Satellite data ground transmission The satellite ground receiving station as the original starting point of data, the central station or other sites that need satellite data as the destination site of data, this topic is the acceleration of satellite terrestrial data transmission optimization technology. In this paper, a satellite data reduction scheme is designed, which combines traditional data compression with today’s hot deduplication technology. Two optimization techniques are combined to achieve data compression and duplication of data blocks to eliminate the perfect match, to reduce the amount of data, reducing the ground station transmission pressure. Finally, the prototype system for satellite data reduction is designed.

Deduplication; Data compression; Acceleration platform

TP391.41

: A

10.3969/j.issn.1003-6970.2017.02.021

田浩(1991-），华北计算技术研究所研究生；孙剑伟，华北计算技术研究所，研究员级高级工程师。

本文著录格式：田浩，孙剑伟. 基于卫星数据缩减的传输优化技术研究与实现[J]. 软件，2017，38（2）：98-104