纠删码的数学原理竟然这么简单
消息来源:baojiabao.com 作者: 发布时间:2024-05-09
超级计算机的一个必要组件是存储系统。小型超算用到的数据较少,磁盘阵列就够了,而大中型超算就要配备容量巨大的分散式存储系统。
分散式存储中经常遇到纠删码的概念:当冗余级别为n+m时,从n个源数据块中计算出m个的校验块,将这n+m个数据块分别存放在n+m个硬盘上,就能容忍任意m个硬盘故障;硬盘故障时,只需任意选取n个正常的数据块就能计算得到所有的源数据。如果将n+m个数据块分散在不同的存储节点上,那么就能容忍m个节点故障。
图1
图1中的D、C的长度均为一个字(word),例如1个字节、1个bit。D为源数据,C为校验数据。
那么问题来了:纠删码是如何计算校验数据的呢?又是如何恢复源数据的呢?
纠删码有很多种,这里介绍广泛应用:
Reed-Solomon纠删码
以冗余级别为5+3的纠删码为例说明。将n个源数据块D1~Dn按列排成向量D,再构造一个(n+m)*n矩阵B(图2),B称为分布矩阵。对矩阵B有一个要求:它的任意n个行向量都是相互独立的,即这n个行向量组成的n*n矩阵可逆。矩阵B的前n行是单位矩阵I,后m行的构造方法放在最后一段介绍,这里先掠过。
图2
执行矩阵向量乘B*D,得到m个校验块C1~ Cm(图3)。
图3
数据恢复算法
假设m个硬盘发生了故障,即图4中的数据块D1、D4、C2丢失,需要从剩下的n个数据块中恢复出来源数据D1~Dn。
图4
从矩阵B中将剩余数据块对应的行向量挑出来,组成新矩阵B’,B’乘以向量D的结果恰好是未故障的数据块(图5)。
图5
因为B的任意n行组成的矩阵都可逆,所以矩阵B’存在逆矩阵,记为B’-1,显然有B’-1*B’=I。
将图5中等式的左右两边同时左乘矩阵B’-1,就得到了n个源数据块D1~Dn,完成数据恢复。
Vandermonde矩阵
分布矩阵B的构造方式有很多种,这里介绍一种常用方法。
由线性代数知道,对互不相等的实数a1,a2,…,ak(k≥n),矩阵V的任意n行组成的矩阵都可逆。
从Vandermonde矩阵V中取出m行,用做分布矩阵B的下部m行,恰好满足对B的要求:任意n行都相互独立。例如冗余级别为6+3纠删码的分布矩阵B可以采用如下形式。
简单总结:纠删码和大家熟悉的RAID技术看起来是有些类似,一个条带(Stripe)是由多个数据块(Strip)构成,分为数据块和校验块。但与RAID5、RAID6不同的是纠删码从功能上来看最大的区分特点是校验和数据的比例按N+M可调整,并且校验块数量不再受限于2个(RAID最多2个,比如RAID6),纠删码的M可以是3、4甚至更多。
相对传统RAID技术,系统的容错能力得到大幅度的提高,即可以允许系统内同时损坏的硬盘数量(或者存储节点数)大幅度增加;实现了多对多的快速的数据重构,传统RAID方式需要十几个小时的重构时间,而这种方式磁盘重构时间可以缩短至分钟级的速度。
相关文章
- 中兴受美国制裁事件 被罚了20亿美元过程事件始末 中兴被制裁后公司现状
2023-11-02 22:12:46
- B站怎么炸崩了哔哩哔哩服务器今日怎么又炸挂了?技术团队公开早先原因
2023-03-06 19:05:55
- 苹果iPhoneXS/XR手机电池容量续航最强?答案揭晓
2023-02-19 15:09:54
- 华为荣耀两款机型起内讧:荣耀Play官方价格同价同配该如何选?
2023-02-17 23:21:27
- google谷歌原生系统Pixel3 XL/4/5/6 pro手机价格:刘海屏设计顶配版曾卖6900元
2023-02-17 18:58:09
- 科大讯飞同传同声翻译软件造假 浮夸不能只罚酒三杯
2023-02-17 18:46:15
- 华为mate20pro系列手机首发上市日期价格,屏幕和电池参数配置对比
2023-02-17 18:42:49
- 小米MAX4手机上市日期首发价格 骁龙720打造大屏标准
2023-02-17 18:37:22
- 武汉弘芯遣散!结局是总投资1280亿项目烂尾 光刻机抵押换钱
2023-02-16 15:53:18
- 谷歌GoogleDrive网云盘下载改名“GoogleOne” 容量提升价格优惠
2023-02-16 13:34:45
- 巴斯夫将裁员6000人 众化工巨头裁员潮再度引发关注
2023-02-13 16:49:06
- 人手不足 韵达快递客服回应大量包裹派送异常没有收到
2023-02-07 15:25:20
- 资本微念与李子柒销声匿迹谁赢? 微念公司退出子柒文化股东
2023-02-02 09:24:38
- 三星GalaxyS8 S9 S10系统恢复出厂设置一直卡在正在检查更新怎么办
2023-01-24 10:10:02
- 华为Mate50 RS保时捷最新款顶级手机2022多少钱?1.2万元售价外观图片吊打iPhone14
2023-01-06 20:27:09
- 芯片常见的CPU芯片封装方式 QFP和QFN封装的区别?
2022-12-02 17:25:17
- 华为暂缓招聘停止社招了吗?官方回应来了
2022-11-19 11:53:50
- 热血江湖手游:长枪铁甲 刚猛热血 正派枪客全攻略技能介绍大全
2022-11-16 16:59:09
- 东京把玩了尼康微单相机Z7 尼康Z7现在卖多少钱?
2022-10-22 15:21:55
- 苹果iPhone手机灵动岛大热:安卓灵动岛App应用下载安装量超100万次
2022-10-03 22:13:45