P2P 与分布式存储 / 系统课时

Reed–Solomon 怎样编码数据块

Reed–Solomon 怎样编码数据块

用一个可手算的 RS(4,2) 条带,把两片原始数据编码成四片存储片。我们会计算有限域中的校验片,验证只保留其中任意两片也能找回原数据,并分清这种容错能力成立的条件。

学习目标

  • 解释 GF(256) 中的加法、乘法与校验片生成规则。
  • 使用系统型编码矩阵算出数据片和校验片。
  • 运行 Python 示例,验证六种两片恢复组合和实际存储边界。

把数据组织成条带

以 RS(4,2) 为例:总共存储 n=4n=4 片,其中 k=2k=2 片是数据片 D0,D1D_0,D_1,其余 m=2m=2 片是校验片 P0,P1P_0,P_1。系统型编码保留原始数据片,不必先解码就能读取没有故障的数据。

实际对象会先按条带拆成两个等长数据片,然后对同一字节位置逐列编码。本课只取一个位置的两个字节 D0=5D_0=5、D1=7D_1=7 演示;真实数据片含有成千上万个这样的字节位置。末尾不足条带长度时需填充,并另存原始数据长度。

四片的总存储量是原数据的两倍,即冗余开销 m/k=100%m/k=100\%。这是用额外两片换取最多两片丢失时的数据恢复能力,不等于保存四份完整副本。

在 GF(256) 中计算校验值

Reed–Solomon 不在普通整数上直接做矩阵运算,而是在有限域 GF(282^8) 中操作。每个元素是 0~255 的一个字节;相加使用按位异或,例如 5⊕7=25\oplus7=2。乘法则是多项式相乘后取模,本例使用不可约多项式 x8+x4+x3+x2+1x^8+x^4+x^3+x^2+1(十六进制 0x11d)。

本例的系数 2、3 都是有限域元素。因为数值较小,2⋅7=142\cdot7=14;但 3⋅7=7⊕14=93\cdot7=7\oplus14=9,而不是普通整数乘积 21。同理,3⋅5=5⊕10=153\cdot5=5\oplus10=15。遇到乘积超出一个字节时,还必须按 0x11d 约减。

用生成矩阵得到四片

取一次多项式 f(x)=a+bxf(x)=a+bx,令 f(0)=D0f(0)=D_0、f(1)=D1f(1)=D_1;在不同位置 x=2,3x=2,3 再求值,就得到 P0P_0、P1P_1。把这一过程写成系统型生成矩阵 GG,每一行给出一个编码片对原始两片的系数:

编码片 D0D_0 系数 D1D_1 系数 本例字节
D0D_0 1 0 5
D1D_1 0 1 7
P0P_0 3 2 1
P1P_1 2 3 3

前两行是单位矩阵,所以直接保留数据片。后两行表示 P0=3D0⊕2D1P_0=3D_0\oplus2D_1、P1=2D0⊕3D1P_1=2D_0\oplus3D_1,系数乘法均在 GF(256) 中进行:

  • P0=(3⋅5)⊕(2⋅7)=15⊕14=1P_0=(3\cdot5)\oplus(2\cdot7)=15\oplus14=1。
  • P1=(2⋅5)⊕(3⋅7)=10⊕9=3P_1=(2\cdot5)\oplus(3\cdot7)=10\oplus9=3。

因此实际编码结果是 [5,7,1,3][5,7,1,3]。矩阵须按 Reed–Solomon 的规则构造,不能随意挑选几行系数后就宣称可以从任意两片恢复。

RS(4,2) 有限域生成矩阵与两片恢复关系

为什么任意两片能够还原原文

丢失哪些片是已知的,称为擦除。恢复时从生成矩阵中取出幸存片对应的两行,组成一个 2×22\times2 矩阵;只要它在 GF(256) 中可逆,就能根据两份编码值求回 D0,D1D_0,D_1。

最极端的情况是两个原始数据片都丢了,只剩 P0=1P_0=1、P1=3P_1=3。对应的系数行为 (3,2)(3,2) 和 (2,3)(2,3),其行列式为 3⋅3⊕2⋅2=5⊕4=13\cdot3\oplus2\cdot2=5\oplus4=1,不为零,因此可以解出原值 (5,7)(5,7)。

本例任意两行都线性独立,因此 (42)=6\binom{4}{2}=6 种组合全部可恢复。一般 RS(n,kn,k) 也需要采用满足任意 kk 行可逆条件的编码矩阵,才能在不超过 n−kn-k 片擦除后重建数据。这里的“有效”还要求片来自同一条带、同一编码版本且内容未损坏。

用 Python 验证编码和恢复

下面的完整示例可在 Python 3 中直接运行,无需第三方依赖。它逐字节实现 GF(256) 乘法,通过二阶逆矩阵恢复,并穷举四片中选两片的所有组合。逆元使用遍历查找以便阅读;生产实现通常使用查表或优化过的有限域运算。

python
from itertools import combinations

# 使用 GF(256) 的不可约多项式 0x11d
def gf_mul(a, b):
    result = 0
    for _ in range(8):
        if b & 1:
            result ^= a
        high = a & 0x80
        a = (a << 1) & 0xff
        if high:
            a ^= 0x1d
        b >>= 1
    return result

def gf_inverse(value):
    if value == 0:
        raise ZeroDivisionError("零元素不可求逆")
    return next(x for x in range(1, 256) if gf_mul(value, x) == 1)

G = ((1, 0), (0, 1), (3, 2), (2, 3))

def restore(pair, values):
    (a, b), (c, d) = (G[i] for i in pair)
    det = gf_mul(a, d) ^ gf_mul(b, c)
    scale = gf_inverse(det)  # 非零行列式才能求逆
    y0, y1 = values
    return (
        gf_mul(scale, gf_mul(d, y0) ^ gf_mul(b, y1)),
        gf_mul(scale, gf_mul(c, y0) ^ gf_mul(a, y1)),
    )

def main():
    data = (5, 7)
    shards = [gf_mul(a, data[0]) ^ gf_mul(b, data[1]) for a, b in G]
    passed = sum(
        restore(pair, [shards[i] for i in pair]) == data
        for pair in combinations(range(4), 2)
    )
    print("编码片:", shards)
    print("只保留 P0、P1:", restore((2, 3), shards[2:]))
    print("任意两片恢复:", f"{passed}/6")

if __name__ == "__main__":
    main()

预期输出:

text
编码片: [5, 7, 1, 3]
只保留 P0、P1: (5, 7)
任意两片恢复: 6/6

如果修改任意一行系数后出现恢复失败,就要检查新矩阵是否仍满足所有两行可逆,而不是简单重试解码。示例只处理一个字节位置;扩展到真实数据片时,对每个对应位置重复编码,并保持条带边界一致。

放到存储系统里还要检查什么

例如实际采用 6 个数据片 + 3 个校验片,容量开销是 3/6=50%3/6=50\%;在任意 3 片明确丢失的情况下,剩余 6 片可以恢复。若 4 片丢失,就不能依靠这组编码保证恢复。

落地时应给每片保存条带 ID、片序号、编码参数、原始长度与校验和;读取时先验证完整性,再把损坏片视作擦除。放置策略还要避免同一个故障域同时带走超过 3 片。对于小范围覆盖写入,应评估重新计算校验片、网络传输和读改写的代价,而不只比较容量百分比。

RS 解决的是已知位置的片丢失后的可恢复性;它不能代替数据校验、版本一致性或跨故障域放置。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Reed–Solomon 怎样编码数据块

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通