Erasure coding across multiple zones

Patent metadata

Field	Value
Publication number	US-9378084-B2
Application number	US-201313926722-A
Country	US
Kind code	B2
Filing date	Jun 25, 2013
Priority date	Jun 25, 2013
Publication date	Jun 28, 2016
Grant date	Jun 28, 2016

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.

First claim

The invention claimed is:

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 stor

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Calder Bradley G
• Gopalan Parikshit Santhana
• Huang Cheng
• Li Jin
• Ogus Aaron W
• Simitci Huseyin
• Yekhanin Sergey

Classifications

• G06F11/10 Primary

  Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's · CPC title

• H03M13/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 title

• H03M13/293

  with erasure setting · CPC title

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/2909

  Product codes · CPC title