Erasure coding across multiple zones and sub-zones
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.
1. A computer-implemented method suitable for use in a distributed computing environment utilizing a processor and a memory for implementing erasure encoding data across multiple storage zones, the method comprising:
dividing data into two or more data chunks, the two or more data chunks corresponding to two or more zones;
for each of the two or more zones:
dividing a data chunk corresponding to a zone, into a plurality of sub-fragments, each of the plurality sub-fragments associated with one of a plurality sub-zones; and
computing a plurality of reconstruction parities using the plurality of sub-fragments;
computing a plurality of cross-zone parities based on an exclusive-or using the plurality of sub-fragments and the plurality of reconstruction parities in the two or more zones, wherein the plurality of sub-fragments and the plurality of reconstruction parities are correspond across the two or more zones; and
assigning the plurality of cross-zone parities to a parity zone, wherein the plurality of cross-zone parities provide at least cross-zone reconstruction of a portion of the data.
2. The method of claim 1 , wherein computing the at least one cross-zone parity is based on an exclusive-or in a horizontal direction.
3. The method of claim 1 , wherein computing the plurality of reconstruction parities using the plurality of sub-fragments further comprises at least one local parity and at least one zone parity.
4. The method of claim 3 , wherein computing the at least one local parity is based on an exclusive-or in a horizontal direction and computing the at least one zone parity is based on an exclusive-or in a vertical direction.
5. The method of claim 3 , further comprising assigning the at least one local parity and the at least one zone parity to a parity sub-zone.
6. The method of claim 1 , further comprising: for each of the two or more zones, replacing an allocation for at least one zone parity with a replacement sub-fragment.
7. The method of claim 6 , further comprising:
computing a cross-zone parity based on an exclusive-or in a horizontal direction of each of the replacement sub-fragment in each of the two or more zones;
assigning the cross-zone parity to parity zone, wherein the cross-zone parity is located in a corresponding location in the parity zone.
8. A computer-implemented method suitable for use in a distributed computing environment utilizing a processor and a memory for implementing erasure encoding data across multiple storage zones, the method comprising:
dividing data into two or more data chunks, the two or more data chunks corresponding to two or more zones;
for each of the two or more zones:
dividing a data chunk corresponding to a zone, into a plurality of sub-fragments, each of the plurality sub-fragments associated with one of a plurality non-correlated sub-zones;
assigning correlated sub-zones to one or more subsets of the plurality of sub-fragments; and
computing at least one intra-zone reconstruction parity using the plurality of sub-fragments in the plurality of non-correlated sub-zones;
computing a plurality of cross-zone parities using the plurality of sub-fragments and the at least one intra-zone reconstruction parity in the two or more zones, wherein the plurality of sub-fragments and the at least one intra-zone reconstruction parity correspond across the two or more zones; and
assigning the plurality of cross-zone parities to a parity zone, wherein the plurality of cross-zone parities provide at least cross-zone reconstruction of a portion of the data.
9. The method of claim 8 , wherein computing the at least one intra-zone reconstruction parity is based on an exclusive-or in a horizontal direction.
10. The method of claim 8 , wherein each of the plurality of the correlated sub-zones is assigned to at least one sub-fragment in each zone.
11. The method of claim 8 , wherein each of the plurality of the correlated sub-zones is assigned to the plurality of sub-fragments located in a different position each zone.
12. The method of claim 8 , wherein computing the plurality of cross-zone parties is based on an exclusive-or in a vertical direction.
13. The method of claim 8 , further comprising: for each of the two or more zones, replacing an allocation for at least one sub-fragment with a replacement reconstruction parity.
14. The method of claim 13 , further comprising:
computing a cross-zone parity based on an exclusive-or in a horizontal direction of the replacement reconstruction parity;
assigning the cross-zone parity to parity zone, wherein the cross-zone parity is located in a corresponding location in the parity zone.
15. A computer-implemented method suitable for use in a distributed computing environment utilizing a processor and a memory for implementing erasure encoding data across multiple storage zones, the method comprising:
dividing data into two or more data chunks, the two or more data chunks corresponding to two or more zones;
for each of the two or more zones:
dividing a data chunk corresponding to a zone, into a plurality of sub-fragments, each of the plurality sub-fragments associated with one of a plurality sub-zones; and
computing a plurality of reconstruction parities using the plurality of sub-fragments, wherein the plurality of reconstruction parities include at least one intra-sub-zone reconstruction parity;
computing a plurality of cross-zone parities using the plurality of sub-fragments and the at least one intra-sub-zone reconstruction parity in the two or more zones; and
assigning the plurality of cross-zone parities to a parity zone, wherein the plurality of cross-zone parities provide at least cross-zone reconstruction of a portion of the data.
16. The method of claim 15 , wherein computing the at least one intra-sub-zone reconstruction parity is based on an exclusive-or in a horizontal direction within a selected sub-zone.
17. The method of claim 15 , wherein the plurality of reconstruction parities includes a plurality of global parities.
18. The method of claim 15 , wherein the plurality of cross-zone parities comprises inter-zone parities computed based on an exclusive-or in a vertical direction.
19. The method of claim 15 , further comprising: for each of the two or more zones, replacing computing the plurality of reconstruction parities using balanced local reconstruction code with frugal reconstruction code.
20. The method of claim 15 , further comprising:
computing a plurality of global parities using all sub-fragments from the one or more zones.