® 存储系统的可靠性 llxx@ustc.edu.cn
存储系统的可靠性 llxx@ustc.edu.cn
内容提要 ·校验码技术，RV$5.5 -海明码：存储器，唐$4.2.6 -CRC码：磁盘，网络，唐$4.4.6 硬盘数据保护技术 ·RAID技术：磁盘阵列，RV$5.11
内容提要 • 校验码技术，RV$5.5 – 海明码：存储器，唐$4.2.6 – CRC码：磁盘，网络，唐$4.4.6 • 硬盘数据保护技术 • RAID技术：磁盘阵列，RV$5.11
Google2009:数据存储设备可靠性 ·DRAM错误率超出人们预想 “可能成为系统宕机和服务中断的罪魁祸首'” DMM中有约8.2%受到了可修正错误的影响 平均一个DIMM每年发生3700次可修正错误 错误类型：软错误、硬错误 ·由电磁干扰或者硬件故障所导致 。 软错误：很少损坏字位，是可修正的； 硬错误：会损坏字位而成为物理缺陷，从而造成数 据错误的反复发生。 硬盘：数据失效率高达6%（厂商：2%）》 一错误类型：位跳变（可由ECC纠错），物理损坏
Google2009：数据存储设备可靠性 • DRAM错误率超出人们预想 – “可能成为系统宕机和服务中断的罪魁祸首” • DIMM中有约8.2%受到了可修正错误的影响 • 平均一个DIMM每年发生3700次可修正错误 – 错误类型：软错误、硬错误 • 由电磁干扰或者硬件故障所导致 • 软错误：很少损坏字位，是可修正的； • 硬错误：会损坏字位而成为物理缺陷，从而造成数 据错误的反复发生。 • 硬盘：数据失效率高达6%（厂商：2%） – 错误类型：位跳变（可由ECC纠错），物理损坏
“风云一号”气象卫星提前退役 宇宙环境中存在大量由电子、质子和α粒子 等高能粒子构成的宇宙射线，当这些穿透力 很强的射线轰击半导体电路时，可能导致 PN结存储的电量发生瞬态变化. 虽然这种瞬态故障一般不会对硬件造成持 久伤害，但是可以通过改变传输信号和存储 单元值等方式影响系统的正常运行，严重时 会造成系统崩溃 硬件瞬态故障对系统可靠性的影响可分为 数据流错误和控制流错误
“风云一号”气象卫星提前退役 • 宇宙环境中存在大量由电子、质子和 α粒子 等高能粒子构成的宇宙射线, 当这些穿透力 很强的射线轰击半导体电路时, 可能导致 PN 结存储的电量发生瞬态变化. • 虽然这种瞬态故障一般不会对硬件造成持 久伤害 ,但是可以通过改变传输信号和存储 单元值等方式影响系统的正常运行, 严重时 会造成系统崩溃 • 硬件瞬态故障对系统可靠性的影响可分为 数据流错误和控制流错误
FAULT-TOLERANT COMPUTING STC Failure(失效故障)：When a component is not living up to its specifications,a failure occurs Error(错误)：The part of a component's state that can lead to a failure Fault(缺陷/故障)：The cause of an error..Types: - Transient(偶发)：occur once,then disappear -Intermittent(间歇：occur,.then vanish,then reappear -Permanent(持久)：continues to exist 指标 -可靠性：MTBF=MTTF+MTTR,AFR -可用性=MTTF/(MTTF+MTTR) 9°s Availability Downtime/Year Examples MTBF 1 90.0% 36 days 12 hours Personal clients 2 99.0% 87 hours 36 minutes Entry-level businesses MTTF MTTD MTTR MTTF 3 99.9% 8 hours 46 minutes ISPs,mainstream businesses Correct behavior Diagnose Repair Correct behavior Time 4 99.99% 52 minutes 33 seconds Data centers 5 99.999% 5 minutes 15 seconds Carrier-grade Telco,medical, First Begin End Second banking Failure Repair Repair Failure 99.9999% 31.5 seconds Military defense system
FAULT-TOLERANT COMPUTING • Failure(失效/故障): When a component is not living up to its specifications, a failure occurs • Error(错误): The part of a component's state that can lead to a failure • Fault(缺陷/故障): The cause of an error. Types: – Transient(偶发): occur once, then disappear – Intermittent(间歇): occur, then vanish, then reappear – Permanent(持久): continues to exist • 指标 – 可靠性：MTBF = MTTF+MTTR，AFR – 可用性=MTTF/(MTTF+MTTR)
Fault Tolerance:Redundancy 提高MTTF:避免，容忍，预测 -故障“难以消除(eliminate),只能掩盖(mask) 。 容错计算系统：出现一定限度的失效时，依然能够提供所 需要的服务. 一服务降级：使之不影响系统的正常使用 冗余 Information redundancy Eg,a Hamming code can be added to transmitted data to recover from noise on the tansmission line. Time redundancy is especially helpful for transient or intermittent faults. ·Eg,using transactions(▣滚，rollback) Physical redundancy Eg,747s have four engines but can fly on three ·RAID 容错能力：检错（发现，定位），纠错
Fault Tolerance：Redundancy • 提高MTTF：避免，容忍，预测 – 故障“难以消除（eliminate），只能掩盖（mask）” • 容错计算系统：出现一定限度的失效时，依然能够提供所 需要的服务. – 服务降级：使之不影响系统的正常使用 • 冗余 – Information redundancy • Eg, a Hamming code can be added to transmitted data to recover from noise on the tansmission line. – Time redundancy • is especially helpful for transient or intermittent faults. • Eg, using transactions(回滚，rollback) – Physical redundancy • Eg, 747s have four engines but can fly on three • RAID • 容错能力：检错（发现，定位），纠错
Error Checking and Correcting Two major types of data errors can occur in data transmission: -hard errors,which are permanent,arise from broken interconnects,internal shorts,or open leads - soft errors,which are transient,are caused by system noise,power surges,and alpha particles. The processor (MIPS R4000)verifies data correctness by using either the parity or the SECDED code as it passes data from the System interface to the secondary cache,or it moves data from the secondary cache to the primary caches or to the System interface
Error Checking and Correcting • Two major types of data errors can occur in data transmission: – hard errors, which are permanent, arise from broken interconnects, internal shorts, or open leads – soft errors, which are transient, are caused by system noise, power surges, and alpha particles. • The processor（MIPS R4000）verifies data correctness by using either the parity or the SECDED code as it passes data from the System interface to the secondary cache, or it moves data from the secondary cache to the primary caches or to the System interface
奇偶编码校验 (Parity Check Code) ·编码规则 在被传送的n位代码(bn.bn2bbo）上（最后）增加一位校 验位P(Parity),将原数据与奇（偶）校验位（生成 算法)一起进行存取或传送（即传送Pbn.bn-2bb）)。 奇校验：使“1”的个数为奇数 ·00000000->000000001 ·00000001->000000010 一 偶校验：使“1”的个数为偶数 ·00000000->000000000 ·00000001->000000011 ·为什么能容错？具有什么容错能力？
奇偶编码校验（Parity Check Code） • 编码规则 – 在被传送的n位代码(bn-1bn-2 ...b1b0 )上（最后）增加一位校 验位P（Parity），将原数据与奇（偶）校验位（生成 算法）一起进行存取或传送(即传送Pbn-1bn-2 ...b1b0 ) 。 – 奇校验：使“1”的个数为奇数 • 0000 0000－>0000 0000 1 • 0000 0001－>0000 0001 0 – 偶校验：使“1”的个数为偶数 • 0000 0000－>0000 0000 0 • 0000 0001－>0000 0001 1 • 为什么能容错？具有什么容错能力？
0000 0000 0001 0001 0010 0010 合法编码 0011 0011 0100 0100 0101 0101k 非法编码 4位表示 0110 4位表示 0110 16个状态 0111 8个状态 0111 《通信原理》 不能检出错误！ 1000 可能检出错误！ 1000 码距：海明(Hamming)距离 1001 1001 两个等长码字之间对应位 1010 1010 不同的个数 1011 1011 相邻两个合法码字之间的不相 1100 1100 同位数 1101 1101 1110 1110 奇偶，格雷，海明，Reed Solomon? 1111 1111
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 4位表示 16个状态 不能检出错误！ 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 4位表示 8个状态 可能检出错误！ 合法编码 非法编码 《通信原理》 码距：海明（Hamming）距离 两个等长码字之间对应位 不同的个数 相邻两个合法码字之间的不相 同位数 奇偶，格雷，海明，ReedSolomon？
编码纠错理论 USTC 任何一种编码是否具有检测能力或纠错能力，都与 编码的最小距离有关。 根据纠错律论：L-1=D+C且D>=C 即编码最小距离L越大，则其检测错误的位数D也越大， 纠正错误位数C也越大，且纠错能力恒小于或等于检测 能力。 ·例如，L=3,则D=2,C=0;或D=1,C=1。 一增大L,提高检错和纠错能力。 应用 一内存：奇偶，ECC(错误检查和纠正)，SECDED 硬盘：CRC -通信：奇偶（串行，物理层），海明，CRC(网络层)
编码纠错理论 • 任何一种编码是否具有检测能力或纠错能力，都与 编码的最小距离有关。 • 根据纠错律论：L-1＝D+C 且 D>=C – 即编码最小距离L越大，则其检测错误的位数D也越大， 纠正错误位数C也越大，且纠错能力恒小于或等于检测 能力。 • 例如，L＝3，则D＝2，C＝0；或D=1，C=1。 – 增大L，提高检错和纠错能力。 • 应用 – 内存：奇偶，ECC（错误检查和纠正），SECDED – 硬盘：CRC – 通信：奇偶（串行，物理层），海明，CRC（网络层）