本文共 1280 字,大约阅读时间需要 4 分钟。
在Ceph和RAID存储领域,RS纠删码扮演着重要的角色,纠删码是经典的时间换空间的案例,通过更多的CPU计算,降低低频存储数据的存储空间占用。
纠删码基于范德蒙德矩阵实现,核心公式如下所示(AD=E)
假设某些数据丢失,右式部分行丢失,变成E',则左式也相应去掉对应行,变成A'。
函数Inverse[A′]Inverse[A′] 代表A'的逆矩阵,I代表单位矩阵
Inverse[A′]∗A′∗D=Inverse[A′]∗E′Inverse[A′]∗A′∗D=Inverse[A′]∗E′
I∗D=Inverse[A′]∗E′I∗D=Inverse[A′]∗E′
D=Inverse[A′]∗E′D=Inverse[A′]∗E′
import numpy as np# 备份数量backup_up = 2# 原始数据data = np.array([1, 0, 0, 8, 6])# 根据纠删码原理生成的数据vander_data = np.concatenate((np.identity(len(data)), np.vander(data, 3).transpose()[::-1]), axis=0)storage_data = vander_data.dot(data)print('生成数据',storage_data)# 模拟数据丢失loss_data = np.concatenate((storage_data[0:3], storage_data[5:7]), axis=0)print('丢失后数据', loss_data)# 恢复数据recover_data = np.linalg.inv(np.concatenate((vander_data[0:3], vander_data[5:7]), axis=0)).dot(loss_data)print('恢复数据',recover_data)
基于Python的Numpy库可以很容易地模拟纠删码数据恢复的流程。效果如下所示
实际上,上述的Python代码只是纠删码的最基础版本,可以发现校验数据大于原始数据,这样就导致校验数据需要更多的存储位,并没有很好的优化存储空间。
在现实场景中,纠删码一般通过自定义的伽罗华域进行运算,保证位数在一定范围内。伽罗华域GF(2w)GF(2w) 代表所有运算结果只能在[0,2w)[0,2w) 之间。
伽罗华域的加法和减法为异或运算,乘法和除法需要基于生成多项式计算出gfilog表。GF(24)GF(24) 的gfilog表如下所示。
以8*9为例,计算过程如下所示,需要注意如果值大于2w2w ,需要模2w2w 。
8∗9=x8x9=x17=x17%15=x2=48∗9=x8x9=x17=x17%15=x2=4
范德蒙德矩阵求逆矩阵的时间复杂度为O(N3)O(N3) ,柯西矩阵求逆矩阵的时间复杂度为O(N2)O(N2) ,因此可以采用柯西矩阵替代范德蒙德矩阵用于编码运算。
转载地址:http://awuii.baihongyu.com/