ERASURE CODING ACROSS MULTIPLE ZONES AND SUB-ZONES
First Claim
1. One or more 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 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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. One or more 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. One or more 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 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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 17, 20)
-
-
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. - View Dependent Claims (16, 18, 19)
-
Specification