1一句话 + 关键问题

一句话：磁盘不只是"要么好、要么整块坏"，它还会悄悄地坏掉某一个块——读不出来（潜在扇区错误），或者读出来的内容是错的（块损坏）。本章的答案是：用校验和（checksum）发现静默损坏，再加上物理 ID、父块中的校验和、磁盘擦洗（scrubbing）去对付错位写入、丢失写入和"没人读的数据慢慢烂掉"这几种更刁钻的情况；发现问题之后，靠 RAID / 镜像等冗余把正确数据找回来。

本章承接第 38 章 RAID（当时只考虑"整盘失效"）和第 40–43 章的文件系统实现：前面几章关心的是快（FFS、LFS）和崩溃后一致（日志），这一章关心的是数据本身对不对。后面的分布式系统章节（第 48 章起）也会反复用到校验和：网络上传输的数据同样会损坏。

2核心概念速览

3磁盘故障模式：不只是"整盘坏"

第 38 章讲 RAID 时，我们采用的是全盘失效（fail-stop）模型：磁盘要么正常工作，要么彻底坏掉，而且"坏掉"很容易检测。这让 RAID 的设计相对简单。

但 Bairavasundaram 等人的研究发现，现代磁盘经常大体上还能工作，只是某一个或几个块出问题。常见的单块故障有两类：

• 潜在扇区错误（latent sector error, LSE）：扇区（或一组扇区）物理损坏。比如磁头碰到盘面（磁头划伤，head crash）弄坏了表面；宇宙射线也可能翻转比特。磁盘内部用纠错码（ECC）判断块里的比特是否完好、有时还能修好；修不好时，读这个块会返回错误。
• 块损坏（block corruption）：块的内容坏了，而磁盘自己察觉不到。例如有 bug 的磁盘固件把块写到了错误的位置——磁盘 ECC 认为内容没问题，但客户端读到的却是"别的块"；又如数据经过有故障的总线从主机传到磁盘时就已经坏了，磁盘把坏数据老老实实存下来。这类故障是静默故障（silent fault）：返回错误数据时磁盘不给任何提示，所以格外阴险。

Prabhakaran 等人把这种更现代的视角称为部分失效（fail-partial）模型：磁盘仍可能整块失效；也可能看似正常，却偶尔读写某块时报错（非静默部分故障），或者干脆返回错误内容（静默部分故障）。

它们有多常见？

原书 Figure 45.1 汇总了 Bairavasundaram 等人两项研究的结果：在大约 3 年里、超过 150 万块磁盘中，至少出现过一次 LSE 或块损坏的磁盘所占比例。"廉价"盘通常是 SATA，"昂贵"盘通常是 SCSI 或光纤通道（Fibre Channel）。

买更好的盘大约能把两类问题的频率降低一个数量级，但它们仍然常见到必须认真对待。原书列出的其他发现：

结论很清楚：想构建可靠的存储系统，就必须有检测并恢复 LSE 和块损坏的机制。

4处理潜在扇区错误：检测容易，靠冗余恢复

LSE 按定义就很容易检测：访问某块时磁盘直接返回错误。存储系统只需要动用已有的冗余机制拿到正确数据：镜像 RAID 就去读另一份副本；RAID-4/5 就用同一奇偶校验组里的其他块重建出这个块。

但 LSE 越来越常见，也影响了 RAID 设计。一个典型难题出现在 RAID-4/5 上：整盘失效和 LSE 同时发生。一块盘坏了，RAID 要把它重建到热备盘上，就得把奇偶校验组里其他所有盘从头到尾读一遍；如果重建途中在另一块盘上碰到 LSE，这一条带就同时缺了两个块，单个奇偶校验块救不回来——重建无法顺利完成。

为此有的系统增加一层冗余。例如 NetApp 的 RAID-DP 相当于有两块奇偶校验盘：重建时碰到 LSE，额外的校验信息可以把缺失块重建出来。代价照例存在：每个条带要维护两个校验块更贵（不过 NetApp 的 WAFL 文件系统是日志结构式的，很多时候能摊薄这部分开销），剩下的主要代价是空间——多占一块盘来放第二个校验块。

5检测损坏：校验和

和 LSE 不同，损坏的难点在于检测。一旦知道某块坏了，恢复方法和前面一样：找另一份副本（但愿那份没坏）。所以这里集中讨论检测技术。

现代存储系统保护数据完整性的主要手段是校验和（checksum）：一个函数，输入一块数据（比如 4 KB），输出一个很小的摘要（比如 4 或 8 字节）。把校验和与数据一起存下来，以后访问时重新计算，对比当前数据的校验和与当初存下的值，就能发现数据是否被改动过。

常见的校验和函数

不同校验和函数在强度（保护数据完整性的能力）和速度（计算快慢）上各有取舍。

• 异或（XOR）：把数据块切成若干等长的单元，全部异或起来。原书的例子：对 16 字节的块算 4 字节校验和，把数据排成每行 4 字节，对每一列求异或。数据 365e c4cd ba14 8a92 ecef 2c3a 40be f666 的结果是 0x201b9403。XOR 的弱点：如果两个比特在各自单元的同一位置同时翻转，校验和不变，检测不到。
• 加法（addition）：对每个单元做二进制补码加法，忽略溢出。很快，能发现很多改动；但如果数据被移位/重排了就不行（加法和异或都满足交换律，顺序变了结果不变）。
• Fletcher 校验和：设数据块 D 由字节 d₁ … d_n 组成，对所有 d_i 依次计算 s1 = (s1 + di) mod 255，s2 = (s2 + s1) mod 255。s2 是 s1 的累加，隐含了位置信息，所以重排也能发现。原书称它几乎和 CRC 一样强，能检测所有单比特、双比特错误和很多突发错误。
• 循环冗余校验（CRC）：把数据块 D 看成一个很大的二进制数，除以一个约定好的值 k，余数就是 CRC。这种"二进制取模"可以实现得很高效，所以 CRC 在网络中也很流行。

无论哪种方法，都不存在完美的校验和：内容不同的两个块可能得到相同的校验和，这叫碰撞（collision）。这很直观：把 4 KB 压缩成 4 或 8 字节的摘要，必然有很多输入对应同一个输出。选校验和函数，就是在"碰撞尽量少"和"计算尽量快"之间找平衡。

CRC 的"除法"到底是什么

CRC 的除法是模 2 运算：没有进位和借位，减法就是异或。以上面模拟器用的 CRC-8 为例，除数 k = 1 0000 0111（多项式 x⁸+x²+x+1，简写 0x07）。实现时维护一个 8 位寄存器，每读入一个字节先异或进寄存器，再逐位处理：

uint8_t crc8(const uint8_t *p, size_t n) {
    uint8_t c = 0;
    for (size_t i = 0; i < n; i++) {
        c ^= p[i];                          // 把下一个字节"拉下来"
        for (int k = 0; k < 8; k++)
            c = (c & 0x80) ? (c << 1) ^ 0x07   // 最高位是 1：够"除"，减去除数（= 异或）
                           : (c << 1);         // 最高位是 0：商这一位为 0，只移位
    }
    return c;                               // 最后剩下的就是余数
}

这和小学的竖式长除法一模一样，只是"减法"变成了异或。每次最高位为 1 时异或上除数，等价于长除法里"够减就减"。实际系统常用 CRC-32（除数 33 位），并用查表法一次处理一个字节（见本章实验）。

校验和放在哪里：布局（layout）

最直接的做法是每个扇区（或块）配一个校验和：给定数据块 D，记其校验和为 C(D)。但校验和很小（如 8 字节），而磁盘只能以扇区（512 字节）为单位写入，怎么放？

磁盘厂商的一种办法是把盘格式化为 520 字节扇区，每扇区多出的 8 字节存校验和。没有这种功能的磁盘，文件系统就得自己把校验和打包进 512 字节的块里：一个校验和扇区存 n 个校验和，后面跟 n 个数据块，然后是下一组。这种方案在所有磁盘上都能用，但效率可能差一些：想覆盖 D1，就得先读入存有 C(D1) 的校验和扇区、更新 C(D1)，再写出校验和扇区和新的 D1——一次读、两次写；而每扇区自带校验和的方案只需一次写。

6使用校验和，以及两个新问题

读块 D 时，客户端（文件系统或存储控制器）同时从磁盘读出它的校验和，称为存储的校验和 C_s(D)；再对读到的块重新算一遍，称为计算的校验和 C_c(D)。相等说明数据很可能没被损坏，可以放心返回；不相等说明数据自存储以来被改动过——校验和帮我们发现了一次损坏。

发现损坏后怎么办？有冗余副本就简单：改用副本。没有副本，多半只能返回错误。要明白，检测损坏不是灵丹妙药：如果没有其他途径拿到未损坏的数据，你就是没辙了。

错位写入（misdirected write）

磁盘和 RAID 控制器有时会把数据正确地写到了错误的位置。单盘系统中，本该写到地址 x 的 D_x 被写到了地址 y（于是"损坏"了 D_y）；多盘系统中，控制器还可能把 D_i,x 写到了另一块盘 j 上。

注意：错位写入后，块 y 上是一份完整、自洽的数据——它的内容和它的校验和完全匹配（校验和就是对这份数据算的）。所以单纯的校验和发现不了！答案也很简单：给校验和再加一点信息——物理 ID（physical ID），即块所在的磁盘号和扇区号。读磁盘 10 的块 4（D_10,4）时，存储的信息里应该写着"disk=10、block=4"；对不上，就说明发生了错位写入。

从这个磁盘格式可以看到，盘上多了不少冗余信息：每个块都重复记着磁盘号，块的偏移也紧挨着块本身存了一份。这并不奇怪：冗余是错误检测（以及恢复）的关键。对完美的磁盘来说这点额外信息并非必需，但在出问题时能帮大忙。

最后一个问题：丢失写入（lost write）

有些设备会告诉上层"写完了"，实际上数据从未落盘，块上留着的还是旧内容。前面的办法有用吗？没用：旧块的校验和与旧数据完全匹配，物理 ID（磁盘号 + 块偏移）也完全正确。

可行的办法有好几种：

• 写验证（write verify）/ 写后读（read-after-write）：写完立刻读回来，确认数据确实到达了盘面。缺点是很慢，完成一次写所需的 I/O 翻倍。
• 在系统的别处再存一份校验和：例如 Sun 的 ZFS 在每个文件的 inode 和间接块里，为文件包含的每个块都存了校验和。即使对数据块的写丢失了，inode 里的校验和也对不上旧数据。只有 inode 和数据块的写同时丢失，这个方案才会失效——不太可能，但遗憾的是确实可能。

7磁盘擦洗与开销

擦洗（scrubbing）：校验和到底什么时候被检查？

应用访问数据时会顺带检查一部分，但大多数数据很少被访问，于是一直没人检查。对可靠的存储系统来说这很危险：比特腐烂（bit rot）最终可能波及同一份数据的所有副本。

补救办法是磁盘擦洗（disk scrubbing）：定期读遍系统中的每一个块，核对校验和是否仍然有效，趁还有好副本时修复坏副本，从而降低某份数据所有副本都坏掉的概率。典型系统每晚或每周扫描一次。（前面的研究也提到：大多数 LSE 就是这样被发现的。）

校验和的开销

和计算机系统中常见的情况一样，开销分空间和时间两种。

• 空间·磁盘上：每个校验和都占掉本可存用户数据的空间。典型比例是每 4 KB 数据块配 8 字节校验和，磁盘空间开销约 0.19%（8 / 4096 ≈ 0.195%）。
• 空间·内存中：访问数据时内存里要同时放校验和。如果校验完就丢掉，这个开销很短暂，不必担心；只有为了防范内存损坏而把校验和一直留在内存里时，才看得到这点小开销。
• 时间·CPU：空间开销很小，时间开销却可能相当明显。CPU 至少要在存储时（算出要存的校验和）和访问时（重算并比较）各算一遍。许多系统（包括网络协议栈）的优化办法是把复制和校验合二为一：数据反正要从内核页缓存复制到用户缓冲区，边复制边算校验和非常划算。
• 时间·额外 I/O：校验和与数据分开存放时需要额外 I/O（可通过设计减少）；后台擦洗也要额外 I/O（可以调节，比如放在大多数人——并非所有人！——都已上床睡觉的深夜进行）。

8模拟器：镜像 + 校验和，检测并恢复

把本章所有机制放进一个小系统：两块互为镜像的磁盘，每块盘 6 个块，每个块旁存着 Fletcher 校验和（可选再加物理 ID）；还可以选择在 inode 里再存一份校验和（ZFS 式）。你可以注入各种故障，然后读取或擦洗，看系统能不能发现、能不能修好。

9先预测，再验证

10动手实验：实现并比较四种校验和

cd labs/45-data-integrity && make && ./csum

// Fletcher（原书定义）：每个字节都取模
for (size_t i = 0; i < n; i++) { s1 = (s1 + p[i]) % 255; s2 = (s2 + s1) % 255; }

// 推迟取模：64 位累加器足够大，每 4096 字节才取一次模，结果完全相同
for (size_t i = 0; i < k; i++) { s1 += p[i]; s2 += s1; }
s1 %= 255; s2 %= 255;

// CRC32 查表：T[] 预先存好"一个字节经过 8 次移位/异或"的结果
for (size_t i = 0; i < n; i++) c = T[(c ^ p[i]) & 0xFF] ^ (c >> 8);

== 自检 ==
原书示例 XOR      = 0x201b9403 （原书：0x201b9403） OK
原书示例 加法     = 0x1e2171ff
原书示例 Fletcher = s2=0x04 s1=0xb2
原书示例 CRC32    = 0x314ca7a8
CRC32("123456789") 逐位=0xcbf43926 查表=0xcbf43926 （标准值 0xcbf43926） OK

== 测速：64 MB 随机数据（每种算至少 0.3 秒）==
  15986.8 MB/s   XOR (64位字)
   3208.7 MB/s   XOR (32位字,大端)
   3358.2 MB/s   加法 (32位字)
    285.6 MB/s   Fletcher 朴素
   1552.7 MB/s   Fletcher 推迟取模
    116.2 MB/s   CRC32 逐位
    409.1 MB/s   CRC32 查表

== 检测率：4 KB 块，每种损坏 100000 次 ==
       XOR      加法  Fletcher     CRC32   损坏方式
  100.000%  100.000%  100.000%  100.000%   随机 1 比特翻转
   96.928%   98.364%   99.984%  100.000%   随机 2 比特翻转
    0.000%   48.549%   99.888%  100.000%   同列 2 比特翻转(相隔 4 字节倍数)
    0.000%    0.000%   97.852%  100.000%   交换两个 4 字节字
  100.000%   99.939%   99.992%  100.000%   随机 3 比特翻转

11自测题

12常见误区与本章小结