[CS61C FA20] Lecture 38.6 - Dependability- Parity, ECC, RAID: Redundancy with RAID — Transcript

Full transcript

1. 0:04[Music]
2. 0:09hello and welcome back to our module on
3. 0:12dependability
4. 0:14so far we have seen how we can add
5. 0:18bit level redundancy to
6. 0:21avoid soft errors errors caused by
7. 0:24some transient effects like cosmic rays
8. 0:28or disturbances in the environment
9. 0:34now the question is what do we do when
10. 0:36with permanent failures
11. 0:38in hardware well
12. 0:42this mechanism may not protect us and
13. 0:45using some kind of an
14. 0:46error correction to protect from
15. 0:48transient errors has a very high
16. 0:50overhead we generally use spare parts
17. 0:54um to say in
18. 0:57our hardware that can
19. 1:00take over from the failed part
20. 1:04this happens in memory chips as well but
21. 1:06it is deep inside
22. 1:08the actually design of the memory
23. 1:12chip so it's not adequate quite for this
24. 1:14class but there is a really good example
25. 1:16out there
26. 1:17in a form of disk drives so
27. 1:20this drives traditionally hard disk
28. 1:23drives are mechanical devices
29. 1:25and they do tend to fail we have seen
30. 1:27that this drives
31. 1:28have some failure rate of percent or two
32. 1:32per year uh nowadays
33. 1:36there may be valuable latest data stored
34. 1:38on these drives
35. 1:41generally there are backups but there is
36. 1:44a
37. 1:45fairly high cost of bringing back
38. 1:48the backup from to restore the operation
39. 1:53after a drive fails
40. 1:56so generally there is a great idea
41. 1:58developed at berkeley
42. 2:00by randy katz and dave patterson
43. 2:04in trying to provide
44. 2:08redundancy that is going to help with
45. 2:10failing disks
46. 2:12it is called the raid which stands for
47. 2:14redundant arrays
48. 2:16of inexpensive disks this is
49. 2:19inexpensive is in there fits well
50. 2:23it applies to any disk whether it's
51. 2:25expensive or not
52. 2:30the idea was actually deployed
53. 2:33as an alternative to really expensive
54. 2:36you know highly reliability disks
55. 2:38that can be replaced with an array of
56. 2:40relatively
57. 2:41cheap off-the-shelf disks
58. 2:44so uh our data then will not be stored
59. 2:48in just one disk it'll
60. 2:49be stored across multiple disks and
61. 2:53um one of the things or one of the
62. 2:56concepts that are typically used in
63. 2:58in storage arrays is that the files are
64. 3:00striped across
65. 3:01multiple disks what does that mean so if
66. 3:03you have a big file
67. 3:05instead of writing everything to one
68. 3:06disk we're going to break it up into
69. 3:09chunks and write it as a stripe across
70. 3:11multiple
71. 3:12disks remember disks are slow so
72. 3:15if we can just write pieces of files to
73. 3:18multiple disks in
74. 3:20parallel we can speed up our operation
75. 3:24so redundancy here can be used
76. 3:27to speed up the disk operation but it is
77. 3:30also there to prevent
78. 3:32from the slowdowns
79. 3:36disruptions in service if there is a
80. 3:39failure
81. 3:40so it improves our availability
82. 3:44so the disk will still fail and the
83. 3:47contents
84. 3:48of the user files are still going to be
85. 3:51reconstructed
86. 3:52from the remaining disks in the array
87. 3:55of course there is an overhead we are
88. 3:57not using all the disks to store
89. 4:00different users data we are using some
90. 4:03of the disks
91. 4:04as a source of redundancy so let's like
92. 4:08take a look
93. 4:09at a few traditional ways how this
94. 4:12concept of raid
95. 4:14of redundant array of inexpensive disks
96. 4:17have been used
97. 4:20there are different levels of raid raid
98. 4:220 doesn't provide any redundancy we're
99. 4:24not going
100. 4:25not going to talk about that it is there
101. 4:27just to speed up
102. 4:28by providing striping
103. 4:32raid 1 is the first form of the
104. 4:34redundant
105. 4:35dist array so essentially what we have
106. 4:38there
107. 4:39is that we keep
108. 4:43two groups of disks as
109. 4:46many as we have primary disks that's how
110. 4:49many
111. 4:51backups we have these are called
112. 4:53recovery groups and essentially
113. 4:55each of a disk in the simplest case we
114. 4:58will just have one disk here
115. 5:00and one in the other group we will be
116. 5:03mirroring the data
117. 5:04from one disk to another
118. 5:08simply we have two copies of our data
119. 5:11and that provides redundancy
120. 5:16um there are no
121. 5:19real speed tradeoffs or advantage or
122. 5:22disadvantages here
123. 5:24it i mean there are some slight um
124. 5:26trade-offs that happen
125. 5:28when these this are not equal when other
126. 5:31one of them
127. 5:32or some of them are slower than the
128. 5:33others well they may be limiting the
129. 5:35speed
130. 5:36um and um
131. 5:40but we don't really need to dive into
132. 5:42that for now
133. 5:44the the point here is that
134. 5:47the these raid
135. 5:501 arrays are expensive we have 100
136. 5:54overhead for every disk that we need we
137. 5:57provide
138. 5:57one additional disk as a backup but
139. 6:01we have seen that we really don't need
140. 6:02to do that in
141. 6:05in dram error correction codes so can we
142. 6:09use the same
143. 6:10or a similar concept to provide
144. 6:12redundancy
145. 6:13in disks so of course we do
146. 6:16uh that's the concept of ray 3 where we
147. 6:19add
148. 6:20the parity so here is how it goes
149. 6:24we can have a few disks and then we
150. 6:27would add a parity disk to that
151. 6:30our data is going to be stored in these
152. 6:32disks
153. 6:34and you can envision it for now as
154. 6:37you know single bit data although this
155. 6:39this would be pair it in the form of
156. 6:42words in ray 3 and
157. 6:45we are going to stripe our file across
158. 6:48multiple disks
159. 6:51so we are going to save our date and if
160. 6:54we are stripping as a single bits
161. 6:56it's more closer to like a raid 2 level
162. 6:59but in raid 3 we can
163. 7:00imagine that these are these bits are
164. 7:02just representatives of words
165. 7:04and then we'll be providing parity in
166. 7:07a separate disk this parity
167. 7:11here is computed in the same way how we
168. 7:14have done
169. 7:14uh in the past if we have
170. 7:17an even number of bits in the world
171. 7:21then the parity bit is zero just
172. 7:24basically
173. 7:25maintains even parity there so
174. 7:30if a disk fails then
175. 7:33the parity is going to replace it
176. 7:38but we remember in in dram we
177. 7:42couldn't actually do that our parity did
178. 7:45not provide
179. 7:46enough information to know where the
180. 7:49error came from well
181. 7:50we here actually know what uh where the
182. 7:52error came from
183. 7:54um we'd know that the disk failed we
184. 7:56would have this
185. 7:57additional information that one of the
186. 7:59disk has failed and we know which disk
187. 8:01has failed so these parity bits
188. 8:05are there to recover the information
189. 8:08that is missing
190. 8:09so by knowing that this bit is zero this
191. 8:12bit is one
192. 8:13and this one is zero we'll know that the
193. 8:14missing bit is also zero
194. 8:18all right so that was raid three raid
195. 8:21four is a variant of that um
196. 8:24it just provides higher input output
197. 8:28rate
198. 8:30so here is uh how it looks like so
199. 8:34this is how we can view an array of five
200. 8:36disks so there are
201. 8:37four disks that hold user data and the
202. 8:40fifth
203. 8:41disk holds parity and you can see
204. 8:44that these these are perhaps increasing
205. 8:48uh logical disk addresses so these are
206. 8:50different
207. 8:51um sectors um in the disk
208. 8:55so um you can view it as insides of the
209. 8:58five
210. 8:59disks that are spinning
211. 9:02now um raid 4 supports
212. 9:07higher rate i o and what does that mean
213. 9:10for example you would like to
214. 9:11do a read of small files from disks 0
215. 9:15and this 5 so
216. 9:16you know the file basically fits in one
217. 9:19disk so
218. 9:20we can essentially read them
219. 9:21concurrently from
220. 9:23disks 0 and 5 at the same time
221. 9:29and for a large
222. 9:32disk for a large write we can speed it
223. 9:36up
224. 9:36by striping across all of the disks
225. 9:41okay it does
226. 9:45have one of the the the challenges
227. 9:49of raid 4 is the fact
228. 9:52that all the parity resides on one disk
229. 9:56so if you're trying to write a bunch of
230. 9:58small files
231. 10:00that's going to be the bottleneck let's
232. 10:01take a quick look at that
233. 10:03so here is our inspiration for raid5 if
234. 10:06we are writing
235. 10:08two small files d0 and d5
236. 10:11we have to generate parity for each
237. 10:17those two rights are going to
238. 10:21happen concurrently
239. 10:25and now the question is how do we
240. 10:27generate the parity
241. 10:29um in order to generate the parity we'll
242. 10:32need
243. 10:33to know all the other data that forms
244. 10:36that parity so we'll need to read all
245. 10:38the other disks so
246. 10:39possibly we can go ahead and read them
247. 10:42and
248. 10:43then repopulate the parity or the other
249. 10:45way which is usually what is actually
250. 10:46being done
251. 10:47uh in in raid controllers um
252. 10:50our parity disk has the old sum so we
253. 10:54can
254. 10:54perhaps just recalculate your read that
255. 10:57parity
256. 10:58updated with this data and write it back
257. 11:02it's a straight linear algebra there
258. 11:07in either case the bottleneck here for
259. 11:10eight five
260. 11:11is that all the parity is being written
261. 11:15to this disk so we need to perhaps
262. 11:19read the parity data update it
263. 11:22and write it back and do that for
264. 11:23multiple files concurrently so generally
265. 11:26that disk is going to be
266. 11:28the bottleneck
267. 11:33then comes
268. 11:36the motivation for raid 5. raid 5
269. 11:39is a way to improve the trumpet and
270. 11:42maintain the parity and the way how
271. 11:44it is being done is by simply
272. 11:47distributing parity across
273. 11:49interleaving parity across the entire
274. 11:51array
275. 11:52so not the parity is not going to be
276. 11:55just on
277. 11:56our fifth drive it is going to be spread
278. 11:58over all
279. 11:59of the drives so if we are writing
280. 12:02to this d0 and d5
281. 12:06over here would be writing on these two
282. 12:09separate disks and we can do that
283. 12:10concurrently
284. 12:12and since their parity checks are
285. 12:14associated with disks three and four
286. 12:17we can do that we can proceed with that
287. 12:20concurrently as well
288. 12:23okay that's essentially
289. 12:27um raid in a nutshell there are
290. 12:28different other types of raid that
291. 12:31generally employ a couple of more a few
292. 12:34extra desks
293. 12:36but we are not going to cover them in
294. 12:38this course
295. 12:41so in conclusion we have seen how
296. 12:44does redundancy improve our
297. 12:47dependability
298. 12:49we can use that by using spatial
299. 12:52redundancy by
300. 12:53employing extra hardware extra hardware
301. 12:56in the form of extra bits
302. 12:57extra checks
303. 13:01or by using temporal uh
304. 13:07redundancy by repeating the operation if
305. 13:10it fails the first time
306. 13:12we have seen the definitions of
307. 13:13reliability and availability
308. 13:15and we have seen a specific example how
309. 13:18we use
310. 13:20parity for single error detection and
311. 13:23then we have seen how we can employ
312. 13:25hamming codes with a distance of 3 to
313. 13:30perform singular correction and
314. 13:36with an additional bit perform uh
315. 13:39double error detection and then we have
316. 13:43seen
317. 13:43that raid arrays are the way uh
318. 13:47to handle failing disk drives
319. 13:51it's an example how does extra hardware
320. 13:55extra disks redundancy
321. 13:58improve the availability of a system if
322. 14:01the disk drive fails
323. 14:03our system does not crash and its
324. 14:05performance actually
325. 14:07is the system's performance is improved
326. 14:09it is not
327. 14:10degraded by using multiple
328. 14:13drives you have seen that there are
329. 14:15different trade levels
330. 14:17there are more of them out there in
331. 14:18practice but
332. 14:20we get a reasonable good understanding
333. 14:23of
334. 14:24how they work anyway that's it
335. 14:27this is all what you wanted to cover
336. 14:29with respect
337. 14:31to dependability and that wraps up this
338. 14:34module
339. 14:36see you later