簡(jiǎn)介

??隨著數(shù)據(jù)的存儲(chǔ)呈現(xiàn)出集中化（以分布式存儲(chǔ)系統(tǒng)為基礎(chǔ)的云存儲(chǔ)系統(tǒng)）和移動(dòng)化（互聯(lián)網(wǎng)移動(dòng)終端）的趨勢(shì)醇锚，數(shù)據(jù)可靠性愈發(fā)引起大家的重視望抽。集群所承載的數(shù)據(jù)量大大上升淆九，但存儲(chǔ)介質(zhì)本身的可靠性進(jìn)步卻很小屁使，這要求我們必須以更加經(jīng)濟(jì)有效的方式來保障數(shù)據(jù)安全猎莲。

??副本與糾刪碼都是通過增加冗余數(shù)據(jù)的方式來保證數(shù)據(jù)在發(fā)生部分丟失時(shí)流济，原始數(shù)據(jù)不發(fā)生丟失究抓。但相較于副本猾担，糾刪碼能以低得多的存儲(chǔ)空間代價(jià)獲得相似的可靠性。比如3副本下刺下，存儲(chǔ)開銷為3绑嘹，因?yàn)橥瑯拥臄?shù)據(jù)被存儲(chǔ)了三份，而在10+3（將原始數(shù)據(jù)分為10份橘茉，計(jì)算3份冗余）的糾刪碼策略下工腋，存儲(chǔ)開銷為為1.3。采用糾刪碼能夠極大地減少存儲(chǔ)系統(tǒng)的存儲(chǔ)開銷畅卓，減少硬件擅腰、運(yùn)維和管理成本，正是這樣巨大的收益驅(qū)使各大公司紛紛將糾刪碼應(yīng)用于自己的存儲(chǔ)系統(tǒng)翁潘，比如Google趁冈、Facebook拜马、Azure渗勘、EMC等等國際巨頭，在國內(nèi)以淘寶俩莽、華為旺坠、七牛云等為代表的公司也在自己的存儲(chǔ)系統(tǒng)上應(yīng)用了糾刪碼。

??糾刪碼（Erasure Code扮超，EC）取刃，是一種前向錯(cuò)誤糾正技術(shù)（Forward Error Correction，F(xiàn)EC）出刷，主要應(yīng)用在網(wǎng)絡(luò)傳輸中避免包的丟失璧疗， 存儲(chǔ)系統(tǒng)利用它來提高 存儲(chǔ) 可靠性。相比多副本復(fù)制而言馁龟， 糾刪碼能夠以更小的數(shù)據(jù)冗余度獲得更高數(shù)據(jù)可靠性病毡， 但編碼方式較復(fù)雜，需要大量計(jì)算 屁柏。糾刪碼只能容忍數(shù)據(jù)丟失啦膜，無法容忍數(shù)據(jù)篡改，糾刪碼正是得名與此淌喻。 Erasure Code是一種編碼技術(shù)僧家，它可以將n份原始數(shù)據(jù)，增加m份數(shù)據(jù)裸删，并能通過n+m份中的任意n份數(shù)據(jù)八拱，還原為原始數(shù)據(jù)。即如果有任意小于等于m份的數(shù)據(jù)失效，仍然能通過剩下的數(shù)據(jù)還原出來肌稻。

??目前清蚀，糾刪碼技術(shù)在分布式存儲(chǔ) 系統(tǒng)中的應(yīng)用主要有三類，陣列糾刪碼（Array Code: RAID5爹谭、RAID6等）枷邪、RS(Reed-Solomon)里德-所羅門類糾刪碼和LDPC(LowDensity Parity Check Code)低密度奇偶校驗(yàn)糾刪碼。

??RAID是EC的特殊情況诺凡。在傳統(tǒng)的RAID中东揣，僅支持有限的磁盤失效，RAID5只支持一個(gè)盤失效腹泌，RAID6支持兩個(gè)盤失效嘶卧，而EC支持多個(gè)盤失效。EC主要運(yùn)用于存儲(chǔ)和數(shù)字編碼領(lǐng)域凉袱。例如磁盤陣列存儲(chǔ)（RAID 5芥吟、RAID 6），云存儲(chǔ)（RS）等专甩。

??LDPC碼也可以提供很好的保障可靠性的冗余機(jī)制钟鸵。與RS編碼相比，LDPC編碼效率要略低配深，但編碼和解碼性能要優(yōu)于RS碼以及其他的糾刪碼携添，主要得益于編解碼采用的相對(duì)較少并且簡(jiǎn)單的異或操作嫁盲。LDPC碼目前主要用于通信篓叶、視頻和音頻編碼等領(lǐng)域。

??最典型的糾刪碼算法是里德-所羅門碼（Reed-Solomon碼羞秤，簡(jiǎn)稱RS碼）缸托，最早應(yīng)用于通信領(lǐng)域，經(jīng)過數(shù)十年的發(fā)展瘾蛋，其在存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用俐镐，比如光盤中使用RS碼進(jìn)行容錯(cuò)，防止光盤上的劃痕導(dǎo)致數(shù)據(jù)不可讀哺哼；生活中經(jīng)常使用的二維碼就利用了RS碼來提高識(shí)別的成功率佩抹。近年RS碼在分布式存儲(chǔ)系統(tǒng)中的應(yīng)用被逐漸推廣，一方面是分布式存儲(chǔ)系統(tǒng)存儲(chǔ)的存儲(chǔ)容量和規(guī)模增大的需求取董；另一方面是由于糾刪碼編碼速度在近年得到迅猛提升棍苹。隨著對(duì)高性能糾刪碼引擎在實(shí)際系統(tǒng)中應(yīng)用需要，也催生了對(duì)糾刪碼在具體系統(tǒng)中實(shí)現(xiàn)的各種優(yōu)化手段茵汰。并為相關(guān)的決策者帶來了困擾——究竟什么樣的編碼引擎才是高效的呢枢里？我們將以這個(gè)問題展開對(duì)RS糾刪碼技術(shù)的剖析，深入的了解糾刪碼在存儲(chǔ)系統(tǒng)中的應(yīng)用并更好地做出技術(shù)選型。本文將從糾刪碼的基本原理開始栏豺，隨后引出如何判斷編碼引擎優(yōu)劣這個(gè)問題彬碱，接下來將深度分析代碼實(shí)現(xiàn)。

一奥洼、RS code原理

??RS code是基于有限域的一種編碼算法巷疼，有限域又稱為Galois Field，是以法國著名數(shù)學(xué)家伽羅華（Galois）命名的溉卓，在RS code中使用GF(2^{w)皮迟，其中2}w >= n + m。

??RS code的編解碼定義如下：

編碼：給定n個(gè)數(shù)據(jù)塊（Data block）D1桑寨、D2……Dn伏尼，和一個(gè)正整數(shù)m，RS根據(jù)n個(gè)數(shù)據(jù)塊生成m個(gè)編碼塊（Code block）尉尾，C1爆阶、C2……Cm。

解碼：對(duì)于任意的n和m沙咏，從n個(gè)原始數(shù)據(jù)塊和m個(gè)編碼塊中任取n塊就能解碼出原始數(shù)據(jù)辨图，即RS最多容忍m個(gè)數(shù)據(jù)塊或者編碼塊同時(shí)丟失。

??RS編解碼中涉及到矩陣求逆肢藐，采用高斯消元法故河，需要進(jìn)行實(shí)數(shù)加減乘除四則運(yùn)算，無法作用于字長為w的二進(jìn)制數(shù)據(jù)吆豹。為了解決這個(gè)問題鱼的， RS采用伽羅華群GF（2^w）中定義的四則運(yùn)算法則。
GF(2^w）域有2w個(gè)值痘煤， 每個(gè)值都對(duì)應(yīng)一個(gè)低于w次的多項(xiàng)式凑阶， 這樣域上的四則運(yùn)算就轉(zhuǎn)換為多項(xiàng)式空間的運(yùn)算。 GF(2^w)域中的加法就是異或XOR衷快， 乘法通過查表實(shí)現(xiàn)宙橱，需要維護(hù)兩個(gè)大小為2^w -1的表格: log表gflog，反log表gfilog蘸拔。
乘法公式： a * b = gfilog(gflog(a) + fglog(b)) % (2^w -1)

??在了解了定義之后师郑，我們?cè)偻ㄋ椎拿枋鲆幌翿S碼的工作模式：

編碼：
為了計(jì)算冗余數(shù)據(jù)，首先我們需要選舉出一個(gè)合適的編碼矩陣调窍。編碼矩陣的上部為一個(gè)單位矩陣宝冕，這樣保證了在編碼后原始數(shù)據(jù)依然可以直接讀取。通過計(jì)算編碼矩陣和原始數(shù)據(jù)的乘積陨晶，可以到最終的結(jié)果猬仁。

解碼：
當(dāng)數(shù)據(jù)塊發(fā)生丟失帝璧，在編碼矩陣中去掉相應(yīng)行，等式仍然保持成立湿刽。這為我們接下來恢復(fù)原始數(shù)據(jù)提供了依據(jù)的烁。
為了恢復(fù)數(shù)據(jù)，首先我們求剩余編碼數(shù)據(jù)的逆矩陣诈闺，等式兩邊乘上這個(gè)逆矩陣仍然保持相等渴庆。與此同時(shí)，互逆矩陣的乘積為單位矩陣雅镊，因此可以被消掉襟雷。那么所求得的逆矩陣與剩余塊的數(shù)據(jù)的乘積就是原始數(shù)據(jù)了。

文章后面會(huì)給出具體的編碼解碼計(jì)算示例仁烹；這里只做理論說明耸弄；

??數(shù)據(jù)編碼以字節(jié)為單位，如果將被編碼數(shù)據(jù)看做一個(gè)「數(shù)組」卓缰，「數(shù)組」中每個(gè)元素是一個(gè)字節(jié)计呈，數(shù)據(jù)按照字節(jié)順序被編碼。編碼過程是計(jì)算編碼矩陣中元素和「數(shù)組」的乘積過程征唬。為保證乘積的運(yùn)算結(jié)果仍舊在一個(gè)字節(jié)大小以內(nèi)（即0-255）捌显，必須應(yīng)用到有限域。有限域上的算術(shù)運(yùn)算不同于通常實(shí)數(shù)的運(yùn)算規(guī)則总寒。我們通常事先準(zhǔn)備好乘法表扶歪，并在算術(shù)運(yùn)算時(shí)對(duì)每一次乘法進(jìn)行查表得到計(jì)算結(jié)果。早期的編碼引擎之所以性能不佳摄闸，是因?yàn)橹鹱止?jié)查表的性能是非常低的善镰。倘若能一次性對(duì)多字節(jié)進(jìn)行查表以及相應(yīng)的吞吐和運(yùn)算，引擎的工作效率必將大幅度提升贪薪。

??許多CPU廠商提供了包含更多位數(shù)的寄存器（大于64位）媳禁，這類寄存器和相應(yīng)支持的運(yùn)算使得用戶程序可以同時(shí)對(duì)大于機(jī)器位數(shù)的數(shù)據(jù)進(jìn)行運(yùn)算眠副，支持這類寄存器和運(yùn)算的指令稱之為SIMD（SingleInstructionMultipleData）指令集画切，比如Intel支持的SSE指令集最大支持128bits的數(shù)據(jù)運(yùn)算，AVX2指令集最大支持512bits的數(shù)據(jù)運(yùn)算囱怕。它們?yōu)槲覀儗?duì)一個(gè)「數(shù)組」數(shù)據(jù)分別執(zhí)行相同的操作霍弹，提高了數(shù)據(jù)運(yùn)算的并行性。目前娃弓，市面上所有高性能的糾刪碼引擎均采用了該項(xiàng)技術(shù)以提高編解碼性能典格。

1. 數(shù)學(xué)理論工程化

??以RS碼為例，糾刪碼實(shí)現(xiàn)于具體的存儲(chǔ)系統(tǒng)可以分為幾個(gè)部分：編碼台丛、解碼和修復(fù)過程中的計(jì)算都是在有限域上進(jìn)行的耍缴；編碼過程即是計(jì)算生成矩陣（范德蒙德或柯西矩陣）和所有數(shù)據(jù)的乘積砾肺；解碼則是計(jì)算解碼矩陣（生成矩陣中某些行向量組成的方陣的逆矩陣）和重建數(shù)據(jù)的乘積。

1.1有限域運(yùn)算

??有限域是糾刪碼中運(yùn)算的基礎(chǔ)域防嗡，所有的編解碼和重建運(yùn)算都是基于某個(gè)有限域的变汪。不止是糾刪碼，一般的編碼方法都在有限域上進(jìn)行蚁趁，比如常見的AES加密中也有有限域運(yùn)算裙盾。使用有限域的一個(gè)重要原因是計(jì)算機(jī)并不能精確執(zhí)行無限域的運(yùn)算，比如有理數(shù)域和虛數(shù)域他嫡。

??此外番官，在有限域上運(yùn)算另一個(gè)重要的好處是運(yùn)算后的結(jié)果大小在一定范圍內(nèi)，這是因?yàn)?code>有限域的封閉性決定的钢属，這也為程序設(shè)計(jì)提供了便利徘熔。比如在RS中，我們通常使用GF(28)淆党，即0～255這一有限域近顷，這是因?yàn)槠溟L度剛好為1字節(jié)，便于我們對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和計(jì)算宁否。

??在確定了有限域的大小之后窒升，通過有限域上的生成多項(xiàng)式可以找到該域上的生成元，進(jìn)而通過生成元的冪次遍歷有限域上的元素慕匠，利用這一性質(zhì)我們可以生成相應(yīng)的指數(shù)表饱须。通過指數(shù)表我們可以求出對(duì)數(shù)表，再利用指數(shù)表與對(duì)數(shù)表最終生成乘法表台谊。

??有了乘法表蓉媳，我們就可以在運(yùn)算過程中直接查表獲得結(jié)果，而不用進(jìn)行復(fù)雜的多項(xiàng)式運(yùn)算了锅铅。同時(shí)也不難發(fā)現(xiàn)酪呻，查表優(yōu)化將會(huì)成為接下來工作的重點(diǎn)與難點(diǎn)。

1.2選擇生成矩陣

??生成矩陣（GM,generatormatrix）定義了如何將原始數(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)碼沒有單位矩陣，整個(gè)生成矩陣都是冗余矩陣统舀，因此編碼后只有冗余數(shù)據(jù)塊匆骗。通常我們會(huì)使用系統(tǒng)碼以提高數(shù)據(jù)提取時(shí)的效率劳景，那么接下來我們需要找到合適的冗余矩陣。

??在解碼過程中我們要對(duì)矩陣求逆碉就，因此所采用的矩陣必須滿足子矩陣可逆的性質(zhì)枢泰。目前業(yè)界應(yīng)用最多的兩種矩陣是Vandermondematrix(范德蒙矩陣）和Cauchymatrix（柯西矩陣）。其中范德蒙矩陣歷史最為悠久铝噩，但需要注意的是我們并不能直接使用范德蒙矩陣作為生成矩陣衡蚂，而需要通過高斯消元后才能使用，這是因?yàn)樵诰幋a參數(shù)（k+m）比較大時(shí)會(huì)存在矩陣不可逆的風(fēng)險(xiǎn)骏庸。

??柯西矩陣運(yùn)算簡(jiǎn)單毛甲，只不過需要計(jì)算乘法逆元，我們可以提前計(jì)算好乘法逆元表以供生成編碼矩陣時(shí)使用具被。創(chuàng)建以柯西矩陣為生成矩陣的編碼矩陣的偽代碼如下圖所示：

     /*
     * 存儲(chǔ)系統(tǒng)中的符號(hào)約定
     * k:數(shù)據(jù)塊的個(gè)數(shù)
     * m:校驗(yàn)塊的個(gè)數(shù)（就是code）
     * n:k+m玻募，也就是數(shù)據(jù)塊和校驗(yàn)塊的個(gè)數(shù)總和。
     編碼效率：r = k/m
     */
//這里有設(shè)定 行數(shù)為 rows=(k),cols(=k)為列數(shù),編碼生成矩陣為M
//先生成單位矩陣（在線性代數(shù)中一姿，n階單位矩陣七咧，是一個(gè) 的方形矩陣，其主對(duì)角線元素為1叮叹，其余元素為0艾栋。 單位矩陣以In表示；如果階數(shù)可忽略蛉顽，或可由前后文確定的話蝗砾，也可簡(jiǎn)記為I。）
for (j = 0; j < cols; j++)
{
    M[j][j] = byte(1);
}

//生成mxk的柯西矩陣悼粮，這里的cols=k,row = (k+m)
for(i = cols;  i< rows; i++)
{
     for(j = 0; j < cols; j++)
      {
          d = i ^ j;//這里的i j對(duì)應(yīng)的是預(yù)先設(shè)定的兩個(gè)矩陣中對(duì)應(yīng)的元素值
          a = inverseTable[d];// 查乘法逆元表
          M[i][j] = byte(a)
      }
}

1.3矩陣求逆運(yùn)算
??有限域上的求逆方法和我們學(xué)習(xí)的線性代數(shù)中求逆方法相同，常見的是高斯消元法曾棕，算法復(fù)雜度是O(n3)扣猫。過程如下：

1. 在待求逆的矩陣右邊拼接一個(gè)單位矩陣
   2.進(jìn)行高斯消元運(yùn)算
2. 取得到的矩陣左邊非單位矩陣的部分作為求逆的結(jié)果，如果不可逆則報(bào)錯(cuò)

??我們?cè)趯?shí)際的測(cè)試環(huán)境中發(fā)現(xiàn)翘地，矩陣求逆的開銷還是比較大的(大約6000ns/op)申尤。考慮到在實(shí)際系統(tǒng)中子眶，單盤數(shù)據(jù)重建往往需要幾個(gè)小時(shí)或者更長（磁盤I/O占據(jù)絕大部分時(shí)間）瀑凝，求逆計(jì)算時(shí)間可以忽略不計(jì)序芦。需要說明的是臭杰，發(fā)送端和接收端需要統(tǒng)一生成編碼矩陣的算法，否則接收端沒有辦法根據(jù)缺失的包序號(hào)生成對(duì)應(yīng)的矩陣谚中，進(jìn)行求逆運(yùn)算渴杆。
在實(shí)際的測(cè)試環(huán)境中發(fā)現(xiàn)寥枝，矩陣求逆的開銷還是比較大的(大約6000ns/op)〈沤保考慮到在實(shí)際系統(tǒng)中囊拜，單盤數(shù)據(jù)重建往往需要幾個(gè)小時(shí)或者更長（磁盤I/O占據(jù)絕大部分時(shí)間），求逆計(jì)算時(shí)間可以忽略不計(jì)比搭。

??下面我給出了一個(gè)我自己手寫的一個(gè)簡(jiǎn)單的計(jì)算示例：
假設(shè)編碼生成矩陣和源數(shù)據(jù)包如下所示

發(fā)送端編碼.png

假設(shè)傳輸過程中丟失了第二個(gè)包（這里用8代替冠跷，實(shí)際計(jì)算中按字節(jié)計(jì)算）和最后一個(gè)冗余包（22）丟失，接收端只收到了數(shù)據(jù)包 4身诺、9蜜托、1 和冗余包22，則下面我們一起恢復(fù)原始數(shù)據(jù)包霉赡；

摘取生成矩陣中丟失元素對(duì)應(yīng)行后橄务，該方陣的逆矩陣就是解碼矩陣.png

通過解碼矩陣和接收到接受到的有效數(shù)據(jù)塊構(gòu)成的解碼列向量，相乘來恢復(fù)原始數(shù)據(jù)包.png

二穴亏、編碼引擎評(píng)判標(biāo)準(zhǔn)

我們將從以下幾個(gè)關(guān)鍵指標(biāo)來對(duì)編碼引擎進(jìn)行分析：

1蜂挪、高編/解碼速度；

2嗓化、參數(shù)可配置棠涮；

3、代碼簡(jiǎn)潔刺覆、穩(wěn)定故爵；

4、降低修復(fù)開銷等隅津。

2.1 高編/解碼速度

??無須多言诬垂，編/解碼性能是最基本也是最重要的指標(biāo)。對(duì)于一款性能優(yōu)異的引擎來說伦仍，應(yīng)該同時(shí)滿足以下幾個(gè)指標(biāo)：

根據(jù)CPU的特性自動(dòng)選擇最優(yōu)的指令集進(jìn)行加速结窘。上文提到，依賴于SIMD技術(shù)RS碼編碼性能有了大幅度的提高充蓝。其中隧枫，我們可以利用多種指令集擴(kuò)展以供加速，引擎應(yīng)該能夠自主發(fā)現(xiàn)最優(yōu)解谓苟。

通過SIMD加速官脓，性能會(huì)有大幅度攀升。我們還可以將逐字節(jié)查表（下稱基本方法）的編碼速度與利用SIMD技術(shù)加速的編碼速度做對(duì)比涝焙，兩者應(yīng)該有數(shù)倍的差距

??編/解碼速度穩(wěn)定卑笨，對(duì)于不同尺寸的數(shù)據(jù)塊會(huì)有相近的性能表現(xiàn)。由于系統(tǒng)緩存的影響仑撞，當(dāng)被編碼數(shù)據(jù)的大小和緩存大小相當(dāng)時(shí)赤兴，編碼應(yīng)該具有最快的速度妖滔。當(dāng)編碼數(shù)據(jù)的大小大于緩存大小時(shí)，內(nèi)存帶寬成為編碼速度的瓶頸桶良，文件大小和編碼時(shí)間呈現(xiàn)近似線性關(guān)系座舍。這樣，數(shù)據(jù)編碼時(shí)間是可預(yù)期的陨帆，用戶的服務(wù)質(zhì)量也是可保障的曲秉。在實(shí)際中，我們對(duì)于大文件進(jìn)行定長分塊疲牵，依次編碼岸浑，分塊大小和緩存大小保持一定關(guān)系。

下圖展示了在10+4策略下瑰步，不同大小的數(shù)據(jù)塊的編碼速度變化趨勢(shì)[2]：

注：

測(cè)試平臺(tái)：MacBookPro(Retina,13-inch,Mid2014)矢洲，2.6GHzi5-4278U(3MBL3CacheSize),8GB1600MHzDDR3

編/解碼速度計(jì)算公式:在k+m策略下，每一個(gè)數(shù)據(jù)塊的尺寸計(jì)作s,編/解碼m個(gè)數(shù)據(jù)塊的耗時(shí)計(jì)作t,則速度=(k*s)/t

測(cè)試方法：在內(nèi)存中生成隨機(jī)數(shù)據(jù)缩焦，運(yùn)行若干次編／解碼读虏，取平均值

分別執(zhí)行了avx2指令集,ssse3指令集,基本方法(base)這三種編碼方案

被編碼文件尺寸指，每一個(gè)數(shù)據(jù)塊的尺寸與總的數(shù)據(jù)塊個(gè)數(shù)的乘積袁滥，即原始數(shù)據(jù)的總大小

作為對(duì)比盖桥，利用go語言自帶的copy函數(shù)（copy），對(duì)k個(gè)數(shù)據(jù)塊進(jìn)行內(nèi)存拷貝题翻。copy同樣使用了SIMD技術(shù)進(jìn)行加速

image

另外揩徊，解碼速度應(yīng)該大于或等于編碼速度（視丟失的數(shù)據(jù)塊數(shù)量而定），下圖為10+4策略下修復(fù)不同數(shù)量的原始數(shù)據(jù)的速度對(duì)比[2]：

注：

測(cè)試平臺(tái)與上文的編碼測(cè)試相同

lostdata=丟失數(shù)據(jù)塊數(shù)目（個(gè)）

原始數(shù)據(jù)塊每塊大小為128KB嵌赠，總大小為1280KB

image

2.2 參數(shù)可配置

??一款合理的糾刪碼引擎必須能做到編碼策略在理論范圍內(nèi)可隨意切換塑荒，這指的是如果要將編碼策略進(jìn)行變化時(shí)，僅需從接口傳入不同參數(shù)而不需要改動(dòng)引擎本身姜挺。這大大降低了后續(xù)的開發(fā)和維護(hù)所需要的精力齿税。一個(gè)可配置參數(shù)的編碼引擎可以根據(jù)數(shù)據(jù)的冷熱程度和數(shù)據(jù)重要程度選擇不同的編碼系數(shù)，比如可靠性要求高的數(shù)據(jù)可以選擇更多冗余炊豪。

2.3 代碼簡(jiǎn)潔凌箕、穩(wěn)定

??為了利用SIMD加速我們不得不引入?yún)R編代碼或者封裝后的CPU指令，因此代碼形式并不常見词渤。為了增強(qiáng)可讀性可將部分邏輯抽離到高級(jí)語言牵舱，然而會(huì)損失部分性能，這其中的利弊需要根據(jù)團(tuán)隊(duì)的研發(fā)實(shí)力進(jìn)行權(quán)衡缺虐。

??接下來的可維護(hù)性也非常重要芜壁。首先是接口穩(wěn)定，不會(huì)隨著新技術(shù)的引入而導(dǎo)致代碼大規(guī)模重構(gòu)；另外代碼必須經(jīng)過有合理的測(cè)試模塊以便在后續(xù)的更新中校驗(yàn)新算法沿盅。

??比如早先的SIMD加速是基于SSE指令集擴(kuò)展來做的把篓，隨后Intel又推出AVX指令集進(jìn)一步提高了性能纫溃，引擎應(yīng)該能即時(shí)跟上硬件進(jìn)步的步伐腰涧。再比方說，再生碼[5]（可以理解為能減少修復(fù)開銷的糾刪碼）是將來發(fā)展的趨勢(shì)紊浩，但我們不能因?yàn)樗惴ǖ纳?jí)而隨意改變引擎的接口窖铡。

2.4 降低修復(fù)開銷

??糾刪碼的一大劣勢(shì)便是修復(fù)代價(jià)數(shù)倍于副本方案。k+m策略的RS碼在修復(fù)任何一個(gè)數(shù)據(jù)塊時(shí)坊谁，都需要k份的其他數(shù)據(jù)從磁盤上讀取和在網(wǎng)絡(luò)上傳輸费彼。比如10+4的方案下，丟失一個(gè)數(shù)據(jù)塊將必須讀取10個(gè)塊來修復(fù)口芍，整個(gè)修復(fù)過程占用了大量磁盤I/O和網(wǎng)絡(luò)流量箍铲，并使得系統(tǒng)暴露在一種降級(jí)的不穩(wěn)定狀態(tài)。因此鬓椭，實(shí)際系統(tǒng)中應(yīng)該盡量避免使用過大的k值颠猴。

??再生碼便是為了緩解數(shù)據(jù)修復(fù)開銷而被提出的，它能夠極大減少節(jié)點(diǎn)失效時(shí)所需要的吞吐的數(shù)據(jù)量小染。然而其復(fù)雜度大翘瓮，一方面降低了編碼速度，另外一方面犧牲了傳統(tǒng)RS碼的一些優(yōu)秀性質(zhì)裤翩，在工程實(shí)現(xiàn)上的難度也大于傳統(tǒng)糾刪碼资盅。

三、著名引擎對(duì)比

目前被應(yīng)用最廣泛并采用了SIMD加速的引擎有如下幾款：

1.Intel出品的ISA-L[4]

2.J.S.Plank教授領(lǐng)導(dǎo)的Jerasure[5]

3.klauspost的個(gè)人項(xiàng)目（inGolang)[6]

這三款引擎的執(zhí)行效率都非常高踊赠，在實(shí)現(xiàn)上略有出入呵扛，以下是具體分析：

3.1 ISA-L

intel?-storage-acceleration-library Intel存儲(chǔ)加速庫，包括兩個(gè)大類：加密和非加密的筐带。非加密的 crc择份，izip，erase-code烫堤，加密的包括sha512荣赶，sha256，md5鸽斟，sha1等拔创。

核心技術(shù)就是使用intel sse/avx/avx2/avx256的擴(kuò)展指令，并行運(yùn)算多個(gè)流的方法富蓄。單線程比openssl要快2～8倍剩燥。

現(xiàn)在ISA-L已經(jīng)開源：

https://github.com/01org/isa-l

https://github.com/01org/isa-l_crypto

http://www.zhixing123.cn/computer/57905.html

??糾刪碼作為ISA-L庫所提供的功能之一，其性能應(yīng)該是目前業(yè)界最佳。需要注意的是Intel采用的性能測(cè)試方法與學(xué)術(shù)界常用的方式略有出路灭红，其將數(shù)據(jù)塊與冗余塊的尺寸之和除以耗時(shí)作為速度侣滩，而一般的方法是不包含冗余塊的。另外变擒，ISA-L未對(duì)vandermonde矩陣做特殊處理君珠，而是直接拼接單位矩陣作為其編碼矩陣，因此在某些參數(shù)下會(huì)出現(xiàn)編碼矩陣線性相關(guān)的問題娇斑。好在ISA-L提供了cauchy矩陣作為第二方案策添。

ISA-L之所以速度快，一方面是由于Intel諳熟匯編優(yōu)化之道毫缆，其次是因?yàn)樗鼘⒄w矩陣運(yùn)算搬遷到匯編中進(jìn)行唯竹。但這導(dǎo)致了匯編代碼的急劇膨脹，令人望而生畏苦丁。

另外ISA-L支持的指令集擴(kuò)展豐富浸颓，下至SSSE3，上到AVX512旺拉，平臺(tái)適應(yīng)性最強(qiáng)产上。

3.2 Jerasure2.0

??不同于ISA-L直接使用匯編代碼，Jerasure2.0使用C語言封裝后的指令账阻，這樣代碼更加的友好蒂秘。另外Jerasure2.0不僅僅支持GF(2⁸)有限域的計(jì)算，其還可以進(jìn)行GF(2⁴)-GF(2¹²⁸)之間的有限域淘太。并且除了RS碼姻僧，還提供了CauchyReed-Solomoncode（CRS碼）等其他編碼方法的支持。它在工業(yè)應(yīng)用之外蒲牧，其學(xué)術(shù)價(jià)值也非常高撇贺。目前其是使用最為廣泛的編碼庫之一。目前Jerasure2.0并不支持AVX加速冰抢，盡管如此松嘶，在僅使用SSE的情況下，Jerasure2.0依然提供了非常高的性能表現(xiàn)挎扰。不過其主要作者之一JamesS.Plank教授轉(zhuǎn)了研究方向翠订，另外一位作者Greenan博士早已加入工業(yè)界。因此后續(xù)的維護(hù)將是個(gè)比較大的問題遵倦。

3.3 klauspost的ReedSolomon

??klauspost利用Golang的匯編支持尽超，友好地使用了SIMD技術(shù)，此款引擎的SIMD加速部分是目前我看到的實(shí)現(xiàn)中最為簡(jiǎn)潔的梧躺，矩陣運(yùn)算的部分邏輯被移到了外層高級(jí)語言中似谁，加上Golang自帶的匯編支持，使得匯編代碼閱讀起來更佳的友好。不過Go并沒有集成所有指令巩踏，部分指令不得不利用YASM等匯編編譯器將指令編譯成字節(jié)序列寫入?yún)R編文件中秃诵。一方面導(dǎo)致了指令的完全不可讀，另外一方面這部分代碼的語法風(fēng)格是Intel而非Golang匯編的AT&T風(fēng)格塞琼，平添了迷惑菠净。這款引擎比較明顯的缺陷有兩點(diǎn)：1.對(duì)于較大的數(shù)據(jù)塊，編碼速度會(huì)有巨大的下滑屈梁；2.修復(fù)速度明顯慢于編碼速度嗤练。

3.4 編碼速度對(duì)比

??我在這里選取了IntelISA-L（圖中intel),klauspost的ReedSolomon(圖中k),以及自研的一款引擎2這三款引擎進(jìn)行編碼效率的對(duì)比,這三款引擎均支持avx2加速榛了。測(cè)試結(jié)果如下：

image

注：

編碼速度計(jì)算公式在讶，測(cè)試方法與上一節(jié)相同。其中isa-l默認(rèn)的速度計(jì)算方式與公式有沖突霜大，需要修改為一致

測(cè)試平臺(tái)：AWSt2.microIntel?Xeon?CPUE5-2676v3@2.40GHz,Memory1GB

編碼方案：10+4

klauspost的引擎默認(rèn)開了并發(fā)构哺，測(cè)試中需要將并發(fā)數(shù)設(shè)置為1

參考文章：
高性能糾刪碼編碼
基于柯西矩陣的Erasure Code技術(shù)詳解
Erasure Code - EC糾刪碼原理