Multicast raid: distributed parity protection
The present invention introduces a specific form of parity protection chunk (PPC) that allows for distributed creation of coordinated PPCs that can reliably provide protection against the concurrent loss of two or more storage servers of devices. Coordinated PPCs can protect against the concurrent loss of multiple lost chunks by ensuring that the PPCSs protecting any specific chunk have at most a single overlapping failure domain. This is done without requiring full centralized control over the assignment of protected chunks to specific PPCs. The PPCs are created as part of the put transaction for a chunk. The chunk itself is stored as a whole replica, and the PPCs provide parity protection for the chunk.
1. A method for a storage server to create a parity protection conglomerate protecting a received chunk, comprising:
generating a manifest within a parity protection conglomerate, wherein the manifest enumerates: a set of chunks protected by the parity protection conglomerate, including the received chunk; a previously-generated unique chunk identifier for each chunk in the set of chunks; and a failure domain where the primary whole replica of that chunk should be stored, wherein a selection of the parity protection conglomerate by the storage server is constrained such that the created parity protection conglomerate references only chunks contained in failure domains enumerated in an eligibility set specified with a put message;
generating a payload portion of a parity protection conglomerate, wherein the payload portion comprises a Galois transformation of a payload portion of each chunk within the set of chunks, thereby protecting the received chunk as a protected chunk;
updating a local index to map a parity protection conglomerate identifier (PPCID) to the previously-generated unique chunk identifier of the parity protection conglomerate;
generating a protection index entry to map a chunk identifier of the received chunk to the PPCID; and
reducing an eligibility set associated with the PPCID to exclude all failure domains that were not contained in the eligibility set specified for the received chunk.
2. The method of claim 1 , wherein the Galois transform comprises an Exclusive-OR (XOR) operation.
3. The method of claim 1 , further comprising:
initializing, by the storage server, a new parity protection conglomerate with a new PPCID if there are no existing parity protection conglomerates that comply with the eligibility set associated with the first chunk; and
generating an eligibility set for the new parity protection conglomerate to include the same failure domains specified in the eligibility set associated with the first chunk without the failure domain containing the protected chunk.