@HUST张友东 work@taobao zyd_com@126.com
分类: 服务器与存储
2012-07-17 20:47:57
Jerasure库提供Reed-Solomon和Cauchy Reed-Solomon两种编码算法的实现.
Reed-Solomon编解码接口
1. 编码矩阵生成
// generate matrix, last m rowsvoid jerasure_matrix_encode(int k, int m, int w, int *matrix, char **data_ptrs, char **coding_ptrs, int size)
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)
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)
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)
Cauchy Reed-Solomon编解码接口
接口及使用方式与Reed-Solomon的类似,对应的接口分别为:
不同的是,Cauchy Reed-Solomon使用的编码矩阵需要先经过转化。
int *jerasure_matrix_to_bitmatrix(int k, int m, int w, int *matrix)
返回值即为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的增加对编解码时间影响不大。