如何選擇糾刪碼編碼引擎 | 糾刪碼技術(shù)詳解（上）

作者介紹： 
徐祥曦，七牛云工程師，獨(dú)立開發(fā)了多套高性能糾刪碼/再生碼編碼引擎。
柳青，華中科技大學(xué)博士，研究方向?yàn)榛诩m刪碼的分布式存儲(chǔ)系統(tǒng)。

前言：
隨著數(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ì)有效的方式來(lái)保障數(shù)據(jù)安全。

副本與糾刪碼都是通過(guò)增加冗余數(shù)據(jù)的方式來(lái)保證數(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 等等國(guó)際巨頭，在國(guó)內(nèi)以淘寶、華為、七牛云等為代表的公司也在自己的存儲(chǔ)系統(tǒng)上應(yīng)用了糾刪碼。

最典型的糾刪碼算法是里德-所羅門碼（Reed-Solomon 碼，簡(jiǎn)稱 RS 碼）。RS 碼最早應(yīng)用于通信領(lǐng)域，經(jīng)過(guò)數(shù)十年的發(fā)展，其在存儲(chǔ)系統(tǒng)中得到廣泛應(yīng)用，比如光盤中使用 RS 碼進(jìn)行容錯(cuò)，防止光盤上的劃痕導(dǎo)致數(shù)據(jù)不可讀；生活中經(jīng)常使用的二維碼就利用了RS 碼來(lái)提高識(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)的決策者帶來(lái)了困擾——究竟什么樣的編碼引擎才是高效的呢？

我們將以這個(gè)問(wèn)題展開對(duì)糾刪碼技術(shù)的剖析，幫助企業(yè)更全面，深入的了解糾刪碼在存儲(chǔ)系統(tǒng)中的應(yīng)用并更好地做出技術(shù)選型。本系列文章將從糾刪碼的基本原理開始，隨后引出如何判斷編碼引擎優(yōu)劣這個(gè)問(wèn)題，接下來(lái)將深度分析代碼實(shí)現(xiàn)，幫助開發(fā)者順利完成定制開發(fā)。

本系列共計(jì)上下兩篇篇文章：

（上篇）如何選擇糾刪碼編碼引擎

（下篇）實(shí)現(xiàn)高性能糾刪碼引擎

本文作為系列首篇，我們將一起探討糾刪碼的編碼原理與如何選擇編碼引擎這兩個(gè)問(wèn)題。

一 、糾刪碼編碼原理

在展開分析之前，我們先來(lái)看一看 RS 碼是如何工作的。

下圖展示了 3+2（3 份數(shù)據(jù)，2 份冗余）下對(duì) 2 字節(jié)長(zhǎng)度的數(shù)據(jù)進(jìn)行編碼與數(shù)據(jù)修復(fù)過(guò)程：

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

下面介紹解碼過(guò)程，當(dāng) 1，2 兩塊數(shù)據(jù)丟失，即：

當(dāng)數(shù)據(jù)塊發(fā)生丟失，在編碼矩陣中去掉相應(yīng)行，等式仍然保持成立。這為我們接下來(lái)恢復(fù)原始數(shù)據(jù)提供了依據(jù)。

原始數(shù)據(jù)的修復(fù)過(guò)程如下：

為了恢復(fù)數(shù)據(jù)，首先我們求剩余編碼數(shù)據(jù)的逆矩陣，等式兩邊乘上這個(gè)逆矩陣仍然保持相等。與此同時(shí)，互逆矩陣的乘積為單位矩陣，因此可以被消掉。那么所求得的逆矩陣與剩余塊的數(shù)據(jù)的乘積就是原始數(shù)據(jù)了。

數(shù)據(jù)編碼以字節(jié)為單位，如果將被編碼數(shù)據(jù)看做一個(gè)「數(shù)組」，「數(shù)組」中每個(gè)元素是一個(gè)字節(jié)，數(shù)據(jù)按照字節(jié)順序被編碼。編碼過(guò)程是計(jì)算編碼矩陣中元素和「數(shù)組」的乘積過(guò)程。為保證乘積的運(yùn)算結(jié)果仍舊在一個(gè)字節(jié)大小以內(nèi)（即 0-255），必須應(yīng)用到有限域[1]。有限域上的算術(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（Single Instruction Multiple Data）指令集，比如 Intel 支持的 SSE 指令集最大支持 128 bits 的數(shù)據(jù)運(yùn)算，AVX2 指令集最大支持 512 bits 的數(shù)據(jù)運(yùn)算。它們?yōu)槲覀儗?duì)一個(gè)「數(shù)組」數(shù)據(jù)分別執(zhí)行相同的操作，提高了數(shù)據(jù)運(yùn)算的并行性。目前，市面上所有高性能的糾刪碼引擎均采用了該項(xiàng)技術(shù)以提高編解碼性能。

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

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

1、 高編/解碼速度；

2、參數(shù)可配置；

3、編碼速度穩(wěn)定性；

4、代碼簡(jiǎn)潔、穩(wěn)定；

5 、降低修復(fù)開銷等。

2.1 高編/解碼速度

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

速度是最基本的要求。不過(guò)在這里我很難給出一個(gè)絕對(duì)的數(shù)字來(lái)衡量速度，因?yàn)槠涫軈?shù)，運(yùn)行平臺(tái)的影響極大。在下文中提到的三款引擎均有出色的性能表現(xiàn)，可以以它們?yōu)榛鶞?zhǔn)來(lái)衡量引擎的編碼速度。除此之外，我們還可以將逐字節(jié)查表（下稱基本方法）的編碼速度與利用 SIMD 技術(shù)加速的編碼速度做對(duì)比，兩者之間應(yīng)該有非常直觀的差距。以我的個(gè)人電腦為例（i5-4278U 2.6GHz),在 10+4 的策略下（每個(gè)數(shù)據(jù)塊大小為 128KB），基本方法的速度為（原始數(shù)據(jù)總量/編碼耗時(shí)）318.1 MB/s，而通過(guò) AVX2 指令集加速后達(dá)到了 5558.6 MB/s[2],在 SSSE3 指令集的加速下也有 2978.87 MB/s 。

另外，解碼速度應(yīng)該大于或等于編碼速度（視丟失的數(shù)據(jù)塊數(shù)量而定），下圖截自在我本機(jī)上運(yùn)行的修復(fù)原始數(shù)據(jù)塊的性能測(cè)試結(jié)果：

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 編碼速度穩(wěn)定性

速度的穩(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)行定長(zhǎng)分塊，依次編碼，分塊大小和緩存大小保持一定關(guān)系：以 10+4 編碼方法為例，對(duì)比數(shù)據(jù)塊尺寸分別為取 L3 Cache Size 的 1/12 以及 12 倍。如 L3 Cache Size 的大小為 12MB，則每一塊的數(shù)據(jù)尺寸分別取 1MB，144MB。倘若大數(shù)據(jù)塊下編碼速度遠(yuǎn)遠(yuǎn)低于小數(shù)據(jù)塊，則說(shuō)明該引擎 CPU cache 的優(yōu)化工作做得不充分。對(duì)于上述參數(shù)來(lái)說(shuō)，大數(shù)據(jù)塊的速度應(yīng)該不低于小數(shù)據(jù)塊的 70% 。同樣以我的個(gè)人電腦為例（L3 Cache 大小為 3MB）：

2.4 代碼簡(jiǎn)潔、穩(wěn)定

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

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

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

2.5 降低修復(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è)塊來(lái)修復(fù)，這個(gè)修復(fù)過(guò)程占用大量磁盤 I/O 和網(wǎng)絡(luò)流量，并使得系統(tǒng)暴露在一種降級(jí)的不穩(wěn)定狀態(tài)。因此，實(shí)際系統(tǒng)中應(yīng)該盡量避免使用過(guò)大的 k 值。

再生碼[2] 便是為了緩解數(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[4]

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

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

3.1 ISA-L

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

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

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

3.2 Jerasure2.0

不同于 ISA-L 直接使用匯編代碼，Jerasure2.0 使用 C 語(yǔ)言封裝后的指令，這樣代碼更加的友好。另外 Jerasure2.0 不僅僅支持 GF(2^8) 有限域的計(jì)算，其還可以進(jìn)行 GF(2^4) - GF(2^128) 之間的有限域。并且除了 RS 碼，還提供了 Cauchy Reed-Solomon code （CRS 碼）等其他編碼方法的支持。它在工業(yè)應(yīng)用之外，其學(xué)術(shù)價(jià)值也非常高。目前其是使用最為廣泛的編碼庫(kù)之一。目前 Jerasure2.0 并不支持 AVX 加速，盡管如此，不過(guò)在僅使用 SSE 的情況下，Jerasure2.0 依然提供了非常高的性能表現(xiàn)。不過(guò)主要作者之一 James S. Plank 教授轉(zhuǎn)了研究方向，另外一位作者 Greenan 博士早已加入工業(yè)界。因此后續(xù)的維護(hù)將是個(gè)比較大的問(wèn)題。

3.3 klauspost 的 ReedSolomon

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

四、自己實(shí)現(xiàn)一款引擎

可能是由于對(duì)開源庫(kù)后續(xù)維護(hù)問(wèn)題的擔(dān)憂，也有可能是現(xiàn)有方案并不能滿足企業(yè)對(duì)某些特定需求和偏好，很多公司選擇了自研引擎。那么如何寫出高效的代碼呢？在上面的簡(jiǎn)單介紹中，受限于篇幅我跳過(guò)了很多細(xì)節(jié)。比如 SIMD 技術(shù)是如何為糾刪碼服務(wù)的，以及如何利用 CPU Cache 做優(yōu)化等諸多重要問(wèn)題。我們會(huì)在后續(xù)的文章中逐步展開其實(shí)現(xiàn)，歡迎大家繼續(xù)關(guān)注。

附錄：

1. 許以超 馬松雅. 代數(shù)編碼與密碼[M]. 北京:高等教育出版社, 2015.

2. 徐祥曦 Reed-Solomon

3. Alexandros G Dimakis, P Godfrey, Yunnan Wu, Martin J Wainwright, and Kannan Ramchan-dran. Network coding for distributed storage systems. Information Theory, IEEE Transactions on, 56(9):4539–4551, 2010.

4. Intel ISA-L

5. Jerasure

6. klauspost Reed-Solomon