冗余技术介绍
两种技术 | 磁盘利用率 | 计算开销 | 网络负载 | 恢复效率 |
---|---|---|---|---|
多副本n副本) | 1/n | 几乎没有 | 较低 | 较高 |
纠删码n+m) | n/n+m) | 高 | 较高 | 较低 |
条目解释:
磁盘利用率:
n副本:因为要存n副本,则存一份的数据设为n大小)占用n*n个不同的磁盘上的存储空间,故磁盘利用率为1/n;
n+m)冗余:这时存一份数据设为n大小)应该占用n+m)个不同磁盘上的存储空间,故磁盘利用率为n/n+m)。
计算开销:
n副本:n副本只是将原始数据复制n份,故几乎不存在计算开销;
n+m)冗余:因为纠删码涉及到矩阵求逆的过程,这时的计算开销就比较大。
网络负载:
n副本:考虑在分布式系统中,n副本的修复策略只需要找到其中一个存在的副本,将副本复制一遍再返回即可实现数据的修复;进行编码时需要传递n个副本到不同的节点上。例如恢复一个1GB的文件块,采取n副本策略,恢复就需要占用1GB的网络流量,编码需要占用nGB的网络流量。
n+m)冗余:同样考虑在分布式系统中,修复策略则需要找到至少n个块才能进行纠删修复,编码时则需要n+m)个块大小的网络流量。例如恢复一个1GB文件块,采用4+3的冗余策略,则恢复时需要至少占用4*1GB=4GB的网络流量,编码时就需要7*1GB=7GB的网络流量。综上可得,多副本冗余的网络负载相对较低,而纠删码的网络负载相对较高。
恢复效率:
刚好与网络负载成正比,即多副本用较低的网络负载实现了数据恢复,故效率较高,而纠删码则是用较高的网络负载实现了数据恢复,故效率较低。个人认为这也是以空间换效率的体现。
纠删码技术介绍
Reed-Solomon(RS)码是存储系统较为常用的一种纠删码,它有两个参数n和m,记为RSn,m)。n代表原始数据块个数。m代表校验块个数。
RS码原理
以n=5,m=3为例。即5个原始数据块,乘上一个n+m)*n的矩阵,然后得出一个n+m)*1的矩阵。根据矩阵特点可以得知结果矩阵中前面5个值与原来的5个数据块的值相等,而最后3个则是计算出来的校验块。
以上过程为编码过程。D是原始数据块,得到的C为校验块。
假设丢失了m块数据。如下:
那我们如何从剩余的n个数据块(注意,这里剩余的n块可能包含几个原始数据块+几个校验块)恢复出来原始的n个数据块呢,就需要通过下面的decoding(解码)过程来实现。
第一步:从编码矩阵中删去丢失数据块和丢失编码块对应行。 将删掉m个块的n+m)×1个矩阵变形为n×1矩阵,同时B矩阵也需要删掉对应的m个行得出一个B’的变形矩阵,这个B’就是n*n矩阵。如下:假设D1、D4、C2丢失,我们得到如下B’矩阵及等式。
第二步:求出B’的逆矩阵。
第三步:等式两边分别乘上B’的逆矩阵。
B’和它的逆矩阵相乘得到单位矩阵I,如下:
左边只剩下原始数据矩阵D:
至此完成解码过程。
注:图中黄色部分为范德蒙矩阵。至于如何生成B矩阵,以及如何求B’的逆矩阵,请查看其他相关文献,这里不再赘述。
小结
RS的特点:
- 低冗余度,高磁盘利用率。
- 数据恢复代价高。 丢失数据块或者编码块时, RS需要读取n个数据块和校验块才能恢复数据, 数据恢复效率也在一定程度上制约了RS的可靠性。
- 数据更新代价高。 数据更新相当于重新编码, 代价很高, 因此常常针对只读数据,或者冷数据。
工程实践中,一般对于热数据还是会使用多副本策略来冗余,冷数据使用纠删码。
参考文章:
https://www.jianshu.com/p/4abf65ad03af