Method of encoding data signals for storage

• US 6,247,157 B1
• Filed: 05/13/1998
• Issued: 06/12/2001
• Est. Priority Date: 05/13/1998
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Edirisooriya, Samantha J. W.
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US09/078,389
• Time in Patent Office: 1,126 Days
• Field of Search: 714/5, 714/7, 714/710, 714/755, 714/756, 714/766, 714/767, 714/770, 714/802, 714/6, 714/800, 714/807
• US Class Current: 714/767
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks

Abstract

Briefly, in accordance with one embodiment of the invention, a method of encoding data signals for storage to tolerate failure of a storage unit of a storage medium includes the following. For N+2 storage units, N being a positive integer, each of the storage units being divided into N storage blocks, 2N blocks of priority signals are produced from (N)(N) blocks of data signals. The N(N+2) blocks of parity and data signals are allocated over the N+2 storage units of the storage medium so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units. Briefly, in accordance with another embodiment of the invention, a storage medium includes: N+2 storage units to store binary digital signals, N being a positive integer, each of the storage units being divided into N storage blocks, the N+2 storage units having stored thereon 2N blocks of parity signals and (N)(N) blocks of data signals, the 2N blocks of parity signals being based upon the (N)(N) blocks of data signals. The 2N blocks of parity signals are distributively stored over the N+2 storage units so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units.

Claims

1. A method of encoding data signals for storage to tolerate failure of a storage unit of a storage medium comprising:

for N+2 storage units, N being a positive integer, each of the storage units divided into N storage blocks, producing 2N blocks of parity signals from (N)(N) blocks of data signals; and

allocating the N(N+2) blocks of parity and data signals over the N+2 storage units of the storage medium so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units.

2. The method of claim 1, wherein said 2N blocks of parity signals comprise horizontal parity signals and diagonal parity signals.

3. The method of claim 2, wherein the diagonal parity signals generated are substantially in accordance with the following equation:

4. The method of claim 2, wherein the horizontal parity signals generated are substantially in accordance with the following equation:

5. The method of claim 2, wherein the diagonal parity signals are exclusively stored in one of the N+2 storage units.

6. The method of claim 5, wherein the horizontal parity signals are distributively stored across only N of the N+2 storage units.

7. The method of claim 6, wherein one of the N+2 storage units exclusively stores data signals.

8. A storage medium comprising:

N+2 storage units to store binary digital signals, N being a positive integer, each of the storage units being divided into N storage blocks, said N+2 storage units having stored thereon 2N blocks of parity signals and (N)(N) blocks of data signals, the 2N blocks of parity signal being based upon the (N)(N) blocks of data signals;

said 2N blocks of parity signals being distributively stored over said N+2 storage units so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units.

9. The storage medium of claim 8, wherein said 2N blocks of parity signals comprise horizontal parity signals and diagonal parity signals.

10. The storage medium of claim 9, wherein the diagonal parity signals are substantially in accordance with the following equation:

11. The storage medium of claim 9, wherein the horizontal parity signals are substantially in accordance with the following equation:

12. The storage medium of claim 9, wherein the diagonal parity signals are exclusively stored in one of the N+2 storage units.

13. The storage medium of claim 12, wherein the horizontal parity signals are distributively stored across only N of the N+2 storage units.

14. The method of claim 13, wherein one of the N+2 storage units exclusively stores data signals.

15. A apparatus comprising:

N+2 storage units adapted to store binary digital signals, N being a positive integer, each of the storage units being adapted to be divided into N storage blocks, said N+2 storage units being adapted to have stored thereon 2N blocks of parity signals and (N)(N) blocks of data signals, the 2N blocks of parity signal being based upon the (N)(N) blocks of data signals;

said N+2 storage units being adapted so that said 2N blocks of parity signals are not to be exclusively stored in two of the N+2 storage units.

16. The apparatus of claim 15, wherein said 2N blocks of parity signals are to comprise horizontal parity signals and diagonal parity signals.

17. The apparatus of claim 16, wherein the diagonal parity signals are to be substantially in accordance with the following equation:

18. The apparatus of claim 16, wherein the horizontal parity signals are to be substantially in accordance with the following equation:

19. The apparatus of claim 16, wherein the diagonal parity signals are to be exclusively stored in one of the N+2 storage units.

20. The apparatus of claim 19, wherein the horizontal parity signals are to be distributively stored across only N of the N+2 storage units.

21. The apparatus of claim 20, wherein one of the N+2 storage units is to exclusively store data signals.

22. An article comprising:

a storage medium, said storage medium having stored therein instructions, which when executed by a processor, result in;

N+2 storage units to store binary digital signals, N being a positive integer, each of the storage units being divided into N storage blocks, said N+2 storage units having stored thereon 2N blocks of parity signals and (N)(N) blocks of data signals, the 2N blocks of parity signal being based upon the (N)(N) blocks of data signals;

said 2N blocks of parity signals being distributively stored over said N+2 storage units so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units.

23. The article of claim 22, wherein said 2N blocks of parity signals comprise horizontal parity signals and diagonal parity signals.

24. The article of claim 23, wherein the diagonal parity signals are substantially in accordance with the following equation:

25. The article of claim 23, wherein the horizontal parity signals are substantially in accordance with the following equation:

26. The article of claim 22, wherein N comprises a positive prime number.

27. A method of reconstruction data signals encoded for storage to tolerate failure of a storage unit of a storage medium having N+2 storage units, N being positive integer, each of the storage units having been divided into N storage blocks, 2N blocks of parity signals having been produced from (N)(N) blocks of data signals, said method comprising:

allocating the N(N+2) blocks of parity and data signals over the N+2 storage units of the medium so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units; and

after at least one of the storage units fail, using selected data and parity signals to reconstruct the data signals lost as a result of the failure.

28. The method of claim 27, wherein the at least one of the storage units comprises two storage units.

29. A method of updating a data signal encoded for storage to tolerate failure of a unit of a storage medium having N+2 storage units, N being a positive integer, each of the storage units having been divided into N storage blocks, 2N blocks of parity signals having been produced from (N)(N) locks of data signals, said method comprising:

allocating the N(N+2) blocks of parity and data signals over the N+2 storage units of the storage medium so that the 2N blocks of parity signals are not exclusively stored in two of the N+2 storage units; and

reading the data to be updated and any associated parity signals;

processing the data signal to be updated, the any associated parity signals, and the data signal updating the data signal to be updated to produce updated parity signals; and

writing the data signal updating the data signal to be updated and the updated parity so as to replace the data signal to be updated and the any associated parity signals.

30. The method of claim 29, wherein the any associated parity signals comprise a horizontal parity signal and a diagonal parity signal corresponding to the data signal to be updated;

and

the updated parity signals comprise an updated horizontal parity signal and an updated diagonal parity signal.

31. A apparatus comprising:

N+2 storage units adapted to store binary digital signals, N being a positive integer, each of the storage units being adapted to be divided into N storage blocks, said N+2 storage units being adapted to have stored thereon (N)(N) blocks of data and parity signals, the blocks of parity signal being based upon the blocks of data signals;

said N+2 storage units being adapted so that said blocks of parity signals are not to be exclusively stored in two of the N+2 storage units; and

said N+2 storage units being adapted so that 2N of said blocks are to comprise spare storage space for any one of data signals and parity signals.

32. The apparatus of claim 31, wherein the 2N blocks of spare storage space are exclusively to be in two storage units of said N+2 storage units.

33. The apparatus of claim 32, wherein the 2N blocks of spare storage space are to be distributed across said N+2 storage units.

34. A storage medium comprising:

N+2 storage units to store binary digital signals, N being a positive integer, each of the storage units being divided into N storage blocks, said N+2 storage units having stored thereon (N)(N) blocks of data and parity signals, the blocks of parity signal being based upon the blocks of data signals;

said blocks of parity signals being distributively stored over said N+2 storage units so that said blocks of parity signals are not exclusively stored in two of the N+2 storage units; and

2N of said blocks of said N+2 storage units comprising spare storage space for any one of data signals and parity signals.

35. The storage medium of claim 34, wherein the 2N blocks of spare storage space are exclusively in two storage units of said N+2 storage units.

36. The storage medium of claim 34, wherein the 2N blocks of spare storage space are distributed across said N+2 storage units.