PRECOMPUTED REDUNDANCY CODE MATRICES FOR HIGH-AVAILABILITY DATA STORAGE

摘要

Techniques described and suggested herein include systems and methods for precomputing regeneration information for data archives (“archives”) that have been processed and stored using redundancy coding techniques. For example, regeneration information, such as redundancy code-related matrices (such as inverted matrices based on, e.g., a generator matrix for the selected redundancy code) corresponding to subsets of the shards, is computed for each subset and, in some embodiments, stored for use in the event that one or more shards becomes unavailable, e.g., so as to more efficiently and/or quickly regenerate a replacement shard.

主权项

1. A computer-implemented method, comprising:
under the control of one or more computer systems configured with executable instructions,
receiving a first request to store an archive;encoding, using a redundancy code, original data of the archive into a plurality of shards;determining, from the plurality of shards and the redundancy code, at least one regeneration set, the regeneration set consisting of a subset of the plurality of shards and having a number of members equal to or greater than a minimum quorum of the plurality of shards sufficient to regenerate the original data;computing one or more matrices for the regeneration set, the one or more matrices capable of being used with the corresponding subset of the plurality of shards to regenerate the original data;storing the computed matrices and the plurality of shards;in response to a second request, retrieving a matrix of the stored matrices that corresponds to a regeneration set associated with the second request; andregenerating one or more shards associated with the second request using the retrieved matrix and the corresponding regeneration set.