Layered data redundancy coding techniques for layer-local data recovery
First Claim
Patent Images
1. A computer-implemented method, comprising:
- processing archives to be stored on a set of volumes, by at least;
applying a redundancy code to the archives to generate a plurality of shards, a first subset of which include original data of the archives, and a second subset of which includes encoded shards derived from the original data;
layering the plurality of shards into a plurality of groups such that;
a first group of the plurality of groups includes a portion of the first subset of shards and a portion of the second portion of shards; and
a second group that includes at least a portion of a remainder of the plurality of shards not in the first group;
associating the first group with a first subset of the set of volumes, the first subset of the set of volumes being associated with a first data storage facility of a plurality of data storage facilities;
associating the second group with at least a second subset of the set of volumes, the second subset of the set of volumes being associated with a second data storage facility of the plurality of data storage facilities; and
applying a redundancy code to the first group to generate additional shards;
adding the additional shards to the first group; and
storing the first group, including the additional shards, and the second group on the first subset of the set of volumes and the second subset of the set of volumes, respectively, to enable regeneration of any shard in the first group using only shards stored in the first data storage facility.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques and methods for generating and implementing multiple layers of redundancy coded data are disclosed. For example, a redundancy coding scheme may include data elements that include data that is unencoded relative to the input, yet may still fully participate in providing redundancy to any data element in a given set. In a layered scheme, the input may include a bundle or group of encoded (or unencoded) data elements, thereby nesting two or more layers of redundancy coding. The specific amount of redundancy generated by such a scheme may be adjusted and adapted to failure characteristics of the entity on which the data elements are stored.
160 Citations
20 Claims
-
1. A computer-implemented method, comprising:
-
processing archives to be stored on a set of volumes, by at least; applying a redundancy code to the archives to generate a plurality of shards, a first subset of which include original data of the archives, and a second subset of which includes encoded shards derived from the original data; layering the plurality of shards into a plurality of groups such that; a first group of the plurality of groups includes a portion of the first subset of shards and a portion of the second portion of shards; and a second group that includes at least a portion of a remainder of the plurality of shards not in the first group; associating the first group with a first subset of the set of volumes, the first subset of the set of volumes being associated with a first data storage facility of a plurality of data storage facilities; associating the second group with at least a second subset of the set of volumes, the second subset of the set of volumes being associated with a second data storage facility of the plurality of data storage facilities; and applying a redundancy code to the first group to generate additional shards; adding the additional shards to the first group; and storing the first group, including the additional shards, and the second group on the first subset of the set of volumes and the second subset of the set of volumes, respectively, to enable regeneration of any shard in the first group using only shards stored in the first data storage facility. - View Dependent Claims (2, 3, 4)
-
-
5. A system, comprising:
at least one computing device that implements one or more services, wherein the one or more services at least; group a plurality of redundancy coded shards associated with archives into a plurality of groups such that; a first group of the plurality of groups includes a first subset of the shards to be stored on a first data storage entity, and a second group of the plurality of groups includes a second subset of the shards to be stored on at least a second data storage entity; and process the first group of shards by applying a redundancy code to the shards so as to generate additional shards; and store the first group of shards with the additional shards on the first data storage entity to enable the first data storage entity to rebuild any unavailable shards of the first group of shards without the use of any of the second group of shards. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12)
-
13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, upon execution by one or more processors of a computer system, cause the computer system to at least:
-
layer a plurality of redundancy coded shards associated with archives into a plurality of groups, of which a first group includes a first subset of the shards to be stored on a first data storage entity, and of which a second group includes a second subset of the shards to be stored on a second data storage entity; process, based at least in part on the shards of the first group of shards, the first group of shards to generate additional shards; add the additional shards to the first group; store the first group of shards including the additional shards on the first data storage entity, and the second group of shards on the second data storage entity, such that the first data storage entity is capable of regenerating unavailable shards of the first group using only the first group of shards including the additional shards. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification