Latent Sector Errors, Disk Failure, and RAID Failure (part 1)

本文来自三篇关于磁盘错误的论文：

• Understanding Latent Sector Errors and How to Protect Against Them, FAST 2010
• Disk failures in the real world: What does an MTTF of 1,000,000 hours mean to you, FAST 2007
• RAIDShield : Characterizing , Monitoring , and Proactively Protecting Against Disk Failures, FAST 2015

三篇文章分别从扇区（sector）错误，单块磁盘失效，RAID 失效的角度观察磁盘的可靠性问题，他们的分析都基于大量的企业级数据。通过阅读这些文章，可以对磁盘的可靠性有一些基础的认识。其中前两篇文章都来自Bianca Schroeder，CMU 出身，曾在 Garth Gibson 那做 post-doc，现在 Toronto 大学当 faculty；第三篇文章来自 EMC，Ao Ma 是 Remzi 的学生，他之前的工作 ffsck得到了 Dr. Marshall Kirk McKusick 很高的评价，并被实现到 BSD filesystem。这些工作都需要大量的工业界数据，这是高校所不具备的条件，不过我们仍然可以学习他们统计的技巧。

1. 扇区错误（latent sector error）

这类错误一般称为 Latent Sector Errors（LSEs）。LSE 的特点是潜伏，在再次访问损坏扇区之前，LSE 是无法被发现的。而且随着磁盘密度增加，LSE 变得更常见。在早期的建模中并没有考虑 LSE，随后得到了重视，因为同时坏2块磁盘的概率很低，但是碰到坏一块磁盘 + 另一个磁盘的 LSE 就会更常见，这也是为什么RIAD 6被认为是必要的（见 Greenan 的博士论文）。一般磁盘会有 scrubbing 机制去检测 LSE，即后台定期扫描整块磁盘做校验。另一种保护机制是磁盘内部冗余（intra-disk redundancy），类似将 raid 的做法移植到磁盘内部。这篇文章的贡献就是分析了 LSE 的特点（使用的数据来自另一篇 SIGMETRICS’07 论文，这篇文章也是分析 LSE；但是 Bianca 的文章侧重于分析 spatial and temporal locality，以及如何利用locality去改进 scrubbing 和 intra-disk redundancy），以及评价了各种 scrubbing 和 intra-disk redundancy 的可靠性。

1.1 统计分析

1.1.1 How Long Are Error Bursts?

Error Burst 的意思是在逻辑块空间上连续的 LSE。那么 Error Burst 的长度分布如何呢？如图所示，对于所有的 disk models，90-98%的Error Burst 都只有一个 LSE；除了 A1和n3以外，不到2.5%的 Error Burst 有 2 个或以上 LSE。作者还检查了几种概率分布，包括Geometric，Weibull，Rayleigh，Pareto 和 Lognormal，发现 Pareto 是最匹配的（因为长尾）。

1.1.2 How Far Are Errors Spaced Apart？

上图描述了 2个礼拜时间内（2个礼拜是 NetApp 设置的 scrubbing 周期）连续发生的 LSE 之间的空间距离分布（间隔几个健康的扇区）。 考察这个指标主要是检查短时间内连续发生的 LSE 是否具有空间的局部性 。20-60%的 LSE 的距离非常近，只有10个扇区。同时也发现在某些距离会有激增的现象，比如 o2 在10^3 和 10^5 。

1.1.3 Where on the Drive Are Errors Located?

上图描述了是否存在某些磁盘区域更容易出现 LSE。 如果存在这种现象，就可以调整 scrubbing 或者 intra-disk redundacy 的策略，在这些区域采取更强的保护机制 。磁盘的前10%逻辑地址包含了20-50%的 LSE。另外，一些 disk models 出现了某些高发区域。

1.1.4 What is the Burstiness of Errors in Times?

这次主要是检查 LSE 的时间局部性。

上图检查了出现一次 LSE 后，磁盘再次遇到 LSE 的时间分布（已2个礼拜为单位）。在发现 LSE 的一个月后，出现 LSE 的概率是指数下降的。作者的意思就是 LSE 更有可能在时间上连续出现，也就是由同一个事件导致的。

这幅图显示了在磁盘出现 LSE 后一年的时间内，额外的 LSE 都分布在几个 2-week periods。可以看到，对于55-85%的磁盘，这些 LSE 聚集在同一个2-week period 里。只有10-15%的磁盘会在2个不同的2-week periods 看到 LSE。所以作者的结论是LSE 具有时间局部性，它们大多会集中在一个时间发生，很可能是由同一个事件导致的。也因此，泊松分布不是一个理想的模型。作者发现 Pareto 分布是一个更好的模型。

1.1.5 Does Close in Space Mean Close in Time?

1.1.2 节讲的是时间邻近的 LSE 是否空间也邻近，这一节则反过来，空间邻近的 LSE 是否时间也邻近。也就是从充分条件/必要条件进化到充要条件。如果这个假设是成立的，那么 intra-disk redundancy 的效果就要大打折扣，因为 data 和 parity 块一般放在一起，很可能会同时遇到 LSE 而丢失数据。

上图显示一个 Error Burst 在时间上的距离，也就是同一个 Burst 内，第一个 LSE 与最后一个 LSE 的时间间隔。大约90%的 Error Burst，LSEs 都发生在同一个 2-week period；而大约95%在一个月内；只有不到2%在3个月以上。也就是说地址邻近的 LSE 大多是同时发生的。

上图显示了时间局部性和空间局部性的相关性。X 轴显示的是空间距离，从1个扇区到50GB。就是给定时间范围（2周或者整个磁盘的生命周期）内，在一个 LSE 的某个空间范围内又出现 LSE 的概率。可以看到扩大空间范围，可以发现更多 LSE。但是扩展时间范围，并不能发现更多的 LSE，预示了空间邻近的 LSE 基本是同时发生的。

1.2 保护机制

针对 LSE，主要的保护机制是 intra-disk redundancy 和 scrubbing。

1.2.1 intra-disk redundancy

intra-disk redundancy 基本就是在扇区之间做 erasure coding。现存的工作并没有使用真实数据验证有效性。因此作者用收集的数据测试了三种现存方案，以及两种改良的方案。

• Single parity check (SPC)：为 k 个连续的扇区布置1个校验扇区，这 k+1个扇区整体称为 parity group。SPC 只能纠正一个LSE，但存储/性能的开销也较小。但是LSE 呈现出的时间/空间局部性对 SPC 很不利。
• Maximum distance separable (MDS) erasure code：一个 k+m MDS编码为 k 个数据扇区计算 m 个校验扇区，因此可以容忍任意 m 个 LSE。但是开销比 SPC 大很多。
• Interleaved parity check codes (IPC)：可以看成是 SPC 的改良，例如，扇区1，5，9，13为一组计算一个校验放在扇区17，扇区2，6，10，14为一组计算校验放在扇区18，以此类推。IPC 只能容一个 LSE。
• SPC + MDS：1.1.3小节发现磁盘的某些区域是 LSE 的多发区域，可以在这些区域用 MDS，在剩余区域用 IPC。
• Column diagonal parity (CDP)：CDP希望比 IPC 容更多错，但计算开销比 MDS 小。CDP 为 k=(p-1)^2 个扇区（可以看成 (p-1)*(p-1) 的矩阵）计算 m=2*(p-1) 个校验，其中 p 是质数。矩阵的每一行计算一个校验，每个斜对角线再计算一个校验。CDP 可以容任意2个错。CDP 的存储效率不如其它编码灵活，完全由 p 决定。

作者首先评测了最简单的 SPC，从1+1到128+1（即调整参数 k，例如128个数据扇区计算1个校验）。考虑到存储开销，实际中使用的 k 一般大于8。当一个 parity group 出现2个或以上 LSE 时，就会丢失扇区。

上图显示了使用不同 SPC，出现不可修复错误的磁盘的比例。在实用的 k 值范围内，大约1/4的磁盘出现了不可修复的错误，即一个 parity group 出现2个以上 LSE。即便是1+1，牺牲了50%的存储效率，也有15%的磁盘遇到不可修正的错误。

上图显示了不同 SPC，由于 LSE 丢失的扇区数。平均每块磁盘丢失5个扇区。LSE 是否能被 SPC 修复，与发生的时间间隔有关。如果一个 parity group 发生了很多LSE，但是时间间隔很长，那么2周一次的 scrubbing 机制就会发现这些 LSE 并纠正。

上图显示了 8+1 SPC，出现多个 LSE 的 parity group，第一个和第二个 LSE 的时间间隔的分布。大约90%的情况，时间间隔小于2周（竖线所示，2.4*10^6秒）。验证了 LSE 的时间局部性。

上图显示了出错 parity group 的 LSE 的数量分布。如果一般 LSE 的数量很多，那么使用更强的 erasure code 也没有办法改进可靠性；反之，使用一个稍强的 erasure code 就可以显著提高可靠性。由图可见。50%以上的情况下，LSE 只有2个，也就是纠2错的 erasure code 可以解决一半的问题。

上图比较了在不同存储效率（通过改变 CDP 的p 值，而其它编码的 m 和 k 值可以通过 p 计算，k=(p-1)^2，m=2*(p-1) ）下，四种编码的可靠性。可以看到 MDS 总是最好的，CDP 次之（为什么 CDP 比 MDS 差一些呢？），SPC+MDS 最差。

上图比较了在相同存储效率（87%，平均8个数据扇区计算一个校验）下，不同策略的可靠性（这里没有 CDP，因为 CDP 的存储效率没有那么灵活）。X 轴是校验块的数量，从1到23。当 m=1时，IPC 和 MDS 就退化为 SPC。不出意外，MDS 总是可靠性最好的，但是计算、IO开销也最大（更新一个扇区，需要更新所有 m 个校验）。 SPC+MDS 比 SPC 减少了25%的不可修正错误，但比不上其它策略。 IPC 在中间，弱于 MDS，但是开销也更低（更新一个扇区，只需更新一个校验）。

1.2.2 scrubbing

scrubbing 是一种主动探测 LSE 的机制。很多磁盘厂商都使用了这种技术。srubber会定期地从头到尾扫描整块磁盘寻找 LSE并纠错。scrubbing 的速率一般不高，避免影响应用。如果 scrubbing 的周期是 s，磁盘的容量是 c，那么 scrubbing 的速率是 c/s。除了这种标准 srubbing，作者检查了四种 srubbing 机制检测 LSE 的效率（Mean Time to Error Detection）。

• Localized scrubbing：由于 LSE 的局部性，可以在发现一个 LSE 后，立刻用更快的速率 a 检查其附近r 个扇区。
• Accelerated scrubbing：当发现一个 LSE，加速检查剩余整块磁盘。
• Staggered scrubbing：磁盘被分成 r 个区域，每个区域又分为大小为 s 的块。首先依次扫描每个区域的第一个块，然后依次扫描第二个块。如果发现了一个 LSE，就立刻扫描该区域。
• Accelerated staggered scrubbing：同样将磁盘分区和块。当发现一个 LSE 后，立刻加速扫描该区域。

实验的困难在于我们并不知道 LSE 发生的精确时间，而只知道被检测到的时间。除了将检测时间当作 LSE 的发生时间外，作者提出了三种估计方法：1. 被同一次 scrubbing 发现，并且距离小于50MB 的 LSE，认为是同时发生的，因此以早检测到的 LSE 为准；2. 假定所有在同一次 scrubbing 内检测到的 LSE 都是同时发生的，以早检测到的 LSE 为准；3. 随机时间。

上图是结果，以 LSE 检测到的时间作为 LSE 发生的时间。X 轴是 scrubbing 的周期，1-2周是常用设置。Local 和 Accelerated 的表现让人失望，因为它们只是加速了发现第二个 LSE 的速率，而由于 LSE 的局部性，标准方法也可以很快发现。Staggered 方法的表现更好，因为它加速了发现第一个 LSE 的速率。在常用的 scrubbing 周期，Staggered 可以减少10-20%的MTTED。

如果采用上述三个方法估计 LSE 的发生时间，作者发现四种 scrubbing 优化机制的优势会不变或者更大。比如采用方法1，Staggered 进一步提升了50%，而其它方法不变。如果是方法3，则这些优化机制的就没有用了。

1.3 结论

• Pareto 分布更适合为 LSE 建模；
• LSE 表现出了时间和空间局部性，因此对于一块磁盘，LSE 可能是由同一个事件导致的；
• SPC 没有完全解决问题，50%的磁盘仍然会遇到不可修正的错误；
• 在磁盘的某些区域使用更强的 MDS，可以进一步减少30%的出错磁盘；
• IPC 和 MDS 表现更好；
• Staggered scrubbing 可以减少 40% 的MTTED。