戴世航，李小勇

?

基于CUDA的RS糾刪碼性能優(yōu)化

戴世航，李小勇

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

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

0 引言

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

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

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

1 RS糾刪碼

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

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

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

圖1　RS糾刪碼編碼過程

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

2 基于CUDA加速的r6算法

2.1 GPU計算優(yōu)勢

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

2.2 CUDA編程模型

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

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

圖2　CUDA編程模型

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

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

圖3　CUDA線程組織形式

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

2.3 r6算法

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

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

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

3）對每一個數(shù)據(jù)塊進行變換得到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算法的編碼過程中，不再需要生成生成矩陣，也回避了邏輯復雜的有限域上的矩陣乘法，算法實現(xiàn)邏輯簡單，大大減少了使用CUDA編程時的工作量。當由于數(shù)據(jù)丟失需要重構時，該算法與傳統(tǒng)k+2 RS糾刪碼一樣，可以在至多兩個文件塊損壞的情況下恢復出原數(shù)據(jù)。

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

2.4 CUDA加速策略

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

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

3 實驗與性能分析

實驗的環(huán)境如下：

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

內(nèi)存：6G；

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

操作系統(tǒng)：Ubuntu 14.04.2。

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

圖5　CPU/GPU編碼速度測試結(jié)果

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

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

4 總結(jié)

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

參考文獻

[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] 羅象宏,舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[J].計算機研究與發(fā)展,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-），男，甘肅天水，上海交通大學，信息安全工程學院，副教授，博士，研究方向：海量存儲、高性能網(wǎng)絡、嵌入式系統(tǒng)、上海，200240

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

中圖分類號：TP311

文獻標志碼：A