Digital data storage with increased robustness against data loss

• US 5,737,344 A
• Filed: 05/25/1995
• Issued: 04/07/1998
• Est. Priority Date: 05/25/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Blaum, Mario, Kulakowski, John Edward, Belser, Karl Arnold, Rubin, Kurt Allen
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/450,123
• Time in Patent Office: 1,048 Days
• Field of Search: 371/40.1, 371/40.4, 371/40.14, 395/182.04
• US Class Current: 714/766
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

Digital data is stored on a DASD by generating a parity block for a specified block of data items and storing the parity block at a selected location on the DASD. The parity block includes a parity computation calculated by applying a parity routine to the corresponding data. The parity block also includes a parity code that indicates either (1) the size of the corresponding data block, or (2) the number of data items contributing to the parity computation. The parity block may be stored adjacent to the corresponding data, or at an independent location. Among other things, the invention provides significantly increased robustness against data loss, and improved flexibility and efficiency in storing data.

Claims

1. A method for storing digital data with increased robustness against data loss, comprising the steps of:

storing a first predetermined number of data items in selected positions of a contiguous block of a data storage medium, said contiguous block having a second predetermined number of positions at least as large in number as the first predetermined number;

generating a parity block by performing steps comprising;

applying a parity routine to the first predetermined number of data items to form a parity computation;

forming a parity map representative of the selected positions in which the first predetermined number of data items are stored; and

storing the parity block on the data storage medium.

2. The method of claim 1, wherein each data item comprises one sector.

3. The method of claim 1, wherein each block position corresponds to a different data sector.

4. The method of claim 1, wherein the step of storing the parity block comprises the step of storing the parity block immediately following the data items.

5. The method of claim 1, wherein the step of storing the parity block comprises the step of storing the parity block separate from the data items.

6. The method of claim 1, wherein the parity block includes a flag to distinguish the parity block from a data item.

7. The method of claim 1, wherein the parity map contains a flag to distinguish the parity block from a data item.

8. The method of claim 1, further comprising the steps of:

reading a defective one of the first predetermined data items;

recognizing the defective data item as being defective;

locating the parity block associated with the defective data item;

reading the parity block and all non-defective data items of the first predetermined number of data items; and

using the parity block and the non-defective data items to reconstruct the defective data item.

9. A method for storing digital data with increased robustness against data loss, comprising the steps of:

storing a first number of data items in consecutive positions on a data storage medium;

generating a parity computation by applying a parity computation routine to the first number of data items;

generating a parity map representative of the first number of data items; and

storing the parity computation and parity map on the data storage medium.

10. The method of claim 9, wherein each data item comprises one sector.

11. The method of claim 9, wherein the parity computation and parity map are stored or the data storage medium following the data items.

12. The method of claim 9, wherein the parity computation and parity map are stored on the data storage medium separate from the data items.

13. The method of claim 9, wherein the parity computation is stored in a parity block that includes a flag to distinguish the parity block from a data item.

14. The method of claim 9, wherein the parity map is stored in a parity block that contains a flag to distinguish the parity block from a data item.

15. The method of claim 9, further comprising the steps of:

reading a defective one of the first predetermined data items;

recognizing the defective data item as being defective;

locating the parity computation associated with the defective data item;

reading the parity computation and all non-defective data items of the first predetermined number of data items; and

using the parity computation and the non-defective data items to reconstruct the defective data item.

16. A data storage medium tangibly embodying a program of instructions executable by a digital processor to perform method steps to store digital data with increased robustness against data loss, said method steps comprising:

storing a first predetermined number of data items in selected positions of a contiguous block of a data storage medium, said contiguous block having a second predetermined number of positions at least as large in number as the first predetermined number;

generating a parity computation by applying a parity computation routine to the first predetermined number of data items;

generating a parity map representative of the selected positions in which the first predetermined number of data items are stored; and

storing the parity computation and parity map on the data storage medium.

17. The data storage medium of claim 16, wherein each data item comprises one sector.

18. The data storage medium of claim 16, wherein each block position corresponds to a different data sector.

19. The data storage medium of claim 16, wherein the step of storing the parity computation and parity map comprises the step of storing the parity computation and parity map immediately following the data items.

20. The data storage medium of claim 16, wherein the step of storing the parity computation and parity map comprises the step of storing the parity computation and parity map separate from the data items.

21. The data storage medium of claim 16, wherein the parity computation is stored in a parity block that includes a flag to distinguish the parity block from a data item.

22. The data storage medium of claim 16, wherein the parity map is stored in a parity block that contains a flag to distinguish the parity block from a data item.

23. The data storage medium of claim 16, further comprising the steps of:

reading a defective one of the first predetermined data items;

recognizing the defective data item as being defective;

locating the parity computation associated with the defective data item;

reading the parity computation and all non-defective data items of the first predetermined number of data items; and

using the parity computation and the non-defective data items to reconstruct the defective data item.

24. A data storage medium tangibly embodying a program of instructions executable by a digital processor to perform method steps to store digital data with increased robustness against data loss, said method steps comprising:

storing a first number of data items in consecutive positions on a data storage medium;

generating a parity computation by applying a parity computation routine to the first number of data items;

generating a parity map representative of the first number of data items; and

storing the parity computation and parity map on the data storage medium.

25. The data storage medium of claim 24, wherein each data item comprises one sector.

26. The data storage medium of claim 25, wherein the parity computation and parity map are stored on the data storage medium following the data items.

27. The data storage medium of claim 26, wherein the parity computation and parity map are stored on the data storage medium separate from the data items.

28. The data storage media of claim 24, wherein the parity computation is stored in a parity block that includes a flag to distinguish the parity block from a data items.

29. The data storage media of claim 24, wherein the parity map is stored in a parity block that contains a flag to distinguish the parity block from a data items.

30. The data storage media of claim 24, further comprising the steps of:

reading a defective one of the first predetermined data items;

recognizing the defective data item as being defective;

locating the parity computation associated with the defective data item;

reading the parity computation and all non-defective data items of the first predetermined number of data items; and

using the parity computation and the non-defective data items to reconstruct the defective data item.

31. A data storage drive, comprising:

a read/write unit to selectively read data from and write data to a data storage medium coupled to the data storage drive; and

a data controller, comprising;

an interface connected to a host;

a buffer connected to the read/write unit;

a processor connected to the interface, the buffer, and the read/write unit, and programmed to perform method steps for storing digital data received from the host via the interface on the data storage medium with increased robustness against data loss, said method steps comprising;

storing a first predetermined number of data items in selected positions of a contiguous block of a data storage medium, said contiguous block having a second predetermined number of positions at least as large in number as the first predetermined number;

generating a parity computation by applying a parity routine to the first predetermined number of data items;

generating a parity map representative of the selected positions in which the first predetermined number of data items are stored; and

storing the parity computation and parity map on the data storage medium.

32. The data storage drive of claim 31, wherein each data item comprises one sector.

33. The data storage drive of claim 31, wherein each block position corresponds to a different data sector.

34. The data storage drive of claim 31, the processor being programmed such that the step of storing the parity computation and parity map stores the parity computation and the parity immediately following the data items.

35. The data storage drive of claim 31, the processor being programmed such that the step of storing the parity computation and parity map stores at least one of the parity computation and parity map separate from the data items.

36. The data storage drive of claim 31, wherein the parity computation is stored in a parity block that includes a flag to distinguish the parity block from a data item.

37. The data storage drive of claim 31, wherein the parity map is stored in a parity block that contains a flag to distinguish the parity block from a data item.

38. The data storage drive of claim 31, wherein the processor is programmed such that the method steps further comprise the steps of:

reading a defective one of the first predetermined data items;

recognizing the defective data item as being defective;

locating the parity computation and parity map associated with the defective data item;

reading the parity computation and parity map and all non-defective data items of the first predetermined number of data items; and

using the parity computation and the parity map and the non-defective data items to reconstruct the defective data item.

39. A data storage drive, comprising:

a read/write unit to selectively read data from and write data to a data storage medium coupled to the data storage drive; and

a data controller, comprising;

an interface connected to a host;

a buffer connected to the read/write unit;

a processor connected to the interface, the buffer, and the read/write unit, and programmed to perform method steps for storing digital data received from the host via the interface on the data storage medium with increased robustness against data loss, said method steps comprising;

storing a first number of data items in consecutive positions on a data storage medium;

generating a parity computation by applying a parity routine to the first number of data items;

generating a parity map representative of the first number of data items; and

storing the parity computation and parity map on the data storage medium.

40. The data storage drive of claim 39, wherein each data item comprises one sector.

41. The data storage drive of claim 39, the processor being programmed such that the step of storing the parity computation and parity map stores the parity computation and parity map immediately following the data items.

42. The method of claim 39, the processor being programmed such that the step of storing the parity computation and parity map stores at least one of the parity computation and parity map separate from the data items.

43. The data storage drive of claim 39, wherein the parity computation is stored in a parity block that includes a flag to distinguish the parity block from a data item.

44. The data storage drive of claim 39, wherein the parity map is stored in a parity block that contains a flag to distinguish the parity block from a data item.

45. The data storage drive of claim 39, the processor being programmed such that the method steps further comprise the steps of:

reading a defective one of the first predetermined data items;

recognizing the defective data item as being defective;

locating the parity computation associated with the defective data item;

reading the parity computation and all non-defective data items of the first predetermined number of data items; and

using the parity computation and the non-defective data items to reconstruct the defective data item.

46. A method for storing digital data with increased robustness against data loss, comprising the steps of:

providing a plurality of data blocks each having a first predetermined number of contiguous positions, said plurality of data blocks including first and second data blocks;

storing a second number of data items in selected positions of the first data block with the remaining positions of the first data block being free from data;

storing a third number of data items in selected positions of the second data block with the remaining positions of the second data block being free from data, wherein the third number differs from the second number; and

for each data block, generating a corresponding parity block by performing steps comprising;

forming a parity computation by applying a parity routine only to contents of positions of the data block containing data items; and

forming a parity map representative of the selected positions of the data block in which the data items are stored;

storing each parity block on the data storage medium.

47. A data storage medium tangibly embodying a program of instructions executable by a digital processor to perform method steps to store digital data with increased robustness against data loss, said method steps comprising:

providing a plurality of data blocks each having a first predetermined number of contiguous positions, said plurality of data blocks including first and second data blocks;

storing a second number of data items in selected positions of the first data block with the remaining positions of the first data block being free from data;

storing a third number of data items in selected positions of the second data block with the remaining positions of the second data block being free from data, wherein the third number differs from the second number; and

for each data block, generating a corresponding parity block by performing steps comprising;

forming a parity computation by applying a parity routine only to contents of positions of the data block containing data items; and

forming a parity map representative of the selected positions of the data block in which the data items are stored;

storing each parity block on the data storage medium.

48. A data storage drive, comprising:

a read/write unit to selectively read data from and write data to a data storage medium coupled to the data storage drive; and

a data controller, comprising;

an interface connected to a host;

a buffer connected to the read/write unit;

a processor connected to the interface, the buffer, and the read/write unit, and programmed to perform method steps for storing digital data received from the host via the interface on the data storage medium with increased robustness against data loss, said method steps comprising;

providing a plurality of data blocks each having a first predetermined number of contiguous positions, said plurality of data blocks including first and second data blocks;

storing a second number of data items in selected positions of the first data block with the remaining positions of the first data block being free from data;

storing a third number of data items in selected positions of the second data block with the remaining positions of the second data block being free from data, wherein the third number differs from the second number; and

for each data block, generating a corresponding parity block by performing steps comprising;

forming a parity computation by applying a parity routine only to contents of positions of the data block containing data items; and

forming a parity map representative of the selected positions of the data block in which the data items are stored;

storing each parity block on the data storage medium.

49. A method for storing digital data with increased robustness against data loss, comprising the steps of:

storing a first data block comprising first number of data items by storing the data items in consecutive positions on a data storage medium;

storing a second data block comprising a second number of data items by storing the data items in consecutive positions on the data storage medium, the second number being different than the first number; and

for each data block, generating a corresponding parity block by performing steps comprising;

generating a parity computation by applying a parity computation routine to the data items of the data block; and

generating a parity map representative of the number of data items of the data block; and

storing each parity block on the data storage medium.

50. A data storage medium tangibly embodying a program of instructions executable by a digital processor to perform method steps to store digital data with increased robustness against data loss, said method steps comprising:

storing a first data block comprising first number of data items by storing the data items in consecutive positions on a data storage medium;

storing a second data block comprising a second number of data items by storing the data items in consecutive positions on the data storage medium, the second number being different than the first number; and

for each data block, generating a corresponding parity block by performing steps comprising;

generating a parity computation by applying a parity computation routine to the data items of the data block; and

generating a parity map representative of the number of data items of the data block; and

storing each parity block on the data storage medium.

51. A data storage drive, comprising:

a read/write unit to selectively read data from and write data to a data storage medium coupled to the data storage drive; and

a data controller, comprising;

an interface connected to a host;

a buffer connected to the read/write unit;

a processor connected to the interface, the buffer, and the read/write unit, and programmed to perform method steps for storing digital data received from the host via the interface on the data storage medium with increased robustness against data loss, said method steps comprising;

storing a first data block comprising first number of data items by storing the data items in consecutive positions on a data storage medium;

storing a second data block comprising a second number of data items by storing the data items in consecutive positions on the data storage medium, the second number being different than the first number; and

for each data block, generating a corresponding parity block by performing steps comprising;

generating a parity computation by applying a parity computation routine to the data items of the data block; and

generating a parity map representative of the number of data items of the data block; and

storing each parity block on the data storage medium.