Erasure coded storage aggregation in data centers

• US 8,458,287 B2
• Filed: 07/31/2009
• Issued: 06/04/2013
• Est. Priority Date: 07/31/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ozzie, Raymond E., Mehr, John D., Puri, Siddhartha, McKelvie, Samuel J., Calder, Bradley, Pope, Matt
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): SHAW, ROBERT A
• Application Number:
  US12/534,024
• Publication Number:
  US 20110029840A1
• Time in Patent Office: 1,404 Days
• Field of Search: 709/217
• US Class Current: 709/217
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics

Abstract

Embodiments of erasure coded storage aggregation are disclosed. The erasure coded storage aggregation includes storing a data file as erasure coded fragments in a plurality of nodes of one or more data centers. The erasure coded storage aggregation further includes monitoring an access frequency of the data file. Based on the comparison between the access frequency and a predetermined threshold, the data file is either reconstructed from the erasure coded fragments and stored in a storage node or retained as erasure coded fragments in the plurality of nodes of the one or more data centers.

Claims

1. One or more device memories storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

selecting, by one or more processors configured with executable instructions, a first plurality of nodes of at least one data center to store a data file as a first set of erasure coded fragments;

storing the data file as the first set of erasure coded fragments in the first plurality of nodes of the at least one data center;

monitoring, during a first time period, a first access frequency of the data file that is stored as the first set of erasure coded fragments;

determining that the first access frequency of the data file meets or exceeds a first predetermined frequency threshold during the first time period or after the first time period expires;

reconstructing the data file from at least a portion of the first set of erasure coded fragments after determining that the first access frequency of the data file meets or exceeds the first predetermined frequency threshold;

storing the reconstructed data file in a storage node;

monitoring, during a second time period, a second access frequency of the reconstructed data file that is stored in the storage node;

determining that the second access frequency of the reconstructed data file is below a second predetermined frequency threshold during the second time period or after the second time period expires;

selecting a second plurality of nodes to store the reconstructed data file as a second set of erasure coded fragments, wherein the second plurality of nodes is different than the first plurality of nodes; and

storing the reconstructed data file as the second set of erasure coded fragments in the second plurality of nodes after determining that the second access frequency of the reconstructed data file is below the second predetermined frequency threshold.

2. The one or more device memories of claim 1, wherein the storing the data file as the first set of erasure coded fragments further includes performing hierarchical erasure coding on the data file to obtain erasure coded fragments of the data file.

3. The one or more device memories of claim 1, wherein the reconstructing the data file further includes:

retrieving at least some of the first set of erasure coded fragments from the first plurality of nodes; and

reconstructing the data file from the retrieved at least some of the first set of erasure coded fragments.

4. The one or more device memories of claim 3, wherein the acts further comprise:

receiving the data file from a client device prior to storing the data file as the first set of erasure coded fragments;

receiving an instruction to retrieve the data file from the client device; and

providing the reconstructed data file to the client device.

5. The one or more device memories of claim 3, wherein the acts further comprise storing metadata in multiple locations of the first plurality of nodes, and wherein the retrieving includes retrieving the at least some of the first set of erasure coded fragments using the stored metadata.

6. The one or more device memories of claim 1, wherein the acts further comprise selecting the first plurality of nodes from one or more computation nodes or one or more storage nodes.

7. The one or more device memories of claim 1, wherein the acts further comprise selecting the first plurality of nodes from available nodes on the at least one data center, each of the selected first plurality of nodes being selected based at least in part on an estimated availability, an estimated health status or a proximity to another selected node.

8. The one or more device memories of claim 1, wherein the plurality of nodes comprises a first plurality of nodes, and wherein the acts further comprise:

monitoring an integrity of each of the first set of erasure coded fragments that are stored in the first plurality of nodes; and

reconstructing the data file when the monitoring determines that a predetermined quantity of the first set of erasure coded fragments with a valid integrity is less than a predetermined minimal threshold.

18. The one or more device memories of claim 1, wherein the first predetermined frequency threshold and the second predetermined frequency threshold are a same threshold.

19. The one or more device memories of claim 1, wherein the first predetermined frequency threshold and the second predetermined frequency threshold are a different threshold.

9. A method comprising:

selecting, by one or more processors configured with executable instructions, a first plurality of nodes of at least one data center to store a data file as a first set of erasure coded fragments;

storing the data file as the first set of erasure coded fragments in the first plurality of nodes of the at least one data center;

monitoring, during a first time period, a first access frequency of the data file that is stored as the first set of erasure coded fragments;

determining that the first access frequency of the data file meets or exceeds a first predetermined frequency threshold during the first time period or after the first time period expires;

reconstructing the data file from at least a portion of the first set of erasure coded fragments after determining that the first access frequency of the data file meets or exceeds the first predetermined frequency threshold;

storing the reconstructed data file in a storage node;

monitoring, during a second time period, a second access frequency of the reconstructed data file that is stored in the storage node;

determining that the second access frequency of the reconstructed data file is below a second predetermined frequency threshold during the second time period or after the second time period expires;

selecting a second plurality of nodes to store the reconstructed data file as a second set of erasure coded fragments, wherein the second plurality of nodes is different than the first plurality of nodes; and

storing the reconstructed data file as the second set of erasure coded fragments in the second plurality of nodes after determining that the second access frequency of the reconstructed data file is below the second predetermined frequency threshold.

10. The method of claim 9, wherein the storing the data file as the first set of erasure coded fragments comprises performing hierarchical erasure coding on the data file to obtain erasure coded fragments of the data file.

11. The method of claim 9, wherein the reconstructing the data file comprises:

retrieving at least some of the first set of erasure coded fragments from the first plurality of nodes; and

reconstructing the data file from the retrieved at least some of the first set of erasure coded fragments.

12. The method of claim 11, further comprising:

receiving the data file from a client device prior to storing the data file as the first set of erasure coded fragments;

receiving an instruction to retrieve the data file from the client device; and

providing the reconstructed data file to the client device.

13. The method of claim 11, further comprising storing metadata in multiple locations of the first plurality of nodes, and wherein the retrieving includes retrieving the at least some of the first set of erasure coded fragments using the stored metadata.

14. The method of claim 9, further comprising selecting the first plurality of nodes from one or more computation nodes or one or more storage nodes.

15. The method of claim 9, further comprising selecting the first plurality of nodes from available nodes on the at least one data center, each of the selected first plurality of nodes being selected based at least in part on an estimated availability, an estimated health status or a proximity to another selected node.

16. The method of claim 9, further comprising:

monitoring an integrity of each of the first set of erasure coded fragments that are stored in the first plurality of nodes; and

reconstructing the data file when monitoring the integrity determines that a predetermined quantity of the first set of erasure coded fragments with a valid integrity is less than a predetermined minimal threshold.

17. The method of claim 9, wherein the first plurality of nodes and the second plurality of nodes include at least one different node.

20. The method of claim 9, wherein the first predetermined frequency threshold and the second predetermined frequency threshold are a same threshold.