4/27/11&1&CS&61C:&Great&Ideas&in&Computer&Architecture&(Machine&Structures)&Redundant(Arrays(of(Inexpensive(Disks(Instructors:&Randy&H.&Katz&David&A.&PaHerson&hHp://inst.eecs.Berkeley.edu/~cs61c/fa10&1&Spring&2011&PP&Lecture&4/27/11&4/27/11& Spring&2011&PP&Lecture& 2&Agenda&• RAID&• Administrivia&• Course&Summary&(Randy)&• Cal&Culture&(Dave)&• Course&EvaluaTon&4/27/11& Spring&2011&PP&Lecture& 3&Agenda&• RAID&• Administrivia&• Course&Summary&(Randy)&• Cal&Culture&(Dave)&• Course&EvaluaTon&4/27/11& Spring&2011&PP&Lecture& 4&EvoluTon&of&the&Disk&Drive&4/27/11& Spring&2011&PP&Lecture& 5&IBM&RAMAC&305,&1956&IBM&3390K,&1986&Apple&SCSI,&1986&Can&smaller&disks&be&used&&to&close&gap&in&performance&between&disks&and&CPUs?&Arrays&of&Small&Disks&4/27/11& Spring&2011&PP&Lecture& 6&14”&10”&5.25”&3.5”&3.5”&Disk&Array:&&&&&1&disk&design&ConvenTonal:&&&&&&&&&&&&&&&&&4&disk&&designs&Low&End&High&End&4/27/11&2&Replace&Small&Number&of&Large&Disks&with&Large&Number&of&Small&Disks!&(1988&Disks)&4/27/11& Spring&2011&PP&Lecture& 7&Capacity&&Volume&&Power&Data&Rate&&I/O&Rate&&&&MTTF&&&Cost(IBM&3390K&20&GBytes&97&cu.&e.&3&KW&15&MB/s&600&I/Os/s&250&KHrs&$250K&IBM&3.5"&0061&320&MBytes&0.1&cu.&e.&11&W&1.5&MB/s&55&I/Os/s&50&KHrs&$2K&x70&23&GBytes&11&cu.&e.&1&KW&120&MB/s&3900&IOs/s&???&Hrs&$150K(Disk&Arrays&have&potenTal&for&large&data&and&I/O&rates,&high&MB&per&cu.&e.,&high&MB&per&KW,&but&what&about&reliability?&9X&3X&8X&6X&RAID:&Redundant&Arrays&of&(Inexpensive)&Disks&• Files&are&"striped"&across&mulTple&disks&• Redundancy&yields&high&data&availability&– Availability:&service&sTll&provided&to&user,&even&if&some&components&failed&• Disks&will&sTll&fail&• Contents&reconstructed&from&data&&&redundantly&stored&in&the&array&⇒&Capacity&penalty&to&store&redundant&info&⇒&Bandwidth&penalty&to&update&redundant&info&4/27/11& Spring&2011&PP&Lecture& 8&Redundant&Arrays&of&Inexpensive&Disks&RAID&1:&Disk&Mirroring/Shadowing&4/27/11& Spring&2011&PP&Lecture& 9&•!Each&disk&is&fully&duplicated&onto&its&“mirror”&&&&&&&Very&high&availability&can&be&achieved&•&Bandwidth&sacrifice&on&write:&&&&&&&Logical&write&=&two&physical&writes&Reads&may&be&opTmized&•&Most&expensive&soluTon:&100%&capacity&overhead&recovery&group&Redundant&Array&of&Inexpens ive&Disks&RAID&3:&Parity&Disk&4/27/11& Spring&2011&PP&Lecture& 10&P&10010011&11001101&10010011&.&.&.&logical&record&1&0&1&0&0&0&1&1&1&1&0&0&1&1&0&1&1&0&1&0&0&0&1&1&1&1&0&0&1&1&0&1&P&contains&sum&of&other&disks&per&stripe&&mod&2&(“parity”)&If&disk&fails,&subtract&&P&from&sum&of&other&&disks&to&find&missing&informaTon&Striped&physical&records&Redundant&Arrays&of&Inexpensive&Disks&RAID&4:&High&I/O&Rate&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&Address&Stripe(Insides&of&5&disks&Example:&small&read&D0&&&D5,&large&write&D12PD15&4/27/11& 11&Spring&2011&PP&Lecture&InspiraTon&for&RAID&5&• RAID&4&works&well&for&small&reads&• Small&writes&(write&to&one&disk):&&– OpTon&1:&read&other&data&disks,&create&new&sum&and&write&to&Parity&Disk&– OpTon&2:&since&P&has&old&sum,&compare&old&data&to&new&data,&add&the&difference&to&P&• Small&writes&are&limited&by&Parity&Disk:&Write&to&D0,&D5&both&also&write&to&P&disk&&4/27/11& Spring&2011&PP&Lecture& 12&D0# D1# D2#D3#P#D4# D5# D6#P#D7#4/27/11&3&RAID&5:&High&I/O&Rate&Interleaved&Parity&4/27/11& Spring&2011&PP&Lecture& 13&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&0,&1,&3,&4&Problems&of&Disk&Arrays:&Small&Writes&D0# D1# D2#D3#P#D0'#+#+#D0'# D1# D2#D3#P'#new$data$old$data$old$$parity$XOR#XOR#(1.#Read)#(2.#Read)#(3.#Write)#(4.#Write)#RAID25:$Small$Write$Algorithm$1#Logical#Write#=#2#Physical#Reads#+#2##Physical#Writes#4/27/11& 14&Spring&2011&PP&Lecture&Tech&Report&Read&‘Round&the&World&(December&1987)&4/27/11& Spring&2011&PP&Lecture& 15&RAIDPI&• RAIDPI&(1989)&&– Consisted&of&a&Sun&4/280&workstaTon&with&128&MB&of&DRAM,&four&dualPstring&SCSI&controllers,&28&5.25Pinch&SCSI&disks&and&specialized&disk&striping&soeware&4/27/11& Spring&2011&PP&Lecture& 16&RAID&II&• 1990P1993&• Early&Network&AHached&Storage&(NAS)&System&running&a&Log&Structured&File&System&(LFS)&• Impact:&– $25&Billion/year&in&2002&– Over&$150&Billion&in&RAID&device&sold&since&1990P2002&– 200+&RAID&companies&(at&the&peak)&– Soeware&RAID&a&standard&component&of&modern&OSs&4/27/11& 17&Spring&2011&PP&Lecture&RAID&II&4/27/11& Spring&2011&PP&Lecture& 18&4/27/11&4&RAID&Summary&• LogicalPtoPphysical&block&mapping,&parity&striping,&readPmodifyPwrite&processing&• Embedded&caches&and&orchestraTng&data&staging&between&network&interfaces,&parity&hardware,&and&file&server&interfaces&• Failed&disk&replacement,&hot&spares,&background&copies&and&backup&• Embedded&logPstructured&file&systems,&compression&on&the&fly&• Soeware&complexity&dominates&hardware!&4/27/11& Spring&2011&PP&Lecture& 19&Agenda&• RAID&• Administrivia&• Course&Summary&(Randy)&• Cal&Culture&(Dave)&• Course&EvaluaTon&4/27/11& Spring&2011&PP&Lecture& 20&Administrivia&• Final&Review:&Mon&5/2,&5&–&8PM,&2050&VLSB&• Final&Exam:&Mon&5/9,&11:30P2:30PM,&&100&Haas&Pavilion&– Designed&for&90&minutes,&you&will&have&3&hours&– Comprehensive&(parTcularly&problem&areas&on&midterm),&but&focused&on&course&since&midterm:&lecture,&lab,&hws,&and&projects&are&fair&game&&– 8&½&inch&x&11&inch&crib&sheet&like&midterm&4/27/11& 21&Spring&2011&PP&Lecture&Some&Survey&Results&• I&felt&the&midterm&was&&&9%&Far&too&difficult &&43%&Somewhat&harder&than&it&should&have&been&46%&Fair&&&1%&A&liHle&too&easy&&&1%&Far&too&easy&4/27/11& Spring&2011&PP&Lecture& 22&Some&Survey&Results&• How&much&Tme&per&week&to&you&spend&on&average&in&61C&(including&lecture,&discussion,&and&labs)?&18%&<10&hours&per&week &&26%&11P12&hours&per&week&13%&13P14&hours&per&week&24%&15P16&hours&per&week&10%&17P20&hours&per&week&10%&>21&hours&per&week&4/27/11& Spring&2011&PP&Lecture&
View Full Document