P2P 与分布式存储 / 系统课时
XOR 校验片如何恢复单块丢失
XOR 校验片如何恢复单块丢失
如果三个数据块中丢失了一个,复制整份数据并非唯一的恢复办法。把三个等长数据块异或成一块校验片,便能在已知缺失位置时重建任意一个数据块。本课用十六进制手算与 Python 实验验证这个过程,并计算额外的存储开销。
学习目标
- 理解 XOR 的抵消性质,以及校验片为何能恢复单个丢失块。
- 手工计算三个数据块的校验片,并逆推出缺失数据。
- 使用 Python 实现校验片生成与重建,验证容量收益和故障边界。
用异或生成校验片
XOR(异或)按位计算:两个比特相同得到 0,不同得到 1。它具有两个特别适合数据恢复的性质:一个值与自身异或得到 0,一个值与 0 异或仍得到自身。异或还满足交换律和结合律,因此计算顺序不影响结果。
假设一组数据被划分为三个等长数据块 D0、D1、D2,额外保存一块校验片 P。每个字节位置分别计算:
先用每块的第一个字节演示:
| 数据片 | 十六进制 | 二进制 |
|---|---|---|
| D0 | 0x3A |
00111010 |
| D1 | 0xC5 |
11000101 |
| D2 | 0x0F |
00001111 |
| P | 0xF0 |
11110000 |
手算时,先得到 0x3A ^ 0xC5 = 0xFF,再计算 0xFF ^ 0x0F = 0xF0。其中 ^ 是 Python 等语言中的按位异或运算符,不是乘方。
实际存储块往往有数 KiB 或数 MiB。计算方法完全相同:块内偏移 0 的字节相互异或,偏移 1 的字节相互异或,依次生成与数据块等长的校验片,而不是把整块内容当作一个普通整数相加。
丢失的数据块怎样逆推
假设 D1 丢失,但 D0、D2 和 P 均可读取。由于 D0 与自身异或会抵消,D2 也会抵消,因此可以通过重新异或剩余三块得到 D1:

按照前面的数值,先计算 0xF0 ^ 0x3A = 0xCA,再计算 0xCA ^ 0x0F = 0xC5,正好恢复丢失的 D1。恢复过程不需要访问 D1 的原始内容,只需要其他完整分片和校验片。
如果丢失的是 D0 或 D2,同样将其余两个数据片与 P 异或即可。如果丢失的是 P,则直接用三个数据片重新计算校验片。这种包含三个数据片和一个校验片的布局通常记作 3+1,四片共同组成一个数据条带(stripe)。
使用 Python 恢复四字节数据块
下面使用 Python 3.9 或更高版本实现完整实验。每个数据块包含四个字节,程序先生成校验片,再模拟第二个数据块丢失,并利用其他分片进行恢复。保存为 xor_parity.py,运行 python xor_parity.py,无需第三方依赖。
def xor_blocks(blocks: list[bytes]) -> bytes:
if not blocks:
raise ValueError("至少提供一块数据")
size = len(blocks[0])
# 对齐长度是逐字节异或的前提
if any(len(block) != size for block in blocks):
raise ValueError("数据块必须等长")
result = bytearray(size)
# 相同偏移的字节异或,形成一块等长的结果
for block in blocks:
for index, value in enumerate(block):
result[index] ^= value
return bytes(result)
def main() -> None:
data = [
bytes.fromhex("3a 10 20 30"),
bytes.fromhex("c5 01 02 03"),
bytes.fromhex("0f 22 33 44"),
]
parity = xor_blocks(data)
missing_index = 1
# 重建输入中排除丢失块,模拟无法读取原数据
remaining = [
block for i, block in enumerate(data)
if i != missing_index
]
restored = xor_blocks([parity, *remaining])
print("校验片:", parity.hex(" "))
print("重建块:", restored.hex(" "))
# 原始块仅用于实验验收,不参与恢复计算
print("一致:", restored == data[missing_index])
if __name__ == "__main__":
main()预期输出:
校验片: f0 33 11 77
重建块: c5 01 02 03
一致: True校验片中的 f0、33、11、77 分别来自三个数据块对应位置的字节异或。恢复时把 P 与剩余数据片重新异或,四个字节都能找回,而不只是前面手算的 0xC5。
可以把 missing_index 改为 0 或 2 再运行,最后一行仍应为 一致: True。如果把任意一块改成长度为三个字节,程序会抛出 ValueError,避免在分片未对齐时产生不完整的校验结果。
容量收益与故障边界
假设一个条带包含 12 KiB 原始数据,划分为三个 4 KiB 数据块,再生成一个 4 KiB 校验片。实际占用 16 KiB,其中 4 KiB 是冗余数据,因此:
- 冗余开销:4 ÷ 12 ≈ 33.3%,以原始数据量为基准。
- 存储利用率:12 ÷ 16 = 75%,以实际占用空间为基准。
- 单片容错:D0、D1、D2、P 中任意一片丢失,都能通过剩余三片恢复。
这比保存两份完整数据的 24 KiB 更省空间,但容错能力不同:双副本在分布到独立故障域时也只能保证承受一份副本丢失,而 3+1 XOR 方案同样只能保证一个分片丢失。它不能像三副本一样容忍两个完整副本同时故障。
如果 D0 和 D1 同时丢失,已知的校验关系只能确定两者的异或结果,无法唯一求出各自的内容。一个 XOR 校验片只有一组独立校验关系,因此不能恢复两个未知数据片。
真实系统还必须处理以下边界:
- 故障域隔离:同一条带的四片应放置在四个不同的故障域,例如四台独立存储节点。若全部放在同一磁盘上,磁盘故障会同时毁掉所有分片。
- 末尾补齐:原始数据长度不能被分片布局整除时,需要补齐数据并记录真实长度,重建后才能正确去掉填充字节。
- 数据完整性:XOR 可以恢复已知位置的缺失片,但不能可靠识别哪一片发生了静默损坏。应另外保存校验和或哈希,用于发现并定位损坏,再决定是否执行恢复。
- 恢复窗口:已经丢失一片但尚未重建时,条带处于降级状态。若此时再丢失一片,单 XOR 校验无法继续恢复,应尽快重建并恢复冗余。
因此,XOR 单校验片适合用一片冗余换取单片丢失恢复能力。需要同时容忍两个或更多分片丢失时,应使用具有更多独立校验片的纠删码方案,而不能仅靠重复计算同一份 XOR 校验片。