Jerasure库接口简介及性能测试

Jerasure库提供Reed-Solomon和Cauchy Reed-Solomon两种编码算法的实现.

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: 数据块个数
• m: 校验块个数
• w: WORD SIZE
• matrix：编码矩阵 （m*k，上面的k*k为单位阵）
• data_ptrs：数据块指针 (长度为k的指针数组)
• coding_ptrs：校验块指针(长度为m的指针数组)
• size：数据块大小（必须是sizeof(long)的倍数）

3. 解码接口

根据存活的块，恢复出所有的数据块，如果有校验块丢失，最后会根据数据块计算出对应的校验块。

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: 数据块个数
• m: 校验块个数
• w: WORD SIZE
• matrix：编码矩阵 （m*k，上面的k*k为单位阵）
• row_k_ones: 编码的第一行是否全为1，用于优化
• erasueres: 记录哪些块丢失了，长度超过m则不能恢复，以-1做为结束标识

         erasures[0] = 0; // 第0个块丢失
       erasures[1] = 3; // 第3个块丢失
       erasures[2] = -1; // -1, 结束标识

• data_ptrs：数据块指针
• coding_ptrs：校验块指针
• size：数据块大小（必须是sizeof(long)的倍数）

4. 恢复指定块

如果只丢失一个数据块，要运用3中的接口，则必须获取到前k个存活的块；要想使用任意K个块恢复丢失的某个数据，可先根据存活的块，计算出解码矩阵，运用矩阵乘法恢复出指定块的数据。

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

• k: 数据块个数
• m: 校验块个数
• 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个块丢失
      erased[1] = 1; // 第1个块丢失

decoding_matrix： 解码矩阵（输出）

dm_ids： 存储的数据块 （输出）

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: 数据块个数
• w: WORD SIZE
• matrix_row：解码矩阵，使用上一步的输出decoding_matrix
• src_ids: 运用哪些块计算，直接使用上一步的输出dm_ids
• dest_id: 计算目标块号
• data_ptrs: 数据块指针
• coding_ptrs: 校验块指针
• size: 数据块大小

Cauchy Reed-Solomon编解码接口

接口及使用方式与Reed-Solomon的类似，对应的接口分别为：

• jerasure_bitmatrix_encode // 编码
• jerasure_bitmatrix_decode // 解码
• jerasure_make_decoding_bitmatrix // 生成解码矩阵
• jerasure_bitmatrix_dotprod // 矩阵相乘，计算指定行的数据

不同的是，Cauchy Reed-Solomon使用的编码矩阵需要先经过转化。

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

• k: 数据块个数
• m: 校验块个数
• w: WORD SIZE
• matrix：RS编码矩阵 （m*k，上面的k*k为单位阵）

返回值即为Cauchy Reed-Solomon的编码矩阵。

编解码性能测试

使用Reed-Solomon(RS)和Cauchy Reed-Solomon(CRS)分别进行编解码测试。

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

1. 编码不同大小的数据

上图为使用RS和CRS分别编解码1M-10M大小的数据，可以看出，编码的时间与编码数据大小成正比，并且编解码的时间基本相同，使用RS编码1M的数据耗时约为114ms，使用CRS编码1M的数据耗时约为37ms。

2. 采用不同的WORD SIZE编码

上图为RS和CRS分别使用WORD SIZE为8、16、32来编解码1M的数据（RS、CRS要求m+k<2^w），RS在WORD SIZE为16时性能最佳，而CRS在WORD SIZE为8时性能最佳。

3. 采用不同的数据块数

上图为RS和CRS在数据块数分别为4-10，校验块数为2（容2错）的情况下编解码1M的数据，可以看出，数据块数越多（存储成本越低），编解码时间越长。

4. CRS采用不同的packet size

上图为CRS在不同的packet size情况下编解码1M的数据（RS无此参数， CRS要求size % (w * packet_size) == 0），可以看出，但packet size较小时，packet size的增加极大的降低了编解码的时间，而当packet size增加至1024及以上时，packet size的增加对编解码时间影响不大。