Dependability: Parity, ECC, RAID

Instructor: Morgan Rae Reschenberg

Systems & Fault Tolerance

• So far in this course:
• How software works
• How hardware works
• How computers combine software/hardware
• Now:
• What happens when the real world gets involved!
• Things break in mysterious ways
• We can “count on” things breaking!

How can we ensure the systems we’ve developed function reliably (or predictably) in the face of failure?

2

Measurements of Fault Tolerance, Mitigations

• Dependability
• Avoiding failure! Build “strong” systems :)
• Redundancy
• Replication!
• Make copies of your important state/info so that if it breaks, you can use a replica
• Error Correcting
• If we do incur some damage, how can we:
• Find the problem? (Error detection)
• Fix the problem? (Error correction)

3

Agenda

• Dependability
• Administrivia
• Error Correcting Codes (ECC)
• RAID

​

CS61C Su18 - Lecture 24

4

8/1/2018

What is Dependability?

• A component, or system, is considered highly dependable if it is highly available, or has a low probability of service outages.
• Unlikely to encounter failures
• Recovers quickly when failures occur

​

• The dependability of a system is determined by the overall dependability of its components

​

5

Dependability

• Fault: failure of a component
• May or may not lead to system failure
• Applies to any part of the system
• Repair: the act of restoring normal service after a fault

CS61C Su18 - Lecture 24

6

8/1/2018

Dependability Measures

• Reliability: Mean Time To Failure (MTTF)
• Service interruption: Mean Time To Repair (MTTR)
• Mean Time Between Failures (MTBF)
• MTBF = MTTR + MTTF

CS61C Su18 - Lecture 24

7

8/1/2018

• Availability = MTTF = MTTF� MTTF + MTTR MTBF
• Improving Availability
• Increase MTTF: more reliable HW/SW + fault tolerance
• Reduce MTTR: improved tools and processes for diagnosis and repair

​

Reliability Measures

1. MTTF, MTBF measured in hours/failure
• e.g. “average HDD MTTF is 100,000 hr/failure”
2. Annualized Failure Rate (AFR)
• Average rate of failures per year (%)

​

CS61C Su18 - Lecture 24

8

8/1/2018

Availability Measures

• Availability = MTTF / (MTTF + MTTR) usually written as a percentage (%)
• Want high availability, so categorize by “number of 9s of availability per year”
• 1 nine: 90% => 36 days of repair/year
• 2 nines: 99% => 3.6 days of repair/year
• 3 nines: 99.9% => 526 min of repair/year
• 4 nines: 99.99% => 53 min of repair/year
• 5 nines: 99.999% => 5 min of repair/year

​

CS61C Su18 - Lecture 24

9

8/1/2018

Dependability Example

• 1000 disks with MTTF = 100,000 hr and �MTTR = 100 hr

CS61C Su18 - Lecture 24

10

8/1/2018

• MTBF= MTTR + MTTF = 100,100 hr

300,300 hours

100,000 hr

100,000 hr

100,000 hr

100,100 hours

FAILURE

FAILURE

Dependability Example

• 1000 disks with MTTF = 100,000 hr and �MTTR = 100 hr

CS61C Su18 - Lecture 24

11

8/1/2018

• MTBF

= MTTR + MTTF = 100,100 hr

​

• Availability

= MTTF/MTBF = 0.9990 = 99.9%

​

​

300,300 hours

100,000 hr

100,000 hr

100,000 hr

100,100 hours

FAILURE

FAILURE

Calculating MTTR Example

• Faster repair to get 4 nines of availability?
• GOAL: Closer to x/x == 1, smaller MTTR!

CS61C Su18 - Lecture 24

12

8/1/2018

• 0.9999 = MTTF / (MTTF + MTTR)
• 0.9999 x (MTTF + MTTR) = MTTF
• 0.9999 x MTTF + 0.9999 x MTTR = MTTF
• 0.9999 × MTTR = 0.0001 × MTTF
• Plug in MTTF = 100,000 hr
• MTTR = 10.001 hr

Dependability Design Principle

• No single points of failure
• “Chain is only as strong as its weakest link”

​

• Dependability Corollary of Amdahl’s Law
• Doesn’t matter how dependable you make one portion of system because dependability is limited by the part you do not improve

​

​

CS61C Su18 - Lecture 24

13

8/1/2018

14

Question: There’s a hardware glitch in our system that makes the Mean Time To Failure (MTTF) decrease. Are the following statements TRUE or FALSE?

1. Our system’s Availability will increase.
2. Our system’s Annualized Failure Rate (AFR) will increase.

15

Question: There’s a hardware glitch in our system that makes the Mean Time To Failure (MTTF) decrease. Are the following statements TRUE or FALSE?

1. Our system’s Availability will increase.
2. Our system’s Annualized Failure Rate (AFR) will increase.

16

Question: There’s a hardware glitch in our system that makes the Mean Time To Failure (MTTF) decrease. Are the following statements TRUE or FALSE?

• Our system’s Availability will increase.
• Our system’s Annualized Failure Rate (AFR) will increase.

Availability = MTTF / (MTTF + MTTR)

​

As MTTF shrinks, our fraction is outweighed by MTTR:

​

100/(100 + 50) → 66%

50/(50 + 50) → 50%

10/(10 + 50) → 16%

​

Availability decreases (less 9’s, lower percentage)

17

Question: There’s a hardware glitch in our system that makes the Mean Time To Failure (MTTF) decrease. Are the following statements TRUE or FALSE?

• Our system’s Availability will increase.
• Our system’s Annualized Failure Rate (AFR) will increase.

MTTF = “Mean time to Failure” = average time until something goes wrong!

​

If this number /decreases/, this means failures happen more often!

100 years until failure, 50 years until failure, 10 years until failure, etc.

​

Failures happening more often == an increased rate of failures per year

​

As MTTF decreases, AFR increases

Administrivia

• Proj4 due on August 9th ! (Friday!!)
• Guerilla Session today @Cory 540AB, 7p
• Regrade requests are open for MT2 until Friday
• Please submit ASAP, no late regrades accepted!
• Staff review sessions next week:
• M 5-8p, T 5-8p
• Topic-based; attend the ones you need to!

CS61C Su18 - Lecture 22

18

7/30/2018

What’s next?

19

Agenda

• Dependability
• Administrivia
• Error Correcting Codes (ECC)
• RAID

CS61C Su18 - Lecture 24

20

8/1/2018

Great Idea: Dependability �via Redundancy

• Redundancy so that a failing piece doesn’t make the whole system fail

​

CS61C Su18 - Lecture 24

21

8/1/2018

1+1=2

1+1=2

1+1=1

Great Idea: Dependability �via Redundancy

• Applies to everything from datacenters to memory
• Redundant datacenters so that can lose 1 datacenter but Internet service stays online
• Redundant routes so can lose nodes but Internet doesn’t fail
• Redundant disks so that can lose 1 disk but not lose data (Redundant Arrays of Independent Disks/RAID)
• Redundant memory bits of so that can lose 1 bit but no data (Error Correcting Code/ECC Memory)

​

​

CS61C Su18 - Lecture 24

22

8/1/2018

Error Detection/Correction Codes

• Memory systems generate errors (accidentally flipped-bits)
• DRAMs store very little charge per bit
• “Soft” errors occur occasionally when cells are struck by alpha particles or other environmental upsets
• “Hard” errors occur when chips permanently fail
• Problem gets worse as memory systems get denser and larger

CS61C Su18 - Lecture 24

23

8/1/2018

Error Detection/Correction Codes

• Protect against errors with EDC/ECC
• Extra bits are added to each M-bit data chunk to produce an N-bit “code word” (N>M)
• Extra bits are a function of the data
• Each data word value is mapped to a valid code word
• Certain errors change valid code words to invalid ones (i.e. you can tell something is wrong)

CS61C Su18 - Lecture 24

24

8/1/2018

Detecting/Correcting Code Concept

• Detection: fails code word validity check
• Correction: can map to nearest valid code word

CS61C Su18 - Lecture 24

25

8/1/2018

Space of all possible bit patterns:

2^N patterns, but only 2^M are valid code words (N>M)

Hamming Distance

• Hamming distance = # of bit changes to get from one code word to another

​

CS61C Su18 - Lecture 24

26

8/1/2018

• p = 011011, �q = 001111, Hdist(p,q) = 2
• p = 011011, �q = 110001, Hdist(p,q) = ?
• If all code words are valid, then�min Hdist between valid code words is 1
• Change one bit, at another valid code word

​

3

Why does this matter?

• If the entire “space” of possible codewords is valid, we can’t tell if our word has errors (maybe it morphed into another valid word!)
• If some words are valid, and others are invalid, we can detect errors
• If there are a small subset of valid words and a large subset of invalid words, we can trace/track our errors and revert them!
• Wait really????

27

3-Bit Visualization Aid

• Want to be able to see Hamming distances
• Show code words as nodes, Hdist of 1 as edges
• For 3 bits, show each bit in a different dimension:

CS61C Su18 - Lecture 24

28

8/1/2018

Minimum Hamming Distance 2

CS61C Su18 - Lecture 24

29

8/1/2018

• If 1-bit error, is code word still valid?
• No! So can detect
• If 1-bit error, know which code word we came from?
• No! Equidistant, so cannot correct

Half the available�code words�are valid

Minimum Hamming Distance 3

CS61C Su18 - Lecture 24

30

8/1/2018

• How many bit errors can we detect?
• Two! Takes 3 errors to reach another valid code word
• If 1-bit error, know which code word we came from?
• Yes!

Only a quarter of �the available code�words are valid

Parity Bit

• Describes whether a group of bits contains an even or odd number of 1’s
• Define 1 = odd and 0 = even
• Can use XOR to compute parity bit!
• Adding the parity bit to a group will always result in an even number of 1’s (“even parity”)
• 0b100 Parity: 1, 0b101 Parity: 0
• If we know number of 1’s must be even, can we figure out what a single missing bit should be?
• 10?11 → missing bit is 1

CS61C Su18 - Lecture 24

31

8/1/2018

Parity: Simple Error Detection Coding

• Add parity bit when writing block of data:

• Check parity on block read:
• Error if odd number of 1s
• Valid otherwise

CS61C Su18 - Lecture 24

32

8/1/2018

• Minimum Hamming distance of parity code is 2
• Parity of code word = 1 indicates an error occurred:
• 2-bit errors not detected (nor any even # of errors)
• Detects an odd # of errors

Parity Examples

1. Data 0101 0101
• 4 ones, even parity now
• Write to memory�0101 0101 0 �to keep parity even
2. Data 0101 0111
• 5 ones, odd parity now
• Write to memory:�0101 0111 1�to make parity even

​

3. Read from memory�0101 0101 0
• 4 ones → even parity, so no error
4. Read from memory�1101 0101 0
• 5 ones → odd parity, �so error
1. What if error in parity bit?
• Can detect!

​

CS61C Su18 - Lecture 24

33

8/1/2018

How to Correct 1-bit Error?

• Recall: Minimum distance for correction?
• Three
• Richard Hamming came up with a mapping to allow Error Correction at min distance of 3
• Called Hamming ECC for Error Correction Code

CS61C Su18 - Lecture 24

34

8/1/2018

Hamming ECC (1/2)

• Use extra parity bits to allow the position identification of a single error
• Interleave parity bits within bits of data to form code word
• Note: Number bits starting at 1 from the left
• Use all bit positions in the code word that are powers of 2 for parity bits (1, 2, 4, 8, 16, …)
• All other bit positions are for the data bits�(3, 5, 6, 7, 9, 10, …)

CS61C Su18 - Lecture 24

35

8/1/2018

Hamming ECC

36

D1

D2

D3

D4

D5

D6

P1

P2

D1

P4

D2

D3

D4

D5

D6

P8

Hamming ECC (2/2)

3. Set each parity bit to create even parity for a group of the bits in the code word
• The position of each parity bit determines the group of bits that it checks
• Parity bit p checks every bit whose position number in binary has a 1 in the bit position corresponding to p
• Bit 1 (0001₂) checks bits 1,3,5,7, … (XXX1₂)
• Bit 2 (0010₂) checks bits 2,3,6,7, … (XX1X₂)
• Bit 4 (0100₂) checks bits 4-7, 12-15, … (X1XX₂)
• Bit 8 (1000₂) checks bits 8-15, 24-31, … (1XXX₂)

​

CS61C Su18 - Lecture 24

37

8/1/2018

Hamming ECC

38

P1

P2

D1

P4

D2

D3

D4

D5

D6

D1

D2

D3

D4

D5

D6

P8

XOR

Hamming ECC

39

P1

P2

D1

P4

D2

D3

D4

D5

D6

D1

D2

D3

D4

D5

D6

P8

XOR

Hamming ECC Example

• A byte of data: 10011010
• Create the code word, leaving spaces for the parity bits:

_₁ _₂ 1₃ _₄ 0₅ 0₆ 1₇ _₈ 1₉ 0₁₀ 1₁₁ 0₁₂

​

​

CS61C Su18 - Lecture 24

40

8/1/2018

Hamming ECC Example

• Calculate the parity bits:
• Parity bit 1 group (1, 3, 5, 7, 9, 11): � ? _ 1 _ 0 0 1 _ 1 0 1 0 →
• Parity bit 2 group (2, 3, 6, 7, 10, 11):� 0 ? 1 _ 0 0 1 _ 1 0 1 0 →
• Parity bit 4 group (4, 5, 6, 7, 12):� 0 1 1 ? 0 0 1 _ 1 0 1 0 →
• Parity bit 8 group (8, 9, 10, 11, 12):� 0 1 1 1 0 0 1 ? 1 0 1 0 →

​

CS61C Su18 - Lecture 24

41

8/1/2018

0

1

0

1

?

?

?

?

?

?

Hamming ECC Example

• Valid code word: 011100101010
• Original data: 011100101010

Suppose we read 0₁1₂1₃1₄0₅0₆1₇0₈1₉1₁₀1₁₁0₁₂ instead – fix the error!

But how would we figure out where the error is if we just see the code word? Hmm….

• Let’s examine the parity bits that are dependent on bit 10
• Maybe we can figure out a pattern?

​

CS61C Su18 - Lecture 24

42

8/1/2018

Hamming ECC Example

• Calculate the parity bits for 0₁1₂1₃1₄0₅0₆1₇0₈1₉1₁₀1₁₁0₁₂
• Parity bit 1 group (1, 3, 5, 7, 9, 11): � 0 + 1 + 0 + 1 + 1 + 1 = 4 (EVEN)
• Parity bit 2 group (2, 3, 6, 7, 10, 11):�1 + 1 + 0 + 1 + 1 + 1 = 5 (ODD)
• Parity bit 4 group (4, 5, 6, 7, 12):� 1 + 0 + 0 + 1 + 0 = 2 (EVEN)
• Parity bit 8 group (8, 9, 10, 11, 12):�0 + 1 + 1 + 1 + 0 = 3 (ODD)�

CS61C Su18 - Lecture 24

43

8/1/2018

Graphic of Hamming Code

44

0 1 1 1 0 0 1 0 1 1 1 0

• Looks like p2 and p8 were responsible
• p2 & p8 will be the only incorrect parity bits IFF bit 10 is incorrect
• Notice that 2 + 8 = 10
• Seems like incorrect parity bits tell us where the error is… o:

Hamming ECC Example

• Valid code word: 011100101010
• Recover original data: 011100101010

Suppose we see 0₁1₂1₃1₄0₅0₆1₇0₈1₉1₁₀1₁₁0₁₂ instead – fix the error!

How to figure out where the error is? Hmm….

• Check the parity bits responsible for bit 10
• Parity bits 2 and 8 are incorrect
• As 2+8=10, bit position 10 is the bad bit, so flip it!
• Corrected value: 011100101010

​

CS61C Su18 - Lecture 24

45

8/1/2018

Hold on…

46

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

OMFG

The parity bits form a number—the bit position in the code word!

• This tells you which bit of the code word is incorrect!

Replace all the X’s with 1’s

Everywhere else, put a 0

…

Hamming ECC Example

Going in reverse:

We see 0₁1₂1₃1₄0₅0₆1₇0₈1₉1₁₀1₁₁0₁₂

Figure out which bit is wrong:

p₁: 0₁1₃0₅1₇1₉1₁₁ = even number of 1’s : 0

p₂: 1₂1₃0₆1₇1₁₀1₁₁ = odd number of 1’s : 1

p₄: 1₄0₅0₆1₇0₁₂ = even number of 1’s: 0

p₈: 0₈1₉1₁₀1₁₁0₁₂ = odd number of 1’s : 1

Incorrect code bit:

0b p₈p₄p₂p₁ = 0b 1010 = 10! So flip bit 10

CS61C Su18 - Lecture 24

47

8/1/2018

RAID: Redundant Array of �Inexpensive/Independent Disks

• Files are “shared” across multiple disks
• Concurrent disk accesses improve throughput
• Redundancy yields high data availability
• Service still provided to user, even if some components (disks) fail
• Contents reconstructed from data redundantly stored in the array
• Can detect when data is corrupted
• Can fix data/restore correct version

CS61C Su18 - Lecture 25

48

8/2/2018

RAID 0: Data Striping

• “Stripe” data across all disks
• Generally faster accesses (access disks in parallel)
• No redundancy (really “AID”)
• Bit-striping shown here, can do in larger chunks

CS61C Su18 - Lecture 25

49

8/2/2018

RAID 1: Disk Mirroring

• Each disk is fully duplicated onto its “mirror”
• Very high availability can be achieved
• Bandwidth sacrifice on write:
• Logical write = two physical writes
• Logical read = one physical read
• Most expensive solution: 100% capacity overhead

CS61C Su18 - Lecture 25

50

8/2/2018

RAID 2-4: Data Striping + Parity

CS61C Su18 - Lecture 25

51

8/2/2018

Updating the Parity Data

• Examine small write in RAID 3 (1 byte)
• 1 logical write = 2 physical reads + 2 physical writes
• Same concept applies for later RAIDs, too

CS61C Su18 - Lecture 25

52

8/2/2018

D₀

D₁

D₂

D₃

P

D₀’

new

data

Inspiration for RAID 5

• When writing to a disk, need to update Parity
• Small writes are bottlenecked by Parity Disk: Write to D0, D5 but also also write to P disk twice!

​

CS61C Su18 - Lecture 25

53

8/2/2018

RAID 5: Interleaved Parity

CS61C Su18 - Lecture 25

54

8/2/2018

Independent writes

possible because of

interleaved parity

D0

D1

D2

D3

P

D4

D5

D6

P

D7

D8

D9

P

D10

D11

D12

P

D13

D14

D15

P

D16

D17

D18

D19

D20

D21

D22

D23

P

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Disk Columns

Increasing

Logical

Disk

Addresses

Example: write to D0, D5 uses disks 1, 2, 4, 5

Modern Use of RAID and ECC (1/2)

• RAID 0 has no redundancy
• RAID 1 is too expensive
• RAID 2 is obsolete due to on-disk ECC
• RAID 3 is not commonly used (bad I/O rates)

​

• Typical modern code words in DRAM memory systems:
• 64-bit data blocks (8 B) with 72-bit codes (9 B)
• d = 64 → p = 7, +1 for DED

​

CS61C Su18 - Lecture 25

55

8/2/2018

Modern Use of RAID and ECC (2/2)

• Common failure mode is bursts of bit errors, not just 1 or 2
• Network transmissions, disks, distributed storage
• Contiguous sequence of bits in which first, last, or any number of intermediate bits are in error
• Caused by impulse noise or by fading signal strength; effect is greater at higher data rates
• Other tools: cyclic redundancy check, Reed-Solomon, Fountain Codes, LaGrange

​

CS61C Su18 - Lecture 25

56

8/2/2018

Summary

• Great Idea: Dependability via Redundancy
• Reliability: MTTF & Annual Failure Rate
• Availability: % uptime = MTTF/MTBF
• Memory Errors:
• Hamming distance 2: Parity for Single Error Detect
• Hamming distance 3: Single Error Correction Code + encode bit position of error
• Hamming distance 4: SEC/Double Error Detection
• RAID:
• Many different flavours, all with their pros/cons
• Generally: disks are cheap enough that many of them + some smart organisation yields safe storage

CS61C Su18 - Lecture 24

57

8/1/2018

Hamming ECC “Cost”

• Space overhead in single error correction code
• Form p + d bit code word, where p = # parity bits and d = # data bits
• Want the p parity bits to indicate either “no error” or 1-bit error in one of the p + d places
• Need 2^p ≥ p + d + 1, thus p ≥ log₂(p + d + 1)
• For large d, p approaches log₂(d)

CS61C Su18 - Lecture 24

58

8/1/2018

Hamming Single Error Correction, �Double Error Detection (SEC/DED)

• Adding extra parity bit covering the entire SEC code word provides double error detection as well!

1 2 3 4 5 6 7 8

p₁ p₂ d₃ p₄ d₅ d₆ d₇ p₈

• Let H be the position of the incorrect bit we would find from checking p₁, p₂, and p₄ (0 means no error) and let P be parity of complete code word (p’s & d’s)
• H=0 P=0, no error
• H≠0 P=1, correctable single error (P=1 → odd # errors)
• H≠0 P=0, double error detected (P=0 → even # errors)
• H=0 P=1, an error occurred in p₈ bit, not in rest of word

CS61C Su18 - Lecture 24

59

8/1/2018

60

Question: We saw that when the minimum hamming distance of codewords was 3, we get single error detection and correction. If we had a hamming distance of 4, we’d have

1. single error detection
2. single error correction
3. double error detection
4. double error correction

A) 1, 2�B) 1, 3�C) 1, 2, 3�D) 1, 2, 3 ,4

SEC/DED: Hamming Distance 4

CS61C Su18 - Lecture 24

61

8/1/2018

1-bit error (one 1)

Nearest 0000

1-bit error (one 0)

Nearest 1111

2-bit error �(two 0’s, two 1’s)

halfway between