Jerasure庫(kù)提供Reed-Solomon和Cauchy Reed-Solomon兩種編碼算法的實(shí)現(xiàn).

Reed-Solomon編解碼接口

1. 編碼矩陣生成

??? // generate matrix, last m rows
? matrix = talloc(int, m*k);
? for (i = 0; i < m; i++) {
???? for (j = 0; j < k; j++) {
???? matrix[i*k+j] = galois_single_divide(1, i ^ (m + j), w);
???? }
? }?

2. 編碼接口

void jerasure_matrix_encode(int k, int m, int w, int *matrix,? char **data_ptrs, char **coding_ptrs, int size)

• k: 數(shù)據(jù)塊個(gè)數(shù)
• m: 校驗(yàn)塊個(gè)數(shù)
• w: WORD SIZE
• matrix：編碼矩陣 （m*k，上面的k*k為單位陣）
• data_ptrs：數(shù)據(jù)塊指針 (長(zhǎng)度為k的指針數(shù)組)
• coding_ptrs：校驗(yàn)塊指針(長(zhǎng)度為m的指針數(shù)組)
• size：數(shù)據(jù)塊大小（必須是sizeof(long)的倍數(shù)）

3. 解碼接口

根據(jù)存活的塊，恢復(fù)出所有的數(shù)據(jù)塊，如果有校驗(yàn)塊丟失，最后會(huì)根據(jù)數(shù)據(jù)塊計(jì)算出對(duì)應(yīng)的校驗(yàn)塊。

int jerasure_matrix_decode(int k, int m, int w, int *matrix, int row_k_ones, int *erasures, char **data_ptrs, char **coding_ptrs, int size)

• k: 數(shù)據(jù)塊個(gè)數(shù)
• m: 校驗(yàn)塊個(gè)數(shù)
• w: WORD SIZE
• matrix：編碼矩陣 （m*k，上面的k*k為單位陣）
• row_k_ones: 編碼的第一行是否全為1，用于優(yōu)化
• erasueres: 記錄哪些塊丟失了，長(zhǎng)度超過m則不能恢復(fù)，以-1做為結(jié)束標(biāo)識(shí)

???????? erasures[0] = 0; // 第0個(gè)塊丟失
?????? erasures[1] = 3; // 第3個(gè)塊丟失
?????? erasures[2] = -1; // -1, 結(jié)束標(biāo)識(shí)

• data_ptrs：數(shù)據(jù)塊指針
• coding_ptrs：校驗(yàn)塊指針
• size：數(shù)據(jù)塊大小（必須是sizeof(long)的倍數(shù)）

4. 恢復(fù)指定塊

如果只丟失一個(gè)數(shù)據(jù)塊，要運(yùn)用3中的接口，則必須獲取到前k個(gè)存活的塊；要想使用任意K個(gè)塊恢復(fù)丟失的某個(gè)數(shù)據(jù)，可先根據(jù)存活的塊，計(jì)算出解碼矩陣，運(yùn)用矩陣乘法恢復(fù)出指定塊的數(shù)據(jù)。

int jerasure_make_decoding_matrix(int k, int m, int w, int *matrix, int *erased,? int *decoding_matrix, int *dm_ids)

• k: 數(shù)據(jù)塊個(gè)數(shù)
• m: 校驗(yàn)塊個(gè)數(shù)
• w: WORD SIZE
• matrix：編碼矩陣 （m*k，上面的k*k為單位陣）
• erased：記錄哪些塊丟失，1代表存活，0代表丟失

??????? for (i = 0; i < m + k; i++) erased[i] = 0;
????? erased[0] = 1; // 第0個(gè)塊丟失
????? erased[1] = 1; // 第1個(gè)塊丟失
decoding_matrix： 解碼矩陣（輸出） dm_ids： 存儲(chǔ)的數(shù)據(jù)塊 （輸出）

void jerasure_matrix_dotprod(int k, int w, int *matrix_row,

int *src_ids, int dest_id, char **data_ptrs, char **coding_ptrs, int size)

• k: 數(shù)據(jù)塊個(gè)數(shù)
• w: WORD SIZE
• matrix_row：解碼矩陣，使用上一步的輸出decoding_matrix
• src_ids: 運(yùn)用哪些塊計(jì)算，直接使用上一步的輸出dm_ids
• dest_id: 計(jì)算目標(biāo)塊號(hào)
• data_ptrs: 數(shù)據(jù)塊指針
• coding_ptrs: 校驗(yàn)塊指針
• size: 數(shù)據(jù)塊大小

Cauchy Reed-Solomon編解碼接口

接口及使用方式與Reed-Solomon的類似，對(duì)應(yīng)的接口分別為：

• jerasure_bitmatrix_encode // 編碼
• jerasure_bitmatrix_decode // 解碼
• jerasure_make_decoding_bitmatrix // 生成解碼矩陣
• jerasure_bitmatrix_dotprod // 矩陣相乘，計(jì)算指定行的數(shù)據(jù)

不同的是，Cauchy Reed-Solomon使用的編碼矩陣需要先經(jīng)過轉(zhuǎn)化。

int *jerasure_matrix_to_bitmatrix(int k, int m, int w, int *matrix)

• k: 數(shù)據(jù)塊個(gè)數(shù)
• m: 校驗(yàn)塊個(gè)數(shù)
• w: WORD SIZE
• matrix：RS編碼矩陣 （m*k，上面的k*k為單位陣）

返回值即為Cauchy Reed-Solomon的編碼矩陣。

編解碼性能測(cè)試

使用Reed-Solomon(RS)和Cauchy Reed-Solomon(CRS)分別進(jìn)行編解碼測(cè)試。

Intel(R) Xeon(R) CPU E5310 @ 1.60GHz 4 cores

1. 編碼不同大小的數(shù)據(jù)

上圖為使用RS和CRS分別編解碼1M-10M大小的數(shù)據(jù)，可以看出，編碼的時(shí)間與編碼數(shù)據(jù)大小成正比，并且編解碼的時(shí)間基本相同，使用RS編碼1M的數(shù)據(jù)耗時(shí)約為114ms，使用CRS編碼1M的數(shù)據(jù)耗時(shí)約為37ms。

2. 采用不同的WORD SIZE編碼

上圖為RS和CRS分別使用WORD SIZE為8、16、32來編解碼1M的數(shù)據(jù)（RS、CRS要求m+k<2^w），RS在WORD SIZE為16時(shí)性能最佳，而CRS在WORD SIZE為8時(shí)性能最佳。

3. 采用不同的數(shù)據(jù)塊數(shù)

上圖為RS和CRS在數(shù)據(jù)塊數(shù)分別為4-10，校驗(yàn)塊數(shù)為2（容2錯(cuò)）的情況下編解碼1M的數(shù)據(jù)，可以看出，數(shù)據(jù)塊數(shù)越多（存儲(chǔ)成本越低），編解碼時(shí)間越長(zhǎng)。

4. CRS采用不同的packet size

上圖為CRS在不同的packet size情況下編解碼1M的數(shù)據(jù)（RS無此參數(shù)， CRS要求size % (w * packet_size) == 0），可以看出，但packet size較小時(shí)，packet size的增加極大的降低了編解碼的時(shí)間，而當(dāng)packet size增加至1024及以上時(shí)，packet size的增加對(duì)編解碼時(shí)間影響不大。

轉(zhuǎn)載于:https://www.cnblogs.com/yunnotes/archive/2013/04/19/3032308.html

總結(jié)

以上是生活随笔為你收集整理的Jerasure库接口简介及性能测试的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。