馬玲玲 張功萱

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

隨著云計算技術的普及，其上衍生出來的新興網(wǎng)絡存儲技術——云存儲也越來越受到人們的關注和歡迎。個人及企業(yè)越來越多地傾向于將信息從本地移動到云存儲中，使用者可以不受地域，時間，設備的限制，方便地從云上獲取或存儲數(shù)據(jù)［15］。但同時云存儲也帶來了很多安全隱患：首先為了實現(xiàn)成本效益，云存儲服務提供商一般將所有的用戶數(shù)據(jù)集中存儲，通過應用軟件來協(xié)調(diào)配合但缺乏高安全系數(shù)的數(shù)據(jù)隔離和API 控制措施，攻擊者能夠通過公共訪問接口竊取存儲信息；第二，分布在不同地區(qū)和環(huán)境中的物理存儲設備很可能會發(fā)生宕機，硬件損壞，軟件故障等問題，這樣就會導致該存儲設備中的數(shù)據(jù)不能訪問，嚴重地會導致數(shù)據(jù)永久丟失［1］。因此基于以上兩點，云存儲服務提供商需要對存儲的每一個數(shù)據(jù)塊都添加良好的保密措施以防止信息泄露，同時為了應對某個服務器出現(xiàn)不能使用的狀況，需要有良好的容錯能力。

1998 年，John Byers 和Luby 等首次提出了“數(shù)字噴泉”的概念，主要是為了傳統(tǒng)“抹除信道”上的大規(guī)模數(shù)據(jù)分發(fā)而設計的。在實用的數(shù)字噴泉碼LT 碼和Raptor 碼提出后，它的學術理論日漸完善并且被應用到越來越多的領域，比如無線網(wǎng)、移動網(wǎng)的流媒體點播或廣播，廣域網(wǎng)上的高速大文件傳輸以及深空通信等方面。但是由于它的可譯碼性不是絕對的百分之百等的問題，數(shù)字噴泉碼很少被應用到分布式存儲中的數(shù)據(jù)編碼，少量的研究該方向的文獻也只是討論了數(shù)字噴泉碼在編譯碼效率和節(jié)省空間等方面的優(yōu)勢。

因此本論文將研究如何把Raptor 碼應用到分布式存儲中：利用Raptor碼的優(yōu)勢提出分布式文件存儲架構，解決云存儲中容易出現(xiàn)的信息泄露和容錯能力差的問題；針對譯碼中可能出現(xiàn)的“最后一塊”問題提出反饋機制，提高譯碼效率并使得譯碼概率無限接近于1。

2 相關算法和技術

2.1 Raptor碼編碼

噴泉碼也稱為無率碼，顧名思義就是碼率不需要事先確定。噴泉碼將原始文件劃分為一定數(shù)量的數(shù)據(jù)包，再通過數(shù)據(jù)包編碼出任意數(shù)量的有效編碼包。當發(fā)送端傳送該數(shù)據(jù)時，只要接收端收到稍大于原始數(shù)據(jù)包數(shù)量的編碼包子集，就能夠還原原始數(shù)據(jù)［11］。這在有損連接的場景中是非常高效的傳輸數(shù)據(jù)的方式。因為在傳輸過程中，接收端不需要知道丟包率是多少，也不需要反饋接收到的數(shù)據(jù)包的情況。在“數(shù)字噴泉”概念提出之后，Luby 實現(xiàn)了第一種實用的數(shù)字噴泉碼——LT碼。針對LT碼的不足，Shokrollahi又在LT碼基礎上提出了Raptor 碼，其在編譯碼效率以及譯碼成功率上有了很大的改進，幾乎達到理想的編譯碼性能。

Raptor 編碼過程由預編碼和LT 編碼組成，假設目前原文件M 需要經(jīng)過Raptor 碼進行編碼。編碼過程［6］如下：

1）預編碼：把原文件M 均分為k-n 個分組，將k-n 個輸入單元通過某種傳統(tǒng)的糾刪碼（如：LDPC碼）轉(zhuǎn)換為k個中間編碼校驗單元。

2）LT編碼過程

輸入：k 個數(shù)據(jù)包x1，x2… xk，度分布函數(shù)ρ(d)

輸出：s個編碼包y1，y2… ys

定義：編碼包的度d為一個編碼包包含的原始數(shù)據(jù)包的數(shù)量

（1）通過弱化的魯棒孤波分布確定度分布ρ(d)

（2）根據(jù)度分布ρ(d)得到數(shù)值d，1 ≤d ≤k

（3）在k 個數(shù)據(jù)包中隨機均勻地選出d 個數(shù)據(jù)包

（4）將選出的d 個數(shù)據(jù)包進行異或運算，輸出一個編碼包

（5）重復（2）～（4）步驟產(chǎn)生s 個編碼包，s 值根據(jù)信道質(zhì)量而定

2.2 Raptor碼譯碼

Raptor 譯碼主要用兩種方法，第一為編碼的逆過程，利用LT 解碼技術恢復出一定比例的中間編碼校驗單元，再使用對應糾刪碼的譯碼方法恢復出原始數(shù)據(jù)塊。第二為定義內(nèi)碼和外碼中符號間的關系來直接恢復原始數(shù)據(jù)，例如高斯消元法求解的聯(lián)立方程。本論文所提的模型會針對LT解碼時的效率做出優(yōu)化，因此只討論第一種譯碼方法。

1）LT噴泉碼的解碼過程（置信傳播譯碼）

（1）根據(jù)接收到的一定數(shù)量的編碼包重建數(shù)據(jù)包和編碼包的雙向圖。

（2）找到一個度為1 的編碼包，若存在，則通過復制運算便可求得與之相連的數(shù)據(jù)包。若不存在，則譯碼停止或繼續(xù)接收編碼包直到找到。

（3）將已經(jīng)恢復的數(shù)據(jù)包和與之相連的編碼包進行異或操作，同時在雙向圖中把該數(shù)據(jù)包與此編碼包相連的邊刪除，對應的編碼包度數(shù)減1。

（4）重復步驟（2）和（3）直到恢復所有的數(shù)據(jù)包。

圖1 LT解碼過程示例

2）使用對應糾刪碼的譯碼方法恢復出原始數(shù)據(jù)塊。

2.3 Raptor碼度分布

2.3.1 LT碼度分布

LT 碼的加密過程可以產(chǎn)生無限的編碼包，都是通過原始數(shù)據(jù)包的子集進行異或運算得到的。而編碼過程中的度分布直接影響到最終是否能夠成功解碼以及解碼的復雜度，所以度分布的設計是LT 噴泉碼的關鍵。優(yōu)秀的度分布能夠使接收端以盡可能少的編碼包冗余，較低的解碼復雜度高概率地恢復出原始的數(shù)據(jù)包。在編解碼的過程中，優(yōu)秀的度分布設計需要平衡兩個方面。第一，應使編碼包的平均度數(shù)盡可能小以此降低解碼復雜度，但是又必須選取一定量較大的度以此來確保所有的輸入數(shù)據(jù)包都能夠參與到編碼過程中。第二，在解碼的過程中，度分布設計必須保證每次迭代后都有度為1 的輸出編碼包以確保解碼不會被迫停止導致解碼失敗，但是太多度為1 的編碼包會導致解碼過程過快而產(chǎn)生太多的冗余，尤其是將LT 碼運用到分布式存儲中時，度為1 的個數(shù)太多會使LT 噴泉碼失去它在安全性，低冗余性方面的優(yōu)勢。

1）理想孤波分布

Luby在提出LT噴泉碼的初期提出了理想孤波分布［2］（ISD），表示為ρ(i)，即P{d=i}。

此時編碼包的平均度數(shù)為ln k ，但是在實際使用中幾乎不會用到這種度分布方式，因為隨機數(shù)產(chǎn)生的值很難實現(xiàn)均勻分布，有一定的概率會使得度分布出現(xiàn)浮動，這就很可能會導致在解碼過程中不能出現(xiàn)度為1的編碼包從而解碼失敗。

2）魯棒孤波分布

Luby 之后提出了魯棒孤波分布［2］（RSD）去修正理想孤波分布帶來的不足。

定義：常數(shù)c＞0，允許的最大的解碼失敗概率δ ∈[0，1]，令R=c ln(k/δ)

度分布：μ(i)=( )ρ(i)+τ(i) β i=1，2，…k

由以上度分布公式可得編碼時間復雜度為O(ln(k/δ))，解碼時間復雜度為O(k ln(k/δ))。

2.3.2 Raptor對度分布的改進

上述魯棒孤波分布實現(xiàn)了較好的改進，但為了良好的覆蓋率，少量的編碼包有很高的度，這會升高編解碼復雜度，降低解碼成功率。Raptor 碼的兩步編碼方式正是針對此提出的思想。Raptor 碼在LT 編碼階段采用了弱化的度分度，即減小度的上限值，這樣就會增大連接度小的編碼包的概率。在譯碼的時候，先使用BP 譯碼解碼出絕大部分中間編碼校驗單元，再通過傳統(tǒng)的糾刪碼恢復出原始文件。因此Raptor碼有更低的編解碼復雜度，且在相同譯碼開銷下譯碼成功率更高。

3 基于Raptor 碼的分布式存儲架構及其可行性分析

3.1 基于Raptor碼的分布式存儲架構

云存儲架構仿照Google 的GFS 分布式文件系統(tǒng)搭建，一個控制節(jié)點，若干個存儲節(jié)點以及若干個用戶。1）控制節(jié)點存儲元數(shù)據(jù)，包括文件的命名空間，數(shù)據(jù)塊的命名空間，解碼所需的雙向圖，文件到塊的映射，塊當前的位置等?？刂乒?jié)點與客戶之間沒有文件內(nèi)容的交互傳輸，這能避免控制節(jié)點成為整個系統(tǒng)的性能瓶頸；2）客戶節(jié)點需要安裝使用云存儲服務所需的客戶端應用，由云存儲服務供應商提供。上傳文件和請求文件時直接與云存儲節(jié)點傳輸文件的具體內(nèi)容；3）云存儲節(jié)點負責存儲用戶的數(shù)據(jù)塊，受控制節(jié)點的調(diào)度，當出現(xiàn)異常狀況時會向控制節(jié)點匯報?？刂乒?jié)點也會定時監(jiān)測云存儲節(jié)點數(shù)據(jù)塊的狀況，包括當前數(shù)據(jù)塊的位置，是否存在錯誤等

圖2 基于Raptor碼的分布式存儲架構

文件上傳：客戶端使用軟件應用進行Raptor編碼之后把文件名，塊索引以及Raptor編碼雙向圖加密傳送給控制節(jié)點，控制節(jié)點加密存儲Raptor碼雙向圖并返回數(shù)據(jù)塊句柄及位置給客戶節(jié)點，然后客戶節(jié)點直接查找云存儲節(jié)點的位置，根據(jù)控制節(jié)點反饋的信息將數(shù)據(jù)塊傳送到對應的云存儲節(jié)點上。

文件請求：客戶端向控制節(jié)點發(fā)送文件請求，告知請求文件的名稱，控制節(jié)點查找到對應的解碼雙向圖通過加密的方式傳送給客戶端，并通過設定的規(guī)則查找到符合條件的數(shù)據(jù)塊句柄通知云存儲節(jié)點將數(shù)據(jù)塊傳送給客戶端，客戶端進行Raptor解碼。

雙向圖以Tanner圖的形式存儲，例如：

x:中間編碼校驗單元 y:編碼包

3.2 基于Raptor 碼的分布式存儲架構可行性分析

1）系統(tǒng)容錯性能：當前商用云存儲架構為了提高系統(tǒng)的容錯性，一般通過引入冗余技術實現(xiàn)的，常用的兩種冗余容錯技術為：副本和糾刪碼技術。因此本文將這三種技術的容錯性進行對比。

定義冗余度為采用容錯技術后所需的存儲空間與原始數(shù)據(jù)所需的存儲空間的比值。在云存儲中原始數(shù)據(jù)都會被劃分為固定大小的數(shù)據(jù)塊，而這三種容錯技術都不會改變單個數(shù)據(jù)塊的大小，因此我們設定k個原始數(shù)據(jù)塊經(jīng)過容錯技術后產(chǎn)生n個數(shù)據(jù)塊，最多允許t個數(shù)據(jù)塊失效。則冗余度為

三種技術產(chǎn)生的數(shù)據(jù)塊需滿足以下條件：

副本技術：

糾刪碼技術：

Raptor碼技術：

（e 與譯碼失敗率和n大小相關）

Raptor 的最新版本——RaptorQ Codes 能夠在接收到稍大于k 個編碼包的情況下編碼失敗率低于10-6。并且隨著接收到的符號個數(shù)的增長，編碼成功率將無線接近于百分之百。設定t為10。

圖3 相同容錯性下數(shù)據(jù)包與編碼包關系

由圖3 可得，副本技術的冗余度成線性增長，糾刪碼和Raptor 碼的冗余度相比于副本技術低很多。

2）編解碼復雜度

Raptor碼：

O(k ln(1/ε))（ε 是譯碼開銷）

常見的RS糾刪碼：

副本技術：0

圖4 解碼復雜度與數(shù)據(jù)包關系

從圖4 中可以看出因為副本技術不需要編解碼，所以在編解碼復雜度上占絕對優(yōu)勢，也正是因為這個原因云存儲服務商還是以副本技術為主。Raptor 編解碼復雜度比RS 糾刪碼低很多，尤其是當k 逐漸增大時糾刪碼的編解碼速度會快速減慢，Raptor碼相比于糾刪碼的優(yōu)勢會更明顯。

3）數(shù)據(jù)機密性

本文單從以上三種編碼技術本身來討論它們對保證數(shù)據(jù)機密性的貢獻。

副本糾刪碼Raptor碼攻擊存儲節(jié)點使得數(shù)據(jù)泄露偽造客戶請求獲得原始數(shù)據(jù)1 1 1 1 0 0

Raptor 編碼過程是根據(jù)度分布隨機選取原始數(shù)據(jù)塊異或得到編碼塊，因此會改變原始數(shù)據(jù)的內(nèi)容，即便攻擊者攻破云存儲節(jié)點獲得存儲的數(shù)據(jù)塊，也無法得知具體的內(nèi)容。盡管糾刪碼的校驗數(shù)據(jù)塊也是通過編碼獲得，但是原始數(shù)據(jù)塊仍然保留在存儲設備中，這就跟副本技術一樣，攻擊者容易從存儲節(jié)點找尋弱點來竊取數(shù)據(jù)。

Raptor 是根據(jù)雙向圖來譯碼的，所以如果以高安全系數(shù)的加密方式存儲雙向圖（如：可信安全芯片TCM［4，7］），即便攻擊者偽造客戶請求獲得所有的編碼數(shù)據(jù)塊，也無法恢復原始的數(shù)據(jù)。但是副本技術和糾刪碼技術就不能達到這方面的安全性要求。

4 基于反饋的Raptor譯碼優(yōu)化

將Raptor碼用于分布式存儲中存在一個問題，即控制節(jié)點接收到用戶請求后選取哪些編碼包來譯碼。我們需要保證能夠譯碼，還要盡可能減少譯碼開銷和減少系統(tǒng)調(diào)度開銷。

圖5 Raptor編碼分析圖（由上到下為數(shù)據(jù)包，中間編碼校驗單元，編碼包）

因此本文根據(jù)譯碼的流程提出了基于反饋的Raptor 譯碼優(yōu)化。設定原始文件均分為k 個數(shù)據(jù)包，經(jīng)過預編碼產(chǎn)生k+m 個中間編碼校驗單元，再經(jīng)過LT 編碼產(chǎn)生2k 個編碼包。LT 譯碼過程需要譯碼出≥k 個中間編碼校驗單元才能恢復原始數(shù)據(jù)。

之所以設置2k（副本技術一般存儲3k 個數(shù)據(jù)包）個編碼包是因為盡管Raptor 碼接收到稍大于K個編碼包恢復出原始數(shù)據(jù)的失敗率很低但也不是絕對的百分之百，如果用在分布式云存儲上這很低的概率也可能會導致用戶數(shù)據(jù)永久丟失。此外也是為了提供一定的容錯能力，由于我們不知道云存儲節(jié)點的故障率是多少，所以為了研究方便我們設置存儲2k 個編碼包使得解碼成功率無限接近于百分之百同時也保障了足夠的容錯性能。但是如果在譯碼時收集所有的編碼包并進行譯碼，不僅會增大系統(tǒng)調(diào)度開銷，也會使得編碼包冗余度增大從而增加譯碼開銷，因此本文設定控制節(jié)點只調(diào)度最近的k（1+σ）σ ≥0 個編碼包，如果LT 譯碼環(huán)節(jié)成功譯碼出大于等于k 個包，就向控制節(jié)點反饋成功信息，如果沒有達到最低標準，就向控制節(jié)點反饋未譯碼出的中間編碼校驗單元。以下就詳細分析未達到譯碼要求時的情況。

定義：（中間編碼校驗單元簡稱：中間單元）

已譯碼出的中間單元集合：φ(x)

未譯碼出的中間單元集合：?(x')

已收集的編碼包集合：η(y)

未收集的編碼包集合：μ(y')

待發(fā)送編碼包集合：?(y)

譯碼流程如下：

調(diào)度k（1+σ）個編碼包到客戶端進行譯碼；

將譯碼出的中間單元都加入φ(x)集合中；

未譯碼出的中間單元都加入?(x')集合中；

while（size（φ(x)）＜k）｛

for（i：?(x')）｛

在Tanner圖中定位該中間單元對應的列；

篩選出符合條件的編碼包集合Y ，異或產(chǎn)生該類編碼包的中間單元集合X 定義為{x|x ∈φ(x)，且x ?(?(x')-i)，且一定包含當前i}

if（找到符合條件的Y）｛

從Y 中選出最近的一個編碼包加入待發(fā)送列表?(y)；

｝//if end

｝//for end

將?(y)中的編碼包一起調(diào)度發(fā)送給客戶端并繼續(xù)進行LT譯碼迭代；

將新譯碼出的中間單元添加到φ(x)中；

從?(x')刪除新譯碼出的中間單元；

｝//while end

進行糾刪碼的譯碼過程；譯碼結束；

基于反饋的Raptor譯碼示例：

Tanner圖如下：

假定控制節(jié)點調(diào)度給客戶端的k（1+σ）個編碼包為y1，y2，y3，y4，y5，LT 譯碼過程至少要解出5個中間編碼校驗單元。由圖可知能夠譯碼出x1，x2，x3中 間 編 碼 校 驗 節(jié) 點?？?得φ(x)={x1，x2，x3} ，?(x')={x4，x5，x6} ，η(y)={y1，y2，y3，y4，y5} ，μ(y')={y6，y7}

迭代之后的Tanner圖為

客戶端向控制節(jié)點反饋?(x')，控制節(jié)點到編碼包集合?(x') 中依次選擇中間編碼校驗單元x4，x5，x6，到 μ(y') 中 查 找 符 合 條 件 的 編 碼 包，y6和y7都滿足除了x4之外的中間編碼校驗單元都已經(jīng)被譯碼得到?？刂乒?jié)點選擇最近的編碼包（設定為x6）傳送給客戶端繼續(xù)迭代過程，能夠譯碼出?(x')={x4，x5，x6}中所有的單元，譯碼結束。

5 仿真結果及分析

仿真實驗1：設定度分布參數(shù)c=0.2，δ=0.1，取原始數(shù)據(jù)包個數(shù)分別為k=80，200，400，每個包大小為0.5M。根據(jù)本文提出的基于Raptor 碼的分布式存儲架構進行仿真實驗，基于反饋的Raptor碼譯碼開始時客戶端只接收k 個原始數(shù)據(jù)包，將此解碼冗余度與用于“抹除信道”傳輸時的Raptor 冗余度相對比。

圖6 兩種譯碼方式下冗余度和譯碼成功率關系（實線：基于反饋虛線：基于抹除信道）

圖中虛線為用于“抹除信道”傳輸時的Raptor冗余度，實線為用于分布式存儲時的Raptor 冗余度。由仿真結果可得采用本文提出的譯碼方式在接收到1.1k個編碼包時，譯碼成功率就達到95%以上，且k 越大，譯碼成功率越高。相比于虛線所示的冗余度，該方法有了很大的改進。

仿真實驗2：根據(jù)本論文提出的基于Raptor 碼的云存儲架構，測量客戶從發(fā)送文件請求到接收文件成功所需要的時間。我們從仿真實驗1 中可看出，如果不進行反饋，冗余度大概在1.5的時候才能以很高的概率成功譯碼。因此我們將以下兩種情況做對比：1）采用本文提出的基于反饋的Raptor碼譯碼，測量客戶發(fā)送文件請求到譯碼成功的時間；2）譯碼過程不發(fā)送反饋，測量客戶發(fā)送文件請求到客戶端接收到1.5k個編碼包并譯碼結束的時間（此種情況下小概率會譯碼失敗，為了測量方便當出現(xiàn)這種情況導致譯碼停止時，則測量到譯碼停止的總時間）。原始數(shù)據(jù)包個數(shù)仍為k=80，200，400，每個包大小為0.5M，實驗的網(wǎng)速為1M/s。在針對每個數(shù)據(jù)測量時，我們?nèi)?0 組同等大小不用內(nèi)容的文件進行測量再取平均值得到。

圖7 兩種方式下用戶請求文件響應時間

用戶請求文件的總時間包括控制節(jié)點、客戶端節(jié)點、存儲節(jié)點之間溝通的時間，編碼包傳輸?shù)臅r間，以及譯碼的時間。理論分析上，基于反饋的譯碼方式比不反饋節(jié)省了一部分編碼包傳輸?shù)臅r間，多了節(jié)點之間溝通的時間。從仿真結果看，編碼包傳輸?shù)臅r間占總時間的很大一部分，所以基于反饋的譯碼方式比不反饋的節(jié)省了很大的時間開銷。

6 結語

本文針對分布式云存儲環(huán)境中存在的一些問題提出了基于Raptor碼的可靠云存儲服務，并改進了分布式環(huán)境中Raptor 的譯碼方式。經(jīng)過分析Raptor 碼在編解碼效率，容錯性以及安全性上相比于傳統(tǒng)的分布式存儲技術有很大的優(yōu)越性。并且根據(jù)仿真結果得出，改進的基于反饋的Raptor譯碼在譯碼開銷和整體的用戶時間上都有很大的減少。綜上，將以上改進的Raptor碼應用與分布式云存儲上有較高的實踐價值。