Basic Building Blocks.ppt

1、CPRE 545: Fault Tolerant SystemsBasic Building BlocksStable Storage: RAID ArchitectureCprE 545 Fault-Tolerant Systems (G. Manimaran, ISU)Stable Storage: RAID ArchitectureIntroductionnTypes of Disk FailuresnTransient FailuresnDisk behaves unpredictably for a short period of timenBad SectornA page bec

2、omes corruptednController FailurenDisk controller failsnDisk FailurenEntire disk becomes unreadableStable Storage: RAID ArchitectureIntroduction (contd.)nTypes of Disk ErrorsnRead Errors:nSoft read error: Page “a” is good but read returns bad for a short durationnPersistent read error: Page “a” is g

3、ood but read returns bad for a long durationnUndetected error: page “a” is bad but read returns goodnWrite Errors:nNull write: Page “a” is unchangednBad write: Page “a” becomes (bad, d)Stable Storage: RAID ArchitectureMaking a single disk system stablenAn ordinary single disk system can be made stab

4、le by introducing the following operations:nCareful Read: A read is performed repeatedly until it returns the status good or the page cannot be read after a certain number of timesnCareful Write: Performs a write followed by a read until read returns the status good. This eliminates null write and b

5、ad write errorsnThese operations cannot take care of the decay events (bad sector, etc.)Stable Storage: RAID ArchitectureMaking a single disk system stablenThe decay events can be taking a pair of pages and replicating data in both the pages. The pages are chosen to be decay unrelated. Since the pag

6、es are not decay related, at least one page should have the status good.nStable Read:nDoes a careful read from one of the paired pages, and if the result is bad it performs a careful read from the other page.nStable Write:nPerforms careful write into each one of the paired pages one after the other.

7、Stable Storage: RAID ArchitectureIssuesnThe above discussed single disk mechanisms can handle: soft read error, null write, bad write, and persistent read error.nHowever it cannot handle events like disk crash.nAlthough the inconsistencies caused by disk crashes can be handled, the data is unavailab

8、le until the crashed node/disk is recovered.nTherefore, multiple disk systems are designed to provide availability and reliability.Stable Storage: RAID ArchitectureRAID ArchitecturenRAID: Redundant Array of Inexpensive DisksnCombine multiple small, inexpensive disk drives into a group to yield perfo

9、rmance exceeding that of one large, more expensive drivenAppear to the computer as a single virtual drive nSupport fault-tolerance by redundantly storing information in various waysnUses Data Striping to achieve better performanceStable Storage: RAID ArchitectureBasic IssuesnTwo operations performed

10、 on a disknRead() : small or large.nWrite(): small or large.nAccess Concurrency is the number of simultaneous requests the can be serviced by the disk systemnThroughput is the number of bytes that can be read or written per unit time as seen by one requestnData Striping: spreading out blocks of each

11、 file across multiple disk drives.nThe stripe size is the same as the block sizeStable Storage: RAID ArchitectureBasic IssuesnThe Stripe will introduces a tradeoff between I/O throughput and Access concurrencynSmall Stripe means high throughput but no or few access concurrency.nLarge strip size prov

12、ides better access concurrency but less throughput for single requestStable Storage: RAID ArchitectureRAID Levels: RAID-0nNo RedundancynNo Fault Tolerance, If one drive fails then all data in the array is lost.nHigh I/O performancenParallel I/OnBest Storage efficiencyStable Storage: RAID Architectur

13、eRAID-1nDisk MirroringnPoor Storage efficiency.nBest Read Performance: Maybe double.nPoor write Performance: two disks to be written.nGood fault tolerance: as long as one disk of a pair is working then we can perform R/W operations.MTTFRAID-1 = (MTTF / 2) * (MTTF / MTTR)Stable Storage: RAID Architec

14、tureRAID-2nBit Level Striping.nUses Hamming Codes, a form of Error Correction Code (ECC).nCan Tolerate Disk one Failure.n# Redundant Disks = O (log (total disks).nBetter Storage efficiency than mirroring.nHigh throughput but no access concurrency.nExpensive write.nExample, for 4 disks 3 redundant di

15、sks to tolerate one disk failureStable Storage: RAID ArchitectureRAID-3nByte Level Striping with parity.nNo need for ECC since the controller knows which disk is in error. So parity is enough to tolerate one disk failure.nBest Throughput, but no concurrency.nOnly one Redundant disk is needed.Stable

16、Storage: RAID ArchitectureRAID-4nBlock Level Striping.nStripe size introduces the tradeoff between access concurrency versus throughput.nBlock Interleaved parity.nParity disk is a bottleneck in the case of a small write where we have multiple writes at the same time.nNo problems for small or large reads.Stable Storage: RAID ArchitectureRAID-4 cont.nIn general writes are very expensive.nRead-Modify-Write: for a small write you have to read all the disks, modify the parity, and then write it back along with the new data.nRead-Modify-Write is less obviou