P2P 与分布式存储 / 系统课时
Reed–Solomon 怎样编码数据块
Reed–Solomon 怎样编码数据块
用一个可手算的 RS(4,2) 条带,把两片原始数据编码成四片存储片。我们会计算有限域中的校验片,验证只保留其中任意两片也能找回原数据,并分清这种容错能力成立的条件。
学习目标
- 解释 GF(256) 中的加法、乘法与校验片生成规则。
- 使用系统型编码矩阵算出数据片和校验片。
- 运行 Python 示例,验证六种两片恢复组合和实际存储边界。
把数据组织成条带
以 RS(4,2) 为例:总共存储 片,其中 片是数据片 ,其余 片是校验片 。系统型编码保留原始数据片,不必先解码就能读取没有故障的数据。
实际对象会先按条带拆成两个等长数据片,然后对同一字节位置逐列编码。本课只取一个位置的两个字节 、 演示;真实数据片含有成千上万个这样的字节位置。末尾不足条带长度时需填充,并另存原始数据长度。
四片的总存储量是原数据的两倍,即冗余开销 。这是用额外两片换取最多两片丢失时的数据恢复能力,不等于保存四份完整副本。
在 GF(256) 中计算校验值
Reed–Solomon 不在普通整数上直接做矩阵运算,而是在有限域 GF() 中操作。每个元素是 0~255 的一个字节;相加使用按位异或,例如 。乘法则是多项式相乘后取模,本例使用不可约多项式 (十六进制 0x11d)。
本例的系数 2、3 都是有限域元素。因为数值较小,;但 ,而不是普通整数乘积 21。同理,。遇到乘积超出一个字节时,还必须按 0x11d 约减。
用生成矩阵得到四片
取一次多项式 ,令 、;在不同位置 再求值,就得到 、。把这一过程写成系统型生成矩阵 ,每一行给出一个编码片对原始两片的系数:
| 编码片 | 系数 | 系数 | 本例字节 |
|---|---|---|---|
| 1 | 0 | 5 | |
| 0 | 1 | 7 | |
| 3 | 2 | 1 | |
| 2 | 3 | 3 |
前两行是单位矩阵,所以直接保留数据片。后两行表示 、,系数乘法均在 GF(256) 中进行:
- 。
- 。
因此实际编码结果是 。矩阵须按 Reed–Solomon 的规则构造,不能随意挑选几行系数后就宣称可以从任意两片恢复。

为什么任意两片能够还原原文
丢失哪些片是已知的,称为擦除。恢复时从生成矩阵中取出幸存片对应的两行,组成一个 矩阵;只要它在 GF(256) 中可逆,就能根据两份编码值求回 。
最极端的情况是两个原始数据片都丢了,只剩 、。对应的系数行为 和 ,其行列式为 ,不为零,因此可以解出原值 。
本例任意两行都线性独立,因此 种组合全部可恢复。一般 RS() 也需要采用满足任意 行可逆条件的编码矩阵,才能在不超过 片擦除后重建数据。这里的“有效”还要求片来自同一条带、同一编码版本且内容未损坏。
用 Python 验证编码和恢复
下面的完整示例可在 Python 3 中直接运行,无需第三方依赖。它逐字节实现 GF(256) 乘法,通过二阶逆矩阵恢复,并穷举四片中选两片的所有组合。逆元使用遍历查找以便阅读;生产实现通常使用查表或优化过的有限域运算。
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()预期输出:
编码片: [5, 7, 1, 3]
只保留 P0、P1: (5, 7)
任意两片恢复: 6/6如果修改任意一行系数后出现恢复失败,就要检查新矩阵是否仍满足所有两行可逆,而不是简单重试解码。示例只处理一个字节位置;扩展到真实数据片时,对每个对应位置重复编码,并保持条带边界一致。
放到存储系统里还要检查什么
例如实际采用 6 个数据片 + 3 个校验片,容量开销是 ;在任意 3 片明确丢失的情况下,剩余 6 片可以恢复。若 4 片丢失,就不能依靠这组编码保证恢复。
落地时应给每片保存条带 ID、片序号、编码参数、原始长度与校验和;读取时先验证完整性,再把损坏片视作擦除。放置策略还要避免同一个故障域同时带走超过 3 片。对于小范围覆盖写入,应评估重新计算校验片、网络传输和读改写的代价,而不只比较容量百分比。
RS 解决的是已知位置的片丢失后的可恢复性;它不能代替数据校验、版本一致性或跨故障域放置。