Storing data redundantly

• US 20080126912A1
• Filed: 09/11/2006
• Published: 05/29/2008
• Est. Priority Date: 09/11/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: XIV Ltd. (International Business Machines Corporation)
• Inventors: Zeidner, Efri, Zohar, Ofir, Schwartz, Shemer, Chuchem, Yair
• Granted Patent: US 7,934,120 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

A method for storing data blocks, including forming the data blocks into groups comprising N·M data blocks, where N and M are different positive integers. For every group, the N·M data blocks are assigned to correspond to elements of an array comprising N rows and M columns. A respective parity block is calculated for each of the N rows and M columns, to form (N+M) parity blocks. The resulting (N+M) parity blocks and N·M data blocks are stored in respective storage devices.

Claims

1. A method for storing data blocks, comprising:

forming the data blocks into groups comprising N·

M data blocks, where N and M are different positive integers;

for every group, assigning the N·

M data blocks to correspond to elements of an array comprising N rows and M columns;

calculating respective parity blocks for each of the N rows and M columns, to form (N+M) parity blocks; and

storing the (N+M) parity blocks and the N·

M data blocks in respective storage devices.

2. The method according to claim 1, wherein the respective storage devices comprise S storage devices, and wherein S≧

N·

M+(N+M).

3. The method according to claim 1, wherein storing the parity blocks and the data blocks comprises distributing the parity blocks and the data blocks evenly over the storage devices.

4. The method according to claim 1, wherein the data blocks are conveyed to the storage devices in a sequence, and wherein assigning the N·

M data blocks to correspond to elements in the array comprises assigning the data blocks to the array according to the sequence.

5. The method according to claim 1, wherein the data blocks are conveyed to the storage devices in a sequence, and wherein assigning the N·

M data blocks to correspond to elements in the array comprises assigning the data blocks to the array independently of the sequence.

6. The method according to claim 1, and comprising calculating a further parity block from the (N+M) parity blocks, and storing the further parity block on a further storage device, different from the respective storage devices.

7. The method according to claim 6, wherein there are a total of S storage devices, wherein S≧

N·

M+(N+M)+1.

8. A method for recovering a given data block from a plurality of data blocks, comprising:

forming the plurality of data blocks into groups comprising N·

M data blocks, where N and M are positive integers and N>

M;

for every group, assigning the N·

M data blocks to correspond to elements of an array comprising N rows and M columns, wherein the given data block is in a respective row comprising the given data block and other data blocks in the respective row;

calculating respective parity blocks for each of the N rows and M columns, to form (N+M) parity blocks, the parity blocks including a respective-row parity block formed from the given data block and the other data blocks;

storing the (N+M) parity blocks and the N·

M data blocks in respective storage devices; and

regenerating the given data block using the other data blocks and the respective-row parity block.

9. The method according to claim 8, and comprising calculating a further parity block from the (N+M) parity blocks, and storing the further parity block on a further storage device, different from the respective storage devices.

10. The method according to claim 8, and comprising selecting values for N and M in response to a rate of recovery for the given data block.

11. Apparatus for storing data blocks, comprising:

a plurality of storage devices; and

a processor which is configured to;

form the data blocks into groups comprising N·

M data blocks, where N and M are different positive integers,

for every group, assign the N·

M data blocks to correspond to elements of an array comprising N rows and M columns,

calculate respective parity blocks for each of the N rows and M columns, to form (N+M) parity blocks, and

store the (N+M) parity blocks and the N·

M data blocks in respective storage devices comprised in the plurality of storage devices.

12. The apparatus according to claim 11, wherein the plurality of storage devices comprise S storage devices, and wherein S≧

N·

M+(N+M).

13. The apparatus according to claim 11, wherein storing the parity blocks and the data blocks comprises distributing the parity blocks and the data blocks evenly over the storage devices.

14. The apparatus according to claim 11, wherein the data blocks are conveyed to the plurality of storage devices in a sequence, and wherein assigning the N·

M data blocks to correspond to elements in the array comprises assigning the data blocks to the array according to the sequence.

15. The apparatus according to claim 11, wherein the data blocks are conveyed to the plurality of storage devices in a sequence, and wherein assigning the N·

M data blocks to correspond to elements in the array comprises assigning the data blocks to the array independently of the sequence.

16. The apparatus according to claim 11, wherein the processor is configured to calculate a further parity block from the (N+M) parity blocks, and to store the further parity block on a further storage device, comprised in the plurality of storage devices and different from the respective storage devices.

17. The apparatus according to claim 16, wherein the plurality of storage devices comprise S storage devices, and wherein S≧

N·

M+(N+M)+1.

18. The apparatus according to claim 11, wherein:

assigning the N·

M data blocks comprises assigning a given data block to be in a respective row comprising the given data block and other data blocks in the respective row, and

calculating the respective parity blocks comprises calculating a respective-row parity block from the given data block and the other data blocks,

and wherein the processor is configured to;

regenerate the given data block using the other data blocks and the respective-row parity block.

19. The apparatus according to claim 18, wherein the processor is configured to calculate a further parity block from the (N+M) parity blocks, and to store the further parity block on a further storage device comprised in the plurality of storage devices and different from the respective storage devices.

20. The apparatus according to claim 18, wherein the processor is configured to select values for N and M in response to a rate of recovery for the given data block.

21. A method for configuring storage devices to store data blocks, comprising:

forming data block logical addresses (LAs) for the devices into groups comprising N·

M LAs, where N and M are different positive integers;

for every group, assigning the N·

M data block LAs to correspond to elements of an array comprising N rows and M columns;

assigning N row parity block LAs and M column parity block LAs, to form (N+M) parity block LAs; and

forming a mapping between the (N+M) parity block LAs and the N·

M data block LAs and respective storage devices.

22. The method according to claim 21, and comprising, for each group of N·

M LAs, arranging N·

M respective data blocks in response to the array, calculating parity blocks for the data blocks, and storing the parity blocks and the data blocks in response to the mapping.