用户4700054
纠删码理论基础
关注作者
前往小程序,Get
更优
阅读体验!
立即前往
腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
用户4700054
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
社区首页
>
专栏
>
纠删码理论基础
纠删码理论基础
用户4700054
关注
发布于 2022-08-17 12:34:03
1.3K
0
发布于 2022-08-17 12:34:03
举报
文章被收录于专栏:
存储内核技术交流
纠删码数据容错原理
纠删码是一种前向纠删码。过程分为编码和解码。编码过程是将文件分割为固定大小的文件块,针对这些被分割的文件块编码为k个块(k个块中包括了k1个数据块和k2个校验块)。解码过程是将编码后的多个子块作为输入,经过解码可以恢复任何一个块的数据(不管是数据块还是校验块)。
采用纠删码技术来做数据容错,当磁盘出现故障,失效数据可以通过纠删码的校验链的构建机制来恢复数据,而不是纠正数据自身的错误,一般(k+r,k)纠删码存储开校门为r/k,相对副本纠删码具有低存储开销,但是纠删码涉及到的编解码,计算开销相对较大。
(k+r,r)纠删码中,其中k份原始数据分块通过一定编码规则计算得到k+r个编码块,其中任意的r份数据块出错时候,均可以通过相应的重构善法来恢复原始k份数据块,纠错能力的上限r<=d-1(d是纠删码的最小列距)。
常用的编码编码有RS编码(里得所罗门编码)和LDPC编码(低密度奇偶校验编码)、RAID编码(阵列编码)这三种。
常用纠删码编码方式
范德蒙德RS编码:犯德蒙德RS编码中,范德蒙德生成矩阵和数据列向量在Galois域GW中执行乘法运算得到校验数据。如果数据分块d1发生失效,解码过程为利用存活数据所对应的剩余生成矩阵的逆矩阵与存活数据对应的列向量在Galois域GW中进行乘法uyunsuan得出失效数据。数据编码算法成立的必要条件是生成矩阵任意k个行向量在域GW上是线性无关。Galois域的加法等同于异或运算,而对于乘法和除法,则通过查询域GW上对数表和反对数表来实现。范德蒙德RS编码时间复杂度为O(kr),解码时间复杂度(O r的三次方)
柯西RS编码:柯西矩阵的RS编码在范德蒙德RS编码基础上做了优化。改进1,冗余矩阵采用柯西矩阵,解码过程中的求逆矩阵的计算复杂度有O(r三次方)降低到O(r的二次方);改进2,将有限域中的每个数表示成一个二维矩阵,使得有限域上的乘法运算转换为异或运算,提高运算效率的同事减低复杂度。
LDPC编码:LDPC编码是对于一组给定的数据信息,通过在其末尾添加校验信息进行数据检错。若采用奇校验,则添加校验信息的原则是保证原始数据信息和校验信息的数量为奇数;若采用偶校验,保证原始数据信息和校验信息的数量为偶数。
本文参与
腾讯云自媒体同步曝光计划
,分享自微信公众号。
原始发表:2021-12-06,如有侵权请联系
cloudcommunity@tencent.com
删除
编码
本文分享自
存储内核技术交流
微信公众号,
前往查看
如有侵权,请联系
cloudcommunity@tencent.com
删除。
本文参与
腾讯云自媒体同步曝光计划
,欢迎热爱写作的你一起参与!
编码
评论
登录
后参与评论
0 条评论
热度
最新
推荐阅读
LV.
文章
0
获赞
0
目录
纠删码数据容错原理
领券
问题归档
专栏文章
快讯文章归档
关键词归档
开发者手册归档
开发者手册 Section 归档
0
0
0
推荐