陳歡華

（廣州軟件學(xué)院網(wǎng)絡(luò)中心，廣州 510990）

0 引言

為了應(yīng)對爆炸性的數(shù)據(jù)增長，如今的存儲系統(tǒng)通常在多個地理位置部署數(shù)千個商品存儲節(jié)點或服務(wù)器，以提供大規(guī)模的存儲服務(wù)。這些系統(tǒng)通常構(gòu)建在常見的組件上，這些組件更容易發(fā)生故障。軟件故障、機(jī)器重啟、維護(hù)停機(jī)、電源故障也可能使數(shù)據(jù)隨時不可用，因此這些系統(tǒng)應(yīng)保證數(shù)據(jù)的可靠和持久存儲。為了在發(fā)生故障時保持?jǐn)?shù)據(jù)的可靠性和可用性，傳統(tǒng)的分布式存儲系統(tǒng)通常采用冗余技術(shù)，如三副本［1-2］。當(dāng)數(shù)據(jù)量較小時，冗余方法直接有效；然而，在大型數(shù)據(jù)中心，復(fù)制帶來的200%的存儲開銷是巨大的，無法接受。作為一種折衷方案，糾刪碼是一種存儲高效的容錯技術(shù)，可以提供相同或更高級別的可靠性，同時需要更少的數(shù)據(jù)冗余［2］。因此，糾刪碼變得越來越流行，并被包括Microsoft［3］和Facebook［4］在內(nèi)的企業(yè)廣泛采用。

為了響應(yīng)不同的訪問特性［5］和滿足動態(tài)可靠性要求［6］，現(xiàn)代存儲系統(tǒng)需要糾刪碼具備自適應(yīng)功能。自適應(yīng)糾刪碼，指的是編碼參數(shù)和編解碼方案隨著各類要求的變化。我們認(rèn)為自適應(yīng)糾刪碼在以下場景中是至關(guān)重要的。

（1）適應(yīng)傾斜和動態(tài)的工作負(fù)載。實際存儲系統(tǒng)中的工作負(fù)載是非常傾斜和動態(tài)的。傾斜意味著一小部分熱數(shù)據(jù)被頻繁訪問，而大部分冷數(shù)據(jù)很少被訪問，而動態(tài)屬性意味著數(shù)據(jù)熱度是隨時間變化的。為了兼顧高訪問性能和高存儲效率，實際的存儲系統(tǒng)可以使用高冗余糾刪碼存儲熱數(shù)據(jù)以獲得高性能，同時使用低冗余糾刪碼存儲冷數(shù)據(jù)以獲得低成本持久化。當(dāng)數(shù)據(jù)熱度變化時，執(zhí)行自適應(yīng)以更新編碼參數(shù)或者更改編解碼方案［7］。

（2）適應(yīng)不同的可靠性。不同生命周期的數(shù)據(jù)需要不同程度的可靠性，因此存儲系統(tǒng)需要動態(tài)調(diào)整編碼參數(shù)以滿足不同的可靠性需求。此外，磁盤可靠性會隨著磁盤的老化而變化。為了在存儲開銷和容錯之間提供有效的權(quán)衡，大型數(shù)據(jù)中心應(yīng)該彈性調(diào)整編碼參數(shù)［6］。

（3）生成寬條帶。最近的工作探索了用于糾刪碼存儲的寬條帶，以抑制條帶中奇偶校驗塊的比例，從而實現(xiàn)極大的存儲節(jié)?。?］。為了有效地支持寬條帶，存儲系統(tǒng)可以為新寫入的數(shù)據(jù)部署具有適度低冗余的窄條帶，然后將老化的數(shù)據(jù)轉(zhuǎn)換為具有極低冗余度的寬條帶［8］。

本文將通過介紹一些典型和常用的自適應(yīng)糾刪碼來展示當(dāng)前自適應(yīng)糾刪碼研究的現(xiàn)狀，并從評價這些碼的各項重要指標(biāo)的角度比較和分析現(xiàn)有的自適應(yīng)糾刪碼，指出當(dāng)前存儲系統(tǒng)自適應(yīng)糾刪碼研究中尚未解決的難題以及未來可能的研究方向。

1 基本概念

為了便于理解，通常將一個服務(wù)器稱為一個節(jié)點，下面對本文出現(xiàn)的相關(guān)概念給出如下說明。

a）數(shù)據(jù)塊：編碼的最小數(shù)據(jù)單元。通常，系統(tǒng)將用戶的原始數(shù)據(jù)劃分成k個數(shù)據(jù)塊。

b）校驗塊：指原始數(shù)據(jù)塊經(jīng)過編碼運算得到的冗余塊，塊的大小與數(shù)據(jù)塊大小相同。

c）條帶：指多個數(shù)據(jù)塊與其對應(yīng)的校驗塊所構(gòu)成的塊集合。

d）輔助節(jié)點：指參與數(shù)據(jù)修復(fù)的可用節(jié)點。輔助節(jié)點讀取本地數(shù)據(jù)后通過網(wǎng)絡(luò)傳輸給其他節(jié)點來參與數(shù)據(jù)重建。

e）機(jī)架：若干個服務(wù)器和存儲設(shè)備的集合。數(shù)據(jù)服務(wù)器和同一機(jī)架中的存儲設(shè)備之間的訪問速度非常高，而機(jī)架間的訪問速度則較慢。

2 存儲系統(tǒng)中的糾刪碼

2.1 基礎(chǔ)糾刪碼

2.1.1 RS（Reed-Solomon）碼［9］

RS 碼可用兩個可配置的參數(shù)k和m構(gòu)造，用RS(k,m)表示。RS(k,m)將k個數(shù)據(jù)塊作為輸入進(jìn)行編碼，生成m個奇偶校驗塊，使得任意k+m個數(shù)據(jù)和奇偶校驗塊中的k個足以重建原始的k個數(shù)據(jù)塊。一起編碼的k+m個數(shù)據(jù)和奇偶校驗塊共同形成一個條帶。一個實際的存儲系統(tǒng)包含多個獨立編碼的條帶。它將k+m個塊的每個條帶分布在k+m個節(jié)點上，以容忍任何m個節(jié)點故障。圖1 給出了(k,m)=（4,2）的RS示例。

圖1 RS（4，2）示例圖

RS 碼的存儲開銷小，但其修復(fù)開銷高。修復(fù)任何一個故障塊，均需從其余k個可用節(jié)點中讀取k個塊，然后經(jīng)過計算得到。它的通信開銷是故障塊大小的k倍。

2.1.2 HH（Hitchhiker）碼［10］

圖2 顯示了HH（6,3）碼的示例。在HH(k,m)碼中，每個條帶分為兩個子條帶（a={ai}和b={bi}）。每個條帶中有k個數(shù)據(jù)塊和m個奇偶校驗塊，每個塊分別由a和b中的一個符號共同組成，因此每個子條帶中有k個數(shù)據(jù)符號和m個奇偶符號。編碼時，對同一子條帶的數(shù)據(jù)進(jìn)行RS(k,m)編碼，得到RS 碼的奇偶符號。然后，將子條帶a中的k個數(shù)據(jù)符號分成m-1 個組，每個組中的數(shù)據(jù)符號經(jīng)過按位異或得到組內(nèi)的校驗符號。然后，將各個組中的校驗符號和子條帶b經(jīng)過RS編碼得到的奇偶塊進(jìn)行按位異或，以此得到子條帶b最終的校驗符號。

圖2 HH（6,3）示例圖

當(dāng)有一個數(shù)據(jù)塊故障時，HH 碼可以運行快速解碼過程來恢復(fù)丟失的數(shù)據(jù)塊。請注意，子帶b中的一個奇偶校驗符號仍保留為RS 奇偶校驗符號。該符號僅足以恢復(fù)子條帶b中丟失的一個數(shù)據(jù)符號。假設(shè)子條a中的丟失符號在對應(yīng)于奇偶校驗符號bk+i+1的組Gi中。在完整的子帶b的幫助下，可以計算組Gi的XOR 和。這意味著可以只讀取該組中的其他數(shù)據(jù)符號來恢復(fù)子條帶a中丟失的符號。整個過程只需要讀取k+k/(m-1)k個符號。當(dāng)m＞2 時，有k+k/(m-1)=km/(m-1) ＜k，這意味著與普通解碼過程相比，快速解碼過程可以減少網(wǎng)絡(luò)帶寬和磁盤I/O 的使用。

2.1.3 LRC(Locally Repairable Codes)碼[4]

LRC 可用3 個參數(shù)(k,l,g)構(gòu)造，意味著有k個數(shù)據(jù)塊，l個本地奇偶校驗塊和g個全局奇偶校驗塊。一起編碼的k+l+g個數(shù)據(jù)/奇偶校驗塊的集合稱為條帶，大型存儲系統(tǒng)通常包含多個獨立編碼的條帶。

在LRC 中，LRC 將k個數(shù)據(jù)塊分成l個大小相等的組。它根據(jù)每組k/l數(shù)據(jù)塊計算XOR 和以形成l個本地奇偶校驗塊。它還從所有k個數(shù)據(jù)塊中計算g個全局奇偶校驗塊，計算方法同RS碼。設(shè)b是編碼成本地奇偶校驗塊的數(shù)據(jù)塊的數(shù)量，即b=k/l。我們將b個數(shù)據(jù)塊及其對應(yīng)的本地奇偶校驗塊的集合稱為本地組。圖3 給出了(k,l,g)=(6,2,2)的LRC示例。

圖3 LRC（6，2，2）示例圖

在修復(fù)任何不可用的數(shù)據(jù)塊時，LRC 檢索同一本地組的其他可用塊，而不是k個塊，故LRC將通信開銷降為故障塊大小的b倍。

2.2 自適應(yīng)糾刪碼

2.2.1 HACFS［7］

HACFS 使用來自同一碼系列的兩種不同糾刪碼。即，使用具有低恢復(fù)成本的快速碼和具有低存儲開銷的緊湊碼，如圖4（a）所示。它利用在Hadoop 工作負(fù)載中觀察到的數(shù)據(jù)訪問偏差來決定數(shù)據(jù)塊的初始編碼。在初始編碼之后，HACFS 系統(tǒng)通過使用兩種新穎的操作在快速碼和緊湊碼之間轉(zhuǎn)換數(shù)據(jù)塊來動態(tài)適應(yīng)工作負(fù)載的變化。將最初用快速碼編碼的塊升級為緊湊碼，使HACFS 系統(tǒng)能夠減少存儲開銷。類似地，將數(shù)據(jù)塊從緊湊碼下編碼為快速碼，使HACFS 系統(tǒng)降低整體恢復(fù)成本。上碼和下碼操作非常有效，并且只在兩個碼之間轉(zhuǎn)換時更新相關(guān)的奇偶校驗塊。

2.2.2 HeART［11］

HeART利用異構(gòu)級別的可靠性來權(quán)衡長期的存儲和恢復(fù)性能。HeART的基本思想是對高風(fēng)險數(shù)據(jù)采用一種恢復(fù)速度快的碼，在低風(fēng)險時期采用另一種存儲效率高的碼，如圖4（b）所示。

圖4 HACFS和HeART方法的基本框架

2.2.3 Repair-Scale［12］

Repair-Scale 考慮了兩組LRC 參數(shù)的變化，以響應(yīng)工作負(fù)載的變化。具體來說，Repair-Scale考慮了兩種LRC 結(jié)構(gòu)：①快速LRC，它存儲更多本地奇偶校驗塊以獲得更高的修復(fù)性能（例如，用于熱數(shù)據(jù)），以及②緊湊型LRC，它存儲更少的本地奇偶校驗塊以獲得更高的存儲效率（例如，對于冷數(shù)據(jù)）?？焖俸途o湊的LRC都存儲相同數(shù)量的數(shù)據(jù)塊和全局奇偶校驗塊。執(zhí)行縮放操作以在快速LRC 和緊湊LRC 之間切換，以平衡訪問性能和存儲效率。從快速LRC縮放到緊湊LRC 稱為上編碼，從緊湊LRC 縮放到快速LRC 稱為下編碼。因此，將上行編碼成本和下行編碼成本定義為分別為上行編碼和下行編碼傳輸?shù)目缂壕W(wǎng)絡(luò)流量。

圖5 描繪了(k,l,g,c)=(12,6,2,20) 的快速LRC 和(k,l,g,c)=(12,2,2,16)的緊湊LRC 的上編碼和下編碼。這兩個碼都部署在分層數(shù)據(jù)放置下（即，每個塊都存儲在不同的集群中，參數(shù)c指機(jī)架數(shù)）。上編碼操作（從(12,6,2,20) 到(12,2,2,16)）將L1和L2跨集群發(fā)送到L0以計算新的本地奇偶校驗塊L'0，并將L4和L5跨集群發(fā)送到L3計算一個新的本地奇偶校驗塊L'1。因此，上編碼成本為4。另外，下編碼操作（從（12，2，2，16）到（12，6，2，20））將D2和D3發(fā)送到另一個集群以計算L1，并且將D4和D5發(fā)送到另一個集群以計算L2。然后它將L1和L2發(fā)送到持有L'0的集群以計算L0。L3、L4和L5也是如此?？偣玻戮幋a成本為12。

圖5 快速LRC（12，6，2，20）和緊湊LRC（12，2，2，16）的上下編碼示例

2.2.4 SRS［13］

SRS 碼建立在塊到節(jié)點映射的解耦之上，通過將RS 碼的k個數(shù)據(jù)塊存儲在k'個節(jié)點中，其中k≤k'。ERS 首先計算k和k'的最小公倍數(shù)LCM，即l=lcm(k,k')，并將一個對象劃分為l個數(shù)據(jù)塊。然后將l個數(shù)據(jù)塊排列成k個邏輯列，對每k個具有相同邏輯偏移量的數(shù)據(jù)塊進(jìn)行編碼，計算出m個奇偶校驗塊。最后將l個數(shù)據(jù)塊分布在k'個節(jié)點上，使得每個節(jié)點恰好存儲l/k'個塊，并將奇偶校驗塊分布在m個節(jié)點上。請注意，對于l/k個條帶，奇偶校驗塊放在相同的m個節(jié)點上，而對于不同的條帶組，則將奇偶校驗塊放在不同的節(jié)點上，以平衡奇偶校驗更新的I/O 開銷。由于數(shù)據(jù)塊現(xiàn)在分布在k'個節(jié)點上，當(dāng)對象從RS(k,m)轉(zhuǎn)換到RS(k',m)時，SRS 碼不需要數(shù)據(jù)塊重定位，如圖6所示。

圖6 SRS（2，1，3）示例圖

2.2.5 ERS［14］

ERS 編碼與SRS 編碼在以下方面有所不同。首先，ERS 編碼在邏輯上將l個數(shù)據(jù)塊按行優(yōu)先順序分配到k個節(jié)點中，因此引入了大量重疊數(shù)據(jù)塊用于冗余轉(zhuǎn)換（如圖7）。此外，ERS 編碼使用新穎的編碼矩陣對每k個數(shù)據(jù)塊進(jìn)行編碼，并根據(jù)新穎的放置策略將l個數(shù)據(jù)塊物理分布在k'個節(jié)點上，以增加重疊數(shù)據(jù)塊的數(shù)量。因此，ERS 編碼只需要少量的非重疊數(shù)據(jù)塊，并且可以減少奇偶校驗塊更新的I/O。

圖7 顯示了按行優(yōu)先順序放置的ERS（2，1，3）示例。由于k=2 和k'=3，我們可以推導(dǎo)出l=lcm(2,3)=6。首先將l=6 個數(shù)據(jù)塊順序排列成k=2 邏輯行主要順序的列。每k=2 個具有相同邏輯偏移量（即圖中相同顏色）的數(shù)據(jù)塊在邏輯存儲中被編碼為m=1個奇偶校驗塊。然后，l=6個數(shù)據(jù)塊在物理存儲中也以行優(yōu)先順序在k'=3個節(jié)點上物理拉伸。可以看到，RS（3,1）的數(shù)據(jù)塊分布被保留了，因此在從RS（2,1）到RS（3,1）的轉(zhuǎn)換過程中消除了數(shù)據(jù)塊重定位。我們還可以證明P'0=P0+D2，并且P'1=P2+D3=P2+P1+D2。因此，只需要檢索D2來更新冗余轉(zhuǎn)換中的奇偶校驗塊。

圖7 ERS（2，1，3）示例圖

2.2.6 LRC-HH［15］

LRC-HH 自適應(yīng)碼選擇兩類碼來應(yīng)對訪問傾斜的情況。其中快速碼為LRC(k,m-1,m)碼，緊湊碼為HH(k,m)碼。當(dāng)快速碼的編碼數(shù)據(jù)轉(zhuǎn)換為緊湊碼的形式時，可以將LRC 中的兩個條帶（a和b）視為HH 代碼中的條帶的兩個子條帶（sa和sb），因此LRC 中的所有塊都可以視為符號。所有數(shù)據(jù)符號都可以保留，a中的所有全局奇偶符號都可以保留為sa中的奇偶符號。在b中，第一個全局奇偶校驗符號可以保留為sb中的第一個奇偶校驗符號，但是sb中的其余奇偶校驗符號是b中的全局奇偶校驗符號與其對應(yīng)的a中的數(shù)據(jù)符號組的異或和。為了計算和，不必讀取a中的所有數(shù)據(jù)符號。相反，a中的原始局部奇偶校驗符號正是應(yīng)計算的部分和。因此，要計算sb中的奇偶校驗符號，只需讀取a中相應(yīng)的局部奇偶校驗符號，并將其與b中的原始全局奇偶校驗符號進(jìn)行異或。圖8 顯示了當(dāng)k=6 和m=3時這種碼切換過程的示例。

圖8 從LRC（6,2,3）碼到HH（6,3）碼的轉(zhuǎn)換

當(dāng)HH(k,m)編碼的數(shù)據(jù)轉(zhuǎn)換為LRC（k,m-1,m）形式時，可以將HH 代碼中的條帶的兩個子條帶（sa和sb）視為LRC 的兩個條帶（a和b）。類似地，所有數(shù)據(jù)符號都可以作為數(shù)據(jù)塊保留，sa中的所有奇偶校驗符號可以作為a中的全局奇偶校驗塊保留。所有的本地奇偶校驗塊都只能通過數(shù)據(jù)塊來計算，這部分計算是難以避免的。sb中的第一個奇偶校驗符號可以保留為b中的第一個全局奇偶校驗塊。在這個階段，b中的其余全局塊可以在沒有任何數(shù)據(jù)塊的參與的情況下計算出來。要計算b中的全局符號，只需將a中的相應(yīng)局部奇偶校驗塊（剛剛計算）與sb中的原始奇偶校驗符號進(jìn)行異或。圖9 顯示了當(dāng)k=6 和m=3時此碼切換過程的示例。

圖9 從HH（6，3）碼到LRC（6，2，3）碼的轉(zhuǎn)換

2.2.7 EC-Fusion［16］

為了應(yīng)對動態(tài)的工作負(fù)載，需要在混合糾刪碼之間進(jìn)行碼轉(zhuǎn)換，這是EC-Fusion 的核心模塊。在構(gòu)造RS(k,m)的基礎(chǔ)上，我們可以將奇偶校驗矩陣分解為幾個大小為m×m的子矩陣。然后校驗塊生成方程可以重寫為

由于RS 碼中奇偶校驗矩陣的任何m×m子矩陣都是可逆的，所以每個中間具有以下性質(zhì)，

然后可以很容易地建立中間奇偶校驗和MSR 奇偶校驗之間的轉(zhuǎn)換。其中“Trans1”和“Trans2”可以推導(dǎo)出如下表達(dá)：

因此，中間校驗塊可以作為實現(xiàn)RS 和MSR之間高效轉(zhuǎn)換的橋梁。如圖10（a）所示，對于從MSR 碼到RS 碼的轉(zhuǎn)換，可以將原始奇偶校驗的k/m組轉(zhuǎn)換為中間奇偶校驗，然后將它們合并為最終的RS 奇偶校驗。

從RS 到MSR 的轉(zhuǎn)換可以看作是一個逆過程，其中一組原始RS 被劃分為最終的k/m組MSR。細(xì)節(jié)如圖10（b）所示，其中(k/m)-1 組數(shù)據(jù)乘以它們對應(yīng)的子矩陣。這樣就可以通過所有現(xiàn)有的校驗位得到最后一組的中間校驗位，然后將所有中間校驗位轉(zhuǎn)化為最終的MSR碼。

圖10 MSR碼與RS碼之間的轉(zhuǎn)換

3 自適應(yīng)糾刪碼的比較與分析

3.1 評價指標(biāo)

我們使用碼的選擇、轉(zhuǎn)換效率以及擴(kuò)展性作為自適應(yīng)糾刪碼的評價指標(biāo)。

3.2 比較與分析

3.2.1 碼的選擇

自適應(yīng)碼HACFS，HeART，Repair-Scale，SRS 和ERS 都是同一碼族中的碼之間轉(zhuǎn)換，其轉(zhuǎn)換效率高。但是同碼族轉(zhuǎn)換，無法避免碼族的固有缺陷。比如RS 碼的解碼復(fù)雜度高，LRC碼的存儲開銷大等。而LRC-HH 和MSR-RS 是不同碼族中的碼間轉(zhuǎn)換，其能很好地避開各個碼的缺點。比如MSR 碼的編碼復(fù)雜度高，解碼復(fù)雜度低，而RS 碼正好相反，二者的結(jié)合可以很好地避免碼本身的限制。

3.2.2 轉(zhuǎn)換效率

自適應(yīng)是一項重要的任務(wù)，主要是因為自適應(yīng)過程經(jīng)常導(dǎo)致數(shù)據(jù)塊重定位和奇偶塊更新，這兩種操作都會帶來大量的I/O 成本。具體來說，傳統(tǒng)的糾刪碼通常將塊映射到一組固定的節(jié)點，這樣，對象的數(shù)據(jù)塊數(shù)量就等于存儲對象數(shù)據(jù)的節(jié)點數(shù)量。如果自適應(yīng)改變了數(shù)據(jù)塊的數(shù)量（即k），則需要將一些數(shù)據(jù)塊重新定位到不同的節(jié)點，從而產(chǎn)生額外的I/O。奇偶校驗塊的更新進(jìn)一步加重了I/O：由于數(shù)據(jù)塊的布局發(fā)生了變化，奇偶校驗塊需要相應(yīng)的更新附加I/O，包括檢索所有數(shù)據(jù)塊以重新計算新的奇偶校驗塊，以及將新計算的奇偶校驗塊寫入節(jié)點?，F(xiàn)有的自適應(yīng)糾刪碼都盡可能地避免了數(shù)據(jù)塊重定向，但是校驗塊更新導(dǎo)致的I/O 開銷和數(shù)據(jù)傳輸開銷依舊很大。

3.2.3 可擴(kuò)展性

現(xiàn)有的自適應(yīng)糾刪碼只能在固定的參數(shù)之間變化，靈活性不夠強(qiáng)，不能很好地適應(yīng)時變的網(wǎng)絡(luò)環(huán)境和不斷變化的用戶需求。故，如何根據(jù)網(wǎng)絡(luò)環(huán)境，以及用戶需求，做對應(yīng)的自適應(yīng)操作將是自適應(yīng)糾刪碼的重要研究方向。

4 結(jié)語

本文對目前自適應(yīng)糾刪碼做了比較全面的總結(jié)。首先介紹了糾刪碼的基本概念，隨后介紹了基礎(chǔ)的糾刪碼，接著詳細(xì)介紹了現(xiàn)有主流的自適應(yīng)糾刪碼。最后比較分析了這些糾刪碼的優(yōu)缺點。我們認(rèn)為，在當(dāng)前自適應(yīng)糾刪碼方法的研究中，進(jìn)一步的研究重點主要包含兩個方面：①提高轉(zhuǎn)換效率。當(dāng)前自適應(yīng)碼的轉(zhuǎn)換效率較低，尤其體現(xiàn)在校驗塊的更新上，需要傳輸?shù)臄?shù)據(jù)塊較多，這加重了糾刪碼的帶寬開銷，容易引發(fā)網(wǎng)絡(luò)擁塞。故，有必要研究轉(zhuǎn)換效率更高的糾刪碼。②提高擴(kuò)展性。網(wǎng)絡(luò)和用戶需求具有時變性，靈活的糾刪碼能夠更好地節(jié)省和權(quán)衡存儲開銷和通信開銷。因此，研究擴(kuò)展更為靈活的糾刪碼具有重要意義。