Erasure coding across multiple zones

• US 9,378,084 B2
• Filed: 06/25/2013
• Issued: 06/28/2016
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Calder, Bradley G., Gopalan, Parikshit Santhana, Huang, Cheng, Li, Jin, Ogus, Aaron W., Simitci, Huseyin, Yekhanin, Sergey
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US13/926,722
• Publication Number:
  US 20140380125A1
• Time in Patent Office: 1,099 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• 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/2909 Product codes
• CPC Class Codes: H03M 13/293 with erasure setting
• 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

Abstract

In various embodiments, methods and systems for erasure coding data across multiple storage zones are provided. This may be accomplished by dividing a data chunk into a plurality of sub-fragments. Each of the plurality of sub-fragments is associated with a zone. Zones comprise buildings, data centers, and geographic regions providing a storage service. A plurality of reconstruction parities is computed. Each of the plurality of reconstruction parities computed using at least one sub-fragment from the plurality of sub-fragments. The plurality of reconstruction parities comprises at least one cross-zone parity. The at least one cross-zone parity is assigned to a parity zone. The cross-zone parity provides cross-zone reconstruction of a portion of the data chunk.

Claims

1. One or more hardware computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform a method for erasure encoding data across multiple storage zones, the method comprising:

dividing a data chunk into a plurality of sub-fragments, each of the plurality sub-fragments associated with one of a plurality zones;

computing a plurality of reconstruction parities, each of the plurality of reconstruction parities computed using at least one sub-fragment from the plurality of sub-fragments, wherein the plurality of reconstruction parities is generated based on;

dividing the plurality of sub-fragments into a plurality of groups in a selected zone from the plurality of zones, each of the plurality of groups comprising one or more zone data-fragments in the selected zone; and

wherein for each zone from the plurality of zones;

computing a plurality local parities for each of the plurality of groups in the zone from a subset zone data-fragments in each of the plurality of groups;

computing a plurality of zone parities from the one or more zone data-fragments of the zone; and

computing a plurality of cross-zone parities using a plurality zone fragments comprising the one or more zone data-fragments; and

assigning the at least one cross-zone parity to a parity zone, wherein the cross-zone parity provides cross-zone reconstruction of a portion of the data chunk.

2. The media of claim 1, wherein computing the at least one cross-zone parity is based on an exclusive-or in a vertical direction.

3. The media of claim 1, wherein at least one of the at least cross-zone parities is computed using a combination of one or more zone-data fragments and one or more cross-zone parities.

4. The media of claim 1, wherein

the plurality of local parities, and the plurality of zone parities correspond in each of the plurality of zones, and wherein the plurality of cross-zone parities are assigned to the parity zone.

5. The media of claim 4, wherein the parity zone comprising the plurality of cross-zone parities is configured for in-zone reconstruction and cross-zone reconstruction based on local parities of the plurality of groups and zone parities in the parity zone.

6. The media of claim 1, further comprising:

dividing the plurality of sub-fragments into a plurality of groups in a selected zone from the plurality of zones, each of the plurality of groups comprising one or more zone data-fragments in the selected zone; and

computing the plurality of reconstruction parities, wherein for each zone from the plurality of zones;

computing a plurality local parities for each of the plurality of groups in the zone from a subset zone data-fragments in each of the plurality of groups;

computing an inter-zone parity from the one or more zone data fragments in each of the plurality of zones; and

computing a plurality of cross-zone parities using a plurality of zone fragments comprising the one or more zone data-fragments, the plurality of local parities, and the inter-zone parity corresponding in each of the plurality of zones, wherein the plurality of cross-zone parities are assigned to the parity zone.

7. The media of claim 6, wherein the parity zone comprising the plurality of cross-zone parities is configured for in-zone reconstruction and cross-zone reconstruction based on local parities and an inter-zone parity of the parity zone.

8. The media of claim 1, further comprising:

dividing the plurality of sub-fragments into a group in a selected zone from the plurality of zones, the group comprising one or more zone data-fragments in the selected zone; and

computing the plurality of reconstruction parities, wherein for each zone from the plurality of zones;

computing a local parity for the group in the zone from the one or more zone data-fragments in the group;

computing an inter-zone parity from the one or more zone data-fragments in each of the plurality of zones; and

computing a plurality of cross-zone parities using a plurality of zone fragments comprising the one or more zone data-fragments, the local parity, and the inter-zone parity corresponding in each of the plurality of zones, wherein the plurality of cross-zone parities are assigned to the parity zone.

9. The media of claim 8, wherein the parity zone comprising the plurality of cross-zone parities is configured for in-zone reconstruction and cross-zone reconstruction based on a local parity and an inter-zone parity of the parity zone.

10. The media of claim 1, further comprising:

dividing the plurality of sub-fragments into a plurality of groups in a selected zone from the plurality of zones, each of the plurality of groups comprising one or more zone data-fragments in the selected zone; and

computing the plurality of reconstruction parities, wherein for each zone from the plurality of zones;

computing a plurality of inter-zone parities from the one or more zone data-fragments in each of the plurality of zones; and

computing a plurality of cross-zone parities using a plurality of zone fragments comprising the one or more zone data-fragments and the plurality of inter-zone parities corresponding in each of the plurality of zones, wherein the plurality of cross-zone parities are assigned to the parity zone.

11. The media of claim 10, wherein the parity zone comprising the plurality of cross-zone parities is configured for cross-zone reconstruction based on a plurality of inter-zone parities.

12. A system for erasure encoding data across multiple storage zones, the system comprising:

an encoder component configured for;

dividing a data chunk into a plurality of sub-fragments, each of the plurality of sub-fragments having one or more zone data-fragments, wherein each of the plurality of sub-fragments is associated with one of a plurality of zones;

computing a plurality of reconstruction parities, each of the plurality of reconstruction parities computed using at least one sub-fragment from the plurality of sub-fragments, wherein the plurality of reconstruction parities comprises at least one cross-zone parity; and

assigning the at least one cross-zone parity to a parity zone, wherein the cross-zone parity provides cross-zone reconstruction of a portion of the data chunk; and

a reconstruction component configured for;

reconstructing data using the plurality of sub-fragments and the plurality of reconstruction parities, associated with the plurality of zones, wherein the data is reconstructed based on an erasure coding scheme of the data, and wherein recovering data for a first erasure coding scheme comprises;

providing local reconstruction within a recovery zone and maximum fault-tolerance across zones using local parities and zones parities;

for a second erasure coding scheme comprises;

providing local reconstruction within the recovery zone and maximum fault-tolerance across zones using local parities and inter-zone parities; and

for a third erasure coding scheme comprises;

providing maximum fault-tolerance across zones using inter-zone parities.

13. The system of claim 12, wherein the encoder component and the reconstruction component are implemented as part of a distributed computing environment supporting cloud computing.

14. The system of claim 12, wherein maximum fault-tolerance across zone is based on coding equations for a maximally recoverable property for failure patterns that are information-theoretically decodable.

15. The system of claim 12, wherein the multiple storage zones are associated with large-scale storage characteristics comprising at least one of:

network bandwidth between zones and likelihood of zone failure.

16. A computer-implemented method for selecting an erasure coding scheme for encoding data chunks across multiple storage zones, the method comprising:

providing a plurality of erasure coding schemes, wherein each of the plurality of erasure coding schemes is associated with a plurality of dimensions that define implementation constraints;

selecting an erasure coding scheme for encoding a data chunk based at least in part on the plurality of dimensions; and

encoding the data chunk using the erasure coding scheme selected, the erasure coding scheme divides the data chunk into a plurality of sub-fragments in one or more groups in a selected zone from the plurality of zones, each of the one or more groups comprising one or more zone data-fragments in the selected zone,

wherein a first selected erasure coding scheme is configured for;

for each zone of the plurality of zones;

computing in a horizontal direction a plurality local parities for each of the one or more groups in the zone from a subset zone data-fragments in each of the one or more groups in the zone;

computing in the horizontal direction a plurality of zone parities from the one or more zone data-fragments of the zone; and

computing in the vertical direction a plurality of cross-zone parities using a plurality zone fragments comprising the one or more zone data-fragments, the plurality of local parities, and the plurality of zone parities vertically corresponding in each of the plurality of zones, wherein the plurality of cross-zone parities are assigned to a corresponding position the parity zone;

wherein a second erasure coding scheme is configured for;

for each zone of the plurality of zones;

computing in the horizontal direction local parities for each of the one or more groups in the zone from a subset zone data-fragments in each of the one or more groups;

computing in the horizontal direction an inter-zone parity from the one or more zone data-fragments in each of the plurality of zones; and

computing in the vertical direction a plurality of cross-zone parities using a plurality of zone fragments comprising the one or more zone data-fragments, the plurality of local parities, and the inter-zone parity vertically corresponding in each of the plurality of zones, wherein the plurality of cross-zone parities are assigned to a corresponding position the parity zone;

wherein a third erasure coding scheme is configured for;

for each zone from the plurality of zones;

computing in a horizontal direction a plurality of inter-zone parities from the one or more zone data-fragments in each of the plurality of zones; and

computing in a vertical direction a plurality of cross-zone parities using a plurality of zone fragments comprising the one or more zone data-fragments and the plurality of inter-zone parities vertically corresponding in each of the plurality of zones, wherein the plurality of cross-zone parities are assigned to a corresponding position the parity zone.

17. The computer-implemented method of claim 16, wherein the parity zone comprising the plurality of cross-zone parities is configured for reconstruction of the data chunk based on the plurality of dimensions associated with the erasure coding scheme selected for the data chunk.

18. The computer-implemented method of claim 16, wherein a first dimension comprises the total amount of physical storage to store data chunks and the amount of network bandwidth provisioned to support the multiple storage zones.

19. The computer-implemented method of claim 16, wherein a second dimension comprises the number of I/Os that read one unit of data chunks from a failed storage node and the number of I/Os that read one unit of data chunks from a failed zone.

20. The computer-implemented method of claim 16, wherein a third dimension comprises a mean time to data loss.