Methods for data redundancy across three or more storage devices

• US 8,225,006 B1
• Filed: 06/17/2011
• Issued: 07/17/2012
• Est. Priority Date: 08/30/2007
• Status: Active Grant

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Virident Systems Inc. (Western Digital Corporation)
• Inventors: Karamcheti, Vijay
• Primary Examiner(s): Sorrell, Eron J
• Application Number:
  US13/163,273
• Time in Patent Office: 396 Days
• Field of Search: None
• US Class Current: 710/5
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/20 using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements

Abstract

In one embodiment of the invention, a method for data redundancy across three or more storage devices is disclosed. The method includes storing a collection of data chunks as a plurality of N-1 data stripes across N storage devices where N is three or more, wherein each data chunk of up to N data chunks forming a data stripe is stored in a different storage device; storing a parity stripe across the N storage devices including N-1 data parity chunks and one meta data parity chunk; wherein each Kth storage device of N-1 storage devices stores a Kth data parity chunk of the N-1 data parity chunks computed as parity of up to N data chunks forming the Kth data stripe; and wherein an Nth storage device of the N storage devices stores the meta parity chunk computed as parity of the N-1 data parity chunks stored in the respective N-1 storage devices.

Claims

1. A method for data redundancy across three or more storage devices, the method comprising:

storing a collection of data chunks as a plurality of N-1 data stripes across N storage devices where N is three or more, wherein each data chunk of up to N data chunks forming a data stripe is stored in a different storage device;

storing a parity stripe across the N storage devices including N-1 data parity chunks and one meta data parity chunk;

wherein each Kth storage device of N-1 storage devices stores a Kth data parity chunk of the N-1 data parity chunks computed as parity of up to N data chunks forming the Kth data stripe; and

wherein an Nth storage device of the N storage devices stores the meta parity chunk computed as parity of the N-1 data parity chunks stored in the respective N-1 storage devices.

2. The method of claim 1, further comprising:

reading the first data stripe of data across the N storage devices.

3. The method of claim 2, further comprising:

reading the first data parity chunk from the parity stripe in response to reading the first data stripe;

computing a first computed parity of the data chunks forming the first data stripe read across the N storage devices; and

comparing the first computed parity with the first data parity chunk.

4. The method of claim 1, wherein a first storage device has failed and the method further comprises:

recreating parity previously stored in the first storage device including

recreating a first parity chunk by examining the N-2 parity chunks respectively stored in the second through Nth storage devices.

5. The method of claim 4, further comprises:

recreating data previously stored in the first storage device including

recreating a first data chunk of a first data stripe by examining the data chunks of the first data stripe stored in the second through Nth storage devices and examining the recreated first parity chunk.

6. The method of claim 5, further comprises:

recreating an (N-1)th data chunk of an (N-1)th data stripe by examining the data chunks of the (N-1)th data stripe stored in the second through Nth storage devices and examining an (N-1)th parity chunk stored in an (N-1)th storage device.

7. The method of claim 1, wherein the Nth storage device has failed and the method further comprises:

recreating data previously stored in the Nth storage device including

recreating an Nth data chunk of the first data stripe by examining the data chunks of the first data stripe stored in the first through (N-1)th storage devices and examining the first parity chunk stored in the first storage device.

8. The method of claim 1, wherein the Nth storage device has failed and the method further comprises:

recreating parity previously stored in the Nth storage device including

recreating the Nth parity chunk by computing the parity of the first through (N-1)th parity chunks respectively stored in the first through (N-1)th storage devices.

9. The method of claim 8, further comprises:

recreating data previously stored in the Nth storage device including

recreating an Nth data chunk of the first through (N-1)th data stripes by examining the data chunks of

the first through (N-1)th data stripes stored in the first through (N-1)th storage devices and examining each respective parity chunk stored in each of the first through (N-1)th storage devices.

10. A method for data redundancy across four storage devices, the method comprising:

storing a collection of twelve data chunks in three data stripes of data across four storage devices including a first data stripe, a second data stripe, and a third data stripe, wherein each data chunk forming a data stripe is stored in a different storage device;

storing a parity stripe across the four storage devices including a first parity chunk, a second parity chunk, a third parity chunk, and a fourth parity chunk;

wherein a first storage device of the four storage devices stores the first parity chunk computed as parity of four data chunks forming the first data stripe;

wherein a second storage device of the four storage devices stores the second parity chunk computed as parity of four data chunks forming the second data stripe;

wherein a third storage device of the four storage devices stores the third parity chunk computed as parity of four data chunks forming the third data stripe; and

wherein a fourth storage device of the four storage devices further stores the fourth parity chunk computed as parity of the first parity chunk, second parity chunk and the third parity chunk.

11. The method of claim 10, further comprising:

reading the first data stripe of data across the four storage devices.

12. The method of claim 11, further comprising:

reading the first parity chunk from the parity stripe in response to reading the first data stripe;

computing a first computed parity of the four data chunks forming the first data stripe read; and

comparing the first computed parity with the first parity chunk.

13. The method of claim 10, wherein the first storage device has failed and the method further comprises:

recreating parity previously stored in the first storage device including

recreating the first parity chunk by examining the second, third, and fourth parity chunks respectively stored in the second, third, and fourth storage devices.

14. The method of claim 13, further comprises:

recreating data previously stored in the first storage device including

recreating a first data chunk of the first data stripe by examining the data chunks of the first data stripe stored in the second, third, and fourth storage devices and examining the recreated first parity chunk.

15. The method of claim 14, further comprises:

recreating a second data chunk of the second data stripe by examining the data chunks of the second data stripe stored in the second, third, and fourth storage devices and examining the second parity chunk stored in the second storage device; and

recreating a third data chunk of the third data stripe by examining the data chunks of the third data stripe stored in the second, third, and fourth storage devices and examining the third parity chunk stored in the third storage device.

16. The method of claim 10, wherein the fourth storage device has failed and the method further comprises:

recreating data previously stored in the fourth storage device including

recreating a fourth data chunk of the first data stripe by examining the data chunks of the first data stripe stored in the first, second, and third storage devices and examining the first parity chunk stored in the first storage device.

17. The method of claim 10, wherein the fourth storage device has failed and the method further comprises:

recreating parity previously stored in the fourth storage device including

recreating the fourth parity chunk by computing the parity of the first, second, and third parity chunks respectively stored in the first, second, and third storage devices.

18. The method of claim 17, further comprises:

recreating data previously stored in the fourth storage device including

recreating a fourth data chunk of the first data stripe by examining the data chunks of the first data stripe stored in the first, second, and third storage devices and examining the first parity chunk stored in the first storage device;

recreating a fourth data chunk of the second data stripe by examining the data chunks of the second data stripe stored in the first, second, and third storage devices and examining the second parity chunk stored in the second storage device; and

recreating a fourth data chunk of the third data stripe by examining the data chunks of the third data stripe stored in the first, second, and third storage devices and examining the third parity chunk stored in the third storage device.

19. A method for data redundancy across multiple storage devices, the method comprising:

storing a collection of data chunks as a plurality of N-1 data stripes across N daughter boards including non-volatile memory, where N is three or more, wherein each data chunk of up to N data chunks forming a data stripe is stored in a different daughter board;

storing a parity stripe across the N daughter boards including N-1 data parity chunks and one meta data parity chunk;

wherein each Kth daughter board of N-1 daughter boards stores a Kth data parity chunk of the N-1 parity chunks computed as parity of up to N data chunks forming the Kth data stripe; and

wherein an Nth daughter board of the N daughter boards stores the meta parity chunk computed as parity of the N-1 data parity chunks stored in the respective N-1 daughter boards.

20. The method of claim 19, further comprising:

reading a first data stripe of data across the N daughter boards.

21. The method of claim 20, further comprising:

reading the first data parity chunk from the parity stripe in response to reading the first data stripe;

computing a first computed parity of the N-1 data chunks forming the first data stripe read; and

comparing the first computed parity with the first data parity chunk.

22. The method of claim 20, wherein

the N-1 data chunks and the one data parity chunk or meta parity chunk in a daughter board collectively has a size of one write page into non-volatile memory.

23. The method of claim 22, wherein

the write page size is four kilobytes.

24. The method of claim 19, further comprising:

invalidating a data chunk in a data stripe by

marking a data chunk in a data stripe invalid; and

retaining the previous data in the data chunk for data redundancy until all data chunks in the data stripe are invalid.

25. The method of claim 22, wherein a daughter board has failed and the method further comprises:

unplugging the failed daughter board from a socket in a base board;

plugging a new daughter board into the socket of the base board;

configuring the new daughter board for use within the base board;

recreating the data chunks of the failed daughter board in the new daughter board; and

recreating the data parity chunk or the meta parity chunk of the failed daughter board in the new daughter board.