Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4010466
  • 博文数量: 251
  • 博客积分: 11197
  • 博客等级: 上将
  • 技术积分: 6862
  • 用 户 组: 普通用户
  • 注册时间: 2008-12-05 14:41
个人简介

@HUST张友东 work@taobao zyd_com@126.com

文章分类

全部博文(251)

文章存档

2014年(10)

2013年(20)

2012年(22)

2011年(74)

2010年(98)

2009年(27)

分类: 服务器与存储

2012-07-17 20:47:57

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. 编码不同大小的数据

      clip_image002[4]

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


      2. 采用不同的WORD SIZE编码

      clip_image004[5]

      上图为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

      clip_image008[4]

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


    • 阅读(12495) | 评论(7) | 转发(1) |
      给主人留下些什么吧!~~

      YL_dai2015-05-04 15:19:05

      你好,请问你的测试是在Linux下做的吗?

      hhhhhhjik2015-05-02 14:12:25

      请问编解码的时间怎么得到啊

      navylq2012-09-10 19:02:27

      zyd_cu: 是的,目前我们系统准备做这个,节省成本。.....
      jerasure 提供的没有系统码吧?用在存储系统中还是系统码好些吧?

      zyd_cu2012-08-05 12:46:31

      IdleMind: 东哥研读这个库是要在分布式存储系统中加RS纠删编码吗? 我也在做这个,只是没有好的思路。。。坐等后续文章.....
      是的,目前我们系统准备做这个,节省成本。

      IdleMind2012-08-03 11:27:43

      东哥研读这个库是要在分布式存储系统中加RS纠删编码吗? 我也在做这个,只是没有好的思路。。。坐等后续文章