CS448/548 Sequence 17Decentralized Services!We want to take a look at decentralization as a way towards survivability!The case study is: Survivable Storage Systems–What is Survivable Storage–Have we seen “flavors” of such concept before?»RAID technology can be considered survivable»However, malicious concepts were not considered–We want to look at the PASIS project»basis for the discussion on Survivable Storage are the PASIS papers"http://www.pdl.cmu.edu/Pasis/1CS448/548 Sequence 17Decentralization–Before discussing Survivable Storage, I would like to briefly discuss the concept of RAIDs and how it plays into “thinking survivable”»The basis for the RAID discussion is the 1988 paper by Patterson"Patterson, D.A., et. al., “A Case for Redundant Arrays of Inexpensive Disks (RAID)”, ACM SIGMOD Records, International Conference on Management of Data, Vol.~17, No.~3, pp.~109-116, June~1988.»The following material is probably to detailed for our discussion. I will only outline the basic concepts of RAID, as they will help to get a feeling for the performance issues associated with survivable storage»Note that the Patterson paper is very dated, yet, there are very interesting issues that are still valid!2CS448/548 Sequence 17RAID!RAID Redundant Arrays of Inexpensive Disks!Motivation–single chip computers improved in performance by 40% per year–RAM capacity quadrupled capacity every 2-3 years–Disks (magnetic technology)»capacity doubled every 3 years»price cut in half every 3 years»raw seek time improved 7% every year–Note: values presented in Pattersons’ paper are dated!–Note: paper discusses “pure” RAID, not smarter implementations, e.g. caching.3CS448/548 Sequence 17RAID–Amdahl’s Law: Effective Speedup»f = fraction of work in fast mode»k = speedup while in fast mode Example:»assume 10% I/O operation»if CPU 10x => effective speedup is 5 »if CPU 100x => effective speedup is 10"90 % of potential speedup is wasted4CS448/548 Sequence 17RAID!Motivation–compare “mainframe mentality” with “today's” possibilities, e.g. cost, configurationCPUMemory ChannelControllerSCSICPUMemory DMAMainframeSmall Computer5CS448/548 Sequence 17RAID–Reliability–e.g. MTTFdisk = 30,000 h MTTF100 = 300 h ( < 2 weeks) MTTF1000 = 30 h–Note, that these numbers are very dated. Todays drives are much better. MTBF > 300,000 to 800,000 hours.–even if we assume higher MTTF of individual disks, the problem stays.Bad news!6CS448/548 Sequence 17RAID!RAID Reliability–partition disks into reliability groups and check disks»D = total number of data disks»G = # data disks in group»C = # check disks in group7CS448/548 Sequence 17RAID!Target Systems–Different RAID solutions will benefit different target system configurations.–Supercomputers»larger blocks of data, i.e. high data rate–Transaction processing»small blocks of data»high I/O rate»read-modify-write sequences8CS448/548 Sequence 17RAID!5 RAID levels–RAID 1: mirrored disks–RAID 2: hamming code for ECC–RAID 3: single check disk per group–RAID 4: independent read/writes–RAID 5: no single check disk9CS448/548 Sequence 17RAID!RAID level 1: Mirrored Disks–Most expensive option–Tandem doubles controllers too–Write to both disks–Read from one disk–Characteristics:»S = slowdown. In synchronous disks spindles are synchronized so that the corresponding sectors of a group of disks can be accessed simultaneously. For synchr. disks S = 1.»Reads = 2D/S, i.e. concurrent read possible »Write = D/S, i.e. no overhead for concurrent write of same data»R-Modify-Write = 4D/(3S)»Pat88 Table II (pg. 112)10CS448/548 Sequence 17RAID Pat88 Table II11CS448/548 Sequence 17RAID!RAID level 2: Hamming Code–DRAM => problem with !-particles »Solution, e.g. parity for SED, Hamming code for SEC–Recall Hamming Code–Same idea using one disk drive per bit–Smallest accessible unit per disk is one sector»access G sectors, where G = # data disks in a group–If operation on a portion of a group is needed:1) read all data2) modify desired position3) write full group including check info12CS448/548 Sequence 17Recall Hamming Codem = data bitsk = parity bits13CS448/548 Sequence 17Compute Check14CS448/548 Sequence 17RAID–Allows soft errors to be corrected “on the fly”.–Useful for supercomputers, not useful for transaction processing e.g. used in Thinking Machine (Connection Machine) “Data Vault” with G = 32, C = 8.–Characteristics:»Pat88 Table III (pg 112)15CS448/548 Sequence 17RAID Pat88 Table III16CS448/548 Sequence 17RAID!RAID level 3: Single Check Disk per Group–Parity is SED not SEC!–However, often controller can detect if a disk has failed»information of failed disk can be reconstructed»extra redundancy on disk, i.e. extra info on sectors etc.–If check disk fails »read data disks to restore replacement–If data disk fails»compute parity and compare with check disk»if parity bits are equal => data bit = 0»otherwise => data bit = 117CS448/548 Sequence 17RAID–Since less overhead, i.e. one check disk only => Effective performance increases–Reduction in disks over L2 decreases maintenance–Performance same as L2, however, effective performance per disk increases due to smaller number of check disks–Better for supercomputers, not good for transaction proc.–Maxtor, Micropolis introduced first RAID-3 in 1988–Characteristics:»Pat88 Table IV (pg 113)18CS448/548 Sequence 17RAID Pat88 Table IV (pg 113)19CS448/548 Sequence 17RAID!RAID level 4: Independent Reads/Writes–Pat88 fig 3 pg. 113 compares data locations 20CS448/548 Sequence 17RAID!RAID level 4: Independent Reads/Writes–Disk interleaving has advantages and disadvantages–Advantage of previous levels:»large transfer bandwidth–Disadvantages of previous levels:»all disks in a group are accessed on each operation (R,W) »spindle synchronization"if none => probably close to worse case average seek times, access times (tracking + rotation)–Interleave data on disks at sector level–Uses one parity disk 21CS448/548 Sequence 17RAID–for small accesses »need only access to 2 disks, i.e. 1 data & parity»new parity can be computed from old parity + old/new data»compute: Pnew = dataold XOR datanew XOR Pold–e.g. small write1) read old data + parity 2) write new data + parity–Bottleneck is parity disk–e.g. small read»only