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

作者介紹：

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

前言：

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

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

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

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

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

一、糾刪碼編碼原理

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

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

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

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

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

原始數據的修復過程如下：

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

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

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

二、編碼引擎評判標準

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

1、高編/解碼速度；

2、參數可配置；

3、代碼簡潔、穩定；

4、降低修復開銷等.

2.1高編/解碼速度

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

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

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

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

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

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

注：

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

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

測試方法：在內存中生成隨機數據,運行若干次編／解碼,取平均值

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

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

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

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

注：

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

lostdata=丟失數據塊數目(個)

原始數據塊每塊大小為128KB,總大小為1280KB

2.2參數可配置

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

2.3代碼簡潔、穩定

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

接下來的可維護性也非常重要.首先是接口穩定,不會隨著新技術的引入而導致代碼大規模重構；另外代碼必須經過有合理的測試模塊以便在后續的更新中校驗新算法.

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

2.4降低修復開銷

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

再生碼便是為了緩解數據修復開銷而被提出的,它能夠極大減少節點失效時所需要的吞吐的數據量.然而其復雜度大,一方面降低了編碼速度,另外一方面犧牲了傳統RS碼的一些優秀性質,在工程實現上的難度也大于傳統糾刪碼.

三、著名引擎對比

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

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

2.J.S.Plank教授領導的Jerasure[5]

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

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

3.1ISA-L

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

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

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

3.2Jerasure2.0

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

3.3klauspost的ReedSolomon

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

3.4編碼速度對比

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

注：

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

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

編碼方案：10+4

klauspost的引擎默認開了并發,測試中需要將并發數設置為1

四、自己實現一款引擎

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

轉載請注明本頁網址：
http://www.snjht.com/jiaocheng/4083.html