数据完整性和保护

1 磁盘故障模式

磁盘并不完美，并且可能会出现故障（有时）。在早期的 RAID 系统中，故障模型非常简单：要么整个磁盘正常工作，要么完全故障，并且检测此类故障非常简单。这种磁盘故障的故障停止模型使得构建 RAID 相对简单。

但现代磁盘所表现出的还有其他类型的故障模式。具体来说，如 Bairavasundaram 等人经过详细研究 ，现代磁盘有时看起来大部分工作正常，但在成功访问一个或多个块时遇到问题。具体来说，有两种类型的单块故障很常见且值得考虑：静默扇区错误 (LSE) 和块损坏。我们现在将更详细地讨论每一个。

当磁盘扇区（或扇区组）受到某种损坏时，就会出现 LSE。例如，如果磁盘磁头由于某种原因（磁头撞击，正常运行中不应该发生的情况）接触到磁盘表面，可能会损坏磁盘表面，导致位无法读取。宇宙射线也会使位翻转，导致内容错误。幸运的是，硬盘会使用磁盘内纠错码 (ECC) 来确定块中的磁盘位是否正确，并在某些情况下对其进行修复；如果位不正确，而硬盘又没有足够的信息来修复错误，则在请求读取时磁盘会返回错误信息。

还有一种情况是，磁盘块损坏的方式无法被磁盘本身检测到。例如，存在漏洞的磁盘固件可能会将块写入错误位置；在这种情况下，磁盘 ECC 显示块内容正常，但从客户端的角度来看，随后访问时会返回错误的块。同样，当数据块通过故障总线从主机传输到磁盘时，也可能会损坏数据块；磁盘会存储损坏的数据，但这些数据并不是客户想要的。这类故障特别隐蔽，因为它们是静默故障；磁盘在返回故障数据时不会显示问题。

Prabhakaran 等人将这种更现代的磁盘故障观点称为部分故障磁盘故障模型。在这种观点中，磁盘仍有可能全部失效（就像传统的故障-停止模型中的情况一样）；但是，磁盘也有可能看似正常工作，但有一个或多个区块变得不可访问（即 LSE）或包含错误的内容（即损坏）。因此，在访问看似正常工作的磁盘时，偶尔会在尝试读取或写入给定块时返回错误（非静默部分故障），偶尔也会简单地返回错误数据（静默部分故障）。

这两类故障都比较罕见，但究竟有多罕见呢？下图总结了两份 Bairavasundaram 研究报告的部分结论。

该图显示了在研究过程中（约 3 年，超过 150 万台硬盘）至少出现过一次 LSE 或块损坏的硬盘百分比。该图将结果进一步细分为 “廉价 “硬盘（通常为 SATA 硬盘）和 “昂贵 “硬盘（通常为 SCSI 或光纤通道硬盘）。正如您所看到的，虽然购买更好的硬盘降低了这两类问题的发生频率（大约降低了一个数量级），但它们仍然经常发生，因此您需要仔细考虑如何在存储系统中处理它们。

关于 LSE 的一些其他发现包括：

• 具有多个 LSE 的昂贵驱动器与较便宜的驱动器一样可能产生额外错误；
• 对于大多数驱动器，第二年的年错误率会增加；
• LSE 数量随着磁盘大小的增加而增加；
• 大多数磁盘具有LSE 少于 50 个；
• 具有 LSE 的磁盘更有可能产生额外的 LSE；
• 存在大量的空间和时间局部性；
• 磁盘清理很有用（大多数 LSE 都是通过这种方式找到的） 。

关于损坏的一些发现：

• 同一驱动器类别中不同驱动器型号的损坏几率差异很大；
• 型号之间的老化影响不同；
• 工作负载和磁盘大小对损坏影响很小
• 大多数损坏的磁盘只有少数损坏；
• 损坏在磁盘内或 RAID 中的磁盘之间不是独立的；
• 存在空间局部性和一些时间局部性
• 与LSE 的相关性很弱

一个可靠的存储系统，需要有检测和恢复 LSE 和块损坏的机制

2 处理静默扇区错误（LSE）

考虑到这两种新的部分磁盘故障模式，我们现在应该尝试看看我们可以对它们做些什么。让我们首先解决两者中较容易的一个，即静默扇区错误。

关键问题：存储系统应如何处理静默扇区错误？需要多少额外的机制来处理这种形式的部分故障？

事实证明，静默扇区错误的处理相当简单，因为它们（根据定义）很容易检测到。当存储系统尝试访问块并且磁盘返回错误时，存储系统应该简单地使用它所拥有的任何冗余机制来返回正确的数据。例如，

• 在镜像 RAID 中，系统应该访问备用副本；
• 在基于奇偶校验的 RAID-4 或 RAID-5 系统中，系统应从奇偶校验组中的其他块重建该块。

因此，诸如 LSE 等容易检测到的问题可以通过标准冗余机制轻松恢复。

LSE的不断增多影响了多年来RAID设计。在RAID-4/5系统中，当整个磁盘故障和LSE同时发生时，会出现一个特别有趣的问题。具体而言，在整个磁盘失败时，RAID尝试通过读取奇偶校验组中所有其他磁盘并重新计算缺失值来重建该磁盘（比如说，到一个热备用上）。如果在重建过程中，在任何其他一块磁盘上遇到LSE，则会出现问题：无法成功完成重建。

为了解决这个问题，一些系统增加了额外的冗余度。例如，NetApp的RAID-DP相当于两块奇偶校验硬盘而不是一块。当在重建过程中发现LSE时，额外的奇偶校验有助于重构丢失的数据块。正如始终如此地存在成本那样，在每条条带保持两块奇偶校验硬盘更昂贵；然而，NetApp WAFL文件系统的日志结构化性质在许多情况下可以减轻这种成本。剩下的成本是空间方面，在第二个奇偶校验区块形式上需要额外一块硬盘。

3 检测损坏：校验和

3.1 基本介绍

现在让我们解决更具挑战性的问题，即通过数据损坏导致的静默故障。当数据损坏导致磁盘返回坏数据时，我们如何防止用户获得坏数据？

关键问题：鉴于此类故障的隐匿性，存储系统可以采取哪些措施来检测何时发生损坏？需要什么技术？如何有效地实施它们？

与静默扇区错误不同，损坏检测是一个关键问题。客户端如何知道某个块已经坏了？一旦知道某个特定块损坏，恢复就与以前相同：您需要该块的其他副本（希望是一个未损坏的副本！）。因此，我们在这里重点关注检测技术。

现代存储系统用于保持数据完整性的主要机制称为校验和。校验和只是一个函数的结果，该函数将一块数据（例如 4KB 块）作为输入，并根据所述数据计算函数，生成数据内容的小摘要（例如 4 或 8 字节），该摘要称为校验和。这种计算的目标是使系统能够通过将校验和与数据一起存储来检测数据是否已被损坏或更改，然后在以后访问时确认数据的当前校验和与原始存储值相匹配。

3.2 常用校验和函数

许多不同的函数用于计算校验和，它们的强度（即，它们在保护数据完整性方面的能力）和速度（即，它们的计算速度）各不相同。这里出现了系统中常见的权衡：通常，获得的保护越多，成本就越高。

有些人使用的一种简单的校验和函数是基于异或 (XOR) 的。对于基于 XOR 的校验和，校验和是通过对正在校验和的数据块的每个块进行异或来计算的，从而生成表示整个块的 XOR 的单个值。

为了更具体地说明这一点，假设我们正在 16 字节的块上计算 4 字节的校验和（这个块当然太小，不能真正成为磁盘扇区或块，但它将用于示例）。 16 个数据字节（十六进制）如下所示：

1

365e c4cd ba14 8a92 ecef 2c3a 40be f666

如果用二进制表示，我们会得到以下结果：

1
2
3
4

0011 0110 0101 1110 1100 0100 1100 1101
1011 1010 0001 0100 1000 1010 1001 0010
1110 1100 1110 1111 0010 1100 0011 1010
0100 0000 1011 1110 1111 0110 0110 0110

由于我们以每行 4 个字节为一组排列数据，因此很容易看出校验和的结果：在每列上执行 XOR 即可得到最终的校验和值：

1

0010 0000 0001 1011 1001 0100 0000 0011

结果（十六进制）为0x201b9403。 XOR 是一种合理的校验和方法，但有其局限性。例如，如果每个校验和单元中同一位置的两个位发生变化，则校验和将无法检测到损坏。为此，人们研究了其他校验和函数。

另一种基本的校验函数是加法。这种方法的优点是速度快；计算时只需对每块数据执行 2 的补码加法，忽略溢出。它可以检测到数据的许多变化，但如果数据发生移位等情况，则效果不佳。

Fletcher校验和是一种略微复杂的算法，以John G. Fletcher的名字命名。它的计算非常简单，只需计算两个校验字节 $s_1$ 和 $s_2$。具体来说，假设数据块 $D$ 由字节 $d_1 \dots d_n$ 组成；$s_1$ 的定义如下：$s_1 = (s_1 + d_i) \mod 255$（对所有 $d_i$ 进行计算）；$s_2$ 的定义如下：$s_2 = (s_2 + s_1) \mod 255$（同样对所有 $d_i$ 进行计算）。Fletcher 校验和与 CRC 几乎一样强（见下文），能检测出所有单bit、双bit错误和许多突发错误。

最后一种常用的校验和称为循环冗余校验（CRC）。假设要计算数据块 D 的校验和，只需将 D 视为一个大的二进制数（毕竟只是一串bit），然后除以一个约定的值（$k$）。除数的余数就是 CRC 的值。事实证明，我们可以相当高效地实现这种二进制模运算，因此 CRC 在网络中也很流行。

无论使用哪种方法，显而易见的是，没有完美的校验和：两个内容不相同的数据块有可能具有完全相同的校验和，这就是所谓的冲突。这个事实应该是直观的：毕竟，计算校验和是把一个大的东西（如 4KB），生成一个小得多的摘要（如 4 或 8 字节）。因此，在选择一个好的校验和函数时，我们试图找到一个既能尽量减少冲突几率，又能保持计算简便的函数。

3.3 校验和布局

现在您已经了解了如何计算校验和，接下来我们来分析如何在存储系统中使用校验和。我们必须解决的第一个问题是校验和的布局，即校验和应该如何存储在磁盘上？

最基本的方法只是存储每个磁盘扇区（或块）的校验和。给定一个数据块 D，让我们调用该数据的校验和 C(D)。因此，如果没有校验和，磁盘布局如下所示：

使用校验和时，布局会为每个块添加一个校验和：

由于校验和通常很小（如 8 字节），而磁盘只能以扇区大小的块（512 字节）或其倍数写入，因此出现的一个问题是如何实现上述布局。硬盘制造商采用的一种解决方案是用 520 字节扇区格式化硬盘；每个扇区额外的 8 字节可用于存储校验和。

对于不具备这种功能的磁盘，文件系统必须想办法将校验和存储到 512 字节的块中。其中一种方法如下：

在此方案中，$n$ 个校验和一起存储在一个扇区中，后面是 $n$ 个数据块，然后是下一个的 $n$ 个块的另一个校验和扇区，依此类推。这种方法的优点是可以在所有磁盘上工作，但效率可能较低；例如，如果文件系统想要覆盖块D1，则必须读入包含C(D1)的校验和扇区，更新其中的C(D1)，然后写出校验和扇区和新的数据块D1（因此，一次读取和两次写入）。早期的方法（每个扇区一个校验和）仅执行一次写入。

3.4 使用校验和

在确定了校验和布局之后，我们就可以着手了解如何使用校验和了。读取数据块 D 时，客户端（即文件系统或存储控制器）也会从磁盘读取其校验和$C_s(D)$，我们称之为存储校验和（因此使用了下标 $C_s$）。然后，客户端对检索到的数据块 D 计算校验和，我们称之为计算校验和 $C_c(D)$。此时，客户端会比较存储的校验和与计算的校验和；如果两者相等（即 $C_s(D) == C_c(D)$），则数据很可能没有损坏，因此可以安全地返回给用户。如果它们不匹配（即 $C_s(D) != C_c(D)$），这意味着数据在存储后发生了变化（因为存储的校验和反映的是数据当时的值）。在这种情况下，我们的校验和帮助我们检测到了数据损坏。

有了损坏，我们自然会问该如何处理？如果存储系统有冗余副本，答案很简单：尝试使用它。如果存储系统没有这样的副本，答案很可能是返回错误。不管是哪种情况，都要认识到损坏检测并不是灵丹妙药；如果没有其他办法获取未损坏的数据，那就只能走霉运了。

4 一个新问题：错误写入

上述基本方案在一般的块损坏情况下效果很好。然而，现代磁盘有几种不同寻常的故障模式，需要不同的解决方案。

第一种故障模式称为误写。磁盘和 RAID 控制器会出现这种情况，它们会将数据正确写入磁盘，只是写错了位置。在单磁盘系统中，这意味着磁盘将数据块 $D_x$ 写入的地址不是 $x$，而是 $y$（从而 “破坏 “了 $D_y$）；此外，在多磁盘系统中，控制器也可能将 $D_{i,x}$ 写入的地址不是磁盘 $i$ 的 $x$，而是其他磁盘 $j$。因此关键问题是：

存储系统或磁盘控制器应如何检测错误写入？校验和需要哪些附加功能？

答案很简单：在每个校验和中增加一点信息。在这种情况下，增加一个**物理标识符（物理 ID）**是非常有用的。例如，如果现在存储的信息包含校验和 $C(D)$以及块的磁盘编号和扇区编号，那么客户端就很容易确定正确的信息是否存在于特定位置。具体来说，如果客户端读取的是磁盘 $10$ 上的块 $4$（$D_{10,4}$），则存储的信息应包括该磁盘编号和扇区偏移量，如下图所示。如果信息不匹配，就说明发生了错误写入，此时就会检测到损坏。下面是双磁盘系统中添加信息的示例。请注意，该图和之前的其他图一样，并不是按比例绘制的，因为校验和通常很小（如 8 字节），而数据块却大得多（如 4 KB 或更大）：

从磁盘上的格式可以看出，磁盘上现在有相当多的冗余信息：对于每个块，磁盘编号在每个数据块内重复出现，而相关块的偏移量也保留在数据块本身旁边。冗余信息的存在不足为奇，因为冗余是错误检测（在本例中）和恢复（在其他情况下）的关键。虽然完美的磁盘并不严格需要一点额外的信息，但如果出现问题，这些信息却能帮助检测出问题所在。

5 最后一个问题：写入丢失

不幸的是，错误写入并不是我们要解决的最后一个问题。具体来说，一些现代存储设备还存在一个称为写入丢失的问题，当设备通知上层写入已完成但实际上从未被持久化时，就会发生这种情况；因此，剩下的是块的旧内容而不是更新的新内容。

这里明显的问题是：上面的任何校验和策略（例如基本校验和或物理标识）是否有助于检测丢失的写入？不幸的是，答案是否定的：旧块可能有匹配的校验和，并且上面使用的物理 ID（磁盘号和块偏移量）也将是正确的。

因此，我们的最后一个关键问题是：

存储系统或磁盘控制器应如何检测丢失的写入？校验和还需要哪些附加功能？

有许多可能的解决方案可以帮助。一种经典方法是执行写入验证或写入后读取；通过在写入后立即读回数据，系统可以确保数据确实到达磁盘表面。然而，这种方法非常慢，完成写入所需的 I/O 数量会增加一倍。

有些系统在系统的其他地方添加校验和来检测丢失的写入。例如，Sun 的 Zettabyte 文件系统 (ZFS) 在每个文件系统inode中包含一个校验和，并为文件中包含的每个块提供间接块。因此，即使对块本身的写入丢失，inode 内的校验和也不会与旧数据匹配。只有当对inode和数据的写入同时丢失时，这种方案才会失败，这是一种不太可能（但不幸的是，有可能！）的情况。

6 扫描

说了这么多，你可能会问：这些校验和什么时候会被检查？当然，在应用程序访问数据时会进行一定量的校验，但大多数数据很少被访问，因此会保持未校验状态。对于可靠的存储系统来说，未校验的数据是有问题的，因为bit损坏最终会影响特定数据的所有副本。

为了解决这个问题，许多系统都采用了各种形式的磁盘扫描。通过定期读取系统中的每个块，并检查校验和是否仍然有效，磁盘系统可以降低某个数据项的所有副本损坏的几率。典型的系统每晚或每周安排一次扫描。

7 校验和的开销

在结束之前，我们现在讨论使用校验和进行数据保护的一些开销。正如计算机系统中常见的那样，有两种不同类型的开销：空间和时间。

空间开销有两种形式。

• 第一个是在磁盘（或其他存储介质）本身上；每个存储的校验和都会占用磁盘空间，无法再用于存储用户数据。典型的比率可能是每 4 KB 数据块 8 字节校验和，磁盘空间开销为 0.19%。
• 第二种类型的空间开销来自系统的内存。访问数据时，内存中必须有空间用于存放校验和以及数据本身。但是，如果系统只是检查校验和，然后在完成后将其丢弃，则这种开销是短暂的，不必担心。只有当校验和保存在内存中（为了防止内存损坏的额外保护级别），这个小开销才会被观察到。

虽然空间开销很小，但校验和引起的时间开销可能非常明显。至少，CPU 必须计算每个块的校验和，无论是在存储数据时（以确定存储的校验和的值）还是在访问数据时（再次计算校验和并将其与存储的校验和进行比较）。许多使用校验和（包括网络栈）的系统采用的一种减少 CPU 开销的方法是将数据复制和校验和合并为一项简化的活动；因为无论如何都需要复制（例如，将数据从内核页缓存复制到用户缓冲区），因此组合复制/校验和可能非常有效。

除了 CPU 开销之外，某些校验和方案还会产生额外的 I/O 开销，特别是当校验和与数据分开存储时（因此需要额外的 I/O 来访问它们），以及后台扫描所需的任何额外 I/O。前者可以通过设计来减少；后者可以进行调整，从而限制其影响，或许可以通过控制此类扫描活动的发生时间来实现（如半夜）。