柳青，馮丹，李白

（華中科技大學 計算機科學與技術學院，湖北 武漢 430074）

1 引言

隨著分布式存儲系統(tǒng)集群的擴張和云存儲的廣泛應用，冗余編碼逐漸應用于分布式存儲系統(tǒng)中保證數據的可靠性，減少了存儲容量和存儲成本[1]。常用的糾錯碼有Reed-Solomon碼（RS碼[2]）。(n,k)-RS 碼是一種最大距離可分（MDS, maximum distance seperable）碼，也就是所有數據存儲在n 個節(jié)點中，其中，任意k個節(jié)點的數據可以恢復出原始數據[3]。(n,k)-RS 保證了最多可失效(n-k)節(jié)點而原數據不丟失。而分布式存儲系統(tǒng)中，單個節(jié)點的失效是常態(tài)，多個節(jié)點的失效不常見。將RS碼應用于分布式存儲系統(tǒng)中有幾點值得注意：1) RS碼修復一個節(jié)點的數據所需要的修復帶寬遠大于該節(jié)點數據的數據量，從信息角度來說，傳輸過量數據用于修復少量數據是一種浪費；2) RS碼修復一個存儲節(jié)點和多個存儲節(jié)點所需要下載數據量是一樣的。從本質上看導致以上2點的原因是：RS碼的修復重建了原始數據并重新對丟失的數據進行編碼，所以每次修復無論修復數據量的大小，都必須從網絡上傳輸相當于原始數據量大小的數據。云存儲系統(tǒng)中存儲了海量數據，如何減少因為數據丟失而產生的修復數據量是云存儲系統(tǒng)需要面對的關鍵問題之一。

云存儲服務提供了開放的存儲接口，用戶只需要付費即可使用相應的存儲和帶寬服務?；诂F有的多個商業(yè)云存儲服務，搭建了統(tǒng)一云存儲系統(tǒng)Ustor[4]，并采用功能性修復再生碼（FRC）保證數據冗余的同時減少修復帶寬。實驗表明，與傳統(tǒng)的RS碼相比，采用FRC能夠減少修復單個云存儲系統(tǒng)中丟失數據的修復帶寬，節(jié)省開支，且對系統(tǒng)響應時間影響較小。

2 相關編碼技術

2.1 冗余編碼

Ustor實現了RAID碼、RS碼和再生碼等冗余編碼，它們都是線性碼，即使用線性組合的方式計算得到編碼后的冗余數據。本節(jié)將介紹Ustor如何使用這些冗余編碼將文件編碼為冗余數據塊。冗余編碼包括再生碼中的所有計算都是在有限域GF(2w)中進行的，w為字大小，它決定了有限域的大小和每次運算的位數。w越小，編解碼的速度越快；w越大，存儲系統(tǒng)可以支持更多的存儲節(jié)點。Ustor可選的w有8、16、32和64，考慮到編、解碼速度，w一般為8。

生成矩陣（GM, generator matrix）定義了如何將原始數據塊編碼為冗余數據塊，RS碼的生成矩陣是一個n行k列矩陣，將k塊原始數據塊編碼為n塊冗余數據塊。如果對應的編碼是系統(tǒng)碼（比如RAID），編碼后包含了原始數據，則生成矩陣中包含一個k×k大小的單位矩陣和(n-k)×k的冗余矩陣，單位矩陣對應的是原始數據塊，冗余矩陣對應的是冗余數據塊。非系統(tǒng)碼沒有單位矩陣，整個生成矩陣都是冗余矩陣，因此編碼后只有冗余數據塊。行向量中項對應的是由原始數據塊的組合系數，每個冗余數據塊是原始數據塊線性組合得到的。生成矩陣的每一個行向量對應一個冗余數據塊，它們關系可以表示為

其中，Ei和Dj分別表示第i塊編碼數據塊和第j塊數據塊，GMi,j代表生成矩陣GM第i行、第j列項的值。RS碼保持著MDS性質。MDS性質指的是，編碼后n個云存儲服務中任意k個可以恢復出原始數據，這要求RS碼生成矩陣中n行向量中任意k行都是行滿秩的。

2.2 修復帶寬和再生碼

如果將每個云存儲服務看做獨立的存儲節(jié)點，修復指的是當該存儲節(jié)點數據丟失時，從其他助手存儲節(jié)點下載一定量的數據用于恢復丟失的數據。如果恢復出來的數據和原來丟失的數據一樣，則這樣的修復是精確修復；但如果恢復出的數據和丟失的數據不同，而只是保持了MDS性質，本文稱之為功能性修復。精確修復恢復出來的數據和丟失的數據完全一致，因此編碼數據塊MDS性質得以保持。RAID碼和RS碼都是精確修復，每個存儲節(jié)點保存一塊冗余數據塊，修復一個冗余數據塊時，從其余任意k個助手存儲節(jié)點中下載冗余數據塊可以精確修復出丟失的冗余數據塊。

修復帶寬指的是節(jié)點發(fā)生失效導致數據丟失時，需要從網絡中其他節(jié)點下載的數據量。在分布式存儲系統(tǒng)中，單個節(jié)點失效已經是常態(tài)，減少修復帶寬能夠更快地修復丟失的數據[5]，并減少對其他正常數據使用的影響，因為較大的修復帶寬會占據更多寶貴的網絡資源和磁盤I/O資源。微軟Azure云存儲系統(tǒng)[6]使用局部重建碼（LRC, local reconstruction codes）對固定大小的數據塊進行冗余編碼，通過減少每次編碼關聯的節(jié)點個數減少了修復帶寬。NCFS是基于云存儲系統(tǒng)的一個用戶態(tài)文件系統(tǒng)，利用最小存儲再生碼F-MSR[7]減少了修復帶寬。

再生碼[8]是近年提出的一種應用于分布式存儲系統(tǒng)的冗余編碼。已有理論證明它可以達到存儲和修復帶寬的最優(yōu)權衡[9]，顯著減少了修復帶寬。再生碼也是一種MDS 碼，但其并不一定是存儲最優(yōu)的。最小存儲再生碼[10](MSR, minimum storage regenerating codes)是和RS碼一樣具有最優(yōu)存儲效率，最小帶寬存儲再生碼（MBR,minimum bandwidth regenerating codes）不是存儲最優(yōu)的，它在每個存儲節(jié)點存儲了更多的數據，但在修復單個節(jié)點失效數據時具有最高的修復效率，其在網絡上傳輸的修復數據量和該節(jié)點丟失的數據量相同。

再生碼或者通過增加每個云存儲服務中存儲的數據量，或者增加每次修復時助手存儲節(jié)點的數量(d)，來減少修復帶寬。不同于RS碼，再生碼在每個云存儲服務中保存α塊冗余數據塊，每次修復時是從d(d≥k)個助手存儲節(jié)點中下載共計d×β個冗余數據塊，每個節(jié)點下載β(α＞β)塊。每個再生碼由一個六元組參數確定(n,k, α, β, d, B)，最后一個參數B是原始數據塊的個數。根據Dimakis推導出的再生碼理論限制，以上參數應滿足

相應地，再生碼的生成矩陣GM有nα行B列，nα個行向量對應著nα個冗余數據塊。如果將生成矩陣GM對應n個節(jié)點按行分為n個子矩陣GMi(i=1, …, n)，每個子矩陣對應著一個云存儲服務，且GM=[GM1, GM2,…,GMn]T。GMi是第i個云存儲服務中冗余數據塊的生成矩陣，即云存儲服務i中的α個冗余數據塊（E(i-1)α+1,…,Eiα）等于子矩陣GMi和原始數據塊(D1, D2,…, DB)的乘積，即

再生碼也是MDS碼，也必須滿足MDS性質。那么n個云存儲中任意k個中的所有冗余數據塊可以恢復出原始數據，同理n個子矩陣GMi中任意k個子矩陣組合成的矩陣秩等于B，則MDS性質滿足。

3 Ustor系統(tǒng)結構

3.1 Ustor簡介

統(tǒng)一云存儲系統(tǒng)（Ustor）基于成熟的商業(yè)云存儲服務，并對用戶提供理論上無限的存儲資源。Ustor向下通過統(tǒng)一的接口對多個云存儲服務提供商的存儲資源進行管理，向上對用戶提供簡單的上傳、下載接口。多個云存儲服務對用戶是透明的，用戶可以像使用本地磁盤一樣使用多個云存儲服務的存儲資源。Ustor由Ustor服務器和多個云存儲服務組成的混合云（cloud of clouds）組成。Ustor服務器并不存儲用戶的任何數據，其職責有：1) 云網關，緩存用戶上傳和下載的數據，并將其上傳到云存儲服務或者返回給用戶；2) 冗余編碼，對用戶上傳的數據進行冗余編碼，并對下載的編碼數據塊解碼為原始數據；3) Web服務器，Ustor提供一個簡單易用的Web接口使用戶可以通過瀏覽器上傳和下載文件。

3.2 Ustor系統(tǒng)架構

如圖1所示，Ustor服務器和多個云存儲服務組成了Ustor云存儲系統(tǒng)。Ustor支持一次寫入、多次讀取的訪問模式。用戶可以通過廣域網連接至Ustor服務器，下載或上傳文件。Ustor服務器將負責用戶數據緩存和數據編碼，也通過廣域網連接不同地域上、異構的云存儲系統(tǒng)。這些云存儲系統(tǒng)在地域上分布廣泛，國內外都有。這些云存儲提供的認證方法不同，訪問接口不相同，但都提供一種類似于REST的訪問接口，于是Ustor虛擬化出統(tǒng)一的接口代替云存儲服務商提供異構的、差異化云存儲接口，實現編碼數據塊在云存儲系統(tǒng)的存與取。多個云存儲服務共同負責存儲數據文件和元數據文件。其中，數據文件通過冗余編碼的方式保障可靠性，元數據文件通過副本的方法保障可靠性。當某個云存儲因為網絡不可訪問，通過訪問其他可用的云存儲服務，保證數據的可用性。當某個云存儲中冗余數據塊發(fā)生丟失時，通過修復過程生成新的冗余數據塊保證數據的可靠性。

圖1 Ustor云存儲系統(tǒng)結構

Ustor服務器主要由數據編碼模塊、元數據管理和數據分布模塊組成。模塊層次和組成如圖2 所示。數據編碼模塊負責將用戶上傳的文件進行冗余編碼?？梢圆捎肦S碼或RAID碼，也可以使用功能性修復再生碼(FRC, functional regenerating codes)。這些冗余碼共同的基礎是一個編碼庫（coding library），其負責將讀入內存的文件編碼為多個冗余數據塊。編碼庫中使用的部分數據結構來自于線性代數庫（linear algebra library），比如生成矩陣GM和生成矩陣每一行的行向量。生成矩陣GM決定了如何將原始文件編碼為冗余數據塊，RS碼使用的是范德蒙德矩陣，FRC碼使用隨機矩陣。編碼過程中生成矩陣和數據塊的計算不同于通常的算術運算，而是基于有限域。伽羅瓦有限域運算庫（galois arithmetic library）提供了有限域上基本的算術運算，是編碼庫的基礎。整個編碼模塊就像一個黑盒子（erasure coding box），輸入的是將原始文件分割為k塊等大小的原始數據塊，輸出的是編碼后的n個冗余數據塊。編碼過程中的編碼方法和編碼參數將作為元數據信息由元數據管理模塊記錄于元數據文件中。

圖2 Ustor服務器模塊

LibCloud 是Apache的項目之一，它消除不同云服務提供商的差異性服務，抽象出了云存儲服務的統(tǒng)一接口。Ustor系統(tǒng)將其作為數據分布層的基礎，它的作用相當于Ustor的I/O驅動模塊（不同的云存儲類似于不同的存儲設備）。Ustor寫入數據時，所有編碼后的數據塊都是通過其寫入到具體的云存儲中；讀取數據或者修復數據塊時，它從指定的云存儲中讀取指定的數據塊，并返回給編碼層用于解碼或修復。系統(tǒng)在原有LibCloud的基礎上做了2點改進：1) 原有LibCloud兼容Amazon S3等國外云存儲，不支持Dropbox和國內的云存儲，本系統(tǒng)整合了Dropbox、阿里云存儲和快盤云存儲，并補充了各自的身份認證方法；2) 修改LibCloud對上層的接口，使其能夠兼容編碼層。每一個云存儲對應著一個存儲節(jié)點，為這些存儲節(jié)點編號，并記錄下每個云存儲與編碼的一一對應關系。元數據管理模塊將在數據塊寫入時，記錄下編碼后數據塊所上傳的云存儲編號等元數據信息，并在讀取數據塊時，利用元數據信息中編碼數據塊所在的存儲節(jié)點編號找到相應的云存儲。

如之前兩段所言，數據進行冗余編碼和冗余數據塊分布的過程中會產生一些元數據信息，這些上傳文件的元數據由文件元數據模塊管理。對于用戶上傳的每個文件都有對應一個元數據文件保存這些全局和冗余數據塊的元數據。在編碼時，元數據模塊記錄下編碼前文件大小、所采用的編碼方法、所使用的生成矩陣和計算有限域的大小等編碼信息，并記錄下每個冗余數據塊所對應存儲節(jié)點的編號。分布層中LibCloud按照云存儲的編號和每個冗余數據塊對應的編號來上傳冗余數據塊。在解碼或者修復某個節(jié)點的數據塊時，也需要這些冗余數據塊的分布信息和編碼信息進行解碼和修復。因此Ustor為保證元數據文件的高可靠性，在保存了該文件冗余數據塊的所有云存儲上都保留了一份元數據文件副本。在修復時冗余數據塊會發(fā)生改變時，Ustor將同步更新所有元數據文件以保證數據的一致性。每個元數據文件大小在1 KB左右，帶來額外的存儲、網絡開銷很小，可以忽略不計。下面給出了一個包含全局（global）元數據信息和一個冗余數據塊（chunk00）的部分元數據信息的例子。全局元數據信息包含的是原始文件信息、編碼相關參數和所使用的云存儲編號，冗余數據塊元數據信息記錄了某個冗余數據塊所在云存儲編號等信息。

包含全局元數據信息和一個冗余數據塊的部分元數據信息：

4 基于再生碼的云存儲系統(tǒng)

Ustor將用戶上傳的文件編碼為冗余數據塊，分別保存至多個云存儲服務中。當用戶下載文件時，從任意指定個數量的云存儲服務中下載冗余數據塊，解碼出原始數據并將文件返回給用戶。當冗余數據塊發(fā)生損壞或者丟失時，從其他云存儲服務下載一定數量的冗余數據塊再生該冗余數據塊。

4.1 文件上傳

文件的上傳指的是用戶將文件F保存至Ustor云存儲系統(tǒng)，包括以下步驟：1) 編碼模塊（erasure coding box）將用戶上傳的文件等分為B塊原始數據塊（F1, F2, … , FB），不足的位用零填充；2) 編碼模塊隨機生成(nα)×B大小、且滿足MDS性質的生成矩陣GM，如不滿足，重新生成新的生成矩陣直至該性質滿足；3) 編碼模塊使用GM將B塊原始數據塊編碼為nα塊冗余數據塊(E1, …, Eα,…,Enα)；4) LibCloud模塊將nα塊冗余數據塊上傳到n個可用的云存儲服務中；5) LibCloud模塊將元數據文件Fmeta上傳至上一步保存冗余數據塊的n個云存儲服務中，每個保存一份副本。

4.2 文件下載

文件的下載指的是用戶從Ustor下載指定文件F。包括以下步驟：1) LibCloud從任意一個云存儲服務中下載該文件的元數據文件Fmeta，獲得用于編碼的生成矩陣GM等元數據信息；2) 從n個云存儲服務中選定k個，并從相應的k個子矩陣中選取B個不相關行向量構成B×B大小的正方矩陣，根據MDS性質這樣的B個行向量總是可以找到的。這個正方矩陣的逆矩陣為解碼矩陣（DM, decode matrix）；3) LibCloud從上一步驟中選定的k個云存儲服務中下載正方矩陣中行向量一一對應的冗余數據塊，共計B塊（記作Ed,1，Ed,2,…,Ed,B）；4) 計算解碼矩陣DM和下載的B塊冗余數據塊（Ed,1，Ed,2,…,Ed,B）的乘積，得到B塊原始數據塊（D1,D2, …, DB）。合并原始數據塊，利用元數據中文件長度截取得到文件F返回給用戶。

4.3 數據修復

具有MDS性質的編碼最多允許n-k個云存儲服務同時丟失數據，但這里僅討論一個云存儲服務丟失其存儲的冗余數據塊的情況（n=d+1）。不妨設發(fā)生冗余數據塊丟失的云存儲服務編號為i，那么該云存儲中冗余數據塊（E(i-1)α+1,…, Eiα）丟失，且生成矩陣GM中的生成子矩陣GMi也不再可用。數據修復過程包括：生成子矩陣GMi的修復和冗余數據塊的修復。生成子矩陣修復將生成新的GMi'代替不可用的GMi，使生成矩陣的MDS性質繼續(xù)保持，修復前的生成矩陣記作GM，修復后的生成矩陣記作GM '。冗余數據塊的修復將真正地修復冗余數據塊，而上一步生成子矩陣的成功修復保證了將要生成的冗余數據塊也是滿足MDS性質的。

修復GMi的思路是從d個參與修復的子矩陣（GM1,…,GMi-1, GMi+1,…,GMn）中各找到 β個行向量，將這dβ個行向量線性組合為具有α個行向量的新子矩陣GMi'，用其代替原來失效的GMi，使新的生成矩陣GM '滿足MDS性質。修復流程如圖3所示。具體步驟如下：1) LibCloud從任意一個云存儲服務中下載文件的元數據文件Fmeta，獲得用于編碼的生成矩陣GM和n、k、α、β、d、B等參數；2) 除去失效的子矩陣GMi，從剩余的d=n-1個子矩陣中隨機選取dβ個行向量組成一個候選矩陣（CM,candidate matrix），每個子矩陣隨機選取β個行向量；3) 隨機生成一個α×dβ大小的修復矩陣（RM, repair matrix），修復矩陣RM的作用是將候選矩陣CM線性組合為新的子矩陣GMi'；4) 新的子矩陣GMi'為修復矩陣RM和候選矩陣的乘積，即GMi'α×B=RMα×dβ×CMdβ×B。5)將原先GM中子矩陣GMi替換為GMi'，如果替換后的新生成矩陣GM '的MDS性質得以保持，則子矩陣修復成功；如果MDS性質不保持，則返回至第2)步進行下一輪修復嘗試，并重新選取候選矩陣和修復矩陣生成新的生成子矩陣GMi'，直至它使得新生成GM '的MDS性質滿足。

圖3 其他生成子矩陣參與修復生成子矩陣GMi

以上循環(huán)的修復過程可能會遇到一種困境：無論修復嘗試多少次，從d個子矩陣中都無法找到一個候選矩陣CM，使得由它線性組合得來的子矩陣GMi'都無法使得GM '滿足MDS性質。因此設置一個閾值（比如1 000次），當嘗試修復了超過了這個閾值，則從第2)步d個子矩陣中多選擇一些行向量以輔助修復。實際修復中超過閾值的修復很少發(fā)生，可以忽略不計。需要說明的是生成子矩陣的修復是在Ustor服務器上進行的，只需要對生成矩陣進行修復計算，每一次修復嘗試也不需要從云端下載任何數據，所以這個過程非?？臁Ｖ挥腥哂鄶祿K的修復才真正地從云端下載冗余數據塊。

一旦生成子矩陣GMi的修復成功，LibCloud從d個云存儲服務中下載dβ 個冗余數據塊，每個冗余數據塊對應著候選矩陣CM中的每一行向量，也就是說這些數據塊都是通過候選矩陣CM編碼得來的。計算修復矩陣RM和這dβ個冗余數據塊的乘積可以得到新的α個冗余數據塊，這α個冗余數據塊和其他節(jié)點的冗余數據塊是滿足MDS性質的。這是因為修復子矩陣和修復冗余數據塊是對應的，它們之間有關系：

因此，只要包含修復得到新生成子矩陣GMi'的生成矩陣GM'是滿足MDS 性質的，那么新生成的冗余數據塊總是滿足MDS性質的。接著LibCloud將這α個新生成冗余數據塊上傳到編號為i的云存儲服務中，將它們作為新的冗余數據塊（E'(i-1)α+1,…,E'iα）。最后生成新的元數據文件并更新所有云存儲服務中的元數據文件Fmeta，修復完畢。

5 性能評價

本文從2個方面評測基于再生碼的Ustor云存儲系統(tǒng)性能：分析Ustor所使用的云存儲服務的價格和速度；分析系統(tǒng)響應時間，分析不同編碼對數據存儲的影響。實驗環(huán)境：一臺Ustor服務器CPU為Intel Xeon E5620 2.40 GHz，32 GB內存，并通過100 Mbit/s專線寬帶連接Internet。

5.1 Ustor的云存儲服務分析

Ustor云存儲系統(tǒng)現已采用國內的阿里云（AliYun）、金山快盤（KuaiPan）和國外的Amazon S3和Dropbox等云存儲服務。Ustor服務器通過廣域網連接著以上4個云存儲服務。表1給出了在2013年6月這4個云存儲服務提供商的計費。所有的云存儲服務都主要以存儲計費和下載計費作為主要盈利方式。雖然所有云存儲服務上傳帶寬都是免費的，但下載數據的費用卻都比較高，大于相同數據量數據存儲一個月的費用。

每個云存儲服務不僅價格不同，所提供的上傳、下載帶寬也不同。圖4是Ustor 從單個云存儲服務和多個云存儲服務上傳或下載100 MB數據的速度與響應時間。如果Ustor連接的是單個云存儲服務，上傳速度最快的是阿里云存儲，最慢的是金山快盤；下載速度最快的是金山快盤，最慢的是Dropbox。相比單個云存儲服務，多個云存儲服務組成的混合云相應時間更加穩(wěn)定，速度也更快，這是因為利用了多個云存儲服務的網絡帶寬，抹平了單個云帶寬的“短板”。因此Ustor的存儲帶寬對應的是圖3中4個云存儲服務一起使用時的上傳下載帶寬，這4個云存儲服務組成的混合云也是本文下一小節(jié)測試響應時間的基礎。

表1 4個云存儲服務計費比較

5.2 Ustor響應時間分析

測試Ustor使用FRC對響應時間的影響，圖5給出了Ustor使用再生碼編碼和不使用編碼時，上傳和下載不同大小文件的響應時間。編碼采用的是(4, 2, 2, 1, 3, 4)-FRC，不編碼則將等量的分塊數據上傳或下載。n=4，所以冗余分塊存儲在所有4個云存儲服務中。文件越大，所需要的編碼、解碼時間越長，其占響應時間就越長，當原始文件大小為256 MB時，不編碼上傳響應時間為78.8 s，編碼上傳響應時間為83.5 s，編碼時間占整個上傳響應時間5.6%。測試下載響應時間時，Ustor僅從下載速度最快的2個云存儲服務中下載冗余數據塊進行解碼。256 MB文件不解碼下載和解碼下載時間分別為18.4 s和20.5 s，解碼占響應時間的10.2%。如果文件小于256 MB時，編、解碼占響應時間更少。

接下來使用100 MB文件測試Ustor上傳、下載和修復3個操作中響應時間的組成。本文一共測試了4組編碼，包括容2個云存儲服務失效的(4, 2, 2, 1,3, 4)-FRC（簡寫為(4, 2)-FRC）和(4, 2)-RS與容單個云存儲服務失效的(4, 3, 2, 1, 5)-FRC（簡寫為(4,3)-FRC）和(4, 3)-RS。圖6(a)給出了Ustor服務器采用4種編碼方法在上傳、下載和修復3個操作中響應時間的組成：上傳、下載和編碼與磁盤讀寫。不難看出，和編碼與磁盤讀寫所占用的時間相比較，4種操作中網絡傳輸時間（上傳、下載）占了響應時間的絕大部分。進一步分析響應時間的組成，圖6(b)中給出了不包括網絡傳輸的響應時間組成。上傳、下載和修復3種操作中，修復磁盤讀寫（灰色）都占了大部分，而編、解碼都在1 s內完成。因為FRC是非系統(tǒng)碼，所以其編碼、解碼時間要長于系統(tǒng)碼的Reed-Solomon編碼，但2種編碼修復時間相差不大。

圖6中(4,2)-FRC和(4,3)-FRC是功能性修復再生碼(4,2,2,1,3,4)-FRC和(4,3,2,1,3,5)-FRC；(4,2)-RS和(4,3)-RS分別表示使用Reed-Solomon編碼的RAID6和RAID5。

在上面的例子中每個100 MB文件被(4,2)-FRC編碼為8塊25 MB冗余塊，被(4,2)-RS編碼為4塊50 MB冗余塊，每個云存儲服務均存儲50 MB數據。每修復一個失效云存儲服務的50 MB數據，(4,2)-FRC需要下載25 MB×3=75 MB數據，而(4,2)-RS卻需要下載50 MB×2=100 MB數據，(4,2)-FRC比(4,2)-RS具有相同的存儲效率，卻節(jié)省了用于下載數據塊25%的修復帶寬。從上一小節(jié)可以知道云存儲服務是按照下載計費的，節(jié)省了25%修復帶寬意味著節(jié)省了25%的下載成本。同理(4,3)-FRC比(4,3)-RS需要額外16.67%的存儲開銷，但卻節(jié)省了40%的修復帶寬。所有情況元數據文件大小遠小于冗余數據塊大小，成本可忽略?？傊?，Ustor在使用FRC時，其性能和使用Reed-Solomon碼接近，但再生碼在修復單個云存儲服務中丟失的數據時節(jié)省了修復帶寬，從而節(jié)省了下載成本。

圖4 Ustor上傳/下載100 MB文件到單個云存儲服務或者多個云存儲服務的響應時間和速度（圖中縮寫S/D/A/K分別表示亞馬遜S3、Dropbox、阿里云和金山快盤）

圖5 Ustor上傳/下載100 MB文件到多個云存儲服務的響應時間和速度

圖6 Ustor采用FRC編碼和RS編碼100 MB文件的響應時間

圖6中，(4,2)-FRC和(4,3)-FRC是功能性修復再生碼(4,2,2,1,3,4)-FRC和(4,3,2,1,3,5)-FRC；(4,2)-RS和(4,3)-RS分別表示使用Reed-Solomon編碼的RAID6和RAID5。

6 結束語

本文提出并實現了基于再生碼的云存儲系統(tǒng)Ustor，其在多個商業(yè)云存儲服務上使用編碼提供可靠性。在單個云存儲中數據發(fā)生丟失時，相對于傳統(tǒng)的Reed-Solomon碼，功能性修復再生碼能夠達到存儲和修復帶寬的折衷，減少數據重建時的修復帶寬，即需要從其他云存儲中下載的數據量，從而減少成本。從Ustor云存儲系統(tǒng)的測試來看，使用FRC對數據編碼帶來的響應時間的影響最大在5%～10%左右，而采用FRC或Reed-Solomon碼對系統(tǒng)的性能影響相當。Ustor可以通過網址http://www.ustor.cn/訪問。

[1] LI J, LI B. Erasure coding for cloud storage systems: a survey[J].Tsinghua Science and Technology, 2013, 18(3): 259-272.

[2] PLANK J S. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems[J]. Software: Practice and Experience 1997, 27(9):995-1012.

[3] PLANK J S, LUO J, SCHUMAN C D. A performance evaluation and examination of open-source erasure coding libraries for storage[A].Proceedings of the seventh USENIX Conference on File and Storage Technologies (FAST'09)[C]. San Francisco, USA, 2009.253-265.

[4] Ustor[EB/OL]. http://www.ustor.cn/, 2013.

[5] HU Y, YU C M, LI Y K. On the practicality and extensibility of a network-coding-based distributed file system[A]. Proceedings of the Seventh IEEE International Symposium on Network Coding (Net-Cod'11)[C]. Boston, MA, USA, 2011.1-6.

[6] HUANG C, SIMITCI H, X Y. Erasure coding in windows azure storage[A]. Proceedings of the 25-th USENIX Annual Technical Conference(ATC'12)[C]. Boston, USA, 2012.15-26.

[7] HU Y, CHEN H C, LEE P P. NCCloud: applying network coding for the storage repair in a cloud-of-clouds[A]. Proceedings of The 10th USENIX Conference on File and Storage Technologies (FAST'12)[C].San Francisco, USA, 2012.265-271.

[8] SHUM K W, HU Y. Functional-repair-by-transfer regenerating codes[A].Proceedings of the IEEE 20th International Symposium on Information Theory Proceedings (ISIT'12)[C]. Cambridge, MA, USA, 2012.1192-1196.[9] DIMAKIS A G, GODFREY P B, WU Y. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory,2010, 56(9): 4539-4551.

[10] SHAH N B, RASHMI K V, VIJAY K P. Distributed storage codes with repair-by-transfer and nonachievability of interior points on the storage-bandwidth tradeoff[J]. IEEE Transactions on Information Theory,2012, 59(3): 1837-1852.