基于衛星數據縮減的傳輸優化技術研究與實現

田 浩，孫劍偉

基于衛星數據縮減的傳輸優化技術研究與實現

田 浩，孫劍偉

(華北計算技術研究所，北京 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