FORK CODES FOR ERASURE CODING OF DATA BLOCKS

• US 20100138717A1
• Filed: 12/02/2008
• Published: 06/03/2010
• Est. Priority Date: 12/02/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dimakis, Georgios-Alex, Wu, Yunnan
• Application Number:
  US12/326,880
• Publication Number:
  US 20100138717A1
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

Described is a technology in which data blocks are coded into erasure coded blocks in a two-stage, two-level processing operation. In a first processing stage, such as via MDS coding, original blocks are coded into a first level of output data blocks including one or more parity blocks. In a second, fork code processing stage, the first level blocks are partitioned into groups, and those groups used to generate a second level of parity blocks. The blocks are maintained among a plurality of storage nodes. Recovery of a failed data block is accomplished by accessing only the other data blocks associated with the failed data block'"'"'s coding group (whenever possible), thus facilitating significantly more efficient recovery than with conventional erasure coding techniques.

Claims

1. In a computing environment, a method comprising, coding original data blocks into a first set of output data blocks including at least one parity data block, partitioning the output data blocks into one or more groups, and coding the groups into a second set of output data blocks.

2. The method of claim 1 further comprising, maintaining the first set of output data blocks and the second set of output data blocks among a plurality of nodes.

3. The method of claim 2 wherein the blocks within a group and the data blocks computed therefrom comprise a coding group, and further comprising, determining whether a data block that needs to be recovered can be recovered using only other data blocks associated with that data block'"'"'s coding group, and if so, recovering the data block that needs to be recovered by using the other data blocks associated with that data block'"'"'s coding group.

4. The method of claim 3 wherein the data block that needs to be recovered cannot be recovered using only other data blocks associated with that data block'"'"'s coding group, and further comprising, accessing at least one block that is not within that data block'"'"'s coding group to perform a recovery operation.

5. The method of claim 1 wherein coding the original data blocks into the first set of output data blocks comprises performing MDS erasure coding to generate the at least one parity data block.

6. The method of claim 1 wherein coding the groups comprises performing MDS erasure coding to generate the second set of output data blocks.

7. In a computing environment, a system comprising, a first stage coding processor that generates a first set of output data blocks from original data blocks, the output data blocks including at least one data block that is generated as a function of the original data blocks, and a second stage coding processor that partitions the first set of output data blocks into groups and generates a second set of output data blocks, including data blocks that are functions of the data blocks from the groups.

8. The system of claim 7 wherein the first stage coding processor generates the first set of output data blocks via MDS coding.

9. The system of claim 7 wherein first second coding processor generates the second set of output data blocks via MDS coding.

10. The system of claim 7 wherein the system includes storage nodes for maintaining the first set of output data blocks and the second set of output data blocks.

11. The system of claim 10 further comprising, a recovery mechanism that accesses the storage nodes to recover a copy of at least one data block.

12. The system of claim 11 wherein the blocks within a group and the data blocks computed therefrom comprise a coding group, and wherein the recovery mechanism includes logic that recovers a data block by using only other data blocks associated with that data block'"'"'s coding group when those other data blocks are sufficient to recover that data block.

13. The system of claim 12 wherein the logic recovers the data block by using at least one other data block that is not associated with that data block'"'"'s coding group when the other data blocks associated with that data block'"'"'s coding group are not sufficient for recovery.

14. The system of claim 10 wherein the second set of output data blocks includes a parity block that is generated from at least one parity block in the first set of output data blocks.

15. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising:

generating a first level of output data blocks (including one or more parity blocks) from original blocks;

partitioning the original blocks and at least one parity block from the first level into groups;

generating a second level of parity blocks from the groups, including generating at least one second level parity block from a first level parity block; and

maintaining the first level of output data blocks, and the second level of parity blocks among a plurality of nodes.

16. The one or more computer-readable media of claim 15 having further computer-executable instructions, comprising recovering a recovered data block by accessing at least two of the nodes.

17. The one or more computer-readable media of claim 16 wherein the blocks within a group and the data blocks computed therefrom comprise a coding group, and wherein recovering the recovered data block comprises accessing only other data blocks associated with that data block'"'"'s coding group to perform the recovery.

18. The one or more computer-readable media of claim 16 wherein the blocks within a group and the data blocks computed therefrom comprise a coding group, and wherein recovering the recovered data block comprises determining that one or more data blocks not associated with that data block'"'"'s coding group are needed to perform the recovery.

19. The one or more computer-readable media of claim 16 wherein generating the first level of one or more parity blocks from the original blocks comprises performing MDS erasure coding.

20. The one or more computer-readable media of claim 16 wherein generating the second level of parity blocks comprises performing MDS erasure coding.