柳青，馮丹，李白

（華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430074）

1 引言

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

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

2 相關(guān)編碼技術(shù)

2.1 冗余編碼

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

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

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

2.2 修復(fù)帶寬和再生碼

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

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

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

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

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

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

3 Ustor系統(tǒng)結(jié)構(gòu)

3.1 Ustor簡(jiǎn)介

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

3.2 Ustor系統(tǒng)架構(gòu)

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

圖1 Ustor云存儲(chǔ)系統(tǒng)結(jié)構(gòu)

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

圖2 Ustor服務(wù)器模塊

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

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

包含全局元數(shù)據(jù)信息和一個(gè)冗余數(shù)據(jù)塊的部分元數(shù)據(jù)信息：

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

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

4.1 文件上傳

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

4.2 文件下載

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

4.3 數(shù)據(jù)修復(fù)

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

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

圖3 其他生成子矩陣參與修復(fù)生成子矩陣GMi

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

一旦生成子矩陣GMi的修復(fù)成功，LibCloud從d個(gè)云存儲(chǔ)服務(wù)中下載dβ 個(gè)冗余數(shù)據(jù)塊，每個(gè)冗余數(shù)據(jù)塊對(duì)應(yīng)著候選矩陣CM中的每一行向量，也就是說(shuō)這些數(shù)據(jù)塊都是通過(guò)候選矩陣CM編碼得來(lái)的。計(jì)算修復(fù)矩陣RM和這dβ個(gè)冗余數(shù)據(jù)塊的乘積可以得到新的α個(gè)冗余數(shù)據(jù)塊，這α個(gè)冗余數(shù)據(jù)塊和其他節(jié)點(diǎn)的冗余數(shù)據(jù)塊是滿足MDS性質(zhì)的。這是因?yàn)樾迯?fù)子矩陣和修復(fù)冗余數(shù)據(jù)塊是對(duì)應(yīng)的，它們之間有關(guān)系：

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

5 性能評(píng)價(jià)

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

5.1 Ustor的云存儲(chǔ)服務(wù)分析

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

每個(gè)云存儲(chǔ)服務(wù)不僅價(jià)格不同，所提供的上傳、下載帶寬也不同。圖4是Ustor 從單個(gè)云存儲(chǔ)服務(wù)和多個(gè)云存儲(chǔ)服務(wù)上傳或下載100 MB數(shù)據(jù)的速度與響應(yīng)時(shí)間。如果Ustor連接的是單個(gè)云存儲(chǔ)服務(wù)，上傳速度最快的是阿里云存儲(chǔ)，最慢的是金山快盤(pán)；下載速度最快的是金山快盤(pán)，最慢的是Dropbox。相比單個(gè)云存儲(chǔ)服務(wù)，多個(gè)云存儲(chǔ)服務(wù)組成的混合云相應(yīng)時(shí)間更加穩(wěn)定，速度也更快，這是因?yàn)槔昧硕鄠€(gè)云存儲(chǔ)服務(wù)的網(wǎng)絡(luò)帶寬，抹平了單個(gè)云帶寬的“短板”。因此Ustor的存儲(chǔ)帶寬對(duì)應(yīng)的是圖3中4個(gè)云存儲(chǔ)服務(wù)一起使用時(shí)的上傳下載帶寬，這4個(gè)云存儲(chǔ)服務(wù)組成的混合云也是本文下一小節(jié)測(cè)試響應(yīng)時(shí)間的基礎(chǔ)。

表1 4個(gè)云存儲(chǔ)服務(wù)計(jì)費(fèi)比較

5.2 Ustor響應(yīng)時(shí)間分析

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

接下來(lái)使用100 MB文件測(cè)試Ustor上傳、下載和修復(fù)3個(gè)操作中響應(yīng)時(shí)間的組成。本文一共測(cè)試了4組編碼，包括容2個(gè)云存儲(chǔ)服務(wù)失效的(4, 2, 2, 1,3, 4)-FRC（簡(jiǎn)寫(xiě)為(4, 2)-FRC）和(4, 2)-RS與容單個(gè)云存儲(chǔ)服務(wù)失效的(4, 3, 2, 1, 5)-FRC（簡(jiǎn)寫(xiě)為(4,3)-FRC）和(4, 3)-RS。圖6(a)給出了Ustor服務(wù)器采用4種編碼方法在上傳、下載和修復(fù)3個(gè)操作中響應(yīng)時(shí)間的組成：上傳、下載和編碼與磁盤(pán)讀寫(xiě)。不難看出，和編碼與磁盤(pán)讀寫(xiě)所占用的時(shí)間相比較，4種操作中網(wǎng)絡(luò)傳輸時(shí)間（上傳、下載）占了響應(yīng)時(shí)間的絕大部分。進(jìn)一步分析響應(yīng)時(shí)間的組成，圖6(b)中給出了不包括網(wǎng)絡(luò)傳輸?shù)捻憫?yīng)時(shí)間組成。上傳、下載和修復(fù)3種操作中，修復(fù)磁盤(pán)讀寫(xiě)（灰色）都占了大部分，而編、解碼都在1 s內(nèi)完成。因?yàn)镕RC是非系統(tǒng)碼，所以其編碼、解碼時(shí)間要長(zhǎng)于系統(tǒng)碼的Reed-Solomon編碼，但2種編碼修復(fù)時(shí)間相差不大。

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

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

圖4 Ustor上傳/下載100 MB文件到單個(gè)云存儲(chǔ)服務(wù)或者多個(gè)云存儲(chǔ)服務(wù)的響應(yīng)時(shí)間和速度（圖中縮寫(xiě)S/D/A/K分別表示亞馬遜S3、Dropbox、阿里云和金山快盤(pán)）

圖5 Ustor上傳/下載100 MB文件到多個(gè)云存儲(chǔ)服務(wù)的響應(yīng)時(shí)間和速度

圖6 Ustor采用FRC編碼和RS編碼100 MB文件的響應(yīng)時(shí)間

圖6中，(4,2)-FRC和(4,3)-FRC是功能性修復(fù)再生碼(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 結(jié)束語(yǔ)

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

[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.