Skip to content

可信存储器

1. 可信性基础

1.1. 关注点

  • 存储器层次结构不仅要追求高性能，可信性 (Dependability) 也至关重要。如果系统不可靠，速度再快也没有意义。
  • 提高可信性的核心方法是冗余技术 (Redundancy)。

1.2. 失效相关的术语定义

  • 服务需求 (Service Requirement)：用户对系统提供的功能或性能的期望。
  • 服务状态：
    1. 服务实现 (Service Accomplishment)：交付的服务与需求相符。
    2. 服务中断 (Service Interruption)：交付的服务与需求不符。
  • 失效 (Failure)：导致系统从“服务实现”状态转换到“服务中断”状态的事件。
  • 恢复 (Restoration)：系统从“服务中断”状态转换回“服务实现”状态的过程。
  • 失效类型：
    • 永久性失效 (Permanent Failure)：一旦发生，除非修复，否则一直存在。诊断相对容易。
    • 间歇性失效 (Intermittent Failure)：时好时坏，随机出现。诊断非常困难。

1.3. 可信性度量

  1. 可靠性 (Reliability)：
    • 定义：系统或模块能够持续提供用户需求服务的度量，即从开始使用到失效的时间间隔。
    • 度量指标：平均无故障时间 (Mean Time To Failure, MTTF)。
  2. 年失效率 (Annual Failure Rate, AFR)：
    • 定义：在给定 MTTF 情况下，一年内预期的器件失效比例。
    • 计算：AFR = (小时数/年) / MTTF (小时)
    • 示例 (磁盘的 MTTF 和 AFR)：
      • MTTF = 1,000,000 小时 (约114年)。
      • 一年小时数 = 365 × 24 = 8,760 小时。
      • AFR = 8,760 / 1,000,000 = 0.876%。
      • 对于有100,000块磁盘的系统，每年失效磁盘数 = 100,000 × 0.876% = 876 块 (平均每天超过2块)。
      • 结论：MTTF 可能给人误导，AFR 更直观。
  3. 维修平均时间 (Mean Time To Repair, MTTR)：
    • 定义：服务中断后，进行维修所需的平均时间。
  4. 失效间隔平均时间 (Mean Time Between Failures, MTBF)：
    • 定义：两次连续失效之间的平均时间。
    • 计算：MTBF = MTTF + MTTR。
    • 注意：MTTF 通常比 MTBF 更能准确反映系统本身的可靠性。
  5. 可用性 (Availability)：
    • 定义：系统正常工作时间在连续两次服务中断间隔时间中所占的比例。
    • 计算：可用性 = MTTF / (MTTF + MTTR) = MTTF / MTBF。
    • 提高可用性的途径：增加 MTTF 或减少 MTTR (例如通过故障检测、诊断和修复工具)。

1.4. 提高 MTTF 的方法

  • 故障 (Fault)：指一个器件的失效，可能导致也可能不导致整个系统的失效。
  • 提高系统 MTTF 的三种方式：
    1. 故障避免技术 (Fault Avoidance)：通过高质量构建和设计来从根本上避免故障的出现。
    2. 故障容忍技术 (Fault Tolerance)：采用冗余措施，当发生故障时，通过冗余部分保证系统仍然能正常工作。
    3. 故障预报技术 (Fault Forecasting)：对故障进行预测，从而允许在器件真正失效前进行替换。

2. 汉明编码 (Hamming Code)

一种广泛应用于存储器的冗余技术，由理查德·汉明发明。

2.1. 基本概念

  • 汉明距离 (Hamming Distance)：两个等长二进制数对应位置上不同比特的数量。
    • 例如：011011 和 001111 的汉明距离是 2 (第2位和第4位不同)。
  • 最小距离与检错能力：
    • 如果一种编码中，任意两个合法码字之间的最小汉明距离为 d，则该编码：
      • 可以检测出多达 d-1 位的错误。
      • 可以纠正多达 ⌊(d-1)/2⌋ 位的错误。
  • 1位错误检测编码：如果码字间的最小距离为2，发生1位错误会将一个有效码字变为无效码字，从而可以检测出1位错误。

2.2. 奇偶校验码 (Parity Check Code)

  • 原理: 计算码字中 '1' 的个数是奇数还是偶数。
  • 写入: 写入数据时，同时写入一个奇偶校验位，使得整个 (数据位 + 校验位) 码字中 '1' 的个数符合预设的奇偶性（如始终为偶数，称为偶校验）。
  • 读取与检测: 读出数据和校验位，重新计算奇偶性。如果计算出的奇偶性与存储的不符，则发生错误。
  • 示例 (偶校验)：
    • 数据：00011111 (5个'1'，奇数)。
    • 为使其变为偶数个'1'，奇偶校验位设为 1。
    • 存储码字：000111111 (6个'1'，偶数)。
    • 如果最高位翻转：100111111 (7个'1'，奇数)。检测到错误。
    • 如果最高两位同时翻转：110111111 (8个'1'，偶数)。无法检测到错误。
  • 能力:
    • 可以检测出任意奇数个位的错误。
    • 主要用于检测1位错误 (因为多位同时出错的概率远低于1位出错)。
    • 不能纠正错误，只能检测。

2.3. 汉明纠错码 (Hamming Error Correction Code, ECC) - SEC (Single Error Correction)

汉明设计了一种将数据映射到最小汉明距离为3的码字的方法，可以纠正1位错误。 * 计算步骤 (针对数据位进行编号)： 1. 位编号: 对整个码字（包含数据位和校验位）从左到右由1开始编号。 2. 校验位位置: 所有编号为2的整数次幂的位 (1, 2, 4, 8, 16, ...) 被指定为奇偶校验位 (Parity bits: p1, p2, p4, p8, ...)。 3. 数据位位置: 剩余位置用作数据位 (Data bits: d1, d2, d3, ...)。 4. 校验位覆盖范围 (图 5-24)：每个校验位负责检查一组特定的数据位和自身，其规则基于位编号的二进制表示： * p1 (位置0001₂): 检查所有最右边二进制位为1的位置 (1, 3, 5, 7, 9, 11, ...)。 * p2 (位置0010₂): 检查所有右边起第二位二进制位为1的位置 (2, 3, 6, 7, 10, 11, ...)。 * p4 (位置0100₂): 检查所有右边起第三位二进制位为1的位置 (4, 5, 6, 7, 12, 13, 14, 15, ...)。 * p8 (位置1000₂): 检查所有右边起第四位二进制位为1的位置 (8, 9, 10, 11, 12, 13, 14, 15, ...)。 * 关键: 每个数据位至少被两个奇偶校验位覆盖。 5. 设置校验位: 设置每个校验位的值，使其所覆盖的组内 '1' 的个数为偶数 (偶校验)。 * 错误检测与纠正: 1. 读取码字后，重新计算每个校验位的奇偶性，得到一组新的校验位值 (称为校验子 (Syndrome)，例如 S8, S4, S2, S1)。 2. 如果校验子全为0 (例如 S8S4S2S1 = 0000₂)，则没有检测到错误。 3. 如果校验子不为0，则校验子形成的二进制数直接指出了发生错误的位的位置。 * 例如，若 S8S4S2S1 = 1010₂ (十进制10)，则表示第10位出错了。 4. 由于是二进制数据，纠错只需将出错位取反即可。 * 示例 (8位数据 10011010₂): * 加上4个校验位，共12位码字。 * 按规则计算出校验位p1,p2,p4,p8，得到码字 011100101010。 * 假设第10位 (d6) 翻转为1，码字变为 011100101110。 * 重新计算校验子： * p1组: 偶数 -> S1=0 * p2组: 奇数 -> S2=1 (原p2=1, 期望偶校验，实际是奇数，说明p2覆盖的位有错) * p4组: 偶数 -> S4=0 * p8组: 奇数 -> S8=1 (原p8=0, 期望偶校验，实际是奇数，说明p8覆盖的位有错) * 校验子 S8S4S2S1 = 1010₂ (十进制10)。第10位出错，将其翻转回0即可纠正。

2.4. 纠正一位错、检测两位错的汉明编码 (SEC/DED - Single Error Correction / Double Error Detection)

  • 原理: 在 SEC 码的基础上，增加一个额外的奇偶校验位，该校验位对整个码字 (所有数据位和原有的SEC校验位) 进行奇偶校验（例如，偶校验）。
  • 最小汉明距离: 这种编码的最小汉明距离增加到4。
  • 算法:
    1. 计算出原始的汉明 SEC 码 (得到校验位组 H = Pn...P1)。
    2. 计算整个码字 (包含数据和H) 的总奇偶校验位 P_total。
    3. 当读取数据时，重新计算 H' 和 P_total'。
  • 四种情况判断:
    1. H' 为偶 (全0) 且 P_total' 为偶: 没有错误发生。
    2. H' 为奇 (非0) 且 P_total' 为奇: 发生1位可纠正错误。(1位错会改变H，也会改变总奇偶性)
    3. H' 为偶 (全0) 且 P_total' 为奇: 仅总奇偶校验位 P_total 自身出错，将其取反即可。(如果只有P_total出错，H不变)
    4. H' 为奇 (非0) 且 P_total' 为偶: 发生2位错误，不可纠正，但可检测。(2位错会改变H，但总奇偶性不变)
  • 应用: SEC/DED 广泛应用于服务器内存。例如，8字节 (64位) 的数据块使用 SEC/DED 只需要额外1字节 (8位) 的开销 (7位用于SEC，1位用于DED的总校验)。这就是为什么许多内存条 (DIMM) 是72位宽 (64位数据 + 8位ECC)。

2.5. 计算 ECC 需要的位数

  • p: 校验位的位数
  • d: 数据位的位数
  • 总码字长度: p + d
  • p 个校验位需要能够表示 p + d 种可能的错误位置，外加一种“无错误”状态。
  • 不等式: 2^p ≥ p + d + 1
  • 因此: p ≥ log₂(p + d + 1)
  • 示例：
    • d=8 (8位数据): 2^p ≥ p + 8 + 1 => p=4 (2⁴=16 ≥ 4+8+1=13)
    • d=16: p=5
    • d=32: p=6
    • d=64: p=7

3. 高级错误控制技术

3.1. Chipkill (Intel 称 SDDC - Single Device Data Correction)

  • 背景: 在大型系统中，多位错误和整个内存芯片出错的概率变得显著。
  • 原理: 类似于磁盘阵列中的 RAID 技术。将数据和校验信息分散到多个内存芯片上。
  • 效果: 当某一内存芯片完全失效时，可以通过其他芯片中的内容重建出错芯片的数据。
  • 可靠性对比 (IBM针对3年运行时间的计算)，一个10000处理器、每处理器4GB内存的集群：
    • 仅奇偶校验: ~90,000次不可恢复错误 (每17分钟一次)。
    • 仅SEC/DED: ~3,500次不可恢复/检测错误 (每7.5小时一次)。
    • Chipkill: ~6次不可恢复/检测错误 (每2个月一次)。
  • 结论: 数据仓库级别的计算机需要采用 Chipkill 技术。

3.2. 网络系统中的突发错误与 CRC

  • 问题: 网络传输中可能出现突发型错误 (连续多位错误)。
  • 解决方案: 循环冗余校验 (Cyclic Redundancy Check, CRC)。
    • 发送端: 对一个 K 位的字块，生成一个 r (n-k) 位的帧校验序列 (Frame Check Sequence, FCS)。
    • 发送的 n 位序列 (数据+FCS) 构成的数字可以被一个预定义的生成多项式 (Generator Polynomial，对应一个特定的二进制数) 整除。
    • 接收端: 用相同的生成多项式去除接收到的 n 位帧。
      • 如果余数为0，认为没有错误。
      • 如果余数不为0，认为发生错误，丢弃消息并请求重传。
    • 实现: CRC 的除法运算可以通过移位寄存器方便地实现。

3.3. 里德-所罗门编码 (Reed-Solomon Codes)

  • 用途: 纠正多位传输错误，尤其适用于突发错误。
  • 原理:
    • 使用伽罗瓦域 (Galois Fields) 理论。
    • 数据被看作是多项式的系数。
    • 校验码被看作是多项式在某些点上的值。
  • 复杂度: 比 CRC 的二进制除法运算复杂得多。
  • 应用: CD、DVD、蓝光光盘、硬盘、数字电视、二维码、数据通信等。