博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Erasure Code原理
阅读量:4090 次
发布时间:2019-05-25

本文共 1794 字,大约阅读时间需要 5 分钟。

1.什么是erasure code?
    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+merasure编码,能容m块数据故障的场景,这时候的存储成本是1+m/n,通常m<n。因此,通过erasure编码,我们能够把副本数降到1.x
Erasure code 原理 - yandong_8212 - UltraDream
2.使用场景
    凡是需要通过冗余来进行高可用的场景。但总体来说,主要运用于存储和数字编码领域。
1) 阵列
    如果磁盘阵列需要使用高级特性,比如需要能够容错两个磁盘失效(RAID6),那么可以用n+2的模式;如果想容错4个磁盘失效,则可使用n+4的模式。
2) 云存储
    erasure code是云存储的核心技术,最初诸如hadoop, GFS,CEPH等都采用的是n-way replication来做冗余,但是这样会带来极大的成本开销,因此几乎各大公司都在用erasure code替代n-way replication,之后我还会简要介绍一下具体他们使用的模式。
3) P2P领域
    erasure code 的理论起码也有20年的历史了,但真正实践可能也就最近几年的时间,在P2P领域,动态的分布和智能的容错,特别是对短暂失效是非常关键的。以往的算法或多或少都有点山寨的感觉,而借助erasure code之后,将会使P2P的算法更具有数学的严谨性。
4) 数字编码
    erasure code本身就是出自编码理论,所以在这一块具有先天的优势。
3.Reed-Solomon Codes(最常见的
Erasure Code
Reed Solomon算法)
    erasure code是所有基于之前定义的统称,但具体下来有很多种,其中RS code是最基本的一种。RS codes是基于有限域的一种编码算法,有限域又称为Galois Field,是以法国著名数学家Galois命名的,在RS codes中使用GF(2^w),其中2^w >= n + m. 
RS codes定义了一个(n + m) * n的分发矩阵(Distribution Matrix) 
Erasure code 原理 - yandong_8212 - UltraDream
因此,对每一段的n份数据,我们都可以通过B * D 得到:
Erasure code 原理 - yandong_8212 - UltraDream
假如D1, D4, C2 失效,那么我们可以同时从矩阵B和B*D中,去掉相应的行,得到下面的等式:
接下来就是算法的核心部分,如果想要从survivors 求得D,我们只需简单的做矩阵乘法:
Erasure code 原理 - yandong_8212 - UltraDream
因为(B')^-1 * B' = I 单位矩阵,所以我们就秋得了原始矩阵D:
Erasure code 原理 - yandong_8212 - UltraDream
    但是上面的推导并不严谨,存在一些问题:
1) B'是否一定存在可逆矩阵?
2) Distribution Matrix - B如何求得?
3) 每次都用乘法,CPU的开销会很大。
    针对上面问题,有如下解决方案:
在线性代数中有一种矩阵称为Vandermonde矩阵,这种矩阵的特点是,任意的子方阵均为可逆方阵。其定义如下:
Erasure code 原理 - yandong_8212 - UltraDream
    其中a(i) 均不相同,且不为0. 之后,再利用vandermonde矩阵特性,在GF(2^w)上进行矩阵变换,最终得到Distribution Matrix - B. 具体可参考[Plank,Ding:2005]
    在GF域上的加法是异或操作,乘法可以采用乘法表来进行。
4.其他
    关于erasure code,有一个开源的实现Jerasure,有兴趣可以自己去研究一下。本原理主要是参考James S. Plank教授的论文写成,且Jerasure也是由其开发,不足之处请指正。
你可能感兴趣的文章
PX4官方用户和开发手册的首页面是会给你选择英文和中文的
查看>>
网络协议栈我是不是可以这么理解,就是把你要发送的数据自动处理成TCPIP格式的消息发出去,这种底层的转换不需要你弄了。
查看>>
除了LwIP还有uIP
查看>>
《跟工程师学嵌入式开发》这本书最后的终极项目我反而觉得有说头
查看>>
博士的申请考核制
查看>>
MAVLink学习之路05_MAVLink应用编程接口分析(也有讲STM32下的收发函数)
查看>>
找到了中文版的mavlink手册
查看>>
浅谈飞控开发的仿真功能
查看>>
我觉得在室内弄无人机开发装个防撞机架还是很有必要的,TBUS就做得很好。
查看>>
serial也是见到很多次了,似乎它就是一种串行通信协议
查看>>
TBUS的一些信息
查看>>
PX4+激光雷达在gazebo中仿真实现(古月居)
查看>>
专业和业余的区别就在于你在基础在基本功打磨练习花的时间
查看>>
通过mavlink实现自主航线的过程笔记
查看>>
Ardupilot飞控Mavlink代码学习
查看>>
这些网站有一些嵌入式面试题合集
查看>>
我觉得刷题是有必要的,不然小心实际被问的时候懵逼,我觉得你需要刷个50份面试题。跟考研数学疯狂刷卷子一样!
查看>>
我觉得嵌入式面试三要素:基础吃透+项目+大量刷题,缺一不可。不刷题是不行的。而且得是大量刷,刷出感觉套路,别人做题都做得是固定题型套路条件反射了,你还在那慢慢理解慢慢推是不行的,也是考研的教训。
查看>>
现在来看,做个普罗米修斯的docker镜像对我而言并不难,对PX4仿真环境配置也熟悉了。
查看>>
删除docker容器和镜像的命令
查看>>