本文共 1882 字,大约阅读时间需要 6 分钟。
erasure code可以认为是RAID的通式,任何RAID都可以转换为特定的erasure code。在传统的RAID中,仅支持少量的磁盘分布,当系统中存在多个分发点和多节点时,RAID将无法满足需求。比如RAID5只支持一个盘失效,即使是RAID6也仅支持两个盘失效,所以支持多个盘失效的算法也就是erasure code是解决这一问题的办法。(Erasure Code作为可有效提升存储效率、安全性和便捷性的新兴存储技术)
定义:erasure code是一种技术,它可以将n份原始数据,增加m份数据(用来存储erasure编码),并能通过n+m份中的任意n份数据,还原为原始数据。定义中包含了encode和decode两个过程,将原始的n份数据变为n+m份是encode,之后这n+m份数据可存放在不同的device上,如果有任意小于m份的数据失效,仍然能通过剩下的数据还原出来。也就是说,通常n+m的erasure编码,能容m块数据故障的场景,这时候的存储成本是1+m/n,通常m<n。因此,通过erasure编码,我们能够把副本数降到1.x。
Paste_Image.png
凡是需要通过冗余来进行高可用的场景。但总体来说,主要运用于存储和数字编码领域。
最常见的Erasure Code是Reed Solomon算法,如图,RS codes定义了一个(n + m) * n的分发矩阵(Distribution Matrix) 。
Paste_Image.png
对每一段的n份数据,我们都可以通过B * D 得到得到对n份数据的Encode结果即n+m分数据。
Paste_Image.png
Decode的过程对应着存在数据受损时,可以由任意n份数据恢复出其他受损数据。这个过程分成2个阶段:恢复原始数据、恢复编码数据。
假设如上图中的原始数据D1~5对应的编码后存储数据中D1, D4, C2 失效
a) 恢复原始数据
Step1: 可以同时从矩阵B和B*D中,去掉相应的行,得到下面的等式:
Paste_Image.png
Step2: 用Survivors数据恢复原始数据D1~5,我们只需简单的做矩阵乘法:
Paste_Image.png
因为(B')^-1 * B' = I 单位矩阵,所以我们就秋得了原始矩阵D:
Paste_Image.png
b) 恢复编码数据
矩阵B是已知的,原始数据D已经完成恢复,只需要再做一次Encode的过程即可。因为是矩阵乘法,只取出受损数据对应的行进行矩阵乘即可。
参考文档[http://blog.csdn.net/sinat_27186785/article/details/52034588]作者:EdwardLee 链接:https://www.jianshu.com/p/e43dcdefae05 来源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。