引言

本文借友商輪值CEO 于2020年8月28日在長(zhǎng)沙“數(shù)學(xué)促進(jìn)企業(yè)創(chuàng)新發(fā)展論壇”上分享的《后香農(nóng)時(shí)代，數(shù)學(xué)決定未來(lái)發(fā)展的邊界》【85】進(jìn)行開(kāi)篇，發(fā)言提出了后香農(nóng)時(shí)代，ICT信息產(chǎn)業(yè)面向數(shù)學(xué)的十大挑戰(zhàn)性問(wèn)題，其中就有一項(xiàng)“高效的糾刪碼問(wèn)題”，雖然這個(gè)問(wèn)題的提出背景是出于通信編碼領(lǐng)域，但對(duì)于糾刪碼在存儲(chǔ)領(lǐng)域的使用同樣面臨著具大的機(jī)遇與挑戰(zhàn)。

圖1：糾刪碼問(wèn)題挑戰(zhàn)

針對(duì)糾刪碼的研究分為兩派：

• 一派則是純理論界針對(duì)糾刪碼編碼技術(shù)在編解碼復(fù)雜度、修復(fù)帶寬及磁盤IO、存儲(chǔ)開(kāi)銷等維度進(jìn)行研究提出新的理論完備性證明過(guò)的糾刪碼，這類研究可能考慮更多的是理論完備性的證明；不會(huì)考慮工程界的實(shí)現(xiàn)復(fù)雜度等情況；
• 一派是不改變編碼理論，利用糾刪碼結(jié)合生產(chǎn)環(huán)境進(jìn)行適當(dāng)改造（多AZ、異構(gòu)服務(wù)器、大條帶、跨rack等）再結(jié)合實(shí)驗(yàn)數(shù)據(jù)在修復(fù)開(kāi)銷、存儲(chǔ)開(kāi)銷、可靠性等指標(biāo)來(lái)證明價(jià)值。這兩派的研究相輔相成共同推動(dòng)糾刪碼技術(shù)在分布式存儲(chǔ)領(lǐng)域的發(fā)展。

本次分享的主題“糾刪碼技術(shù)在vivo存儲(chǔ)系統(tǒng)的演進(jìn)”，分為上下兩篇：

• 上篇側(cè)重介紹和分析糾刪碼技術(shù)的演進(jìn)歷程、核心糾刪碼技術(shù)的原理和以及工業(yè)界存儲(chǔ)產(chǎn)品當(dāng)中的糾刪碼技術(shù)的探索與實(shí)踐，最后介紹vivo存儲(chǔ)系統(tǒng)在糾刪碼技術(shù)上的一些探索；
• 下篇重點(diǎn)展開(kāi)介紹存儲(chǔ)團(tuán)隊(duì)在糾刪碼領(lǐng)域的研究成果及糾刪碼研究成果在vivo存儲(chǔ)系統(tǒng)中的實(shí)踐，與工業(yè)界存儲(chǔ)產(chǎn)品中的糾刪碼相關(guān)指標(biāo)進(jìn)行全方位對(duì)比，以及未來(lái)的一些規(guī)劃。 

圖2：本文的組織結(jié)構(gòu)

注：本文當(dāng)中有大量的專業(yè)術(shù)語(yǔ)，不可能所有術(shù)語(yǔ)都去作個(gè)解釋，因此針對(duì)不懂的有些術(shù)語(yǔ)可以自行去搜索相關(guān)含義

一、相關(guān)背景

1.1 研究意義

分布式存儲(chǔ)系統(tǒng)為了降低成本往往采用大量廉價(jià)通用的服務(wù)器提供服務(wù)，然而這些服務(wù)器的磁盤的可靠性是個(gè)很大的問(wèn)題，其平均壽命在2-7年，還受外部環(huán)境因素的影響，受限于其機(jī)械構(gòu)造，磁盤會(huì)發(fā)生磁盤故障、扇區(qū)故障和不可檢測(cè)磁盤故障等。因此，分布式存儲(chǔ)系統(tǒng)為了提高原始數(shù)據(jù)的可靠性，副本和糾刪碼是兩種最常見(jiàn)的數(shù)據(jù)冗余方法。副本將原始數(shù)據(jù)復(fù)制到n份，并存儲(chǔ)到不同的存儲(chǔ)節(jié)點(diǎn)上，能夠容忍任意n-1個(gè)節(jié)點(diǎn)失效，其缺點(diǎn)是存儲(chǔ)開(kāi)銷大。糾刪碼則以計(jì)算資源換存儲(chǔ)資源，采用了一種更高效的方式增加數(shù)據(jù)冗余，因此，糾刪碼成為了當(dāng)前云存儲(chǔ)的主流數(shù)據(jù)冗余方式，并且持續(xù)成為學(xué)術(shù)界和工業(yè)界在存儲(chǔ)領(lǐng)域的一種研究熱點(diǎn)。

圖3：使用糾刪碼技術(shù)公司列表

1.2 研究現(xiàn)狀

糾刪碼也被稱為糾錯(cuò)碼，它將原始數(shù)據(jù)編碼為數(shù)據(jù)量更大的編碼數(shù)據(jù)，并能夠利用編碼后的部分編碼數(shù)據(jù)恢復(fù)出原始數(shù)據(jù)。當(dāng)有節(jié)點(diǎn)發(fā)生故障時(shí)，要恢復(fù)這個(gè)節(jié)點(diǎn)的數(shù)據(jù)需要讀取多個(gè)節(jié)點(diǎn)的數(shù)據(jù)，這個(gè)過(guò)程會(huì)消耗大量的網(wǎng)絡(luò)帶寬和磁盤IO，另外解碼復(fù)雜度對(duì)業(yè)務(wù)可用性和數(shù)據(jù)可靠性也有影響，解碼復(fù)雜度越高，則臨時(shí)修復(fù)時(shí)延就高，從而增加業(yè)務(wù)讀取時(shí)延；因此，影響糾刪碼好壞的指標(biāo)很多，主要有如下一些指標(biāo)：以下指標(biāo)都是以可靠性統(tǒng)一基準(zhǔn)的前提下進(jìn)行參考：

• 【編碼復(fù)雜度】編碼復(fù)雜度決定了數(shù)據(jù)寫入的時(shí)延
• 【解碼復(fù)雜度】解碼復(fù)雜度決定了讀取的時(shí)延以及節(jié)點(diǎn)故障時(shí)數(shù)據(jù)臨時(shí)修復(fù)及永久修復(fù)的時(shí)延
• 【修復(fù)網(wǎng)絡(luò)帶寬】節(jié)點(diǎn)故障時(shí)數(shù)據(jù)修復(fù)所需消耗的整體網(wǎng)絡(luò)帶寬，這個(gè)指標(biāo)非常關(guān)鍵
• 【修復(fù)磁盤IO】磁盤IO消耗和網(wǎng)絡(luò)帶寬一般成正比，考慮大部分存儲(chǔ)服務(wù)器是高密服務(wù)器，一般網(wǎng)絡(luò)會(huì)是瓶頸
• 【修復(fù)節(jié)點(diǎn)數(shù)】修復(fù)節(jié)點(diǎn)數(shù)減少，往往也就降低了修復(fù)需要的網(wǎng)絡(luò)帶寬 
• 【更新復(fù)雜度】更新復(fù)雜度是指一份數(shù)據(jù)有少量更新操作，比如更新一兩個(gè)字節(jié)很頻繁所涉及的相關(guān)操作復(fù)雜度
• 【存儲(chǔ)開(kāi)銷】這個(gè)指標(biāo)是指的編碼效率，編碼效率越高，存儲(chǔ)開(kāi)銷越低
• 【參數(shù)限制】比如糾刪碼的碼長(zhǎng)受不受限制等等

以應(yīng)用最為廣泛的【n,k】RS碼【2】為例，RS的碼長(zhǎng)為n，碼的維度為k，當(dāng)出現(xiàn)有節(jié)點(diǎn)故障時(shí)，需要k個(gè)節(jié)點(diǎn)進(jìn)行恢復(fù)，同時(shí)可以容忍n-k個(gè)節(jié)點(diǎn)的故障，這種編碼也被稱為最大距離可分糾刪碼MDS【3】，對(duì)應(yīng)上述指標(biāo)也就意味著相同的容錯(cuò)能力下RS碼的存儲(chǔ)開(kāi)銷小，另外RS碼的碼長(zhǎng)不受限制，這也是RS碼如此受歡迎的原因；而在通信領(lǐng)域大殺四方的LDPC【4】糾錯(cuò)碼在存儲(chǔ)領(lǐng)域應(yīng)用較少，原因就是因?yàn)長(zhǎng)DPC不滿足MDS特性，容錯(cuò)能力不限，意味著相同的容錯(cuò)能力LDPC需要更大的存儲(chǔ)開(kāi)銷, LDPC更多是應(yīng)用在磁盤內(nèi)部的冗余；而得益于早期在RAID5和RAID6中的廣泛使用，具有MDS特性的陣列糾刪碼也被嘗試著應(yīng)用在分布式存儲(chǔ)系統(tǒng)當(dāng)中，MDS陣列碼相對(duì)于RS碼全是異或操作，編解碼相對(duì)RS碼復(fù)雜度低，但是同時(shí)相關(guān)參數(shù)有所受限，這也抑制了它在分布式存儲(chǔ)的廣泛應(yīng)用；常見(jiàn)的陣列碼有EVENODD碼【5】、RDP碼【6】、STAR碼【7】支持3容錯(cuò)、Liberation碼相對(duì)EVENODD更新復(fù)雜度接近理論下界【8】，ZigZag碼【9】磁盤IO開(kāi)銷達(dá)理論下界，Blaum-Roth碼【10】基于多項(xiàng)式環(huán)上構(gòu)造的MDS陣列碼，相對(duì)于RS是編解碼復(fù)雜度要低些。

另外針對(duì)RS碼高昂的網(wǎng)絡(luò)修復(fù)帶寬，涌現(xiàn)出一類再生碼【11】來(lái)降低修復(fù)中所要消耗的帶寬。再生碼是一類通過(guò)允許節(jié)點(diǎn)發(fā)送編碼過(guò)的數(shù)據(jù)來(lái)使得修復(fù)中可最小化修復(fù)帶寬的糾刪碼，其可在不增加存儲(chǔ)開(kāi)銷的情況下顯著降低修復(fù)帶寬。Dimakis等人將再生碼分為兩大類：MSR碼【23-47】和MBR碼【12,13】。MBR碼是最小化修復(fù)帶寬主要分為Polygonal MBR Code【14】和Product-Matrix MBR Code【15】；MSR碼是在最小化存儲(chǔ)開(kāi)銷下降低修復(fù)帶寬，又分為精確修復(fù)碼和功能修復(fù)碼，精確修復(fù)碼是指通過(guò)修復(fù)可修復(fù)出原始丟失數(shù)據(jù)，功能修復(fù)碼則不保證，數(shù)據(jù)讀取每次都需要進(jìn)行解碼操作。比如Hu等人提出了一種功能性MSR碼F-MSR【16】，精確性MSR研究主要基于Product-Matrix MSR【26】，還有比如Butterfly碼【48】、Coupled Layer Code碼【38-40】等當(dāng)前已經(jīng)在工業(yè)界有所應(yīng)用的再生碼。最近又有一些工作【18,19,20】是針對(duì)跨機(jī)架帶寬和機(jī)架內(nèi)帶寬進(jìn)行區(qū)分，為最小化跨機(jī)架帶寬為目標(biāo)減少修復(fù)帶寬。降低修復(fù)帶寬還有一些其它的研究工作，比如2013年Rashmi等人提出Piggybacking框架【22】，框架以MDS碼為基本碼通過(guò)將子條帶數(shù)據(jù)嵌入其它條帶來(lái)顯著降低修復(fù)帶寬，Piggybacking框架的編碼設(shè)計(jì)也有很多研究成果?！?9-81】

針對(duì)修復(fù)節(jié)點(diǎn)數(shù)降低這個(gè)指標(biāo)，Huang等人提出了一種局部修復(fù)碼LRC【17,21】通過(guò)對(duì)傳統(tǒng)編碼數(shù)據(jù)塊進(jìn)行分組，并針對(duì)每組生成校驗(yàn)塊，從而使得單塊修復(fù)只需要組內(nèi)節(jié)點(diǎn)參與修復(fù)提高修復(fù)性能。但由于引入額外存儲(chǔ)開(kāi)銷，LRC沒(méi)達(dá)到存儲(chǔ)最優(yōu)。但由于LRC的簡(jiǎn)易性，工業(yè)界有很多的實(shí)踐反饋，因此LRC逐漸成為近年來(lái)糾刪碼領(lǐng)域的研究熱點(diǎn)【66-78】。LRC的一個(gè)分支MRC碼的研究PMDS也吸引了不少關(guān)注【49-60】，除了單節(jié)點(diǎn)修復(fù)相關(guān)的LRC碼的構(gòu)造，針對(duì)修復(fù)多個(gè)節(jié)點(diǎn)的LRC碼【62-65)】是一個(gè)研究方向，另外，結(jié)合LRC和RC的Local Regeration Code【61】也是個(gè)研究思路。

圖4：糾刪碼研究方向概覽

二、原理解析

2.1 基礎(chǔ)知識(shí)介紹

概念1：糾刪碼原理

糾刪碼通用由兩個(gè)參數(shù)n和k來(lái)進(jìn)行配置，稱為(n,k)編碼。在分布式系統(tǒng)當(dāng)中，通常將數(shù)據(jù)以固定大小的塊進(jìn)行組織，編碼時(shí)，存儲(chǔ)系統(tǒng)將k個(gè)數(shù)據(jù)塊進(jìn)行編碼生成額外的n-k = m個(gè)大小相同的校驗(yàn)塊，這樣n個(gè)數(shù)據(jù)塊和校驗(yàn)塊中有任意的磁盤節(jié)點(diǎn)故障，都可以通過(guò)其它的磁盤節(jié)點(diǎn)進(jìn)行解碼恢復(fù)丟失的數(shù)據(jù)。以下為糾刪碼的一個(gè)示意圖：

圖5：糾刪碼原理示意圖

概念2：Singleton頓界

假設(shè)C是一個(gè)參數(shù)為[n,k]的線性碼，則C的極小距離d≤n-k+1。以上表明一個(gè)線性碼的極小距離不會(huì)“太大”，無(wú)論怎樣努力，都不能夠構(gòu)造出一個(gè)參數(shù)為[n,k]的線性碼，使得它的極小距離大于n-k+1，這個(gè)n-k+1就稱為Singleton界。

概念3：MDS特性

一個(gè)參數(shù)為[n,k]的線性碼C，若滿足dmin(C)=n-k+1，則稱該碼為極大距離可分碼，簡(jiǎn)稱為MDS（Maximum Distance Separable）碼。

概念4：系統(tǒng)性

系統(tǒng)性就是系統(tǒng)中存儲(chǔ)了k個(gè)數(shù)據(jù)塊可用來(lái)直接存取，如果故障的節(jié)點(diǎn)沒(méi)包括數(shù)據(jù)塊，則不影響數(shù)據(jù)的讀取，系統(tǒng)性可降低讀取時(shí)延。非系統(tǒng)性則在每次讀取時(shí)都需要進(jìn)行解碼操作，讀取時(shí)延相對(duì)偏大。

2.2 經(jīng)典糾刪碼介紹

2.2.1 Reed-Solomon Code

RS碼最早是ECC領(lǐng)域的一種糾錯(cuò)算法，RS編碼算法是一種典型的系統(tǒng)編碼，也是一種典型的MDS性質(zhì)的編碼。

RS碼基本思想其實(shí)就是拉格朗日插值多項(xiàng)式，我覺(jué)得用拉格朗日插值多項(xiàng)式來(lái)推導(dǎo)RS碼相對(duì)于其它文獻(xiàn)的講解會(huì)更清晰，下面我們簡(jiǎn)單回顧一下拉格朗日插值多項(xiàng)式：對(duì)于任何k階的多項(xiàng)式函數(shù)f(x)=a0+a1x+a2x^2+...+akx^k，我們很容易通過(guò)任意的n+1個(gè)點(diǎn)(x0, f(x0)，(x1,f(x1))，... (xk,f(xk))對(duì)這個(gè)多項(xiàng)式進(jìn)行恢復(fù)。

解碼過(guò)程如下：

那么RS碼是如何使用拉格朗日插值的呢？對(duì)于一個(gè)(n,k)的RS碼，假設(shè)a0,a1,...ak-1在Fq域內(nèi)的k個(gè)發(fā)送信號(hào)，我們?cè)贔q中采樣n個(gè)插值點(diǎn)x0,x1,...xn-1，則可以得到拉格朗日插值多項(xiàng)式為：

不難發(fā)現(xiàn)，前k個(gè)插值的多項(xiàng)式值有如下：

如果用矩陣來(lái)表示則為：

令上式的范德蒙德矩陣的逆*a向量 = b向量，則校驗(yàn)矩陣有如下：

【A|B】【A^-1】 a向量= 【E|BA^-1】* a向量 = 【a0,a1,...ak, c1,...cn-k】

這樣就有了經(jīng)典的(A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries For Storage)描述Reed-Solomon碼的編解碼方式如下圖所示：

圖6：RS編解碼示意圖

可以看出，RS(n,k)碼一個(gè)滿足MDS性質(zhì)的編碼，當(dāng)有數(shù)據(jù)丟失需要k個(gè)節(jié)點(diǎn)同時(shí)進(jìn)行恢復(fù)，另外，允許n-k+1個(gè)節(jié)點(diǎn)同時(shí)數(shù)據(jù)丟失。

2.2.2 MDS Array Code

MDS陣列碼是一類比較特殊的線性分組碼。陣列碼相對(duì)于RS碼避免了有限域計(jì)算，僅通過(guò)異或運(yùn)算實(shí)現(xiàn)糾刪碼。在這類碼中，符號(hào)均為m維的列向量，從而每個(gè)碼字都是一個(gè)m*n的二維陣列。絕大部分的陣列碼都是二元陣列碼，陣列碼的每一列可以全是數(shù)據(jù)位也可以既有數(shù)據(jù)位也有校驗(yàn)位。以下為一個(gè)m=2, n = 5, k = 3的陣列碼的示意圖：

圖7：陳列碼示意圖

不難看出該碼的奇偶校驗(yàn)方程為：

（1）EVENODD Code

EVENODD碼是一種允許丟雙列的容錯(cuò)碼，有兩列的校驗(yàn)列，是繼RS碼后最先運(yùn)用在RAID當(dāng)中的碼，它是一個(gè)(m-1)*(m+2)的陣列碼，其中m是一個(gè)素?cái)?shù)。第m+1列和第m+2列的編碼方式如下： 

另外，對(duì)于每一個(gè)l，0<= l <= m-2，可以通過(guò)以下方式獲取冗余符號(hào)：

可以看到，第m+1列校驗(yàn)碼的構(gòu)造是前m列的數(shù)據(jù)位的異或；第m+2列的校驗(yàn)碼的構(gòu)造則是通過(guò)追加沿斜率為1的對(duì)角線異或和來(lái)達(dá)到容錯(cuò)目的。EVENODD碼推出后，針對(duì)斜率不為1引入到糾刪碼的研究作為EVENODD碼的推廣為也就不足為奇。

圖8：EVENODD碼示意圖

（2）RDP Code

RDP碼的碼字結(jié)構(gòu)與EVENODD碼非常類似，只是比EVENODD碼少了一個(gè)數(shù)據(jù)列，是一個(gè)(m-1)*(m+1)陣列碼，其中m是一個(gè)素?cái)?shù)。RDP相對(duì)于EVENODD編解碼復(fù)雜度都要低不少，因此在RAID應(yīng)用廣泛。

RDP碼的編碼結(jié)構(gòu)示意框圖如下所示：

圖9：RDP碼示意圖

2.2.3 Regeration Code

在討論再生碼這前我們來(lái)分析一下存儲(chǔ)開(kāi)銷和修復(fù)開(kāi)銷的關(guān)系，從定性分析，我們很容易理解，當(dāng)碼率越大，存儲(chǔ)空間效率越高，修復(fù)所需要的數(shù)據(jù)量就越大。A.G.Dimakis等人首次利用信息流圖推導(dǎo)出存儲(chǔ)開(kāi)銷與修復(fù)開(kāi)銷滿足以下：

其中，alpha代表每個(gè)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)量，belta代表修復(fù)過(guò)程中每個(gè)參與節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量，d代表輔助節(jié)點(diǎn)的個(gè)數(shù)。那么存儲(chǔ)開(kāi)銷為所有節(jié)點(diǎn)存儲(chǔ)量的總和。n* alpha。而修復(fù)開(kāi)銷是所有參與修復(fù)的存儲(chǔ)節(jié)點(diǎn)所需要傳輸?shù)臄?shù)據(jù)量，d* belta。不難看出，alpha和belta不可能同時(shí)最小，alpha最小也就是M/k；belta最小也就是上式所有的(d-i)* belta都最小，可以求得d * belta = 2Md/(2kd-k^2+k)。

圖10：再生碼信息流圖

（1）MSR

MSR全稱為最小存儲(chǔ)再生碼Minimum Storage Regenerating碼，不難理解，MSR是保證了存儲(chǔ)消耗最小，所以MSR的存儲(chǔ)數(shù)據(jù)塊大小和失效修復(fù)帶寬值計(jì)算公式如下：

具體的編碼方式就不介紹了，在下一章節(jié)介紹的Clay碼就是MSR的一種工業(yè)上的應(yīng)用MSR碼。通過(guò)公式不難看出，d越大，修復(fù)開(kāi)銷越小。MSR的研究方向?qū)W術(shù)界和工程界側(cè)重點(diǎn)有所有同，學(xué)術(shù)界是不考慮分包數(shù)大小，為了不斷逼近最小的修復(fù)帶寬去盡可能設(shè)計(jì)MSR碼或者固定分包數(shù)然后在固定分包數(shù)下不斷的去降低修復(fù)帶寬；而工程界則更多考慮設(shè)計(jì)出分包數(shù)不高但是修復(fù)帶寬低的MSR碼，因?yàn)樾枰紤]工程實(shí)現(xiàn)。

（2）MBR

MBR全稱為最小帶寬再生碼Minimum Bandwidth Regenerating，不難理解，MBR是保證了單節(jié)點(diǎn)失效修復(fù)帶寬最小，所以MBR的存儲(chǔ)數(shù)據(jù)塊大小和失效修復(fù)帶寬值計(jì)算公式如下：

MBR相對(duì)于MSR實(shí)用性沒(méi)有那么高，原因是因?yàn)榉植际较到y(tǒng)更多的是在存儲(chǔ)開(kāi)銷最小化的情況去盡量降低修復(fù)帶寬，因而MBR的研究熱度沒(méi)有MSR那么高。

2.2.4 Locally Repairable Code

局部修復(fù)碼則是通過(guò)一類增加額外的存儲(chǔ)來(lái)將數(shù)據(jù)修復(fù)盡可能在少量節(jié)點(diǎn)內(nèi)完成，從而達(dá)到大大降低網(wǎng)絡(luò)開(kāi)銷操作的糾刪碼。由于引入了額外的存儲(chǔ)開(kāi)銷，局部修復(fù)碼并沒(méi)有達(dá)到存儲(chǔ)最優(yōu)。但是局部修復(fù)碼實(shí)現(xiàn)簡(jiǎn)單，因此生產(chǎn)環(huán)境有了很多的實(shí)踐，當(dāng)前，LRC編碼成為最近幾年糾刪碼研究領(lǐng)域的一個(gè)熱點(diǎn)研究方向。

圖11：LRC碼示意圖

Singleton-型上界：

針對(duì)于一個(gè)(n,k,r)的局部修復(fù)碼，即碼長(zhǎng)為n的碼中有k個(gè)信息位和具有局部修復(fù)性r，則有一個(gè)經(jīng)過(guò)證明的該碼的最小距離d(C)滿足上界如下：

任何一個(gè)達(dá)到這個(gè)界的局部修復(fù)碼稱為最優(yōu)局部修復(fù)碼。因此，設(shè)計(jì)達(dá)到最優(yōu)局部修復(fù)的碼是LRC方向的一個(gè)研究熱點(diǎn)。

上述局部修復(fù)碼只能修復(fù)一個(gè)故障節(jié)點(diǎn)，多個(gè)故障節(jié)點(diǎn)沒(méi)有考慮，學(xué)術(shù)界針對(duì)多個(gè)故障節(jié)點(diǎn)的LRC修復(fù)引入了(n,k,r,gama)-局部修復(fù)碼，針對(duì)多個(gè)故障節(jié)點(diǎn)修復(fù)的局部修復(fù)碼滿足上界如下：

2.2.5 piggyback框架

piggyback框架嚴(yán)格意義上是MSR的一個(gè)子集，piggyback框架的核心思想是通過(guò)擴(kuò)展后MDS碼的子條帶數(shù)據(jù)嵌入到其他子條帶的操作，在不改變?cè)芯幋a結(jié)構(gòu)的情況下顯著降低修復(fù)帶寬。

例如，以一個(gè)（4，2）MDS碼如圖所示，它有兩個(gè)子條帶，每個(gè)子條帶上分別有兩個(gè)信息數(shù)據(jù)，每個(gè)子條帶的后兩位存儲(chǔ)該條帶的數(shù)據(jù)線性組合，圖左1為MDS碼，圖左2為piggyback編碼，我們來(lái)分析一下右圖1和右圖2兩種節(jié)點(diǎn)故障的情況下修復(fù)帶寬的消耗情況：

（1）右圖1修復(fù)：傳統(tǒng)MDS碼：任意2個(gè)節(jié)點(diǎn)的2個(gè)符號(hào)來(lái)修復(fù)；piggyback碼：b2, b1+b2, b1+2b2+a1這三個(gè)符號(hào)可以修復(fù)a1, b1兩個(gè)符號(hào)；

（2）右圖2修復(fù)：傳統(tǒng)MDS碼：任意2個(gè)節(jié)點(diǎn)的2個(gè)符號(hào)來(lái)修復(fù)；piggyback碼：b1,b1+b2, 2a2-2b2-b1這三個(gè)符號(hào)可以修復(fù)a2,b2兩個(gè)符號(hào)。

圖12：PiggyBack框架示意圖

三、糾刪碼行業(yè)探索與實(shí)踐

在第二大章節(jié)以經(jīng)對(duì)當(dāng)前糾刪碼幾個(gè)核心領(lǐng)域的編碼原理進(jìn)行了闡述，本章則介紹這幾個(gè)核心領(lǐng)域的糾刪碼在工業(yè)界的應(yīng)用?；旧厦糠N類型的糾刪碼都或多或少在工業(yè)界有具體的編碼算法及實(shí)踐經(jīng)驗(yàn)。為了保持和第二章的順序保持一致，本章也從RS碼、陣列碼、RC、LRC、PiggyBack這幾個(gè)方向應(yīng)用于工業(yè)界的具體編碼順序進(jìn)行詳細(xì)介紹。

3.1 RS：CRS

首先是應(yīng)用最為廣泛，也是最成熟的RS碼，當(dāng)前工業(yè)界大多數(shù)的糾刪碼都是基于該編碼實(shí)現(xiàn)的。雖然RS碼的修復(fù)帶寬一直是一個(gè)痛點(diǎn)，但是由于其基本上每家公司的最早的糾刪碼算法上線都是基于RS完成的。比如早期的Google、AWS、阿里、騰訊、華為、百度等公有云廠商。

3.2 陣列碼：HashTag

An alternate construction of an access-optimal regenerating code with optimal sub-packetization level

3.3 MSR：Butterfly

butterfly是FAST 2016年的一篇論文提出的編碼算法，最多可校正2個(gè)節(jié)點(diǎn)故障的數(shù)據(jù)丟失，算法只涉及XOR操作，性能較好。節(jié)點(diǎn)故障后只需要所有節(jié)點(diǎn)的1/2數(shù)據(jù)參數(shù)修復(fù)。由于編碼操作用線相連對(duì)應(yīng)符號(hào)位看起來(lái)像蝴蝶一樣，如下圖所示，所以取名butterfly code。

圖13：Butterfly碼示意圖

編碼方法：

首先數(shù)據(jù)符號(hào)需要轉(zhuǎn)換成一個(gè)bit矩陣2^(k-1) * k記為Dk，用矩陣表示如下：

其中，A,B是2^(k-2) * (k-1)的bit矩陣，a,b則是一個(gè)包含2^(k-2)個(gè)元素的列向量。如果把 butterfly編碼后的碼字記為：Ck = (Dk?1 k ,...,D0 k ,H,B),則不難看出，H,B分別帶為butterfly后的一個(gè)水平校驗(yàn)列和butterfly校驗(yàn)列。H,B的生成遵循如下遞歸準(zhǔn)則：

如果 k = 2，那么有：

如果 k > 2，那么有：

其中，Pk帶表一個(gè)包含2^k * 2^k個(gè)元素的矩陣，矩陣的副對(duì)角線元素為1，其余元素為0。下圖為一個(gè)k = 4的 butterfly編碼：

圖14：k=4 Butterfly編碼構(gòu)造

3.4 MSR：Clay

Clay碼是FAST 2018年的一篇論文提出的編碼算法，Clay碼能夠?qū)⒁话愕腗DS碼轉(zhuǎn)化為MSR碼，Clay碼包含兩個(gè)特點(diǎn)：1 將MDS碼分層處理；2 分層之間數(shù)據(jù)耦合，以（4，2）Clay碼為例，為了更形象了解編碼方式，將編碼后的數(shù)據(jù)放在棱形柱上，其中alpha = 4，也就是有4層，原始數(shù)據(jù)如下：

圖15：原始數(shù)據(jù)結(jié)構(gòu)

圖中被耦合的數(shù)據(jù)用黃色表示，耦合關(guān)系如上圖右虛線表示，黃色數(shù)據(jù)塊存儲(chǔ)的是耦合之后的數(shù)據(jù)，也就是不再是系統(tǒng)碼，相當(dāng)于解碼需要進(jìn)行解耦合才能得到原始數(shù)據(jù)。

圖16：CLAY編碼結(jié)構(gòu)

當(dāng)有一個(gè)節(jié)點(diǎn)失效后，CLAY碼的修復(fù)過(guò)程如下：

圖17：CLAY修復(fù)結(jié)構(gòu)

Clay 修復(fù)該節(jié)點(diǎn)失效只需要第二層和第三層的剩余數(shù)據(jù)塊（如上圖（中）所示），修復(fù)步驟如下：

• 兩個(gè)耦合的數(shù)據(jù)塊(b_3,d_1) 和[b_3, d_1] 解耦得到b3 和d1，如上圖（右）；
• 第二層通過(guò)b1，b3 的MDS 解碼得到b_0, b_2，第四層MDS 解碼得到d_0，d_2；
• 利用第二層中[a_2, b_0] 和步驟2 得到的b_0 得到a_2，同理得到c_2。

簡(jiǎn)單推導(dǎo)可以發(fā)現(xiàn)其他三個(gè)節(jié)點(diǎn)也可以以最小開(kāi)銷完成數(shù)據(jù)修復(fù)。

3.5 LRC：azure、yottachain LRC

局部可恢復(fù)碼LRC是微軟在2012年FAST發(fā)表的一篇論文，該論文同時(shí)也是當(dāng)年FAST的best paper。核心思路就是通過(guò)引入局部校驗(yàn)位來(lái)輔助全局校驗(yàn)位進(jìn)行節(jié)點(diǎn)故障后的修復(fù)，由于局部校驗(yàn)節(jié)點(diǎn)的存在，所以當(dāng)有一個(gè)節(jié)點(diǎn)故障的時(shí)候可以只用局部少數(shù)節(jié)點(diǎn)進(jìn)行恢復(fù)，而不需要全局節(jié)點(diǎn)進(jìn)行恢復(fù)提升修復(fù)帶寬。以下以（6，2，2）LRC為例進(jìn)行介紹：

圖18：全局&局部校驗(yàn)示意圖

如上圖所示px,py為局部校驗(yàn)節(jié)點(diǎn)，p0,p1為全局校驗(yàn)節(jié)點(diǎn)，不難看出，雖然LRC有4個(gè)校驗(yàn)節(jié)點(diǎn)，但是LRC不滿足MDS性質(zhì)，比如x0,x1,x2,px 4個(gè)節(jié)點(diǎn)全都故障，LRC無(wú)論如何校造都是無(wú)法恢復(fù)的，因?yàn)槿中ｒ?yàn)節(jié)點(diǎn)只有2個(gè)，而py和x0,x1,x2無(wú)關(guān)，所以無(wú)論如何都恢復(fù)不出來(lái)x0,x1,x2這三個(gè)數(shù)據(jù)節(jié)點(diǎn)，這種故障也稱為信息論無(wú)法解碼故障；雖然LRC不能容忍這種場(chǎng)景的4個(gè)節(jié)點(diǎn)故障，但是如果LRC構(gòu)造得好，是可以達(dá)成其它場(chǎng)景的4個(gè)節(jié)點(diǎn)的故障，比如下圖所示：

圖19：4數(shù)據(jù)節(jié)點(diǎn)失效示意圖

a圖是x0,x1,p1三個(gè)節(jié)點(diǎn)故障，b圖是x0,x1,y0,y1四個(gè)節(jié)點(diǎn)故障，這類故障是有可能重建的也稱為信息論可解碼故障。那么LRC的研究就是設(shè)計(jì)合理的編碼方式來(lái)盡可能的覆蓋所有信息論可解碼故障場(chǎng)景，當(dāng)LRC的構(gòu)造方式覆蓋了所有信息論可解碼場(chǎng)景則稱LRC碼符合Maximally Recoverable（MR）性質(zhì)。 (6，2，2)的校驗(yàn)位構(gòu)造方程如下：

然后該編碼構(gòu)造方法需要覆蓋所有理論可解碼故障場(chǎng)景比如以下三種典型場(chǎng)景：

（1）4個(gè)節(jié)點(diǎn)全故障，平均分布在6個(gè)數(shù)據(jù)節(jié)點(diǎn)

這種場(chǎng)景則不難看出要想可求解就必需保證：

G的行列為不為0，G矩陣是奇異矩陣。

（2）px,py中有一個(gè)故障，假設(shè)是py故障，則必須有：

（3）同理如果px,py全故障，則必須有：

因此，alpha，belta的取值必須滿足上述矩陣的行列式不為0。（6，2，2）LRC與（6，3）的RS對(duì)比不難發(fā)現(xiàn)：LRC可靠性略高，成本也略高，修復(fù)帶寬幾乎是原來(lái)的一半。

3.6 piggyback：Hitchhiker

piggyback框架的一個(gè)典型的工業(yè)界的應(yīng)用實(shí)踐場(chǎng)景是facebook在2014年提出的，當(dāng)時(shí)facebook的f4系統(tǒng)原本也是用（10，4）RS糾刪碼來(lái)降低冗余度，但是RS碼的修復(fù)帶寬非常高，據(jù)當(dāng)時(shí)統(tǒng)計(jì)數(shù)據(jù)，facebook一個(gè)PB級(jí)的集群中因?yàn)楣?jié)點(diǎn)恢復(fù)所需要消耗的網(wǎng)絡(luò)帶寬達(dá)到了180TB。所以facebook針對(duì)冷存集群提出了一種基于piggyback框架的Hitchhiker編碼來(lái)降低修復(fù)帶寬。

（1) Hitchhiker-XOR

傳統(tǒng)的(10,4)的RS編碼如下圖左1所示，引入piggyback框架后則編碼方式如下左2所示，Hitchhiker-XOR編碼方式如下右1所示：

圖20：Hitchhiker-XOR編碼示意圖

編碼：
4個(gè)校驗(yàn)單元：f1保持不變，f2引入a1,a2,a3的奇偶校驗(yàn)位，f3引入a4,a5,a6的奇偶校驗(yàn)位，f4引入a7,a8,a9,a10的奇偶校驗(yàn)位。

修復(fù)：
當(dāng)1-3有一個(gè)節(jié)點(diǎn)故障，則可以通過(guò)，b1-10,f1(b)中的任意10個(gè)但愿恢復(fù)出故障的bi，然后可以通過(guò)f2函數(shù)計(jì)算出f2(b)，再結(jié)合第2個(gè)子條帶的第2個(gè)校驗(yàn)單元以及a1-a3中的2個(gè)單元一起，可以計(jì)算出ai，這樣就把a(bǔ)i,bi修復(fù)出來(lái)了。 同理，當(dāng)4-6有一個(gè)節(jié)點(diǎn)故障時(shí)，也是一樣的，可以通過(guò)13個(gè)byte將ai,bi進(jìn)行恢復(fù)。

而當(dāng)7-10有一個(gè)節(jié)點(diǎn)故障時(shí)，則需要通過(guò)14個(gè)byte進(jìn)行恢復(fù)，原因是第2個(gè)子條帶的第4個(gè)校驗(yàn)單元是由a7,a8,a9,10四個(gè)組合，其中有一個(gè)失效，需要引入第1個(gè)子條帶的3個(gè)單元才能進(jìn)行恢復(fù)。

（2）Hitchhiker-XOR+

針對(duì)Hitchhiker-XOR算法，可以看到在第7-10節(jié)點(diǎn)故障時(shí)需要14個(gè)Bytes進(jìn)行修復(fù)，XOR+通過(guò)對(duì)RS碼進(jìn)行適當(dāng)限制來(lái)降低這一部分的開(kāi)銷，限制條件如下：4個(gè)校驗(yàn)單元的函數(shù)f需要有一個(gè)滿足：ALL-XOR性質(zhì)，也就是子條帶數(shù)據(jù)全部進(jìn)行異或操作的同時(shí)滿足MDS性質(zhì)。通過(guò)該限制，則兩個(gè)子條帶的校驗(yàn)單元的編碼方式如下圖所示：

圖21：Hitchhiker-XOR+編碼示意圖

修復(fù)： 

不難看出，1-9節(jié)點(diǎn)故障時(shí)的修復(fù)是和Hitchhiker-XOR是完全一樣的，只需要13個(gè)bytes進(jìn)行修復(fù)，第10個(gè)節(jié)點(diǎn)故障時(shí)，則通過(guò)第2個(gè)子條帶的1-10，13，14單元和第1條帶的12單元可以恢復(fù)a10,b10，不難看出，恢復(fù)節(jié)點(diǎn)10也只需要13個(gè)bytes。

所以Hitchhiker-XOR+相對(duì)于Hitchhiker-XOR限制了RS碼構(gòu)造的條件，但進(jìn)進(jìn)一步降低了部分?jǐn)?shù)據(jù)修復(fù)的開(kāi)銷。

（3）Hitchhier-NoXOR

這種編碼是針對(duì)于Hitchhier-XOR+是引入了限制條件，為了消除這個(gè)限制條件，可以通過(guò)有限域運(yùn)算的方式來(lái)達(dá)到Hitchhier-XOR+同樣的效果，但是可以消除RS的校驗(yàn)生成限制，與此同時(shí)也是通過(guò)有限域運(yùn)算開(kāi)銷來(lái)替換XOR操作。

圖22：Hitchhier-NoXOR編碼示意圖

以上編碼方式可以擴(kuò)展到任意的(k,r)，對(duì)于不同的k,r參數(shù)，HH碼相對(duì)傳統(tǒng)RS碼可以降低25%-45%不等的開(kāi)銷。

3.7 糾刪碼對(duì)比

（n,k）糾刪碼，數(shù)據(jù)大小為M，劃分為k份，生成m份校驗(yàn)數(shù)據(jù) k + m = n，則相關(guān)糾刪碼算法的相關(guān)開(kāi)銷和性質(zhì)總結(jié)如下：

圖23：糾刪碼算法相關(guān)維度對(duì)比

四、vivo 糾刪碼探索與實(shí)踐

4.1 線上EC方案介紹

vivo對(duì)象存儲(chǔ)的EC方案是采用RS糾刪碼，前面章節(jié)已經(jīng)介紹過(guò)RS碼是通過(guò)構(gòu)造生成矩陣來(lái)編碼數(shù)據(jù)塊。生成矩陣可以采用范德蒙德矩陣，原因是因?yàn)榉兜旅傻戮仃囀强赡娴?，另外，還有一種矩陣是也可逆矩陣那就是Cauchy矩陣，Cauchy矩陣是由兩個(gè)交集為空的集合構(gòu)成的矩陣，具體為：令C = [c(i,j)]m*n，有集合X = {x1,x2,...xm}，Y = {y1,y2, ...,yn}，且X交集Y={空}。矩陣C中的元素cij滿足：

不難理解，如果不做優(yōu)化，柯西編解碼過(guò)程會(huì)充斥著大量的有限域的乘法和加法運(yùn)算，為了降低復(fù)雜度，通過(guò)利用有限域任何一個(gè)GF（2^w）域上的元素都可以映射到GF(2)域上的一個(gè)二進(jìn)制矩陣，例如，GF(2^3)域中的元素可以表示成GF（2）域中的二進(jìn)制矩陣：

圖24：GF(2^3)在GF(2)映射矩陣

其中，M ( e )的第i 列為V ( e ? 2^ (i ? 1 )) 其中e ? 2^(i-1) 為G F ( 2 ^3 ) )上的乘法。

所以基于Cauchy矩陣的RS編碼方案可以優(yōu)化為bit-matrix為生成矩陣，原有的有限域上的乘法和加法也變成了有限域的“與運(yùn)算”和“XOR”運(yùn)算，從而提高編碼效率。

在真正實(shí)現(xiàn)的時(shí)候， vivo糾刪碼的CRS編碼和jeasure的CRS編碼一樣，針對(duì)bit-matrix在GF(2)有限域的與和OXR操作進(jìn)行也進(jìn)一步優(yōu)化，就是通過(guò)將bit-matrix轉(zhuǎn)化為一個(gè)schedule的方式，也就是一個(gè)五元組，其中，op操作是O,1對(duì)應(yīng)是拷貝還是XOR，sd是源數(shù)據(jù)的id，sb為源數(shù)據(jù)中bit位的相對(duì)id，dd和db則為目的校驗(yàn)數(shù)據(jù)的id和校驗(yàn)數(shù)據(jù)bit位id。如下圖針對(duì)一個(gè)k = 3, w = 5的bit-matrix對(duì)應(yīng)的schedule操作為如下：

圖25：bitmatrix的schedule操作

不難看出，通過(guò)schedule方式轉(zhuǎn)化后編解碼操作簡(jiǎn)化了好多，以下為一段C++代碼：

圖26：存儲(chǔ)糾刪碼schedule代碼片斷

4.2 生產(chǎn)環(huán)境分析

注：這里的生產(chǎn)環(huán)境分析章節(jié)是參照常規(guī)的業(yè)界生產(chǎn)環(huán)境部署規(guī)范進(jìn)行假設(shè)和模擬，不代表本公司的真實(shí)生產(chǎn)環(huán)境。

4.2.1 IDC資源

現(xiàn)在很多公司為了能夠防止數(shù)據(jù)中心因?yàn)槟承┎豢煽沽Ρ热缱匀粸?zāi)害、斷電等極端情況導(dǎo)致整體故障而造成數(shù)據(jù)丟失和服務(wù)中斷建設(shè)了多個(gè)數(shù)據(jù)中心，分布式存儲(chǔ)服務(wù)可以通過(guò)將數(shù)據(jù)打散存儲(chǔ)在多個(gè)不同的數(shù)據(jù)中心來(lái)保證當(dāng)某個(gè)IDC故障后依然能提供穩(wěn)定可靠的存儲(chǔ)服務(wù)。糾刪碼技術(shù)通過(guò)將數(shù)據(jù)分塊和校驗(yàn)碼分塊均勻打散到不同數(shù)據(jù)中心，實(shí)現(xiàn)同城容災(zāi)冗余。當(dāng)某個(gè)數(shù)據(jù)中心不可用時(shí)，另外其他數(shù)據(jù)中心的數(shù)據(jù)依舊可以正常讀取和寫入，保障客戶數(shù)據(jù)持久存儲(chǔ)不丟失，維持客戶業(yè)務(wù)數(shù)據(jù)連續(xù)性和高可用。

以下為一個(gè)同城冗余的示意圖【引用自公有云多region多AZ機(jī)構(gòu)】

圖27：同城冗余機(jī)房示意圖

4.2.2 存儲(chǔ)資源

隨著近年互聯(lián)網(wǎng)業(yè)務(wù)的非速發(fā)展，互聯(lián)網(wǎng)業(yè)務(wù)數(shù)據(jù)的規(guī)模及多樣性也越來(lái)越復(fù)雜，各大公司的存儲(chǔ)型服務(wù)器由于歷史原因迭代過(guò)很多的版本，從4xTB到1x00TB容量不等的演進(jìn)了有多種套餐類型，因此生產(chǎn)環(huán)境很難避免的有多種存儲(chǔ)類型的服務(wù)器共存的情況出現(xiàn)，服務(wù)器的攜帶的HDD硬盤的塊數(shù)和單盤的容量也不盡相同，單盤容量從4T到20多T不等，服務(wù)器攜帶的硬盤數(shù)目也從12到60多不等，還有各種其它類型的存儲(chǔ)陣列比如JBOD產(chǎn)品（由多塊60TB的硬盤組成的存儲(chǔ)資源陣列）。

4.2.3 網(wǎng)絡(luò)資源

如第1章所述，糾刪碼技術(shù)在海量分布式存儲(chǔ)系統(tǒng)的引入為企業(yè)節(jié)省了大量的成本，但是在節(jié)約成本的同時(shí)，由于糾刪碼技術(shù)特點(diǎn)也帶了帶寬成本的上升，基于糾刪碼冗余的分布式系統(tǒng)在出現(xiàn)節(jié)點(diǎn)或硬盤故障時(shí)，需要多個(gè)節(jié)點(diǎn)進(jìn)行同時(shí)恢復(fù)，這就需要大量的網(wǎng)盤帶寬，而且以（n,k）RS碼為例，1個(gè)RS碼的節(jié)點(diǎn)故障，需要n個(gè)節(jié)點(diǎn)進(jìn)行恢復(fù)，而副本技術(shù)的系統(tǒng)只需要1個(gè)節(jié)點(diǎn)參與，相當(dāng)于糾刪碼技術(shù)的系統(tǒng)網(wǎng)絡(luò)帶寬放大了n倍速。因此，在IDC內(nèi)部和IDC機(jī)房之間的帶寬就成為了糾刪碼技術(shù)實(shí)施的關(guān)鍵因素。

以下為業(yè)界某司的IDC之間的網(wǎng)絡(luò)拓?fù)浼軜?gòu)如下：【引用自公有云多region多AZ機(jī)構(gòu)】

圖28：業(yè)界IDC帶寬拓?fù)浼軜?gòu)

而由于成本上的考慮，往往數(shù)據(jù)中心與數(shù)據(jù)中心之間的專線帶寬都不會(huì)太高，但是傳統(tǒng)的糾刪碼技術(shù)在提供低冗余度和高可靠的同時(shí)帶來(lái)的是大理的修復(fù)帶寬的成本，因此，跨IDC之間的糾刪碼技術(shù)不得不考慮IDC之間的帶寬不大這個(gè)因素。

4.2.4 業(yè)務(wù)特性

• 對(duì)象存儲(chǔ)業(yè)務(wù)特點(diǎn)1：通常接入對(duì)象存儲(chǔ)的大規(guī)模業(yè)務(wù)的更新的操作比較少，因此原有的更新的操作消耗帶寬成本高的痛點(diǎn)可以不考慮；
• 對(duì)象存儲(chǔ)業(yè)務(wù)特點(diǎn)2：通常接入對(duì)象存儲(chǔ)業(yè)務(wù)在線場(chǎng)景和離線場(chǎng)景區(qū)分比較明顯；大存儲(chǔ)業(yè)務(wù)呈現(xiàn)冷數(shù)據(jù)趨勢(shì)；
• 對(duì)象存儲(chǔ)業(yè)務(wù)特點(diǎn)3：互聯(lián)網(wǎng)行業(yè)的數(shù)據(jù)類型豐富，一般對(duì)跨AZ和不跨AZ的需求有所不同，數(shù)據(jù)可靠性的要求各有不同；可用性指標(biāo)各有不同。

4.3 vivo新糾刪碼方案

4.3.1 糾刪碼優(yōu)化思路

• 基于糾刪算法思考：通過(guò)對(duì)學(xué)術(shù)界和工業(yè)界的整體調(diào)研考慮實(shí)現(xiàn)復(fù)雜度和效果發(fā)現(xiàn)還是RS碼還是當(dāng)前工業(yè)界糾刪碼的主流，特別是對(duì)RS碼引入并行修復(fù)后非常的適合降低跨IDC之間的帶寬消耗；可以將大部分的帶寬消耗收斂到IDC內(nèi)部；
• 基于機(jī)房資源思考：基于多數(shù)據(jù)中心的數(shù)據(jù)分布考慮，糾刪碼可以考慮引入LRC，在數(shù)據(jù)中心內(nèi)部引入局部校驗(yàn)塊來(lái)進(jìn)行數(shù)據(jù)中心內(nèi)部的快速修復(fù)從而提高整體可靠性；
• 基于業(yè)務(wù)特性思考：根據(jù)互聯(lián)網(wǎng)業(yè)務(wù)的通用特性分析可以將離線在線存儲(chǔ)集群進(jìn)行分離；以及數(shù)據(jù)可靠性要求進(jìn)行規(guī)劃EC集群，比如不考慮機(jī)房容災(zāi)的業(yè)務(wù)可以在同一個(gè)數(shù)據(jù)中心內(nèi)部的不同Region進(jìn)行部署EC集群；
• 基于服務(wù)資源思考： 互聯(lián)網(wǎng)行業(yè)的存儲(chǔ)服務(wù)器資源的存儲(chǔ)和網(wǎng)卡配置迭代較快，線上這種異構(gòu)環(huán)境導(dǎo)致的線上擴(kuò)縮容操作都會(huì)引起集群可靠性的變化，因此引入可靠性評(píng)估模型對(duì)集群進(jìn)行近實(shí)時(shí)的預(yù)估；
• 基于恢復(fù)帶寬思考：優(yōu)化目標(biāo)是為了進(jìn)一步降低EC冗余度但同時(shí)可靠性不降低，因此恢復(fù)帶寬降低是一個(gè)重要優(yōu)化思路，因此在全局引入并行修復(fù)和在局部引入MSR糾刪修復(fù)的方式進(jìn)一步降低恢復(fù)帶寬。

4.3.2 可靠性模型設(shè)計(jì)

在優(yōu)化思路我們提到引入可靠性評(píng)估模型來(lái)對(duì)集群進(jìn)行近實(shí)時(shí)的預(yù)估，那么可靠性模型如何預(yù)估是合理的？當(dāng)前并沒(méi)有一個(gè)統(tǒng)一的可靠性評(píng)估方案，不過(guò)學(xué)術(shù)界基本都是基于馬爾可夫鏈的MTTDL模型來(lái)進(jìn)行EC的可靠性計(jì)算，工業(yè)界就沒(méi)有特別統(tǒng)一的可靠性評(píng)估方案，在調(diào)研了行業(yè)內(nèi)相關(guān)方案后我們的可靠性模型主要是基于MTTDL馬爾可夫鏈模型再結(jié)合我之前分享的一篇【分布式存儲(chǔ)系統(tǒng)的可靠性估算】形成特有的分布式存儲(chǔ)可靠性模型估算方案。這套方案是結(jié)合了兩種可靠性估算最合理的部分邏輯：MTTDL模型的理論嚴(yán)謹(jǐn)性 + 集群級(jí)磁盤故障的組合概率引入的必要性。

在介紹可靠性模型之前，我們先來(lái)看幾個(gè)概念如下圖所示：

圖29：系統(tǒng)故障處理流流程【時(shí)間線】

• MTTF：Mean Time To Failure，平均無(wú)故障時(shí)間，指系統(tǒng)無(wú)故障運(yùn)行的平均時(shí)間，取所有系統(tǒng)開(kāi)始正常遠(yuǎn)行到發(fā)生故障之間的時(shí)間段的平均值，如上圖的T1的平均值；
• MTTR：Mean Time To Repair，平均修復(fù)時(shí)間，指系統(tǒng)從發(fā)生故障到維修結(jié)束之間的時(shí)間段的平均值。如上圖的T2+T3的平均值；
• MTTDL：Mean Time to Data Loss，平均數(shù)據(jù)丟失時(shí)間，換個(gè)說(shuō)法也可以是系統(tǒng)兩次故障發(fā)生時(shí)間的間隔平均值，如上圖的T1+T2+T3的平均值。

（1）Markov可靠性模型

Markov可靠性模型是基于MTTDL進(jìn)行預(yù)估的，Markov可靠性模型是基于下圖來(lái)進(jìn)行狀態(tài)轉(zhuǎn)移的：

圖30：馬爾科夫鏈的故障狀態(tài)轉(zhuǎn)移模型

初始狀態(tài)為1狀態(tài)，1狀態(tài)為n塊磁盤都沒(méi)有故障的概率為1-n* ramda，從狀態(tài)1轉(zhuǎn)移到狀態(tài)2則是有n*ramda概率，狀態(tài)2恢復(fù)到1狀態(tài)則由u決定，狀態(tài)2轉(zhuǎn)移到狀態(tài)3的概率為1-(n-1)* ramda，則不難計(jì)算出維持2狀態(tài)的概率如上圖所示：

本文不對(duì)馬爾科夫鏈狀態(tài)轉(zhuǎn)移進(jìn)行詳細(xì)推導(dǎo)，僅給出最終的MTTDL的簡(jiǎn)化版計(jì)算公式如下：

（2）其它可靠性模型

Markov可靠性模型是把所有磁盤都用在了數(shù)據(jù)的條帶化處理，但是真實(shí)的線上環(huán)境集群可能非常龐大，整個(gè)集群的節(jié)點(diǎn)數(shù)會(huì)遠(yuǎn)大于進(jìn)行糾刪碼的n的大小，那么從集群角度看可靠性如何估算呢？我曾經(jīng)在21年有發(fā)表過(guò)一篇外發(fā)期刊【分布式存儲(chǔ)系統(tǒng)可靠性：系統(tǒng)量化估算】，這篇文章就是以生產(chǎn)環(huán)境以集群部署的角度進(jìn)行分析分布式存儲(chǔ)系統(tǒng)的可靠性如何估算，這篇文章相對(duì)于Markov可靠性模型一個(gè)最大的借鑒意義是它把集群內(nèi)的一個(gè)數(shù)據(jù)的條帶化組合引入到了可靠性估算，因此，新的可靠性估算模型可以結(jié)合Markov可靠性模型和集群條帶化組合比例進(jìn)行設(shè)計(jì)，更加具體的設(shè)計(jì)方案會(huì)在【糾刪碼技術(shù)在vivo存儲(chǔ)系統(tǒng)的演進(jìn)-下篇】中介紹。

4.3.3 多融合EC方案設(shè)計(jì)

根據(jù)對(duì)IDC資源、服務(wù)器資源、業(yè)務(wù)特性、網(wǎng)絡(luò)資源的分析，結(jié)合可靠性評(píng)估近實(shí)時(shí)系統(tǒng)的支撐，我們?cè)谠械?+4 CRS糾刪碼算法的基礎(chǔ)上進(jìn)行優(yōu)化，將整體的EC策略分為兩種如下圖所示：

圖31：多融合EC方案架構(gòu)圖

跨AZ-EC策略

核心業(yè)務(wù)數(shù)據(jù)有跨AZ存儲(chǔ)需求進(jìn)行機(jī)房數(shù)據(jù)容災(zāi)，但是同時(shí)也帶來(lái)在節(jié)點(diǎn)故障情況下有跨機(jī)房網(wǎng)絡(luò)帶寬的影響，因此EC策略是LRC+RS+并行修復(fù)+MSR結(jié)合的EC方式，針對(duì)不同的場(chǎng)景有不同的優(yōu)化措施：

• 當(dāng)只有一個(gè)數(shù)據(jù)節(jié)點(diǎn)故障情況下，通過(guò)在各機(jī)房的局部校驗(yàn)塊，只需要在機(jī)房?jī)?nèi)用MSR最小帶寬進(jìn)行快速修復(fù)；
• 當(dāng)只有一個(gè)局部校驗(yàn)節(jié)點(diǎn)故障下，也是通過(guò)在各機(jī)房的數(shù)據(jù)塊在機(jī)房?jī)?nèi)進(jìn)行快速修復(fù)；
• 當(dāng)只有一個(gè)全局校驗(yàn)節(jié)節(jié)點(diǎn)故障下，則可以通過(guò)一個(gè)機(jī)房的局部校驗(yàn)塊再結(jié)合其它機(jī)房的中間結(jié)果數(shù)據(jù)進(jìn)行并行恢復(fù)；條帶越寬，帶寬節(jié)省越多，比如單機(jī)房12數(shù)據(jù)塊，3機(jī)房可節(jié)省跨機(jī)房帶寬80%+；
• 當(dāng)有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)同時(shí)故障的情況下，才需要進(jìn)行跨機(jī)房傳輸數(shù)據(jù)修復(fù)，我們可以通過(guò)局部校驗(yàn)塊+其它機(jī)房中間結(jié)果結(jié)合+并行修復(fù)的形式來(lái)降低網(wǎng)絡(luò)帶寬消耗。

為了能描述清楚我們的策略，我們以（16，4，4）4機(jī)房，4個(gè)局部校驗(yàn)塊，4個(gè)全局校驗(yàn)塊，16個(gè)數(shù)據(jù)塊【如下圖所示】為例來(lái)說(shuō)明：

圖32：（16，4，4）LRC編碼拓?fù)?/span>

我們假設(shè)局部校驗(yàn)塊P1、P2、P3、P4的構(gòu)造按如下所示：

同樣按RS碼構(gòu)造方式，我們假設(shè)Q1、Q2、Q3、Q4的構(gòu)造按如下所示：

接下來(lái)我們來(lái)分析一下不同場(chǎng)景下的恢復(fù)情況：

• 只有一個(gè)數(shù)據(jù)節(jié)點(diǎn)或P節(jié)點(diǎn)故障：只需要在每個(gè)局部進(jìn)行即可，利用生成矩陣的逆矩陣：

• 只有一個(gè)Q節(jié)點(diǎn)故障：按原來(lái)的算法是需要D1-16全部參與進(jìn)行計(jì)算，但是我們分析可以發(fā)現(xiàn)生成矩陣是固定的，因此，完全可以在機(jī)房?jī)?nèi)部進(jìn)行中間運(yùn)算后再發(fā)送到故障機(jī)房進(jìn)行最終運(yùn)算得到，以Q2為例，只需要以下四個(gè)生成矩陣在各自機(jī)房與機(jī)房數(shù)據(jù)Di進(jìn)行中間結(jié)果運(yùn)算即可：

• 有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)故障：可以通過(guò)在集群運(yùn)行前先把所有可能的校驗(yàn)矩陣【如下圖所示】準(zhǔn)備好，然后再通過(guò)在各自機(jī)房與機(jī)房數(shù)據(jù)Di或Qj進(jìn)行中間結(jié)果的計(jì)算，最后在需要恢復(fù)機(jī)房進(jìn)行最終結(jié)果的合并計(jì)算得到恢復(fù)數(shù)據(jù)：

具體算法的詳細(xì)細(xì)節(jié)會(huì)在后續(xù)的【糾刪碼技術(shù)在vivo存儲(chǔ)系統(tǒng)的演進(jìn)-下篇】介紹，整體思路就是全局RS+并行修復(fù)結(jié)合局部MSR最小帶寬修復(fù)的策略來(lái)達(dá)到多AZ數(shù)據(jù)可靠性保障的目標(biāo)。

五、總結(jié)

云存儲(chǔ)領(lǐng)域針對(duì)糾刪碼技術(shù)的研究截止到現(xiàn)在仍然是學(xué)術(shù)界和工業(yè)界研究的熱點(diǎn)，如何能降低網(wǎng)絡(luò)的修復(fù)帶寬，降低存儲(chǔ)開(kāi)銷同時(shí)保證數(shù)據(jù)的可靠性的同時(shí)編解碼算法又能工程落地，編解碼復(fù)雜度又偏低，這些維度的考量衍生了各式各樣的糾刪碼編碼技術(shù)，vivo也在糾刪碼技術(shù)根據(jù)生產(chǎn)環(huán)境可落地的前提下在傳統(tǒng)RS碼的基礎(chǔ)上引入并行修復(fù)以利用LRC+MSR局部校驗(yàn)塊的組合來(lái)降低傳統(tǒng)LRC在生產(chǎn)環(huán)境上運(yùn)用導(dǎo)致的跨機(jī)房帶寬開(kāi)銷，從而較低的跨機(jī)房帶寬開(kāi)銷為高條帶低冗余度的EC策略提供了保障。隨著業(yè)務(wù)的發(fā)展，數(shù)據(jù)的存儲(chǔ)開(kāi)銷成本會(huì)越來(lái)越明顯，因此，針對(duì)糾刪碼技術(shù)的研究會(huì)是一個(gè)長(zhǎng)期的過(guò)程，本人也會(huì)時(shí)刻關(guān)注學(xué)術(shù)界和工業(yè)界的動(dòng)態(tài)，結(jié)合IDC、服務(wù)器、網(wǎng)絡(luò)及業(yè)務(wù)的特性進(jìn)行創(chuàng)新和優(yōu)化為業(yè)務(wù)持續(xù)助力。

參考文獻(xiàn)：

1. Reed I S, Solomon G. Polynomial Codes over Certain Finite Fields. Journal of the society for industrial and applied mathematics, 1960, 8(2):300-304
2. Plank J S, Ding Y. Note: Correction to the 1997 tutorial on Reed-Solomon coding.Software: Practice and Experience, 2005, 35(2):189-194
3. Shokrollahi A. LDPC codes: An Introduction. Technical report, 2003.
4. Blaum M, Brady J, Bruck J, et al. EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures. IEEE Transactions on computers (TOC), 1995, 44(2):192-202.
5. Corbett P, English B, Goel A, et al. Row-diagonal Parity for Double Disk Failure Correction. in: Proceedings of The 2nd USENIX Conference on File and Storage Technologies (FAST'04), Berkeley, CA, USA, March 31 - April 2, 2004, 1-14.
6. Huang C, Xu L. STAR: An Efficient Coding Scheme for Correcting Triple Storage Node Failures. IEEE Transactions on Computers (TOC), 2008, 57(7):889-901.
7. James S. Plank: The RAID-6 Liberation Codes. FAST 2008: 97-110
8. I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,2013.
9. Blaum M, Roth R, New array codes for multiple phased burst correction. IEEE Trans on Inform Theory, 1993,39(1): 66 ~ 77.
10. A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory,vol. 56, no. 9, pp. 4539–4551, Sep. 2010.
11. M. N. Krishnan and P. V. Kumar, “On MBR codes with replication,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 71–75.
12. N. B. Shah, “On Minimizing Data-Read and Download for Storage-Node Recovery,” IEEE Communications Letters, vol. 17, no. 5, pp. 964–967, 2013.
13. K. Rashmi, N. Shah, P. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed storage,” in Proc. 47th Annu. Allerton Conf. Communication, Control, and Computing, Urbana-Champaign, IL, Sep. 2009, pp. 1243–1249.
14. K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, 2011.
15. Y. Hu, H. C. H. Chen, P. P. C. Lee, and Y. Tang, “NCCloud: applying network coding for the storage repair in a cloud-of-clouds,” in Proc. 10th
    USENIX conference on File and Storage Technologies, San Jose, CA, USA,2012, p. 21.
16. Huang C, Simitci H, Xu Y, et al. Erasure Coding in Windows Azure Storage. in: Proceedings of USENIX Annual Technical Conference (ATC), Boston, MA, USA, June, 2012, USENIX.
17. Hu Y, Li X, Zhang M, et al. Optimal repair layering for erasure-coded data centers: From therory ot practive. ACM Transactions on Storage (TOS), 2017, 13(4):33.
18. Rashmi K, Nakkiran P, Wang J, et al. Having Your Cake and Eating It Too: jonintly Optimal Erasure Codes for I/O, Storage, and Network-bandwidth. in: Proceedings of USENIX Conference on File and Storage Technologies (FAST), Santa Clara, CA, USA, February, 2015, USENIX, 81-94.
19. Hou H, Lee P, Shum K, et al. Rack-aware regenerating codes for data centers. IEEE Transactions Information Theory, 2019,65(8):4730-4745.
20. Sathiamoorthy M, Asteris M, Papailiopoulos D, et al. XORing Elephants: Novel Erasure Codes for Big Data. in: Proceedings of VLDB Endowment. VLDB, March, 2013, 325-336.
21. RASHMI K, SHAN N B, RAMCHANDRAN K. A Piggybacking Design Framework for Read and Download-Efficient Distributed Storage Codes[J]. IEEE Transactions on Information Therory, 2017,63(9):5802-5820.
22. N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and
    Code Constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2134–2158, Apr. 2012.
23. Y.WuandA.G.Dimakis,“Reducingrepairtrafficforerasurecoding-basedstorageviainterferencealignment,”Proc.IEEEInternationalSymposium on Information Theory, Seoul, Korea, June 2009, pp. 2276–2280.
24. C.SuhandK.Ramchandran,“Exact-repairMDScodeconstructionusinginterferencealignment,”IEEETrans.Inf.Theory,vol.57,no.3,pp.1425–1442,Mar. 2011.
25. K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, Aug. 2011.
26. S. J. Lin, W. H. Chung, Y. S. Han, and T. Y. Al-Naffouri, “A Unified Form of Exact-MSR Codes via Product-Matrix Frameworks,” IEEE Trans Inf
    Theory, vol. 61, no. 2, pp. 873–886, Feb 2015.
27. D. Papailiopoulos, A. Dimakis, and V. Cadambe, “Repair Optimal Erasure Codes through Hadamard Designs,” IEEE Trans. Inf. Theory, vol. 59, no. 5,pp. 3021–3037, 2013.
28. V.Cadambe,S.A.Jafar,H.Maleki,K.Ramchandran,andC.Suh,“AsymptoticInterferenceAlignmentforOptimalRepairofMDSCodesinDistributed
    Storage,” IEEE Trans. Inf. Theory, vol. 59, no. 5, pp. 2974–2987, 2013.
29. I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,2013.
30. Z. Wang, I. Tamo, and J. Bruck, “On codes for optimal rebuilding access,” in Proc. 49th Annual Allerton Conference on Communication, Control, and Computing, Sept 2011, pp. 1374–1381.
31. V. R. Cadambe, C. Huang, J. Li, and S. Mehrotra, “Polynomial length MDS codes with optimal repair in distributed storage,” in Proc. Forty Fifth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA*, 2011, pp. 1850–1854.
32. Z. Wang, I. Tamo, and J. Bruck, “Long MDS codes for optimal repair bandwidth,” in Proc. IEEE International Symposium on Information Theory,Cambridge, MA, USA, 2012, pp. 1182–1186.
33. I. Tamo, Z. Wang, and J. Bruck, “Access Versus Bandwidth in Codes for Storage,” IEEE Trans. Inf. Theory, vol. 60, no. 4, pp. 2028–2037, 2014.
34. S. Goparaju, I. Tamo, and A. R. Calderbank, “An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes,” IEEE Trans. on Inf.Theory, vol. 60, no. 5, pp. 2770–2779, 2014.
35. B. Sasidharan, G. K. Agarwal, and P. V. Kumar, “A high-rate MSR code with polynomial sub-packetization level,” in Proc. IEEE International Symposium on Information Theory, 2015, pp. 2051–2055.
36. A.S.Rawat,O.O.Koyluoglu,andS.Vishwanath,“Progressonhigh-rateMSRcodes:Enablingarbitrarynumberofhelpernodes,”in Proc.Information Theory and Applications Workshop, La Jolla, CA, USA, 2016, pp. 1–6.
37. S. Goparaju, A. Fazeli, and A. Vardy, “Minimum Storage Regenerating Codes for All Parameters,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp.6318–6328, 2017.
38. G. K. Agarwal, B. Sasidharan, and P. V. Kumar, “An alternate construction of an access-optimal regenerating code with optimal sub-packetization level,” in Proc. Twenty First National Conference on Communications, Mumbai, India, 2015, pp. 1–6.
39. N. Alon, “Combinatorial nullstellensatz,” Combinatorics, Probability and Computing, vol. 8, no. 1-2, pp. 7–29, 1999.
40. N. Raviv, N. Silberstein, and T. Etzion, “Constructions of High-Rate Minimum Storage Regenerating Codes Over Small Fields,” *IEEE Trans. Inf.Theory, vol. 63, no. 4, pp. 2015–2038, 2017.
41. M. Ye and A. Barg, “Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth,” IEEE Trans. Inf. Theory, vol. 63, no. 4,pp. 2001–2014, 2017.
42. ——, “Explicit Constructions of Optimal-Access MDS Codes With Nearly Optimal Sub-Packetization,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp.6307–6317, 2017.
43. B. Sasidharan, M. Vajha, and P. V. Kumar, “An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level,Small Field Size and All-Node Repair,” CoRR, vol. abs/1607.07335, 2016.
44. J. Li, X. Tang, and C. Tian, “A generic transformation for optimal repair bandwidth and rebuilding access in MDS codes,” in Proc. IEEE International**Symposium on Information Theory, Aachen, Germany, June 2017, pp. 1623–1627.
45. S. B. Balaji and P. V. Kumar, “A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes,” CoRR, Accepted at ISIT**2018, vol. abs/1710.05876, 2017.
46. M. Vajha, S. B. Balaji, and P. V. Kumar, “Explicit MSR Codes with Optimal Access, Optimal Sub-Packetization and Small Field Size for d =k + 1, k + 2, k + 3,” CoRR, vol. abs/1804.00598, 2018.
47. E.E.Gad,R.Mateescu,F.Blagojevic,C.Guyot,andZ.Bandic,“Repair-optimalMDSarraycodesoverGF(2),”inProc.IEEEInternationalSymposium on Information Theory, Istanbul, Turkey, 2013, pp. 887–891.
48. P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the Locality of Codeword Symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934,2012.
49. S. B. Balaji and P. V. Kumar, “On partial maximally-recoverable and maximally-recoverable codes,” in Proc. IEEE International Symposium on
    Information Theory, Hong Kong, 2015, pp. 1881–1885.
50. M. Chen, C. Huang, and J. Li, “On the maximally recoverable property for multi-protection group codes,” in IEEE International Symposium on Information Theory, June 2007, pp. 486–490.
51. M. Blaum, J. L. Hafner, and S. Hetzler, “Partial-MDS Codes and Their Application to RAID Type of Architectures,” IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4510–4519, 2013.
52. G. Calis and O. O. Koyluoglu, “A General Construction for PMDS Codes,” IEEE Communications Letters, vol. 21, no. 3, pp. 452–455, 2017.
53. R. Gabrys, E. Yaakobi, M. Blaum, and P. H. Siegel, “Constructions of partial MDS codes over small fields,” in Proc. IEEE International Symposium on Information Theory, Aachen, Germany, 2017, pp. 1–5.
54. P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin, “Explicit Maximally Recoverable Codes With Locality,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5245–5256, 2014.
55. G. Hu and S. Yekhanin, “New constructions of SD and MR codes over small finite fields,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 1591–1595.
56. J. Chen, K. W. Shum, Q. Yu, and C. W. Sung, “Sector-disk codes and partial MDS codes with up to three global parities,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1876–1880.
57. M. Blaum, “Construction of PMDS and SD codes extending RAID 5,” CoRR, vol. abs/1305.0032, 2013.
58. M. Blaum, J. S. Plank, M. Schwartz, and E. Yaakobi, “Construction of Partial MDS and Sector-Disk Codes With Two Global Parity Symbols,” IEEE Trans. Inf. Theory, vol. 62, no. 5, pp. 2673–2681, 2016.
59. V.LalithaandS.V.Lokam,“Weightenumeratorsandhighersupportweightsofmaximallyrecoverablecodes,”inProc.53rdAnnualAllertonConference on Communication, Control, and Computing, Monticello, IL, USA, 2015, pp. 835–842.
60. G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar, “Codes With Local Regeneration and Erasure Correction,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4637–4660, 2014.
61. Cai H, Miao Y, Schwartz M, et al. On optimal locally repairable codes with super-linear length. IEEE Trans Inform Theroy, 2020, 66: 4853-4868.
62. Chen B, Fang W, Xia S, et al. Constructions of optimal (r,sigma) locally repairabl codes via constacyclic codes. IEEE Trans Commun, 2019, 67: 5253-5263.
63. Chen B, Xia S, Hao J, et al. Constructions of optimal cyclic (r,sigma) locally repairable codes. IEEE Trans Inform Theory, 2018, 64:2499-2511.
64. Fang W, Fu F. Optimal cyclic (r,sigma) locally repairable codes with unbounded length. Finite Fields Appl, 2020,63:101650.
65. A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, “Combinatorial alphabet-dependent bounds for locally recoverable codes,” IEEE Trans. Inf. Theory, vol. PP, no. 99, pp. 1–1, 2018.
66. I. Tamo, A. Barg, S. Goparaju, and A. R. Calderbank, “Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes,” CoRR, vol. abs/1603.08878, 2016.
67. S. Goparaju and A. R. Calderbank, “Binary cyclic codes that are locally repairable,” in Proc. IEEE International Symposium on Information Theory, Honolulu, HI, USA, 2014, pp. 676–680.
68. A. Zeh and E. Yaakobi, “Optimal linear and cyclic locally repairable codes over small fields,” in Proc. IEEE Information Theory Workshop, Jerusalem, Israel, 2015, pp. 1–5.
69. I. Tamo, A. Barg, and A. Frolov, “Bounds on the Parameters of Locally Recoverable Codes,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3070–3083, 2016.
70. A. Barg, I. Tamo, and S. Vldu, “Locally Recoverable Codes on Algebraic Curves,” IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4928–4939, 2017.
71. X. Li, L. Ma, and C. Xing, “Construction of asymptotically good locally repairable codes via automorphism groups of function fields,” CoRR, vol. abs/1711.07703, 2017.
72. M.Y.NamandH.Y.Song,“BinaryLocallyRepairableCodesWithMinimumDistanceatLeastSixBasedonPartialt-Spreads,”IEEECommunications Letters, vol. 21, no. 8, pp. 1683–1686, Aug 2017.
73. N. Silberstein and A. Zeh, “Optimal binary locally repairable codes via anticodes,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1247–1251.
74. J. Hao, S. T. Xia, and B. Chen, “Some results on optimal locally repairable codes,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 440–444.
75. M. Shahabinejad, M. Khabbazian, and M. Ardakani, “A Class of Binary Locally Repairable Codes,” IEEE Transactions on Communications, vol. 64, no. 8, pp. 3182–3193, 2016.
76. J. Hao, S. T. Xia, and B. Chen, “On optimal ternary locally repairable codes,” in Proc. IEEE International Symposium on Information Theory, Aachen, Germany, 2017, pp. 171–175.
77. J. Hao and S. Xia, “Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach,” CoRR, vol. abs/1601.05595, 2016. X. Li, L. Ma, and C. Xing, “Optimal locally repairable codes via elliptic curves,” CoRR, vol. abs/1712.03744, 2017.
78. KMM,et,al：An Efficient Piggybacking Design Framework with Sub-packetization l ?? r for All-Node Repair
79. Francisco Maturana and K. V. Rashmi, et, al：Bandwidth Cost of Code Conversions in the Split Regime
80. Hanxu Hou, et, al：New Piggybacking Codes with Lower Repair Bandwidth for Any Single-Node Failure
81. Han Cai,et,al: On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
82. A “Hitchhiker’s” Guide to Fast and Efficient Data Reconstruction in Erasure-coded Data Centers
83. Mean time to meaningless: MTTDL, Markov models, and storage system reliability
84. “后香農(nóng)時(shí)代，數(shù)學(xué)將決定未來(lái)發(fā)展的邊界”
    https://www.ithome.com/0/508/768.htm