《如何選擇并實現(xiàn)高性能糾刪碼編碼引擎(上）》要點：
本文介紹了如何選擇并實現(xiàn)高性能糾刪碼編碼引擎(上），希望對您有用。如果有疑問，可以聯(lián)系我們。

作者介紹：

徐祥曦,七牛云工程師,獨立開發(fā)了多套高性能糾刪碼/再生碼編碼引擎.柳青,華中科技大學(xué)博士,研究方向為基于糾刪碼的分布式存儲系統(tǒng).

前言：

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

副本與糾刪碼都是通過增加冗余數(shù)據(jù)的方式來保證數(shù)據(jù)在發(fā)生部分丟失時,原始數(shù)據(jù)不發(fā)生丟失.但相較于副本,糾刪碼能以低得多的存儲空間代價獲得相似的可靠性.比如3副本下,存儲開銷為3,因為同樣的數(shù)據(jù)被存儲了三份,而在10+3(將原始數(shù)據(jù)分為10份,計算3份冗余)的糾刪碼策略下,存儲開銷為為1.3.采用糾刪碼能夠極大地減少存儲系統(tǒng)的存儲開銷,減少硬件、運維和管理成本,正是這樣巨大的收益驅(qū)使各大公司紛紛將糾刪碼應(yīng)用于自己的存儲系統(tǒng),比如Google、Facebook、Azure、EMC等等國際巨頭,在國內(nèi)以淘寶、華為、七牛云等為代表的公司也在自己的存儲系統(tǒng)上應(yīng)用了糾刪碼.

最典型的糾刪碼算法是里德-所羅門碼(Reed-Solomon碼,簡稱RS碼).RS碼最早應(yīng)用于通信領(lǐng)域,經(jīng)過數(shù)十年的發(fā)展,其在存儲系統(tǒng)中得到廣泛應(yīng)用,比如光盤中使用RS碼進行容錯,防止光盤上的劃痕導(dǎo)致數(shù)據(jù)不可讀；生活中經(jīng)常使用的二維碼就利用了RS碼來提高識別的成功率.近年RS碼在分布式存儲系統(tǒng)中的應(yīng)用被逐漸推廣,一方面是分布式存儲系統(tǒng)存儲的存儲容量和規(guī)模增大的需求；另一方面是由于糾刪碼編碼速度在近年得到迅猛提升.隨著對高性能糾刪碼引擎在實際系統(tǒng)中應(yīng)用需要,也催生了對糾刪碼在具體系統(tǒng)中實現(xiàn)的各種優(yōu)化手段.并為相關(guān)的決策者帶來了困擾——究竟什么樣的編碼引擎才是高效的呢?

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

本文作為系列首篇,我們將一起探討糾刪碼的編碼原理與如何選擇編碼引擎這兩個問題.

一、糾刪碼編碼原理

在展開分析之前,我們先來看一看RS碼是如何工作的.

下圖展示了3+2(3份數(shù)據(jù),2份冗余)下對2字節(jié)長度的數(shù)據(jù)進行編碼與數(shù)據(jù)修復(fù)過程：

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

下面介紹解碼過程,當1,2兩塊數(shù)據(jù)丟失,即：

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

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

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

數(shù)據(jù)編碼以字節(jié)為單位,如果將被編碼數(shù)據(jù)看做一個「數(shù)組」,「數(shù)組」中每個元素是一個字節(jié),數(shù)據(jù)按照字節(jié)順序被編碼.編碼過程是計算編碼矩陣中元素和「數(shù)組」的乘積過程.為保證乘積的運算結(jié)果仍舊在一個字節(jié)大小以內(nèi)(即0-255),必須應(yīng)用到有限域[1].有限域上的算術(shù)運算不同于通常實數(shù)的運算規(guī)則.我們通常事先準備好乘法表,并在算術(shù)運算時對每一次乘法進行查表得到計算結(jié)果.早期的編碼引擎之所以性能不佳,是因為逐字節(jié)查表的性能是非常低的.倘若能一次性對多字節(jié)進行查表以及相應(yīng)的吞吐和運算,引擎的工作效率必將大幅度提升.

許多CPU廠商提供了包含更多位數(shù)的寄存器(大于64位),這類寄存器和相應(yīng)支持的運算使得用戶程序可以同時對大于機器位數(shù)的數(shù)據(jù)進行運算,支持這類寄存器和運算的指令稱之為SIMD(SingleInstructionMultipleData)指令集,比如Intel支持的SSE指令集最大支持128bits的數(shù)據(jù)運算,AVX2指令集最大支持512bits的數(shù)據(jù)運算.它們?yōu)槲覀儗σ粋€「數(shù)組」數(shù)據(jù)分別執(zhí)行相同的操作,提高了數(shù)據(jù)運算的并行性.目前,市面上所有高性能的糾刪碼引擎均采用了該項技術(shù)以提高編解碼性能.

二、編碼引擎評判標準

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

1、高編/解碼速度；

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

3、代碼簡潔、穩(wěn)定；

4、降低修復(fù)開銷等.

2.1高編/解碼速度

無須多言,編/解碼性能是最基本也是最重要的指標.對于一款性能優(yōu)異的引擎來說,應(yīng)該同時滿足以下幾個指標：

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

不亞于目前最出色的幾款引擎的性能表現(xiàn)(詳見第三章著名引擎對比)

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

編/解碼速度穩(wěn)定,對于不同尺寸的數(shù)據(jù)塊會有相近的性能表現(xiàn).由于系統(tǒng)緩存的影響,當被編碼數(shù)據(jù)的大小和緩存大小相當時,編碼應(yīng)該具有最快的速度.當編碼數(shù)據(jù)的大小大于緩存大小時,內(nèi)存帶寬成為編碼速度的瓶頸,文件大小和編碼時間呈現(xiàn)近似線性關(guān)系.這樣,數(shù)據(jù)編碼時間是可預(yù)期的,用戶的服務(wù)質(zhì)量也是可保障的.在實際中,我們對于大文件進行定長分塊,依次編碼,分塊大小和緩存大小保持一定關(guān)系.

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

注：

測試平臺：MacBookPro(Retina,13-inch,Mid2014),2.6GHzi5-4278U(3MBL3CacheSize),8GB1600MHzDDR3

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

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

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

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

作為對比,利用go語言自帶的copy函數(shù)(copy),對k個數(shù)據(jù)塊進行內(nèi)存拷貝.copy同樣使用了SIMD技術(shù)進行加速

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

注：

測試平臺與上文的編碼測試相同

lostdata=丟失數(shù)據(jù)塊數(shù)目(個)

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

2.2參數(shù)可配置

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

2.3代碼簡潔、穩(wěn)定

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

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

比如早先的SIMD加速是基于SSE指令集擴展來做的,隨后Intel又推出AVX指令集進一步提高了性能,引擎應(yīng)該能即時跟上硬件進步的步伐.再比方說,再生碼[5](可以理解為能減少修復(fù)開銷的糾刪碼)是將來發(fā)展的趨勢,但我們不能因為算法的升級而隨意改變引擎的接口.

2.4降低修復(fù)開銷

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

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

三、著名引擎對比

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

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

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

3.klauspost的個人項目(inGolang)[6]

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

3.1ISA-L

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

ISA-L之所以速度快,一方面是由于Intel諳熟匯編優(yōu)化之道,其次是因為它將整體矩陣運算搬遷到匯編中進行.但這導(dǎo)致了匯編代碼的急劇膨脹,令人望而生畏.

另外ISA-L支持的指令集擴展豐富,下至SSSE3,上到AVX512,平臺適應(yīng)性最強.

3.2Jerasure2.0

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

3.3klauspost的ReedSolomon

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

3.4編碼速度對比

我在這里選取了IntelISA-L(圖中intel),klauspost的ReedSolomon(圖中k),以及自研的一款引擎[2](圖中xxx)這三款引擎進行編碼效率的對比,這三款引擎均支持avx2加速.測試結(jié)果如下：

注：

編碼速度計算公式,測試方法與上一節(jié)相同.其中isa-l默認的速度計算方式與公式有沖突,需要修改為一致

測試平臺：AWSt2.microIntel(R)Xeon(R)CPUE5-2676v3@2.40GHz,Memory1GB

編碼方案：10+4

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

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

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

轉(zhuǎn)載請注明本頁網(wǎng)址：
http://www.fzlkiss.com/jiaocheng/4083.html