基于CUDA的RS糾刪碼性能優化

戴世航，李小勇

?

基于CUDA的RS糾刪碼性能優化

戴世航，李小勇

摘 要：目前分布式存儲系統中保證數據可用性的常用方法有多副本技術和糾刪碼技術。與多副本技術相比，糾刪碼技術有更高的存儲空間利用率，但附加的編碼流程不可避免地帶來了較高的時間延遲，影響了系統的實時性，限制了糾刪碼的應用。為了提高糾刪碼的編碼效率，對開源代碼庫Jerasure提供的RS糾刪碼進行優化，利用CUDA對其進行加速。實驗結果顯示，相對于原始算法，該方法將編碼速度提高了約20倍，為糾刪碼技術應用于實時系統提供了可能。

關鍵詞：RS糾刪碼；CUDA；GPU加速

0 引言

如今，人類社會已經進入了大數據時代。隨著各種新興媒體、數據倉庫、社交網絡的飛速發展，預計2020年數據總量將達到35萬ZB。為存儲數量如此巨大的數據，各種分布式存儲系統應用而生。

分布式存儲系統往往建立在大量廉價機器上，系統中節點故障不可避免，如何才能在這樣的環境下保證存儲數據的高可用性得到了廣泛的研究。實踐中最常用的方法是多副本技術，通過將文件以多個副本的形式存入存儲系統中以實現冗余容錯，只要其中一個副本沒有損壞，用戶就可以正常訪問到文件。但多副本技術存儲冗余度高這一缺點也隨著數據規模增大而日益突出，而糾刪碼技術在這一方面則具有明顯優勢。不過由于糾刪碼的運算開銷較大，實時性差，因此可應用的場景受到限制。

本文針對糾刪碼技術的這一缺點，在開源糾刪碼庫Jerasure[1]提供的RS糾刪碼reed_sol_r6_op算法（后文簡稱為r6算法）的基礎上，利用GPU強大的并行計算能力，使用CUDA對其進行加速，獲得了很好的加速效果，速度可達原始算法的20倍，為糾刪碼技術在對實時性要求較高的存儲系統中應用提供了可能。

1 RS糾刪碼

糾刪碼技術的基本思想是：首先將文件分割成k個數據塊，然后依照特定的糾刪碼算法對這k個數據塊進行計算得到m個編碼塊，這一過程被稱為編碼。編碼完成后，在存儲系統中分布式存儲這這k+m個文件塊。當有任何文件塊出現錯誤時，利用其他文件塊來恢復它的信息，這一過程被稱為重構或者解碼。一般而言，一組文件塊最多可以容忍m個文件塊出錯。

和多副本技術相比，糾刪碼技術的最大特點是大大降低了數據冗余度，提高了存儲空間的利用率，減少了存儲成本。舉例來說，常用的多副本技術一般為每個文件提供3個副本，數據冗余度為300%，存儲空間的利用率僅為三分之一；而常用4+2糾刪碼（為每4個數據塊計算得到2個編碼塊），將數據冗余度降至150%，存儲空間的利用率翻了一倍達到了三分之二。糾刪碼技術在這方面的優異性能也是它得到越來越多關注的原因。

RS糾刪碼，全稱為Reed-Solomon編碼，是目前應用最廣的糾刪碼算法，使用特定的生成矩陣計算得到編碼塊，過程如圖1所示：

圖1　RS糾刪碼編碼過程

RS糾刪碼最大的特點在于它可以適用于任意k+m的組合。根據生成矩陣的不同RS糾刪碼被分為兩類：一類是范德蒙RS糾刪碼，另一類是柯西RS糾刪碼。范德蒙RS糾刪碼是以范德蒙矩陣為生成矩陣的，而柯西RS糾刪碼則是以柯西矩陣為生成矩陣的。但無論是哪一種，編碼原理都是在有限域上的多項式運算，而有限域上乘法運算極其復雜，這導致其編解碼運算速度很慢，時間開銷很高。由于這樣的原因，RS糾刪碼在實踐中一般用在對實時性要求不高，或者是更新頻率較低的云存儲系統中[2]。

2 基于CUDA加速的r6算法

2.1 GPU計算優勢

GPU最初用于3D圖形處理，但經過不斷的發展，GPGPU（General Purpose GPU，通用計算GPU）技術得到了不斷發展。相對于CPU使用大量晶體管用作復雜的控制單元和緩存以提高少量執行單元的執行效率，GPU將更多的晶體管用作執行單元，因此GPU在處理能力和存儲器帶寬上有明顯優勢。同時由于GPU中可以同時運行大量的線程，在并行計算上有著先天的優勢。另外，GPU的造價和功耗相對于相同計算能力的CPU要低很多，在一定程度上滿足了無法使用高端主機卻需要處理海量數據的用戶的需求。

2.2 CUDA編程模型

2007年NVDIA公司推出了CUDA（Compute Unified Device Architecture，統一計算設備架構），這是一種將GPU作為數據并行計算設備的軟硬件體系，為開發人員有效利用GPU的強大性能提供了條件。

CUDA編程模型采用單指令流多數據流（Single Instruction Multiple Data）執行模式。在這個模型中，CPU 和GPU協同工作，CPU稱為主機（Host），負責進行邏輯性強的事務處理和串行計算，GPU作為設備（Device），負責執行高度線程化并行處理任務。運行在GPU上的CUDA計算函數被稱為kernel（內核函數），一個完整的CUDA程序時由一系列的設備端kernel并行步驟和主機端的串行步驟共同組成的，如圖2所示：

圖2　CUDA編程模型

一個CUDA程序中，基本的主機端代碼主要完成以下功能：啟動CUDA，為數據分配內存和顯存空間，將內存中數據拷貝到顯存，調用設備端的kernel進行計算，將顯存中的結果拷貝到內存中，執行串行代碼，釋放內存和顯存空間，退出CUDA；基本的設備端代碼主要完成以下功能：從顯存讀數據到GPU片中，對數據進行處理，將處理后的數據寫回顯存[3]。

CUDA通過將計算任務映射成大量的可以并行執行的線程，并由硬件動態調度和執行這些線程來提供給使用者GPU強大的計算能力。為了便于使用和管理這些線程，CUDA將這些線程在2個層次上組織起來，分別是grid中block間的并行和block中thread間的并行，如圖3所示：

圖3　CUDA線程組織形式

kernel實質上是以block為單位執行的，block之間無法通信，也沒有執行順序，但同一block中的thread可以通過共享存儲器（shared memory）交換數據，同時每個thread都有獨立的register和local memory用于儲存計算時所需數據。在kernel運行時，使用者可以通過相應的索引準確定位到grid中的每一個block和block中的每一個thread，進而為每一個線程分配獨立的計算任務。從宏觀上看，同時可以能有成千上萬個線程正在工作，這也是GPU強大計算能力的體現[3]。

2.3 r6算法

傳統的RS糾刪碼能夠滿足任一k、m的組合，因而有很好的適用性，但正如前文所介紹的，由于在有限域上的乘法復雜度較高，性能不能令人滿意，雖然柯西RS糾刪碼可以可以將有限域上的乘法運算轉換成異或運算，但性能提升也比較有限，而且本身的運算依然比較復雜，不易使用GPU運算來進行加速。而r6算法借鑒了陣列糾刪碼的思想，不再使用矩陣乘法來得到編碼塊，而是通過對數據塊進行異或運算來得到編碼塊。與陣列糾刪碼不同的是，r6算法中一個文件的編碼塊僅由自己的數據塊計算得到，而不是跨文件編碼。由于不再使用靈活的生成矩陣，r6算法無法應用于任一k、m組合，而是像raid-6一樣，將m的值固定為2。算法流程如下：

1）將文件劃分成為多個數據塊d0、d1、d2、…、dk-1；

2）將d0、d1、d2、…、dk-1通過異或運算得到第一個編碼塊c0；

3）對每一個數據塊進行變換得到d0’、d1’、d2’、…、dk-1’，這里di'= 2i * di，其中0≤i≤k-1；

4）對d0’、d1’、d2’、…、dk-1’通過異或運算得到第二個編碼塊c1;

本文使用CUDA對步驟2、3、4進行加速，如圖4所示：

圖4　r6算法編碼示意圖

在r6算法的編碼過程中，不再需要生成生成矩陣，也回避了邏輯復雜的有限域上的矩陣乘法，算法實現邏輯簡單，大大減少了使用CUDA編程時的工作量。當由于數據丟失需要重構時，該算法與傳統k+2 RS糾刪碼一樣，可以在至多兩個文件塊損壞的情況下恢復出原數據。

雖然在r6算法中，m被指定為2，失去了一定的靈活性。但在實踐中依然可以通過調整k值來滿足特定的場景需求，比如如果數據比較重要，可以采用4+2的編碼方式，而如果存儲的是冷數據，可以使用12+2的編碼方式，同時還可以通過調整編碼時的其他參數來優化編碼性能，這些手段也使得該算法在實踐中依然具有一定的適用性。

2.4 CUDA加速策略

在編碼步驟2、3、4中，需要對待編碼的文件塊進行規模巨大、但邏輯簡單的算術運算，在CPU中，這些無所謂先后順序運算在循環中串行執行，時間開銷巨大，因此對這里使用CUDA進行加速。為充分運用GPU的性能，設定每個block維護1024個線程，這也是一個block最多能夠維護的線程數量，然后根據每次處理的數據大小，動態設定grid中維護的block數量。通過這樣的修改，將原來由CPU進行的串行運算轉換成為由GPU中大量線程同時執行的并行運算，大大減少了時間開銷。

在實驗過程中，發現雖然單純的計算過程中使用CUDA加速的代碼有著明顯的計算優勢，但是一旦考慮到申請內存、顯存，數據在內存、顯存之間傳遞等操作帶來的時間開銷，GPU的執行效率便大打折扣。因此如何減少申請內存、顯存和數據在內存、顯存中傳遞帶來的時間開銷成為了優化算法的關鍵。為此本算法使用了zero-copy技術，使用CUDA提供的API cudaHostAlloc()直接申請不會被換入低速虛擬內存的頁鎖定內存，并通過cudaHostGetDevicePointer()將頁鎖定內存映射到設備地址空間，這樣GPU便可以直接訪問內存中的數據，無須分配顯存空間，也不必在內存和顯存之間進行數據拷貝，也就是達到了zero-copy的效果，申請空間和數據傳輸的時間延遲得以回避，使得性能得到了極大的提升。

3 實驗與性能分析

實驗的環境如下：

CPU：Intel(R) Pentium(R) G630，主頻為2.70GHz；

內存：6G；

顯卡：GTX 660，顯存為2G；

操作系統：Ubuntu 14.04.2。

實驗中，使用的糾刪碼模式為4+2，分別使用大小為154.3MB（文件1）和2.1G（文件2）的文件進行測試，測試結果如圖5所示：

圖5　CPU/GPU編碼速度測試結果

為排除偶然因素帶來的誤差，每個數據都是測試10次之后取平均得到的。圖中buff_size為每次處理的數據大小。

從實驗結果可以看出，無論測試文件大小，使用CUDA加速后的代碼編碼速度都有大幅度的提升，原r6算法編碼速度基本在500MB/s上下，而在CUDA加速后，雖然性能隨參數變化有較大波動，但最低也能達到4GB/s，平均速度在10GB/s左右，速度提高了接近20倍。特別是當文件比較大時，如果參數選擇合適甚至可以達到16GB/s，達到30倍的加速比。同時從圖5中可以看出，隨著buff_size的不斷增大，編碼速度呈現出先增后減的趨勢，這是因為雖然在編碼時每次并行處理的數據越多，編碼越快，但是維護較大內存、顯存的開銷也會比較大，所以在具體實踐中時仍需要根據操作環境的不同，在并行度和內存、顯存的維護之間做出適當的折中，選擇合適的參數以保證系統有較高的效率。從實驗結果可以看出，對于大文件，buff_size選擇64MB或者128MB時性能較優。

4 總結

本文以開源糾刪碼庫Jerasure中提供的r6算法為原型，利用CUDA對其代碼進行加速，并通過申請、使用頁鎖定內存，回避了數據在內存和顯存中來回拷貝帶來的時間開銷。經實驗測試，經加速后的r6算法編碼速度平均可達10GB/s，相當于原r6算法的20倍，為糾刪碼在實時性要求比較高的分布式存儲系統中的應用提供了可能。

參考文獻

[9] Plank J S, Simmerman S, Schuman C D. Jerasure: A library in C/C++ facilitating erasure coding for storage applications-Version 1.2[R]. Technical Report CS-08-627, University of Tennessee, 2008.

[10] 羅象宏,舒繼武.存儲系統中的糾刪碼研究綜述[J].計算機研究與發展,2012,01:1-11.

[11] Nvidia Corporation. NVIDIA CUDA Programming Guide[M]. Santa Clara, USA: Nvidia Corporation, 2011.

CUDA-based Performance Optimization of RS Erasure Coding

Dai Shihang, Li Xiaoyong
(College of Information Security, Shanghai Jiao Tong University, Shanghai 200240, China)

Abstract:At present, the ways used by distributed storage system to ensure the availability of data mainly have multi-replicate and erasure coding technologies. Compared with multi-replicate, erasure coding saves more storage space, however, it takes more time in encoding, which has a bad effect in speed, and limits its application. In order to improve the encoding efficiency of erasure coding, an algorithm provided in the open-source library Jerasure is accelerated by CUDA in this paper. The test result shows that the accelerated algorithm is about 20 times faster than the original one.

Key words:RS Erasure Coding; CUDA; GPU Acceleration

收稿日期：（2015.09.21）

作者簡介：戴世航（1991-），男，吉林延邊，上海交通大學，信息安全工程學院，碩士研究生，研究方向：云存儲、糾刪碼，上海，200240李小勇（1972-），男，甘肅天水，上海交通大學，信息安全工程學院，副教授，博士，研究方向：海量存儲、高性能網絡、嵌入式系統、上海，200240

文章編號：1007-757X(2016)01-0070-03

中圖分類號：TP311

文獻標志碼：A