包 涵 王意潔

（并行與分布計(jì)算全國(guó)重點(diǎn)實(shí)驗(yàn)室（國(guó)防科技大學(xué)） 長(zhǎng)沙 410073）

（國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073）

近年來(lái)，云數(shù)據(jù)中心故障頻發(fā)，常導(dǎo)致其中數(shù)據(jù)長(zhǎng)時(shí)間不可訪問(wèn)[1-6].同時(shí)，云際計(jì)算技術(shù)的逐漸成熟使得部署跨云數(shù)據(jù)中心存儲(chǔ)系統(tǒng)更加便捷[7].因此，各機(jī)構(gòu)紛紛采用跨云數(shù)據(jù)中心多副本技術(shù)來(lái)實(shí)現(xiàn)重要數(shù)據(jù)的容災(zāi)存儲(chǔ)[8].

相較于跨云數(shù)據(jù)中心多副本技術(shù)，跨云數(shù)據(jù)中心糾刪碼技術(shù)具有更高的可靠性和更低的冗余度[9-12].然而，跨云數(shù)據(jù)中心糾刪碼技術(shù)要在生產(chǎn)系統(tǒng)中得到普遍運(yùn)用，還需滿足3 方面要求：

1）低跨云數(shù)據(jù)中心修復(fù)流量.糾刪碼技術(shù)在跨云數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中修復(fù)故障節(jié)點(diǎn)中的數(shù)據(jù)時(shí)，需跨云數(shù)據(jù)中心傳輸大量數(shù)據(jù)，即糾刪碼技術(shù)的跨云數(shù)據(jù)中心修復(fù)流量較大.由于云數(shù)據(jù)中心間帶寬往往遠(yuǎn)低于云數(shù)據(jù)中心內(nèi)帶寬，所以糾刪碼技術(shù)在跨云數(shù)據(jù)中心存儲(chǔ)系統(tǒng)中修復(fù)數(shù)據(jù)的時(shí)間較長(zhǎng)[13-15].因此，亟需降低糾刪碼的跨云數(shù)據(jù)中心修復(fù)流量.

2）高編碼參數(shù)適應(yīng)性.在生產(chǎn)中，用戶通常對(duì)存儲(chǔ)節(jié)點(diǎn)數(shù)n、冗余度n/k、容錯(cuò)度d和容災(zāi)度D等糾刪碼編碼參數(shù)具有多樣化需求.因此，有必要提高跨云數(shù)據(jù)中心糾刪碼的編碼參數(shù)適應(yīng)性.編碼參數(shù)為（n,k,d,D）的糾刪碼將每k個(gè)數(shù)據(jù)塊編碼為n個(gè)編碼塊，并將其分別存儲(chǔ)在位于多個(gè)云數(shù)據(jù)中心的n個(gè)存儲(chǔ)節(jié)點(diǎn)，且當(dāng)任意d-1個(gè)存儲(chǔ)節(jié)點(diǎn)或任意D個(gè)云數(shù)據(jù)中心故障時(shí)，其中存儲(chǔ)的編碼塊可由其他編碼塊修復(fù).

3）高糾刪碼構(gòu)造效率.因?yàn)榧m刪碼編解碼數(shù)據(jù)的過(guò)程與存儲(chǔ)系統(tǒng)的讀寫過(guò)程深度耦合，所以開發(fā)和部署存儲(chǔ)系統(tǒng)前需先完成糾刪碼的構(gòu)造，因而用戶通常對(duì)糾刪碼構(gòu)造用時(shí)較為敏感.因此，有必要提高跨云數(shù)據(jù)中心糾刪碼的構(gòu)造效率.

現(xiàn)有工作提出的跨云數(shù)據(jù)中心糾刪碼[13-18]雖然能在一定程度上降低跨云數(shù)據(jù)中心修復(fù)流量，但普遍存在編碼參數(shù)適應(yīng)性較低的問(wèn)題，無(wú)法在滿足用戶對(duì)編碼參數(shù)的多樣化需求的同時(shí)有效降低跨云數(shù)據(jù)中心修復(fù)流量.此外，有工作提出了面向跨云數(shù)據(jù)中心存儲(chǔ)的自適應(yīng)糾刪碼ACIoT[19]，可求得不同編碼參數(shù)（n,k,d）下的跨云數(shù)據(jù)中心修復(fù)流量下限，并構(gòu)造能達(dá)到該下限的糾刪碼，即最優(yōu)碼.但是，ACIoT需要消耗較長(zhǎng)時(shí)間來(lái)檢驗(yàn)糾刪碼修復(fù)組分布方案與編碼參數(shù)（n,k,d）的匹配性，故其糾刪碼構(gòu)造效率較低.糾刪碼修復(fù)組分布方案E與指定編碼參數(shù)P相匹配是指存在一個(gè)編碼參數(shù)為P的糾刪碼的修復(fù)組分布方案為E.

綜上，現(xiàn)有工作無(wú)法兼顧編碼參數(shù)適應(yīng)性、糾刪碼跨云數(shù)據(jù)中心修復(fù)流量和糾刪碼構(gòu)造效率.本文提出一種低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的快速構(gòu)造方法（fast construction method of the erasure code with small cross-cloud data center repair traffic）FMEL，可在不同的編碼參數(shù)下快速構(gòu)造出具有較低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼.FMEL 的主要思想為：

首先，F(xiàn)MEL 將糾刪碼修復(fù)組分布方案及相應(yīng)的編碼參數(shù)（n,k,d,D）轉(zhuǎn)換為定長(zhǎng)特征向量，并將檢驗(yàn)糾刪碼修復(fù)組分布方案與指定編碼參數(shù)匹配性的問(wèn)題轉(zhuǎn)換為定長(zhǎng)特征向量的二分類問(wèn)題.其中，特征向量屬于正類表示糾刪碼修復(fù)組分布方案與相應(yīng)編碼參數(shù)相匹配.然后，F(xiàn)MEL 采用具有較高分類效率的支持向量機(jī)（support vector machine,SVM）來(lái)對(duì)各個(gè)特征向量進(jìn)行分類以實(shí)現(xiàn)其所對(duì)應(yīng)糾刪碼修復(fù)組分布方案的快速檢驗(yàn).在檢驗(yàn)的同時(shí)，F(xiàn)MEL 不斷采集新的訓(xùn)練集對(duì)SVM 分類器進(jìn)行增量更新，從而不斷提高其分類準(zhǔn)確率.隨后，F(xiàn)MEL 采用一種并行搜索方法來(lái)快速地從所有可通過(guò)SVM 檢驗(yàn)的糾刪碼修復(fù)組分布方案中選出跨云數(shù)據(jù)中心修復(fù)流量最小的一個(gè)方案.最后，F(xiàn)MEL 采用一種基于試錯(cuò)的糾刪碼修復(fù)組分布方案轉(zhuǎn)換方法將搜索到的糾刪碼修復(fù)組分布方案轉(zhuǎn)換為具有低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的生成矩陣.

在跨云數(shù)據(jù)中心環(huán)境中的實(shí)驗(yàn)表明，F(xiàn)MEL 在大部分編碼參數(shù)下可構(gòu)造出能達(dá)到平均跨云數(shù)據(jù)中心修復(fù)流量下限的最優(yōu)碼，且其構(gòu)造糾刪碼的時(shí)間僅為現(xiàn)有工作構(gòu)造最優(yōu)碼時(shí)間的11%.

1 相關(guān)工作

1.1 單云數(shù)據(jù)中心糾刪碼

現(xiàn)有工作提出了2 類低修復(fù)流量糾刪碼——再生碼和局部性碼.再生碼通過(guò)降低新生節(jié)點(diǎn)從各提供者節(jié)點(diǎn)里的編碼塊中讀取的數(shù)據(jù)量來(lái)減少修復(fù)流量，局部性碼通過(guò)降低各個(gè)編碼塊的提供者節(jié)點(diǎn)數(shù)量來(lái)減少修復(fù)流量.與再生碼相比，局部性碼更容易實(shí)現(xiàn)且靈活性更高，因而被廣泛地應(yīng)用于Amazon AWS[20]，Microsoft WAS[21]，F(xiàn)acebook HDFS-RAID[22]等生產(chǎn)系統(tǒng)中.特別地，Shahabinejad 等人[23]提出了一種可達(dá)到平均修復(fù)流量下限的糾刪碼ACAL.

雖然現(xiàn)有單云數(shù)據(jù)中心糾刪碼能夠降低平均修復(fù)流量，但是跨云數(shù)據(jù)中心修復(fù)流量并不與修復(fù)流量正相關(guān).因此，這些糾刪碼在跨云數(shù)據(jù)中心環(huán)境下不能充分降低跨云數(shù)據(jù)中心修復(fù)流量.

1.2 跨云數(shù)據(jù)中心糾刪碼

Yu 等人[13]提出了一種跨域容錯(cuò)糾刪碼DFC，其基本思想是在傳統(tǒng)的RS 碼的基礎(chǔ)上引入局部校驗(yàn)塊，首先使用RS 碼將k個(gè)數(shù)據(jù)塊編碼為w個(gè)編碼塊并在N個(gè)云數(shù)據(jù)中心中各存儲(chǔ)w/N(w/N≤w-k)個(gè)數(shù)據(jù)塊.由于RS 碼可以保證在這w個(gè)編碼塊中的任意w-k個(gè)編碼塊失效時(shí)重構(gòu)原始數(shù)據(jù)，所以在任意一個(gè)云數(shù)據(jù)中心故障時(shí)，仍可以通過(guò)其他云數(shù)據(jù)中心里的w-w/N(w-w/N≥k)個(gè)編碼塊恢復(fù)出原始數(shù)據(jù).然后，DFC 為每個(gè)機(jī)架存放的編碼塊生成局部校驗(yàn)塊，使得在任意一個(gè)編碼塊失效時(shí)，可以使用機(jī)架內(nèi)的編碼塊和局部校驗(yàn)塊對(duì)其進(jìn)行修復(fù).因此，DFC 的跨云數(shù)據(jù)中心修復(fù)流量較小.但是，DFC 對(duì)編碼參數(shù)具有嚴(yán)格的限制，要求n-k-d+1≥N.

Caneleo 等人[14]提出了一種多倍異或碼MXOR，其基本思想是將數(shù)據(jù)塊分為2 行k/2 列，而后通過(guò)異或計(jì)算分別求得各行各列的局部校驗(yàn)塊，然后將所有編碼塊和局部校驗(yàn)塊按行分散到各云數(shù)據(jù)中心.當(dāng)單個(gè)編碼塊失效時(shí)，MXOR 可通過(guò)對(duì)云數(shù)據(jù)中心內(nèi)部的其他編碼塊和局部校驗(yàn)塊進(jìn)行異或計(jì)算對(duì)其進(jìn)行修復(fù)，因此MXOR 的跨云數(shù)據(jù)中心修復(fù)流量較小.但是，MXOR 對(duì)編碼參數(shù)具有嚴(yán)格的限制，要求n/k≥2.4且d≤4.

Chen 等人[15-16]和Hu 等人[17]分別提出FMSR 碼和DRC 碼均能有效降低跨云數(shù)據(jù)中心修復(fù)流量.然而，F(xiàn)MSR 和DRC 均對(duì)編碼參數(shù)有嚴(yán)格的限制，F(xiàn)MSR 要求n-k=2，而DRC 碼要求n,k,N（云數(shù)據(jù)中心數(shù)）至少滿足2 個(gè)條件中的1 個(gè)：1）n=3z,k=2z,N=3（z為正整數(shù)）；2）N=n/（n-k）.

雖然上述糾刪碼均能在一定程度上降低跨云數(shù)據(jù)中心修復(fù)流量，但它們普遍存在編碼參數(shù)適應(yīng)性較差的問(wèn)題，無(wú)法在滿足用戶對(duì)編碼參數(shù)的多樣化需求的同時(shí)有效降低跨云數(shù)據(jù)中心修復(fù)流量.為此，有工作[19]提出了面向跨云數(shù)據(jù)中心存儲(chǔ)的自適應(yīng)糾刪碼ACIoT，可求得不同編碼參數(shù)（n,k,d）下的最小跨云數(shù)據(jù)中心修復(fù)流量碼，即最優(yōu)碼.具體而言，ACIoT 首先定義了糾刪碼的修復(fù)組分布方案，該方案決定了糾刪碼的跨云數(shù)據(jù)中心修復(fù)流量.然后，ACIoT可枚舉指定編碼參數(shù)（n,k）下的糾刪碼修復(fù)組分布方案，并檢驗(yàn)它們是否與指定編碼參數(shù)（n,k,d）相匹配.最后，ACIoT 可從所有與編碼參數(shù)（n,k,d）相匹配的糾刪碼修復(fù)組分布方案中找出具有最小跨云數(shù)據(jù)中心修復(fù)流量的1 個(gè)并將其轉(zhuǎn)換為最優(yōu)碼生成矩陣.然而，ACIoT 忽略了容災(zāi)度對(duì)跨云數(shù)據(jù)中心修復(fù)流量下限的影響.此外，因ACIoT 需要消耗較長(zhǎng)時(shí)間來(lái)檢驗(yàn)糾刪碼修復(fù)組分布方案與編碼參數(shù)（n,k,d）的匹配性，故其糾刪碼構(gòu)造用時(shí)較長(zhǎng).

綜上，現(xiàn)有的跨云數(shù)據(jù)中心糾刪碼無(wú)法同時(shí)滿足低跨云數(shù)據(jù)中心修復(fù)流量、高編碼參數(shù)適應(yīng)性和高糾刪碼構(gòu)造效率，這嚴(yán)重限制了其在生產(chǎn)系統(tǒng)中的運(yùn)用.

除以上聚焦于數(shù)據(jù)修復(fù)的工作外，Saeed 等人[24]還考慮到RS 碼等糾刪碼技術(shù)在讀取數(shù)據(jù)時(shí)具備多種讀取方案，可以通過(guò)訪問(wèn)不同云數(shù)據(jù)中心的節(jié)點(diǎn)來(lái)重構(gòu)用戶數(shù)據(jù).因此，他們提出了距離優(yōu)先讀取策略和負(fù)載均衡優(yōu)先讀取策略，分別用于對(duì)讀取過(guò)程的網(wǎng)絡(luò)開銷和各存儲(chǔ)節(jié)點(diǎn)的負(fù)載進(jìn)行優(yōu)化.同時(shí)，他們對(duì)用戶讀取數(shù)據(jù)時(shí)的網(wǎng)絡(luò)開銷和各節(jié)點(diǎn)的負(fù)載進(jìn)行了綜合建模，得到了一個(gè)綜合考慮2 方面因素的開銷模型，并基于此模型提出了跨數(shù)據(jù)中心糾刪碼數(shù)據(jù)讀取節(jié)點(diǎn)選擇算法Sandooq，能夠有效降低數(shù)據(jù)讀取的綜合開銷.此外，我們?cè)谥暗墓ぷ髦刑岢隽艘环N跨云數(shù)據(jù)中心糾刪碼增量寫入方法[25]和一種基于生成矩陣變換的跨云數(shù)據(jù)中心糾刪碼寫入方法[26]，可分別通過(guò)提高編碼并行度和降低跨云數(shù)據(jù)中心寫入流量來(lái)提高寫入效率.

2 重要定義及定理

定義1.生成矩陣.跨云數(shù)據(jù)中心糾刪碼技術(shù)將用戶數(shù)據(jù)劃分為若干數(shù)據(jù)塊，并將每k個(gè)數(shù)據(jù)塊（記為xt,t∈[1,k]）編碼為n個(gè)編碼塊（記為yi,i∈[1,n]），這n個(gè)編碼塊被稱為一個(gè)條帶，編碼過(guò)程如式（1）所示，其中G為糾刪碼的生成矩陣.生成矩陣G的秩必須為k,否則GT(z1,…,zk)T=(y1,…,yn)T沒(méi)有唯一解，即無(wú)法將一個(gè)條帶中的n個(gè)編碼塊解碼為原始數(shù)據(jù)塊.

定義 2.校驗(yàn)矩陣. 如果為G[z1,…,zk]T=0的基礎(chǔ)解系，那么H=為對(duì)應(yīng)于生成矩陣G的校驗(yàn)矩陣.因?yàn)镚的秩為k，所以H的秩為n-k.

定義3.修復(fù)組.由生成矩陣G與校驗(yàn)矩陣H的定義有，GHT=0，故(y1,…,yn)HT=(x1,…,xk)GHT=0.因此，每個(gè)編碼塊都可以通過(guò)對(duì)其他若干個(gè)編碼塊進(jìn)行線性計(jì)算重構(gòu).如果編碼塊yi可以通過(guò)對(duì)yi,1,yi,2,…,yi,r進(jìn)行線性計(jì)算重構(gòu)，那么{yi,yi,1,yi,2,…,yi,r}為yi的一個(gè)修復(fù)組（用于修復(fù)yi的存儲(chǔ)節(jié)點(diǎn)被稱為新生節(jié)點(diǎn)，存儲(chǔ)yi,1,yi,2…,yi,r的節(jié)點(diǎn)被稱為提供者節(jié)點(diǎn)）.一個(gè)編碼塊可能有多個(gè)修復(fù)組.此外，由于編碼塊之間的線性關(guān)系由生成矩陣G或校驗(yàn)矩陣H決定，所以編碼塊的修復(fù)組也是由生成矩陣G或校驗(yàn)矩陣H決定的.

定義4.編碼塊分布方案.一個(gè)條帶中的編碼塊所在的云數(shù)據(jù)中心的編號(hào)組成的集合為該條帶的編碼塊分布方案R={z1,z2,…,zn}，其中zi表示該條帶中第i個(gè)編碼塊位于第zi個(gè)云數(shù)據(jù)中心.

定義5.編碼塊修復(fù)組分布方案.設(shè)Ti,w為編碼塊yi的第w個(gè)修復(fù)組，如果Ti,w中的編碼塊分布于t個(gè)編號(hào)分別為z1,z2,…,zt的云數(shù)據(jù)中心中（這t個(gè)云數(shù)據(jù)中心分別記為，那么令Ri,w={z1,z2,…,zt}.設(shè)編碼塊yi共有Qi個(gè)修復(fù)組，記為Ti,1,Ti,2,…,Ti,Qi，且（q∈[1,Qi]），那么Ri,q為編碼塊yi的修復(fù)組分布方案.其中，表示Ri,w中含有的云數(shù)據(jù)中心編號(hào)個(gè)數(shù).

定義6.糾刪碼修復(fù)組分布方案.如果C1,C2,…,Cn分別為編碼塊y1,y2,…,yn的修復(fù)組分布方案，那么{C1,C2,…,Cn}為條帶{y1,y2,…,yn}的修復(fù)組分布方案.通常而言，糾刪碼的不同編碼條帶中的編碼塊在各個(gè)云數(shù)據(jù)中心間的分布相同.在此情況下，糾刪碼的各個(gè)條帶的修復(fù)組分布方案相同，因而條帶的修復(fù)組分布方案也被稱為糾刪碼修復(fù)組分布方案.

為了降低跨云數(shù)據(jù)中心修復(fù)流量，在基于糾刪碼技術(shù)的跨云數(shù)據(jù)中心存儲(chǔ)系統(tǒng)修復(fù)編碼塊時(shí)，含有提供者節(jié)點(diǎn)的云數(shù)據(jù)中心通常會(huì)先將其中的提供者節(jié)點(diǎn)的編碼塊合并為一個(gè)和各個(gè)編碼塊大小相同中間塊，然后再將中間塊發(fā)往新生節(jié)點(diǎn).此外，為了保持系統(tǒng)的容災(zāi)度和負(fù)載均衡性不變，失效編碼塊的新生節(jié)點(diǎn)通常和該失效編碼塊位于同一云數(shù)據(jù)中心.在此情況下，如果編碼塊yi的修復(fù)組分布方案為Ci且編碼塊大小為m，那么在修復(fù)yi時(shí)需要向其新生節(jié)點(diǎn)發(fā)送中間塊的云數(shù)據(jù)中心（含新生節(jié)點(diǎn)所在云數(shù)據(jù)中心）的個(gè)數(shù)為Ci中含有的云數(shù)據(jù)中心編號(hào)個(gè)數(shù) |Ci|，因而修復(fù)yi的最小跨云數(shù)據(jù)中心傳輸量為m（|Ci|-1）.所以，一個(gè)糾刪碼的修復(fù)組分布方案為E的糾刪碼的編碼條帶的平均跨云數(shù)據(jù)中心流量為其中，C為E中的編碼塊修復(fù)組分布方案，n為一個(gè)編碼條帶中的編碼塊數(shù).因此，糾刪碼的平均跨云數(shù)據(jù)中心修復(fù)流量由其修復(fù)組分布方案決定.

定義7.糾刪碼Tanner 圖[23].若一個(gè)編碼參數(shù)為（n,k,d,D）的糾刪碼CO的校驗(yàn)矩陣為H，那么該糾刪碼的Tanner 圖 T 為滿足3 個(gè)條件的二分圖：1) T的一個(gè)端點(diǎn)集包含n個(gè)變量端點(diǎn)（variable node,VN）；2)T的另一個(gè)端點(diǎn)集包含n-k個(gè)校驗(yàn)端點(diǎn)（check node,CN）；3）當(dāng)且僅當(dāng)H的第i行、第j列的元素不為0，T的第j個(gè)校驗(yàn)端點(diǎn)覆蓋其第i個(gè)變量端點(diǎn)，即 T中有一條以第j個(gè)校驗(yàn)端點(diǎn)和第i個(gè)變量端點(diǎn)為端點(diǎn)的邊.圖1 舉例說(shuō)明了糾刪碼的Tanner 圖與糾刪碼校驗(yàn)矩陣H間的關(guān)系.

Fig.1 Erasure code’s Tanner graph圖1 糾刪碼Tanner 圖

圖2 舉例說(shuō)明了糾刪碼Tanner 圖與編碼塊和修復(fù)組之間的關(guān)系.糾刪碼的一個(gè)編碼條帶中的6 個(gè)編碼塊y1,y2,…,y6分別對(duì)應(yīng)著該糾刪碼Tanner 圖的6 個(gè)變量端點(diǎn)VN1,VN2,…,VN6.覆蓋糾刪碼Tanner 圖中的第1,4,5,6 個(gè)變量端點(diǎn)VN1,VN4,VN5,VN6的校驗(yàn)端點(diǎn)CN1對(duì)應(yīng)的修復(fù)組為{y1,y4,y5,y6}，該修復(fù)組內(nèi)各編碼塊之間的線性關(guān)系為y1+y4+y5+y6=0.同理，校驗(yàn)端點(diǎn)CN2對(duì)應(yīng)的修復(fù)組為{y2,y4,y5,y6}，該修復(fù)組內(nèi)各編碼塊的線性關(guān)系為y2+y4+2y5+4y6=0；校驗(yàn)端點(diǎn)CN3對(duì)應(yīng)的修復(fù)組為{y3,y4,y5,y6}，該修復(fù)組內(nèi)各編碼塊的線性關(guān)系為y3+y4+3y5+9y6=0.

Fig.2 The relationship between the erasure code’s Tanner graph,coded blocks,and the repair groups圖2 糾刪碼Tanner 圖與編碼塊和修復(fù)組之間的關(guān)系

本文涉及的常用符號(hào)及其含義如表1 所示：

定理2.假設(shè)H(n-k)×n為糾刪碼CO的校驗(yàn)矩陣.當(dāng)且僅當(dāng)由H的第z1～zc列組成的矩陣H1的秩為c，CO能夠在其各條帶中的第l1～lc個(gè)編碼塊同時(shí)失效時(shí)修復(fù)這些失效編碼塊.

證明.從糾刪碼的校驗(yàn)方程(y1,…,yn)HT=0中得到的以為未知數(shù)的方程組如式（2）所示：

因?yàn)槭剑?）中的最大線性無(wú)關(guān)方程數(shù)等于H1的秩，所以，當(dāng)且僅當(dāng)H1的秩為c時(shí)，式（2）有唯一解.因此，當(dāng)且僅當(dāng)H1的秩為c時(shí)，能夠被同條帶中的其他編碼塊修復(fù).證畢.

定理3.假設(shè)糾刪碼的編碼塊分布方案R已確定，即任意條帶中的n個(gè)編碼塊被分配給N個(gè)云數(shù)據(jù)中心，亦即糾刪碼Tanner 圖 T的n個(gè)變量端點(diǎn)和相應(yīng)的校驗(yàn)矩陣H的n個(gè)列被分配給了N個(gè)云數(shù)據(jù)中心（根據(jù)定義7，糾刪碼Tanner 圖 T的n個(gè)變量端點(diǎn)分別對(duì)應(yīng)于校驗(yàn)矩陣H的n個(gè)列和任意條帶中的n個(gè)編碼塊）.在此假設(shè)下，T 匹配于編碼參數(shù)（n,k,d,D）的一個(gè)充要條件是：T有n-k個(gè)校驗(yàn)端點(diǎn)、n個(gè)變量端點(diǎn)（子條件1）；T的任意 γ個(gè)校驗(yàn)端點(diǎn)至少覆蓋γ+k個(gè)變量端點(diǎn)，其中，γ ∈[J,n-k]且J=n-k-d+2（子條件2）；T的最大匹配數(shù)不小于n-k（子條件3）；任意含有B(B≤n-k)個(gè)變量端點(diǎn)的D個(gè)云數(shù)據(jù)中心中的任意β(β∈[1,B])個(gè)變量端點(diǎn)至少覆蓋個(gè)校驗(yàn)端點(diǎn)（子條件4）.

證明.1）必要性證明.

①子條件1 的必要性.

根據(jù)定義7，若 T匹配于編碼參數(shù)（n,k,d,D），那么其對(duì)應(yīng)的糾刪碼的生成矩陣一定有k行n列.根據(jù)糾刪碼Tanner 圖與糾刪碼的生成矩陣的關(guān)系，T一定有n-k個(gè)校驗(yàn)端點(diǎn)、n個(gè)變量端點(diǎn)，即 T一定滿足子條件1.

② 子條件2 的必要性.

如果在 T中存在 γ個(gè)校驗(yàn)端點(diǎn)（不妨設(shè)為CN1,CN2,…,CNγ）僅覆蓋了w個(gè)變量端點(diǎn)（不妨設(shè)為VN1,VN2,…,VNw）且w≤γ+k-1，那么根據(jù)定義7，對(duì)應(yīng)于T的校驗(yàn)矩陣如式（3）所示.其中，0γ×(n-w)為全零矩陣.

（i）如果n-w≤d-1，從糾刪碼的校驗(yàn)方程(y1,…,yn)HT=0中只能得到以yw+1,yw+2,…,yn為未知數(shù)的線性方程組：

因?yàn)閚-w≤d-1，所以n-w≥n-(γ+k-1)=n-kγ+1.所以，式（4）中的具有n-w個(gè)未知數(shù)和n-k-γ個(gè)方程的方程組無(wú)唯一解.因此，yw+1,yw+2,…,yn不能由同條帶中的其他編碼塊修復(fù).因此，T不匹配于編碼參數(shù)d.

（ii）如果n-w＞d-1，從糾刪碼的校驗(yàn)方程[y1,…,yn]HT=0中只能得到以yn-d+2,yn-d+3,…,yn為未知數(shù)的線性方程組：

因?yàn)棣谩蔥J,n-k]且J=n-k-d+2，所以n-k-γ≤nk-(n-k-d+2)=d-2.所以，式（5）中的具有d-1個(gè)未知數(shù)和n-k-γ個(gè)方程的方程組無(wú)唯一解.因此，yn-d+2,yn-d+3,…,yn不能由同條帶的其他編碼塊修復(fù).因此，T不匹配于編碼參數(shù)d.

綜上，如果 T匹配于編碼參數(shù)（n,k,d,D），T的任意 γ個(gè)校驗(yàn)端點(diǎn)至少覆蓋γ+k個(gè)變量端點(diǎn)，其中γ∈[J,n-k]且J=n-k-d+2.

③子條件3 的必要性證明.

假設(shè) T的最大匹配數(shù)為b＜n-k且H(含有n-k行、n列）為任意一個(gè)對(duì)應(yīng)于 T的校驗(yàn)矩陣，那么由定理1 有，H的每個(gè)n-k行、n-k列的子矩陣均不滿秩.因此，H的秩不為n-k.因此，根據(jù)校驗(yàn)矩陣的定義，H不可能是一個(gè)（n,k,d,D）糾刪碼的校驗(yàn)矩陣.因此，T不匹配于（n,k,d,D）.因此，若 T匹配于編碼參數(shù)（n,k,d,D），T 的最大匹配數(shù)不小于n-k.

④ 子條件4 的必要性證明.

如果存在D個(gè)云數(shù)據(jù)中心（不妨設(shè)為），其中的 β個(gè)變量端點(diǎn)（不妨設(shè)為VN1,VN2,…,VNβ)只覆蓋了c≤β-1個(gè)校驗(yàn)端點(diǎn)（不妨設(shè)為CN1,CN2,…,CNc)，那么根據(jù)定義7，對(duì)應(yīng)于 T的校驗(yàn)矩陣H中只有c個(gè)行中的第1～ β列中存在非零元素.因此，從糾刪碼的校驗(yàn)方程(y1,…,yn)HT=0中只能得到以y1,y2,…,yβ為變量的線性方程組:

因?yàn)槭剑?）中的 β元方程組的最大線性無(wú)關(guān)方程數(shù)為c(c＜β)，所以該方程組沒(méi)有唯一解.因此，對(duì)應(yīng)于 T 的糾刪碼的任意編碼條帶{y1,y2,…,yn}中的y1,y2,…,yβ不能被同條帶的其他編碼塊修復(fù) (T對(duì)應(yīng)的糾刪碼不能容忍同時(shí)失效）.因此，T不匹配于編碼參數(shù)（n,k,d,D）.

綜上，若 T匹配于編碼參數(shù)（n,k,d,D），任意含有B(B≤n-k)個(gè)變量端點(diǎn)的D個(gè)云數(shù)據(jù)中心中的任意β(β∈[1,B])個(gè)變量端點(diǎn)至少覆蓋 β個(gè)校驗(yàn)端點(diǎn).

2）充分性證明.

證明.假設(shè)糾刪碼Tanner 圖 T 符合定理3 中的充要條件，那么可按5 個(gè)步驟構(gòu)造出一個(gè)糾刪碼Tanner 圖為 T的匹配于編碼參數(shù)（n,k,d,D）的糾刪碼的生成矩陣，即 T匹配于編碼參數(shù)（n,k,d,D）.

①求得 T 的最大匹配.因?yàn)?T 滿足定理3 中的充要條件的子條件3，所以其最大匹配包含n-k個(gè)變量端點(diǎn).如果 T 的最大匹配包含，那么令H1為由H的第l1,l2,…,ln-k列組成的矩陣.由于H1的行數(shù)和列數(shù)均為n-k，所以其為方陣.然后，我們將H1加入集合LS.

② 求得H的所有的包含n-k行、d-1 列的子矩陣的集合SM1以及H的所有的包含其對(duì)應(yīng)于任意D個(gè)云數(shù)據(jù)中心的列的子矩陣組成的集合SM2.

③根據(jù)糾刪碼Tanner 圖的定義，SM1和SM2中每個(gè)矩陣都對(duì)應(yīng)于 T的一個(gè)子圖.因此，我們求得對(duì)應(yīng)于SM1和SM2中每個(gè)矩陣所對(duì)應(yīng)的 T的子圖的最大匹配.而后，對(duì)于SM1和SM2中的每個(gè)矩陣Z，如果其對(duì)應(yīng)的 T的子圖的最大匹配包含則將其第l1,l2,…,lc行組成的子矩陣加入集合LS.

可以證明，如果SM1或SM2中的某個(gè)矩陣有q列，那么其對(duì)應(yīng)的 T的子圖的最大匹配一定為q（即LS中的矩陣均為方陣），證明過(guò)程為：

首先，證明如果SM1中的某個(gè)矩陣有q列，那么它的最大匹配數(shù)一定為q.由于SM1的矩陣的列數(shù)恒為d-1，因此只需要證明SM1中的矩陣對(duì)應(yīng)的 T的子圖的最大匹配數(shù)恒為d-1.

（i）令?=n-k-γ+1(因?yàn)棣谩蔥J,n-k]且J=n-kd+2，所以?∈[1,d-1])，可以證明 T中任意 ?個(gè)變量端點(diǎn)至少覆蓋 ?個(gè)校驗(yàn)端點(diǎn)：如果存在 ?個(gè)變量端點(diǎn)僅僅覆蓋u≤?-1個(gè)校驗(yàn)端點(diǎn)，那么剩下的n-k-u≥γ個(gè)校驗(yàn)端點(diǎn)最多覆蓋n-?=k+γ-1個(gè)變量端點(diǎn)，這與定理3 中的充要條件的子條件2（任意 γ個(gè)校驗(yàn)端點(diǎn)至少覆蓋γ+k個(gè)變量端點(diǎn)）相矛盾.因此，任意 ?個(gè)變量端點(diǎn)至少覆蓋 ?個(gè)校驗(yàn)端點(diǎn).

（ii）根據(jù)Hall 定理[27]，在 T 的任意含有d-1 個(gè)變量端點(diǎn)、n-k個(gè)校驗(yàn)端點(diǎn)（d-1＜n-k）的子圖存在完全匹配的充要條件是該子圖中任意 ?個(gè)變量端點(diǎn)至少覆蓋 ?個(gè)校驗(yàn)端點(diǎn)（?∈[1,d-1]）.由（i）有，T中任意?個(gè)變量端點(diǎn)至少覆蓋 ?個(gè)校驗(yàn)，所以 T的任意含有d-1 個(gè)變量端點(diǎn)、n-k個(gè)校驗(yàn)端點(diǎn)（d-1＜n-k）的子圖存在完全匹配，即 T中任意d-1 個(gè)變量端點(diǎn)可以一對(duì)一地覆蓋d-1 個(gè)校驗(yàn)端點(diǎn).

（iii）假設(shè)Z為SM1中的任意矩陣且Z包含H的第l1,l2,…,ld-1列.由（ii）有，一定一對(duì)一地覆蓋d-1個(gè)校驗(yàn)端點(diǎn)（不妨設(shè)為CN1,CN2,…,CNd-1).因此，為對(duì)應(yīng)于Z的 T的子圖的最大匹配.因此SM1中任意矩陣對(duì)應(yīng)的 T的子圖的最大匹配數(shù)為d-1.

然后，證明如果SM2中的某個(gè)矩陣有B列，那么它的最大匹配數(shù)一定為B.

（i）不妨假設(shè) T中對(duì)應(yīng)于任意D個(gè)云數(shù)據(jù)中心的任意B個(gè)變量端點(diǎn)為VN1,VN2,…,VNB.根據(jù)Hall 定理[27]，T的由其VN1,VN2,…,VNB和n-k個(gè)校驗(yàn)端點(diǎn)組成的子圖存在完全匹配的充要條件是該子圖中任意β個(gè)變量端點(diǎn)至少覆蓋 β個(gè)校驗(yàn)端點(diǎn)（β∈[1,B]）.因?yàn)門滿足定理3 中的充要條件的子條件4，即任意含有B(B≤nk)個(gè)變量端點(diǎn)的D個(gè)云數(shù)據(jù)中心中的任意β(β∈[1,B])個(gè)變量端點(diǎn)至少覆蓋 β個(gè)校驗(yàn)端點(diǎn)，所以T的由其VN1,…,VNB和n-k個(gè)校驗(yàn)端點(diǎn)組成的子圖存在完全匹配，即 T中對(duì)應(yīng)于任意D個(gè)云數(shù)據(jù)中心的任意B個(gè)變量端點(diǎn)一定可以一對(duì)一地覆蓋B個(gè)校驗(yàn)端點(diǎn).

定理4.糾刪碼修復(fù)組分布方案E匹配于編碼參數(shù)（n,k,d,D）的一個(gè)必要條件為：設(shè)ST為E中所有編碼塊修復(fù)組分布方案的無(wú)重復(fù)集合，對(duì)于任意D個(gè)共含有B個(gè)編碼塊的云數(shù)據(jù)中心（不妨設(shè)這些云數(shù)據(jù)中心的編號(hào)為z1,z2,…,zD，即設(shè)這些云數(shù)據(jù)中心為），ST中僅含有不多于n-k-B個(gè)不包含這些云數(shù)據(jù)中心的編號(hào)集合{z1,z2,…,zD}中任意元素的編碼塊修復(fù)組分布方案.

證明.根據(jù)定義6，如果ST中含有超過(guò)n-k-B個(gè)不包含{z1,z2,…,zD}中任意元素的編碼塊修復(fù)組分布方案，那么相應(yīng)的糾刪碼有超過(guò)n-k-B個(gè)不含有中編碼塊的修復(fù)組.因此，根據(jù)定義7，在任何對(duì)應(yīng)于E的糾刪碼Tanner 圖（不妨設(shè)為T)中，一定有超過(guò)n-k-B個(gè)校驗(yàn)端點(diǎn)沒(méi)有覆蓋對(duì)應(yīng)于中編碼塊的變量端點(diǎn).因此，在T中，對(duì)應(yīng)于中編碼塊的變量端點(diǎn)（不妨設(shè)為)覆蓋的校驗(yàn)端點(diǎn)少于B個(gè).因此，根據(jù)定義7，任意對(duì)應(yīng)于 T的校驗(yàn)矩陣H中的第l1,l2,…,lB列組成的矩陣H1最多只有B-1 個(gè)非零行.因此，H1的秩小于B.因此，根據(jù)定理2，校驗(yàn)矩陣為H的糾刪碼不能容忍任意編碼條帶中的第l1,l2,…,lB個(gè)編碼塊失效，即不能容忍同時(shí)失效.因此，糾刪碼修復(fù)組分布方案E不匹配于編碼參數(shù)（n,k,d,D）.證畢.

定理5.所有匹配于指定編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案的平均跨數(shù)據(jù)中心修復(fù)流量的最小值為編碼參數(shù)（n,k,d,D）下的糾刪碼的平均跨數(shù)據(jù)中心修復(fù)流量下限.

證明.令所有匹配于指定編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案的平均跨數(shù)據(jù)中心修復(fù)流量的最小值為T.假設(shè)存在一個(gè)滿足編碼參數(shù)（n,k,d,D）且平均跨數(shù)據(jù)中心修復(fù)流量小于T的糾刪碼（不妨設(shè)為CO），那么CO的修復(fù)組分布方案的平均跨數(shù)據(jù)中心修復(fù)流量小于T.因?yàn)樗衅ヅ溆谥付ň幋a參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案的平均跨數(shù)據(jù)中心修復(fù)流量的最小值為T，所以不匹配于編碼參數(shù)（n,k,d,D），因而不存在一個(gè)滿足編碼參數(shù)（n,k,d,D）的糾刪碼的修復(fù)組分布方案為，這與CO的修復(fù)組分布方案為相矛盾.因此，不存在一個(gè)匹配于編碼參數(shù)（n,k,d,D）且平均跨數(shù)據(jù)中心修復(fù)流量小于T的糾刪碼，即T為編碼參數(shù)（n,k,d,D）下的糾刪碼的平均跨數(shù)據(jù)中心修復(fù)流量下限.證畢.

3 低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的快速構(gòu)造方法FMEL

本節(jié)提出了一種低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的快速構(gòu)造方法FMEL（如圖3 所示），可在不同編碼參數(shù)下快速求得具有低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼.

Fig.3 The structure of FMEL圖3 FMEL 的結(jié)構(gòu)

具體而言，基于第2 節(jié)推導(dǎo)出的相關(guān)定理，本節(jié)首先得出糾刪碼修復(fù)組分布方案匹配指定編碼參數(shù)（n,k,d,D）的條件，并以此為依據(jù)提出了一種基于SVM 的糾刪碼修復(fù)組分布方案檢驗(yàn)算法（erasure code repair group distribution scheme verification algorithm based on SVM）EVA，可對(duì)糾刪碼修復(fù)組分布方案與編碼參數(shù)匹配性進(jìn)行快速檢驗(yàn).

然后，本節(jié)提出了一種具有近似最小跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼修復(fù)組分布方案的并行搜索算法（distributed search algorithm of the erasure code repair group distribution scheme with the approximate minimum cross-cloud data center repair traffic）DSAOE，可從所有通過(guò)EVA 檢驗(yàn)的糾刪碼修復(fù)組分布方案中選出平均跨云數(shù)據(jù)中心修復(fù)流量較小的一個(gè)糾刪碼修復(fù)組分布方案.

最后，本節(jié)提出一種糾刪碼修復(fù)組分布方案轉(zhuǎn)換算法（erasure code repair group distribution scheme transformation algorithm）EST，可將DSAOE 搜索到的修復(fù)組分布方案轉(zhuǎn)換為具有低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的生成矩陣.

3.1 糾刪碼修復(fù)組分布方案匹配于指定（n,k,d,D）的條件

1）糾刪碼修復(fù)組分布方案匹配于指定（n,k,d,D）的充要條件

糾刪碼修復(fù)組分布方案是由糾刪碼的編碼塊的修復(fù)組和位置決定.如果將一個(gè)糾刪碼Tanner 圖的各個(gè)變量端點(diǎn)分配給不同的云數(shù)據(jù)中心，那么糾刪碼Tanner 圖可以同時(shí)反映相應(yīng)糾刪碼的編碼塊的修復(fù)組及位置.因此，每個(gè)糾刪碼Tanner 圖對(duì)應(yīng)一個(gè)糾刪碼修復(fù)組分布方案.因?yàn)槎鄠€(gè)糾刪碼Tanner 圖可能對(duì)應(yīng)同一個(gè)糾刪碼修復(fù)組分布方案，所以每個(gè)糾刪碼修復(fù)組分布方案通常對(duì)應(yīng)多個(gè)糾刪碼Tanner 圖.糾刪碼Tanner 圖 T匹配于編碼參數(shù)（n,k,d,D）是指存在一個(gè)Tanner 圖為 T的糾刪碼的編碼參數(shù)為（n,k,d,D）.因此，若一個(gè)糾刪碼修復(fù)組分布方案所對(duì)應(yīng)的糾刪碼Tanner 圖中，有不少于一個(gè)糾刪碼Tanner 圖匹配于編碼參數(shù)（n,k,d,D），則該方案匹配于編碼參數(shù)（n,k,d,D），反之則該方案不匹配于編碼參數(shù)（n,k,d,D）.即糾刪碼修復(fù)組分布方案匹配于編碼參數(shù)（n,k,d,D）的充要條件是至少存在一個(gè)與之對(duì)應(yīng)的Tanner 圖滿足定理3 中的子條件1～4.

2）糾刪碼修復(fù)組分布方案匹配于指定（n,k,d,D）的必要條件

糾刪碼修復(fù)組分布方案匹配于編碼參數(shù)（n,k,d,D）的一個(gè)必要條件如定理4 所示.

3.2 EVA 算法

基于3.1 節(jié)得出的糾刪碼修復(fù)組分布方案匹配指定編碼參數(shù)（n,k,d,D）的條件，首先，EVA 把糾刪碼修復(fù)組分布方案和對(duì)應(yīng)的編碼參數(shù)轉(zhuǎn)換為便于分類算法高效處理的定長(zhǎng)特征向量，轉(zhuǎn)換過(guò)程能夠保留判斷糾刪碼修復(fù)組分布方案是否匹配于指定編碼參數(shù)所需的全部信息，因而能夠保證分類的準(zhǔn)確性.此外，EVA 使用一個(gè)SVM 來(lái)對(duì)定長(zhǎng)特征向量進(jìn)行分類以達(dá)到快速檢驗(yàn)糾刪碼修復(fù)組分布方案是否匹配于對(duì)應(yīng)的編碼參數(shù)的目的.在分類過(guò)程中，EVA 可以持續(xù)收集更多帶標(biāo)簽定長(zhǎng)特征向量，并使用這些定長(zhǎng)特征向量對(duì)SVM 分類器進(jìn)行增量更新，從而達(dá)到不斷提高分類準(zhǔn)確率的目的.EVA 使用3.1 節(jié)推導(dǎo)出的糾刪碼修復(fù)組分布方案匹配于指定編碼參數(shù)（n,k,d,D）的條件為定長(zhǎng)特征向量打標(biāo)簽，以得到SVM 分類器的初始訓(xùn)練數(shù)據(jù)集和增量更新數(shù)據(jù)集.

3.2.1 特征向量構(gòu)造

基于SVM 的EVA 對(duì)糾刪碼修復(fù)組分布方案進(jìn)行轉(zhuǎn)換：

首先，由定義6 有，如果可用云數(shù)據(jù)中心的數(shù)目為N，那么編碼塊的修復(fù)組分布方案C一共有2N-1個(gè)可能的取值.因此，EVA 將把這 2N-1個(gè)可能的取值一一映射為1,2,…,2N-1，映射函數(shù)如式（9）所示.

然后，對(duì)于每個(gè)云數(shù)據(jù)中心，EVA 將統(tǒng)計(jì)出糾刪碼修復(fù)組分布方案中對(duì)應(yīng)于該云數(shù)據(jù)中心中的編碼塊的修復(fù)組分布方案的映射值中1,2,…,2N-1出現(xiàn)的次數(shù)，從而得到了一個(gè)長(zhǎng)度為N(2N-1)的定長(zhǎng)特征向量X'，該向量中的第a×b個(gè)元素的值為c表示第a個(gè)云數(shù)據(jù)中心中有c個(gè)編碼塊的修復(fù)組分布方案的映射值為b.例如，如圖4 所示，如果糾刪碼修復(fù)組分布方案為{{1},{1,2},{1,2},{2,3},{1,2,3},{1,2,3}}、云數(shù)據(jù)中心總數(shù)為3、編碼條帶中的第1,2 個(gè)編碼塊位于第1個(gè)云數(shù)據(jù)中心、編碼條帶中的第3,4 個(gè)編碼塊位于第2 個(gè)云數(shù)據(jù)中心、編碼條帶中的第5,6 個(gè)編碼塊位于第3 個(gè)云數(shù)據(jù)中心，那么其中各個(gè)編碼塊修復(fù)組分布方案的映射值分別為1,3,3,6,7,7，因而相應(yīng)的X'=(1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,2).

因?yàn)閄'中含有各個(gè)云數(shù)據(jù)中心中的對(duì)應(yīng)于不同修復(fù)組分布方案的編碼塊數(shù)目，所以使用X'可以恢復(fù)出各個(gè)云數(shù)據(jù)中心中的編碼塊的修復(fù)組分布方案的無(wú)序集合.例如，從X'=(1,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,2)的第3× 7 個(gè)元素為2 可以推導(dǎo)出第3 個(gè)云數(shù)據(jù)中心中有2 個(gè)編碼塊的修復(fù)組分布方案的映射值為7，即它們的修復(fù)組分布方案為{1,2,3}.因此，和原始的糾刪碼修復(fù)組分布方案相比，X'中僅僅丟失了各個(gè)編碼塊在各云數(shù)據(jù)中心內(nèi)的順序信息.因?yàn)楦鱾€(gè)編碼塊在各云數(shù)據(jù)中心內(nèi)的順序并不影響糾刪碼的冗余度、容錯(cuò)度和容災(zāi)度，因此糾刪碼修復(fù)組分布方案轉(zhuǎn)換過(guò)程沒(méi)有丟失判斷一個(gè)其是否匹配于編碼參數(shù)（n,k,d,D）所需的有效信息.

在將糾刪碼修復(fù)組分布方案轉(zhuǎn)換為一個(gè)數(shù)值型的定長(zhǎng)特征向量X'后，EVA 將n,k,d,D追加到X'即可得到用于表示糾刪碼修復(fù)組分布方案及其對(duì)應(yīng)編碼參數(shù)（n,k,d,D）的特征向量X，其長(zhǎng)度恒為N(2N-1)+4.

3.2.2 基于SVM 的特征向量分類

由于匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案之間以及不匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案之間均有一定的相似性，所以匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量之間以及不匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量之間存在一定的相似性.因此，可以采用有監(jiān)督學(xué)習(xí)算法[28-29]來(lái)對(duì)糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量進(jìn)行分類：使用一些已知匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量和已知不匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量作為訓(xùn)練集來(lái)訓(xùn)練一個(gè)分類器.分類器會(huì)判斷新的糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量是否和已知匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量相似，如果相似則判斷其匹配于編碼參數(shù)（n,k,d,D），反之則判斷其不匹配于編碼參數(shù)（n,k,d,D）.由于SVM 具有分類速度快以及可對(duì)線性不可分的數(shù)據(jù)進(jìn)行分類等優(yōu)點(diǎn)[30-32]，所以可以基于SVM 對(duì)糾刪碼修復(fù)組分布方案對(duì)應(yīng)的特征向量進(jìn)行分類，以達(dá)到快速檢驗(yàn)糾刪碼修復(fù)組分布方案的目的.

EVA 的工作流程如算法1 所示.

算法1.EVA 算法.

1）初始訓(xùn)練集獲取

EVA按4 步獲取用于構(gòu)造初始SVM 分類器的訓(xùn)練集：

①隨機(jī)抽取部分編碼參數(shù)下的部分糾刪碼修復(fù)組分布方案（不妨設(shè)糾刪碼修復(fù)組分布方案的集合為TE）；

② 將TE中的糾刪碼修復(fù)組分布方案及其對(duì)應(yīng)的編碼參數(shù)轉(zhuǎn)換為定長(zhǎng)特征向量；

③對(duì)于TE中的任意一個(gè)糾刪碼修復(fù)組分布方案E，枚舉其對(duì)應(yīng)的糾刪碼Tanner 圖，并使用糾刪碼Tanner 圖匹配于指定編碼參數(shù)（n,k,d,D）的充要條件來(lái)檢驗(yàn)這些糾刪碼Tanner 圖是否存在1 個(gè)匹配（n,k,d,D），從而判斷E是否匹配于（n,k,d,D），即得到E對(duì)應(yīng)定長(zhǎng)特征向量的類別標(biāo)簽；

④ 將所有打上類別標(biāo)簽的特征向量組合為SVM 分類器的初始訓(xùn)練集（算法1 的行①～⑧），由于當(dāng)云數(shù)據(jù)中心數(shù)N固定時(shí)，所有糾刪碼修復(fù)組分布方案的特征向量長(zhǎng)度相同，所以同一套部署環(huán)境下只需要準(zhǔn)備一份初始訓(xùn)練集.

2）分類器增量更新

SVM 的分類器的本質(zhì)是一個(gè)能將高維空間一分為二的決策超平面，而其分類特征向量的本質(zhì)則是判斷被投射到高位空間后的特征向量位于決策超平面的哪一側(cè).在SVM 中，能夠?qū)Q策超平面（分類器）的構(gòu)造造成影響的特征向量為有效特征向量.當(dāng)初始訓(xùn)練集中的有效特征向量的數(shù)目有限時(shí)，首次訓(xùn)練出的分類器很難反映真實(shí)的數(shù)據(jù)分布情況，使得其無(wú)法對(duì)特征向量進(jìn)行準(zhǔn)確分類.針對(duì)這個(gè)問(wèn)題，基于SVM 的EVA 將在訓(xùn)練分類器時(shí)篩選出訓(xùn)練集中的有效特征向量，并在分類的同時(shí)持續(xù)收集新的已知確切類別的特征向量.然后，EVA 將挑選部分新收集的特征向量與舊訓(xùn)練集中的有效特征向量組成新的訓(xùn)練集，并使用新的訓(xùn)練集訓(xùn)練出一個(gè)新的分類器（算法1 的行 ?～?）.因?yàn)樾碌挠?xùn)練集同時(shí)包含新收集的特征向量中的有效特征向量和舊訓(xùn)練集中有效特征向量，所以新的分類器的分類準(zhǔn)確性更高.

增量學(xué)習(xí)的關(guān)鍵是如何從舊訓(xùn)練集中挑選出有效特征向量以及如何獲取新的有效特征向量：

①舊的訓(xùn)練集的有效特征向量.EVA 會(huì)在訓(xùn)練分類器的同時(shí)獲取一組支持向量，這些支持向量決定了決策超平面.也就是說(shuō)，這些支持向量即為舊訓(xùn)練集中的有效特征向量.因此，EVA 直接將這些支持向量加入到新的訓(xùn)練集中.

② 新收集的特征向量中的有效特征向量.如果分類器對(duì)一個(gè)特征向量進(jìn)行了誤分類，那么意味著現(xiàn)有的分類器（決策超平面）缺少該特征向量的信息.因此，如果將該特征向量加入到新的訓(xùn)練集中，新的決策超平面將與舊的決策超平面有所不同.所以，新收集的特征向量中被舊分類器錯(cuò)誤分類的部分即為有效特征向量.因此，EVA 將這些支持向量加入到新的訓(xùn)練集中.

具體而言，EVA 搜集新的有效特征向量以及檢驗(yàn)糾刪碼修復(fù)組分布方案的具體過(guò)程如圖5 所示.

Fig.5 Verification process of erasure code repair group distribution scheme圖5 糾刪碼修復(fù)組分布方案檢驗(yàn)過(guò)程

首先，EVA 分別用糾刪碼修復(fù)組分布方案匹配于指定編碼參數(shù)的必要條件和分類器來(lái)檢驗(yàn)輸入的糾刪碼修復(fù)組分布方案.

如果分類器和糾刪碼修復(fù)組分布方案匹配于指定編碼參數(shù)的必要條件的檢驗(yàn)結(jié)果均為某個(gè)糾刪碼修復(fù)組分布方案E匹配于編碼參數(shù)（n,k,d,D），EVA則使用糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件來(lái)檢驗(yàn)E的糾刪碼Tanner 圖.如果存在一個(gè)E的糾刪碼Tanner 圖匹配于編碼參數(shù)（n,k,d,D），則可確定E匹配于編碼參數(shù)（n,k,d,D）.反之，如果不存在任何一個(gè)E的糾刪碼Tanner 圖匹配于編碼參數(shù)（n,k,d,D），則可確定E不匹配于編碼參數(shù)（n,k,d,D）且分類器對(duì)E對(duì)應(yīng)的的特征向量進(jìn)行了錯(cuò)誤分類，此時(shí)E對(duì)應(yīng)的特征向量將被加入新的訓(xùn)練集（算法1 的行?～?）.

如果分類器的分類結(jié)果是某個(gè)糾刪碼修復(fù)組分布方案E不匹配于編碼參數(shù)（n,k,d,D），EVA 將在較小的概率Po下使用糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件對(duì)E進(jìn)行檢驗(yàn)（以檢驗(yàn)分類器的分類結(jié)果）——因?yàn)榉诸惼髡`分類頻率越小，檢驗(yàn)它的分類結(jié)果的必要性越小，所以Po始終等于分類器的當(dāng)前誤分率.如果存在一個(gè)E的糾刪碼Tanner 圖符合其匹配于指定編碼參數(shù)的充要條件，可以確定E匹配于編碼參數(shù)（n,k,d,D）且分類器對(duì)E進(jìn)行了錯(cuò)誤分類，此時(shí)E對(duì)應(yīng)的特征向量將被加入新的訓(xùn)練集.如果EVA 沒(méi)有使用糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件對(duì)E進(jìn)行檢驗(yàn)或者不存在一個(gè)對(duì)應(yīng)于E的糾刪碼Tanner 圖符合其匹配于指定編碼參數(shù)的充要條件，那么EVA 將E視為不通過(guò)檢驗(yàn)的糾刪碼修復(fù)組分布方案（算法1 的行?～?）.

如果分類器的分類結(jié)果是某個(gè)糾刪碼修復(fù)組分布方案E匹配于編碼參數(shù)（n,k,d,D）但E不符合其匹配于指定編碼參數(shù)的必要條件，那么可以確定E不匹配于編碼參數(shù)（n,k,d,D）且分類器對(duì)其進(jìn)行了誤分類，此時(shí)E對(duì)應(yīng)的特征向量將被加入新的訓(xùn)練集（算法1 的行?～?）.

3.3 近似最優(yōu)糾刪碼修復(fù)組分布方案搜索算法

3.2 節(jié)提出EVA 可快速檢驗(yàn)糾刪碼修復(fù)組分布方案是否匹配于指定編碼參數(shù)（n,k,d,D）.DSAOE 可從所有能通過(guò)EVA 檢驗(yàn)的糾刪碼修復(fù)組分布方案中挑選出具有最小平均跨云數(shù)據(jù)中心修復(fù)流量的一個(gè)糾刪碼修復(fù)組分布方案.

根據(jù)定義6，當(dāng)云數(shù)據(jù)中心數(shù)目N、編碼參數(shù)n以及條帶分布方案確定時(shí)，相應(yīng)的所有糾刪碼修復(fù)組分布方案均可被枚舉出來(lái).此外，每個(gè)糾刪碼修復(fù)組分布方案對(duì)應(yīng)一個(gè)平均跨云數(shù)據(jù)中心修復(fù)流量.

因此，DSAOE 的主要思想是：當(dāng)云數(shù)據(jù)中心數(shù)N,編碼塊數(shù)n和編碼塊分布方案被指定后，枚舉出所有與它們相對(duì)應(yīng)的糾刪碼修復(fù)組分布方案，并將這些糾刪碼修復(fù)組分布方案按它們對(duì)應(yīng)的平均跨云數(shù)據(jù)中心修復(fù)流量遞增的順序排序.然后，對(duì)糾刪碼修復(fù)組分布方案進(jìn)行分組并采用多個(gè)計(jì)算節(jié)點(diǎn)對(duì)各組糾刪碼修復(fù)組分布方案進(jìn)行并行檢驗(yàn)——各個(gè)計(jì)算節(jié)點(diǎn)使用EVA 對(duì)其進(jìn)行檢驗(yàn).各個(gè)計(jì)算節(jié)點(diǎn)中第一個(gè)通過(guò)EVA 檢驗(yàn)的糾刪碼修復(fù)組分布方案即為局部最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案.各個(gè)計(jì)算節(jié)點(diǎn)的局部最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案中具有最小平均跨云數(shù)據(jù)中心修復(fù)流量的一個(gè)糾刪碼修復(fù)組分布方案即為DSAOE 的輸出.

DSAOE 使用1 個(gè)協(xié)調(diào)者節(jié)點(diǎn)和多個(gè)工作節(jié)點(diǎn)來(lái)并行完成最優(yōu)糾刪碼修復(fù)組分布方案的搜索，其具體分工為：

1）協(xié)調(diào)者節(jié)點(diǎn)

協(xié)調(diào)者節(jié)點(diǎn)的工作流程如算法2 所示.

算法2.DSAOE 的協(xié)調(diào)節(jié)點(diǎn)的工作流程.

輸入：編碼參數(shù)（n,k,d,D），云數(shù)據(jù)中心總數(shù)N，編碼塊分布方案R，Worker總數(shù)W；

輸出：全局最優(yōu)解GO（包括近似最小跨云數(shù)據(jù)中心修復(fù)流量修復(fù)組分布方案及其對(duì)應(yīng)的最優(yōu)糾刪碼Tanner 圖和平均跨云數(shù)據(jù)中心修復(fù)流量）.

當(dāng)協(xié)調(diào)者節(jié)點(diǎn)接收到編碼參數(shù)（n,k,d,D）、云數(shù)據(jù)中心總數(shù)N以及條帶的編碼塊分布方案R后，協(xié)調(diào)者節(jié)點(diǎn)將枚舉所有可能的糾刪碼修復(fù)組分布方案并計(jì)算出這些糾刪碼修復(fù)組分布方案的平均跨云數(shù)據(jù)中心修復(fù)流量（算法2 的行②）——根據(jù)定義6，糾刪碼的修復(fù)組分布方案E的平均跨云數(shù)據(jù)中心流量為（C為E中的編碼塊修復(fù)組分布方案、n為一個(gè)編碼條帶中的編碼塊數(shù)），所以協(xié)調(diào)者節(jié)點(diǎn)計(jì)算糾刪碼修復(fù)組分布方案的平均跨云數(shù)據(jù)中心修復(fù)流量的開銷較低.

然后，協(xié)調(diào)者節(jié)點(diǎn)將這些糾刪碼修復(fù)組分布方案隨機(jī)分成若干子集并分發(fā)到若干工作節(jié)點(diǎn)進(jìn)行檢驗(yàn)（算法2 的行③④）.工作節(jié)點(diǎn)檢驗(yàn)這些子集時(shí)，協(xié)調(diào)者節(jié)點(diǎn)負(fù)責(zé)維護(hù)臨時(shí)全局近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案及其對(duì)應(yīng)的臨時(shí)全局近似最小平均跨云數(shù)據(jù)中心修復(fù)流量（算法2 的行⑤～?）.

2）工作節(jié)點(diǎn)

工作節(jié)點(diǎn)的工作流程如算法3 所示.

算法3.DSAOE 的工作節(jié)點(diǎn)的工作流程.

輸入：編碼參數(shù)（n,k,d,D），編碼塊分布方案R，糾刪碼修復(fù)組分布方案組subSet，云數(shù)據(jù)中心數(shù)N，分類器svm；

在接收到協(xié)調(diào)者節(jié)點(diǎn)發(fā)來(lái)的糾刪碼修復(fù)組分布方案的集合后，各個(gè)工作節(jié)點(diǎn)首先將這些糾刪碼修復(fù)組分布方案按平均跨云數(shù)據(jù)中心修復(fù)流量遞增的順序進(jìn)行排列（算法3 的行①）.然后，工作節(jié)點(diǎn)依次讀取這些糾刪碼修復(fù)組分布方案.如果一個(gè)糾刪碼修復(fù)組分布方案的平均跨云數(shù)據(jù)中心修復(fù)流量小于臨時(shí)全局近似最小平均跨云數(shù)據(jù)中心修復(fù)流量，那么工作節(jié)點(diǎn)將使用EVA 對(duì)其進(jìn)行檢驗(yàn).第1 個(gè)通過(guò)EVA 的檢驗(yàn)的即為局部最低跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案，其對(duì)應(yīng)的平均跨云數(shù)據(jù)中心修復(fù)流量即為局部近似最小平均跨云數(shù)據(jù)中心修復(fù)流量.一旦一個(gè)工作節(jié)點(diǎn)得到了局部最低跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案和局部近似最小平均跨云數(shù)據(jù)中心修復(fù)流量，它便立即停止后續(xù)糾刪碼修復(fù)組分布方案的檢驗(yàn)，并分別用它的局部最低跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案和局部近似最小平均跨云數(shù)據(jù)中心修復(fù)流量來(lái)更新協(xié)調(diào)者節(jié)點(diǎn)中的臨時(shí)全局最低跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案和臨時(shí)全局近似最小平均跨云數(shù)據(jù)中心修復(fù)流量（算法3 的行②～?）.

當(dāng)所有的工作者節(jié)點(diǎn)均停止檢驗(yàn)糾刪碼修復(fù)組分布方案時(shí)，協(xié)調(diào)者節(jié)點(diǎn)中的臨時(shí)全局近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案和臨時(shí)全局近似最小平均跨云數(shù)據(jù)中心修復(fù)流量即為DSAOE 得到的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案和平均跨云數(shù)據(jù)中心修復(fù)流量近似下限.

由于在EVA 的分類器將一個(gè)糾刪碼修復(fù)組分布方案分為正類后，EVA 還會(huì)使用糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件對(duì)其進(jìn)行檢驗(yàn)，因此DSAOE 得到的全局最優(yōu)糾刪碼修復(fù)組分布方案一定匹配于編碼參數(shù)（n,k,d,D）.

如果EVA 的誤報(bào)率為0，DAOSE 可獲得所有通過(guò)EVA 檢驗(yàn)的糾刪碼修復(fù)組分布方案中平均跨數(shù)據(jù)中心修復(fù)流量最小的一個(gè).根據(jù)定理5，該糾刪碼修復(fù)組分布方案能達(dá)到相應(yīng)編碼參數(shù)下的平均跨數(shù)據(jù)中心修復(fù)流量下限，即該糾刪碼修復(fù)組分布方案為最優(yōu)糾刪碼修復(fù)組分布方案.若EVA 的誤報(bào)率P＞0，且一共存在Q個(gè)最優(yōu)糾刪碼修復(fù)組分布方案，那么DAOSE 錯(cuò)過(guò)所有最優(yōu)糾刪碼修復(fù)組分布方案的概率不超過(guò)PQ.因此，F(xiàn)MEL 可以得到最優(yōu)碼的概率不低于1-PQ.

此外，因?yàn)镈SAOE 使用EVA 來(lái)對(duì)大多數(shù)糾刪碼修復(fù)組分布方案進(jìn)行快速檢驗(yàn)，所以其效率較高.另外，DSAOE 的并行度高的特點(diǎn)可進(jìn)一步保證其搜索效率.

3.4 基于試錯(cuò)的糾刪碼修復(fù)組分布方案轉(zhuǎn)換算法

3.3 節(jié)提出了DSAOE 能搜索到近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案.本節(jié)提出了一種基于試錯(cuò)的糾刪碼修復(fù)組分布方案轉(zhuǎn)換算法EST，用于將近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案轉(zhuǎn)換為相應(yīng)的糾刪碼生成矩陣.

EST 的工作流程如算法4 所示.

算法4.EST 算法.

輸入：全局最優(yōu)解GO（包括近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案及其對(duì)應(yīng)的最優(yōu)糾刪碼Tanner 圖和平均跨數(shù)據(jù)中心修復(fù)流量）；

輸出：近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的生成矩陣G.

1）對(duì)于指定的糾刪碼修復(fù)組分布方案，DSAOE只有在找到一個(gè)與其相對(duì)應(yīng)的匹配于編碼參數(shù)（n,k,d,D）的糾刪碼Tanner 圖時(shí)才會(huì)確認(rèn)該糾刪碼修復(fù)組分布方案匹配于編碼參數(shù)（n,k,d,D）.因此，DSAOE 在搜索近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案的同時(shí)也得到了與之相對(duì)應(yīng)的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼Tanner 圖 T，如算法4 的行①所示.

2）令U為如式（10）所示的柯西矩陣，基于試錯(cuò)的糾刪碼修復(fù)組分布方案轉(zhuǎn)換算法EST 將構(gòu)造一個(gè)對(duì)應(yīng)于 T 的校驗(yàn)矩陣H：如果 T的第j個(gè)校驗(yàn)端點(diǎn)覆蓋其第i個(gè)變量端點(diǎn)，那么H的第j行i列的值等于U的第j行i列的值.如果 T的第j個(gè)校驗(yàn)端點(diǎn)不覆蓋其第i個(gè)變量端點(diǎn)，那么hji的值為0，如算法4的行②所示.

3）EST 獲取H的所有包含n-k行d-1 列的子矩陣的集合SM1以及H的所有包含其對(duì)應(yīng)于任意D個(gè)云數(shù)據(jù)中心的列的子矩陣的集合SM2.根據(jù)定義7，SM1和SM2中的任意矩陣均對(duì)應(yīng)于一個(gè) T的子圖，如算法4 的行③④所示.

4）EST 獲取 T的最大匹配.因?yàn)?T符合其匹配于指定編碼參數(shù)的充要條件的子條件3，其最大匹配中包含n-k個(gè)變量端點(diǎn)，不妨設(shè) T 的最大匹配包含,隨后，EST 求得由H的第l1,l2,…,ln-k列組成的子矩陣H1.顯然，H1是一個(gè)方陣（n-k行、n-k列）.同時(shí)，EST 將H1加入到集合LS中，如算法4的行⑤⑥所示.

5）基于試錯(cuò)的糾刪碼修復(fù)組分布方案轉(zhuǎn)換算法EST 獲取對(duì)應(yīng)于SM1和SM2中各個(gè)矩陣 T的各個(gè)子圖的最大匹配.對(duì)于SM1和SM2中的各個(gè)矩陣Z，如果它對(duì)應(yīng) T的子圖的最大匹配中包含的所有校驗(yàn)端點(diǎn)為則將Z的第l1,l2,…,la行組成的子矩陣添加到集合LS中.根據(jù)定理3 中的糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件的充分性證明的步驟③，LS中的矩陣均為方陣，如算法4 的行⑦～⑩所示.

6）EST 通過(guò)初等行變換將LS中的各個(gè)矩陣轉(zhuǎn)換為如式（11）所示的上三角矩陣（轉(zhuǎn)換過(guò)程見定理3中的糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件的充分性證明的步驟④），并獲得這些上三角矩陣的對(duì)角元素的集合NE=,其中，為不包含的線性多項(xiàng)式，如算法4 的行?所示.

7）EST 考察NE中的各個(gè)對(duì)角元素是否為0.如果NE中某個(gè)元素的值為0（不妨設(shè)），則進(jìn)行操作：對(duì)進(jìn)行加1 操作；更新H，LS；重新構(gòu)造上三角矩陣并更新集合NE；重新考察NE中各個(gè)元素的值.直到NE中的各個(gè)元素的值均不為0，如算法4 的行?～?所示，根據(jù)定理3 中的糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件的證明過(guò)程，此時(shí)LS中的矩陣均滿秩.其中，LS中的H1滿秩意味著H滿秩.此外，由定理2 可知，LS中的其他矩陣滿秩意味著此時(shí)的H對(duì)應(yīng)的糾刪碼CO能夠容忍任意d-1 個(gè)編碼塊失效或任意D個(gè)云數(shù)據(jù)中心失效（即H為一個(gè)匹配于（n,k,d,D）的校驗(yàn)矩陣）.事實(shí)上，在我們的多次實(shí)驗(yàn)中，初始NE中的各個(gè)元素的值全不為0.也就是說(shuō)，在大多數(shù)情況下，不需要對(duì)NE、LS和H進(jìn)行更新即可一次性得到最終的校驗(yàn)矩陣H.

8）EST 對(duì)H執(zhí)行初等行變換以得到矩H′=然后，EST 構(gòu)造G′=和.顯然，G′(H′)T=0.因此GHT=G′·(ΔT)-1ΔT(H′)T=G′In×n(H′)T=0.因此，G為對(duì)應(yīng)于H的生成矩陣，即對(duì)應(yīng)于近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案的生成矩陣，如算法4 的行?所示.

3.5 FMEL 方法描述

低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的快速構(gòu)造方法FMEL 的工作流程如算法5 所示.

算法5.算法FMEL.

輸入：編碼參數(shù)（n,k,d,D），云數(shù)據(jù)中心總數(shù)N，編碼塊分布方案R，Worker總數(shù)W，云數(shù)據(jù)中心數(shù)N；

輸出：G.

①全局最優(yōu)解GO←DSAOE（n,k,d,D,N,R,W,N）；

②G←EST（GO）；

③returnG.

首先，F(xiàn)MEL 通過(guò)DSAOE 從所有能通過(guò)基于SVM 的EVA 的檢驗(yàn)的糾刪碼修復(fù)組分布方案中選出具有較小平均跨云數(shù)據(jù)中心修復(fù)流量的一個(gè)糾刪碼修復(fù)組分布方案，如算法5 的行①所示.挑選出的糾刪碼修復(fù)組分布方案即為近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案.然后，F(xiàn)MEL 通過(guò)EST 將近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼修復(fù)組分布方案轉(zhuǎn)換為相應(yīng)編碼參數(shù)下的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼生成矩陣G，如算法5 的行②所示.

4 實(shí)驗(yàn)與結(jié)果

4.1 方法實(shí)現(xiàn)

為了評(píng)估FMEL 構(gòu)造出的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的實(shí)際性能，我們基于OpenEC[33]和FastDFS[34]實(shí)現(xiàn)了FMEL 構(gòu)造出的糾刪碼.其中，OpenEC 是一種用于在已有的分布式文件系統(tǒng)中實(shí)現(xiàn)不同的糾刪碼編碼方法和修復(fù)方法的可定制框架，F(xiàn)astDFS 是一種輕量級(jí)的文件系統(tǒng).

具體而言，我們首先在原始的FastDFS 上增加了對(duì)OpenEC 的支持.然后，我們?cè)贠penEC 上實(shí)現(xiàn)了FMEL，用于構(gòu)造近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼生成矩陣.最后，基于OpenEC 的編碼方法和修復(fù)方法定制功能，實(shí)現(xiàn)了近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的數(shù)據(jù)編碼方法和數(shù)據(jù)修復(fù)方法.

4.2 實(shí)驗(yàn)環(huán)境與參數(shù)

實(shí)驗(yàn)部署于UCloud[35]的6 個(gè)云數(shù)據(jù)中心，其中2 個(gè)位于北京（記為PEK1 和PEK2）、1 個(gè)位于上海（記為SHA）、1 個(gè)位于洛杉磯（記為L(zhǎng)OS）、1 個(gè)位于臺(tái)北（記為TPE）、1 個(gè)位于廣州（記為CAN）.實(shí)驗(yàn)使用了每個(gè)云數(shù)據(jù)中心的10 個(gè)存儲(chǔ)節(jié)點(diǎn)（云主機(jī)），每個(gè)節(jié)點(diǎn)配備4 核Intel Cascadelake 6248R 3.0 GHz 處理器，8 GB 內(nèi)存和1 TB 磁盤，外網(wǎng)最大帶寬為800 Mbps，內(nèi)網(wǎng)最大帶寬為25 Gbps.

為了評(píng)估FMEL 構(gòu)造出的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的性能，我們將其與典型的糾刪碼進(jìn)行了比較：最優(yōu)碼構(gòu)造方法ACIoT 構(gòu)造出的最優(yōu)碼（因?yàn)樵嫉腁CIoT 只能構(gòu)造出指定編碼參數(shù)（n,k,d）下的最優(yōu)碼，我們對(duì)其進(jìn)行了擴(kuò)展，使其能夠構(gòu)造出指定編碼參數(shù)（n,k,d,D）下的最優(yōu)碼）、一種能夠達(dá)到平均局部性下限的糾刪碼ACL 碼[23]、經(jīng)典的RS 碼[36]、一種典型的局部性碼Xorbas 碼[22]和一種典型的跨云數(shù)據(jù)中心糾刪碼DFC 碼[13].

為了評(píng)估FMEL 構(gòu)造出的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼在不同環(huán)境中的性能，我們將UCloud 的6 個(gè)云數(shù)據(jù)中心分為了2 個(gè)實(shí)驗(yàn)環(huán)境.由于大多數(shù)的跨云數(shù)據(jù)中心存儲(chǔ)系統(tǒng)均是部署在3 個(gè)云數(shù)據(jù)中心[1,14]，所以我們的每個(gè)實(shí)驗(yàn)環(huán)境均包含3個(gè)云數(shù)據(jù)中心.具體而言，實(shí)驗(yàn)環(huán)境1 包含PEK1,PEK2,SHA，實(shí)驗(yàn)環(huán)境2 包含LOS,TPE,CAN.由于各個(gè)實(shí)驗(yàn)環(huán)境包含3 個(gè)云數(shù)據(jù)中心，因而容災(zāi)度D的合理取值范圍為[1,2]，所以實(shí)驗(yàn)中D∈[1,2].此外，在實(shí)際應(yīng)用中，為了便于條帶管理，單個(gè)條帶內(nèi)的編碼塊數(shù)n通常較小.因此，我們?cè)趯?shí)驗(yàn)中將n的范圍限制在[6,11]（常見的生產(chǎn)系統(tǒng)中的n均處于該范圍內(nèi)[37-39]）.另外，實(shí)驗(yàn)中單個(gè)條帶內(nèi)的數(shù)據(jù)塊數(shù)k的取值范圍為[n/3,2n/3]，因?yàn)楫?dāng)k屬于此范圍時(shí)D的取值范圍為[1,2].最后，容錯(cuò)度d的取值范圍為[2,n-k+1]，即d的合理取值范圍[1,12-18].

在本文實(shí)驗(yàn)中，各個(gè)編碼條帶的編碼塊被平均分配到各個(gè)云數(shù)據(jù)中心中，以獲取較高的容災(zāi)度和負(fù)載均衡性.此外，新生節(jié)點(diǎn)與其相應(yīng)的失效編碼塊位于同一云數(shù)據(jù)中心，以保持系統(tǒng)的容災(zāi)度和負(fù)載均衡性.實(shí)驗(yàn)中的編碼塊大小和HDFS 一致[35]，為128 MB.

4.3 評(píng)價(jià)指標(biāo)

我們用4 個(gè)指標(biāo)來(lái)評(píng)價(jià)FMEL 的性能：

1）分類器誤報(bào)率（false-negative rate,FN）.假設(shè)被FMEL 中的SVM 分類器誤分類為負(fù)類（不滿足編參數(shù)（n,k,d,D）的類）的糾刪碼修復(fù)組分布方案的數(shù)目為f1，EVA 檢驗(yàn)過(guò)的糾刪碼修復(fù)組分布方案中匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案數(shù)為f2，那么分類器誤報(bào)率為f1/f2.

2）糾刪碼構(gòu)建時(shí)間（construction time,CT）.糾刪碼構(gòu)造時(shí)間是指ACIoT 構(gòu)造最優(yōu)碼的時(shí)間或FMEL構(gòu)造近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的時(shí)間.

3）平均跨云數(shù)據(jù)中心修復(fù)流量T.令某糾刪碼修復(fù)它的一個(gè)條帶中的n個(gè)編碼塊產(chǎn)生的跨云數(shù)據(jù)中心修復(fù)流量分別為T1,T2,…,Tn且每個(gè)編碼塊的大小為m，那么該糾刪碼的平均跨云數(shù)據(jù)中心修復(fù)流量

4）平均修復(fù)用時(shí)t.令某糾刪碼在實(shí)驗(yàn)環(huán)境1 中修復(fù)它的一個(gè)條帶中的n個(gè)編碼塊所消耗的時(shí)間分別為t1,1,t1,2,…,t1,n，在實(shí)驗(yàn)環(huán)境2 中修復(fù)它的一個(gè)條帶中的n個(gè)編碼塊所消耗的時(shí)間分別為t2,1,t2,2,…,t2,n,每個(gè)編碼塊的大小為m.因?yàn)閠j,i受到云數(shù)據(jù)中心的排列順序的影響，令為tj,i在不同云數(shù)據(jù)中心的排列順序下的平均值.那么，該糾刪碼的平均修復(fù)用時(shí)

4.4 分類器誤報(bào)率

在FMEL 中，SVM 分類器將一個(gè)糾刪碼修復(fù)組分布方案分為正類后，還會(huì)使用糾刪碼Tanner 圖匹配于指定編碼參數(shù)的充要條件對(duì)其進(jìn)行檢驗(yàn)，因此FMEL 不會(huì)將不匹配于編碼參數(shù)（n,k,d,D）糾刪碼修復(fù)組分布方案錯(cuò)誤分為正類.此外，如果SVM 分類器將一個(gè)匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案錯(cuò)誤分為負(fù)類，F(xiàn)MEL 可能會(huì)錯(cuò)過(guò)具有較小平均跨云數(shù)據(jù)中心修復(fù)流量且匹配于編碼參數(shù)（n,k,d,D）的糾刪碼修復(fù)組分布方案.因此，我們主要關(guān)注分類器將糾刪碼修復(fù)組分布方案錯(cuò)誤分為負(fù)類的概率，即誤報(bào)率.

我們的測(cè)試數(shù)據(jù)包括所有編碼參數(shù)下的所有糾刪碼修復(fù)組分布方案.在分類器初始化時(shí)，首先在各組編碼參數(shù)下隨機(jī)挑選了50 個(gè)糾刪碼修復(fù)組分布方案并將這些糾刪碼修復(fù)組分布方案轉(zhuǎn)換為對(duì)應(yīng)的特征向量.然后，使用糾刪碼修復(fù)組分布方案匹配于編碼參數(shù)（n,k,d,D）的充要條件判斷這些糾刪碼修復(fù)組分布方案是否滿足各自的編碼參數(shù)，并以此為依據(jù)為對(duì)應(yīng)的特征向量打上標(biāo)簽.因此，我們可以得到這些糾刪碼修復(fù)組分布方案對(duì)應(yīng)的帶標(biāo)簽的特征向量，它們組成了分類器的初始訓(xùn)練集（10 次實(shí)驗(yàn)的平均初始訓(xùn)練集構(gòu)造用時(shí)為1 711 s、平均初始分類器構(gòu)造用時(shí)為192 s）.然后，我們按編碼參數(shù)n遞增的順序?qū)⑵渌募m刪碼修復(fù)組分布方案輸入到分類器中進(jìn)行分類.與此同時(shí)，F(xiàn)MEL 不斷搜集新的訓(xùn)練集對(duì)分類器進(jìn)行增量更新.

分類器分類每組（n,k）對(duì)應(yīng)的所有糾刪碼修復(fù)組分布方案的誤報(bào)率如圖6 所示.因?yàn)樵诜诸愡^(guò)程中含有效信息的特征向量被逐漸加入到新的訓(xùn)練集中，并不斷更新分類器，因此分類器的誤報(bào)率隨著n的增加而逐漸降低.

Fig.6 False-negative rate of SVM’s classifier圖6 SVM 分類器的誤報(bào)率

因?yàn)橥唤M編碼參數(shù)下的最優(yōu)碼往往存在多個(gè)，所以最優(yōu)糾刪碼修復(fù)組分布方案也往往存在多個(gè).假設(shè)一共存在Q個(gè)最優(yōu)糾刪碼修復(fù)組分布方案且分類器的誤報(bào)率為P，那么FMEL 錯(cuò)過(guò)所有最優(yōu)糾刪碼修復(fù)組分布方案的概率不超過(guò)PQ.因此，F(xiàn)MEL 可以得到最優(yōu)碼的概率不低于1-PQ.由圖6 可知，P總是小于27%的.所以，如果Q＞1，F(xiàn)MEL 有92.7%的概率得到最優(yōu)碼；如果Q＞2，F(xiàn)MEL 則有98%的概率得到最優(yōu)碼.

4.5 糾刪碼構(gòu)造時(shí)間

每組（n,k）對(duì)應(yīng)多組（n,k,d,D），F(xiàn)MEL 和ACIoT在每組（n,k）對(duì)應(yīng)的所有（n,k,d,D）下的糾刪碼構(gòu)造時(shí)間如圖7 所示（FMEL 的工作節(jié)點(diǎn)數(shù)和ACIoT的工作進(jìn)程數(shù)均為5）.在構(gòu)造最優(yōu)碼或近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼時(shí)，ACIoT 和FMEL 均需要枚舉和檢驗(yàn)部分糾刪碼修復(fù)組分布方案的糾刪碼Tanner 圖.由于編碼參數(shù)（n,k,d,D）下的糾刪碼Tanner圖的總數(shù)為2n(n-k)，所以，通常而言，n(n-k)越大，ACIoT和FMEL 需要檢驗(yàn)的糾刪碼Tanner 圖越多.因此，ACIoT和FMEL 的糾刪碼構(gòu)造時(shí)間均呈現(xiàn)出隨著n(n-k)的減少而減少的趨勢(shì).

Fig.7 Erasure code construction time of ACIoT and FMEL圖7 ACIoT 和FMEL 的糾刪碼構(gòu)造時(shí)間

對(duì)于大部分的糾刪碼修復(fù)組分布方案，F(xiàn)MEL 僅需要用SVM 分類器對(duì)它們分類即可，無(wú)需枚舉和檢驗(yàn)它們對(duì)應(yīng)的糾刪碼Tanner 圖.因此，F(xiàn)MEL 的平均糾刪碼構(gòu)造時(shí)間僅為ACIoT 的11%.特別地，當(dāng)n(n-k)較小時(shí)，總的糾刪碼構(gòu)造時(shí)間較短.所以，此時(shí)FMEL中更新分類器的時(shí)間占總的糾刪碼構(gòu)造時(shí)間的比例較大.因此，此時(shí)FMEL 的糾刪碼構(gòu)造時(shí)間比ACIoT 略長(zhǎng).

4.6 平均跨云數(shù)據(jù)中心修復(fù)流量

因?yàn)椴煌募m刪碼適應(yīng)的編碼參數(shù)不同，我們首先在除RS 碼外的所有糾刪碼都適應(yīng)的編碼參數(shù)下比較了各個(gè)糾刪碼的平均跨云數(shù)據(jù)中心修復(fù)流量（RS碼使用和其他糾刪碼相近的編碼參數(shù)），如圖8 所示.在這些編碼參數(shù)下，DFC 碼和ACIoT 均可為每個(gè)云數(shù)據(jù)中心分配一個(gè)局部校驗(yàn)塊，因此，DFC 和ACIoT 均能夠在不跨云數(shù)據(jù)中心傳輸數(shù)據(jù)的情況下完成編碼塊的修復(fù)，因而它們的平均跨云數(shù)據(jù)中心修復(fù)流量為0.大多數(shù)情況下，F(xiàn)MEL 的平均跨云數(shù)據(jù)中心修復(fù)流量也為0，即FMEL 有較大概率得到最優(yōu)碼.

Fig.8 Average cross-cloud data center repair traffic of ACL,Xorbas,DFC,RS,ACIoT and FMEL圖8 ACL 碼、Xorbas 碼、DFC 碼、RS 碼、ACIoT 和FMEL 的平均跨云數(shù)據(jù)中心修復(fù)流量

因?yàn)镽S 碼在修復(fù)任意一個(gè)編碼塊時(shí)均需要讀取k個(gè)編碼塊，而在實(shí)驗(yàn)中使用的全部編碼參數(shù)下各編碼條帶在同一個(gè)云數(shù)據(jù)中心的編碼塊數(shù)始終小于k（如果要使各編碼條帶在同一個(gè)云數(shù)據(jù)中心的編碼塊數(shù)始終不小于k，那么冗余度將十分大），所以RS碼在修復(fù)任意一個(gè)編碼塊時(shí)均需要跨云數(shù)據(jù)中心傳輸數(shù)據(jù).因此，RS 碼跨云數(shù)據(jù)中心修復(fù)流量最大.

因?yàn)閄orbas 碼和ACL 碼具有較低的修復(fù)流量（其中ACL 碼能夠達(dá)到平均修復(fù)流量的下限），所以它們能在一定程度上降低平均跨云數(shù)據(jù)中心修復(fù)流量，進(jìn)而使得它們的平均跨云數(shù)據(jù)中心修復(fù)流量相較于局部性為k-1 的RS 碼更小.但是，由于修復(fù)流量不與跨云數(shù)據(jù)中心修復(fù)流量嚴(yán)格正相關(guān)，所以ACL碼和Xorbas 碼的平均跨云數(shù)據(jù)中心修復(fù)流量大于ACIoT,FMEL,DFC 碼.

因?yàn)镽S 碼和DFC 碼對(duì)編碼參數(shù)的限制較為嚴(yán)格，我們?cè)诟嗟木幋a參數(shù)下比較了其他糾刪碼.如圖9 所示，在這些編碼參數(shù)下，F(xiàn)MEL 的平均跨云數(shù)據(jù)中心修復(fù)流量比ACL 碼和Xorbas 碼分別低了24.0%和34.8%，這是因?yàn)镕MEL 能在這些參數(shù)下達(dá)到平均跨云數(shù)據(jù)中心修復(fù)流量的近似下限.

Fig.9 Average cross-cloud data center repair traffic of ACL,Xorbas,ACIoT and FMEL圖9 ACL 碼、Xorbas 碼、ACIoT 和FMEL 的平均跨云數(shù)據(jù)中心修復(fù)流量

平均而言，F(xiàn)MEL 的平均跨云數(shù)據(jù)中心修復(fù)流量比ACL 碼、Xorbas 碼和RS 碼分別低了42.9%,51.1%,56.0%.此外，F(xiàn)MEL 的平均跨云數(shù)據(jù)中心修復(fù)流量與DFC 碼相近，但DFC 碼對(duì)編碼參數(shù)限制嚴(yán)格.

另外，F(xiàn)MEL 的平均跨云數(shù)據(jù)中心修復(fù)流量是ACIoT的100%～133%，并且在實(shí)驗(yàn)采用的15 組編碼參數(shù)中的13 組編碼參數(shù)下，F(xiàn)MEL 的平均跨云數(shù)據(jù)中心修復(fù)流量與ACIoT 相同，即FMEL 構(gòu)造出最優(yōu)碼的概率較高.

容錯(cuò)度d和FMEL 構(gòu)造的近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的平均跨云數(shù)據(jù)中心修復(fù)流量之間的關(guān)系如圖10 所示，當(dāng)d小于一個(gè)特定值d'后，近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼的平均跨云數(shù)據(jù)中心修復(fù)流量,即平均跨云數(shù)據(jù)中心修復(fù)流程近似下限.這是因?yàn)楫?dāng)d＜d'時(shí)，的主要影響因素為容災(zāi)度D.基于這一發(fā)現(xiàn)，不僅能夠得到編碼參數(shù)（n,k,D）下的平均跨云數(shù)據(jù)中心修復(fù)流量的近似下限，還可以得到滿足該近似下限時(shí)的d的上限，即圖中的最優(yōu)d.

Fig.10 Relationship between d and average cross-cloud data center repair traffic’s approximate lower bound under different n,k,D圖10 不同n,k,D 下d 與平均跨云數(shù)據(jù)中心修復(fù)流量近似下限的關(guān)系

因?yàn)榕c最優(yōu)d相對(duì)應(yīng)的編碼參數(shù)和近似最小跨云數(shù)據(jù)中心修復(fù)流量糾刪碼能夠在冗余度()、容錯(cuò)度(d)、容災(zāi)度(D)和平均跨云數(shù)據(jù)中心修復(fù)流量()之間取得較好權(quán)衡，因此關(guān)于最優(yōu)d的這一發(fā)現(xiàn)對(duì)于實(shí)際應(yīng)用具有指導(dǎo)意義.比如說(shuō)，基于這一發(fā)現(xiàn)，我們找到了2 個(gè)能夠在冗余度、容錯(cuò)度、容災(zāi)度和平均跨數(shù)據(jù)修復(fù)流量之間取得較好權(quán)衡的糾刪碼——FMEL（n=6,k=2）和FMEL（n=9,k=5，其生成矩陣如式（12）和式（13）所示.

如表2 所示，F(xiàn)MEL（n=6,k=2）的d值比3 副本技術(shù)高66.7%，同時(shí)，F(xiàn)MEL（n=6,k=2）的D、和和3 副本技術(shù)相同.此外，F(xiàn)MEL（n=9,k=5）的D比2 副本技術(shù)高33.3%，同時(shí)FMEL（n=9,k=5）的和比2副本技術(shù)低10%和33%且二者D相同.

Table 2 Comparison Between FMEL and Replications表2 FMEL 與多副本的對(duì)比

4.7 平均修復(fù)用時(shí)

因?yàn)椴煌募m刪碼適應(yīng)的編碼參數(shù)不同，我們首先在除RS 碼外的所有糾刪碼都適應(yīng)的編碼參數(shù)下比較了各個(gè)糾刪碼的平均修復(fù)用時(shí)（RS 碼使用和其他糾刪碼相近的編碼參數(shù)），如圖11 所示.

Fig.11 Average repair time of ACL,Xorbas,DFC,RS,ACIoT and FMEL圖11 ACL 碼、Xorbas 碼、DFC 碼、RS 碼、ACIoT 和FMEL 的平均修復(fù)用時(shí)

由于FMEL 和ACIoT 的平均跨云數(shù)據(jù)中心修復(fù)流量小于對(duì)照組中的其他糾刪碼，其修復(fù)數(shù)據(jù)時(shí)跨云數(shù)據(jù)中心傳輸數(shù)據(jù)的時(shí)間較短，使得其平均修復(fù)用時(shí)也比其他糾刪碼少.具體地，F(xiàn)MEL 的平均修復(fù)用時(shí)比ACL 碼、Xorbas 碼和RS 碼分別少了36.9%,46.1%,50.6%.此外，ACIoT 的平均修復(fù)用時(shí)與FMEL相近，但是ACIoT 的糾刪碼構(gòu)造時(shí)間更長(zhǎng).

因?yàn)镽S 碼和DFC 碼的編碼參數(shù)適應(yīng)性較差，我們?cè)诟嗟木幋a參數(shù)下對(duì)除這2 種糾刪碼之外的糾刪碼進(jìn)行了對(duì)比，如圖12 所示.在這些編碼參數(shù)下，F(xiàn)MEL 和ACIoT 的平均修復(fù)用時(shí)少于ACL 碼和Xorbas碼，這是因?yàn)榛贔MEL 和ACIoT 的平均跨云數(shù)據(jù)中心修復(fù)流量較小.特別地，在編碼參數(shù)為（8,3,5,1）時(shí)，F(xiàn)MEL 和ACIoT 的平均修復(fù)用時(shí)遠(yuǎn)低于其他糾刪碼，因?yàn)榇藭r(shí)只有它們能夠在不跨云數(shù)據(jù)中心傳輸數(shù)據(jù)的情況下完成數(shù)據(jù)修復(fù).

Fig.12 Average repair time of ACL,Xorbas,ACIoT and FMEL圖12 ACL 碼、Xorbas 碼、ACIoT 和FMEL 的平均修復(fù)用時(shí)

此外，如表2 所示，因?yàn)镕MEL（n=9,k=5）的平均跨云數(shù)據(jù)中心修復(fù)流量低于2 副本技術(shù)，因此其平均修復(fù)用時(shí)也短于2 副本技術(shù).特別地，雖然FMEL（n=6,k=2）的平均跨云數(shù)據(jù)中心修復(fù)流量與3副本技術(shù)相同，但其平均修復(fù)用時(shí)略長(zhǎng)于3 副本技術(shù)，這是因?yàn)镕MEL（n=6,k=2）在修復(fù)數(shù)據(jù)時(shí)的計(jì)算量大于3 副本技術(shù).

5 總結(jié)

針對(duì)現(xiàn)有糾刪碼構(gòu)造方法無(wú)法兼顧編碼參數(shù)適應(yīng)性、跨云數(shù)據(jù)中心修復(fù)流量和糾刪碼構(gòu)造效率的問(wèn)題，本文提出了一種低跨云數(shù)據(jù)中心修復(fù)流量的糾刪碼的快速構(gòu)造方法FMEL，可在不同編碼參數(shù)下快速求得低跨云數(shù)據(jù)中心修復(fù)流量糾刪碼.在真實(shí)跨云數(shù)據(jù)中心環(huán)境中的實(shí)驗(yàn)表明，相較于現(xiàn)有的可構(gòu)造能達(dá)到平均跨云數(shù)據(jù)中心修復(fù)流量下限的最優(yōu)碼的方法，F(xiàn)MEL 構(gòu)造糾刪碼的時(shí)間少了89%，且在大部分編碼參數(shù)下二者構(gòu)造的糾刪碼的平均跨云數(shù)據(jù)中心修復(fù)流量相同.此外，我們利用FMEL 評(píng)估了大量編碼參數(shù)，并挑選出2 組編碼參數(shù).FMEL 在這2 組編碼參數(shù)下構(gòu)造的糾刪碼的平均修復(fù)流量低于已得到廣泛使用的多副本技術(shù)，同時(shí)其容災(zāi)性、容錯(cuò)性和冗余度相較于多副本技術(shù)具有明顯優(yōu)勢(shì).

作者貢獻(xiàn)聲明：包涵提出了算法思路和實(shí)驗(yàn)方案，并負(fù)責(zé)完成實(shí)驗(yàn)和撰寫論文；王意潔提出指導(dǎo)意見并修改論文.