Multicast Raid: Distributed Parity Protection
AssigneeNexenta Systems, Inc.
InventorsCaitlin BESTLER, Alexander AIZMAN
Life of this patent
Estimating the term…
Abstract
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.
Claims9
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 that 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 the failure domain where the primary whole replica of that chunk should be stored, wherein the 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 the put message;
- generating a payload portion of a parity protection conglomerate comprising 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 the 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 newly protected chunk.
A method for extending the protection provided by an error correcting scheme which protects against the loss of more than a single member of the protection set by creating multiple parity protection sets which protect chunks in non-overlapping failure domains.
A method of generating up to N parity protection conglomerates protecting a first chunk, the method comprising:
- receiving, by a first set of storage servers, a put request for the first chunk, the put request indicating that a replica of the first chunk is to be stored and N parity protection conglomerates are to be generated and stored, where N is an integer greater than 1;
- receiving, by a gateway, responses from each storage server in the first set of storage servers, each response indicating a first state or a second state for the storage server, wherein the first state is that the chunk is already stored by the storage server and the second state is that the storage server can store a parity protection conglomerate, and wherein for the second state the response comprises an eligibility set map, wherein the eligibility set map identifies a parity protection conglomerate that would be used to satisfy the put request;
- selecting, by the gateway, a second set of storage servers, the second set of storage servers comprising N+1 storage servers from the first set of storage servers, wherein the eligibility maps for the second set of storage servers contain no more than one common failure domain;
- all storage targets releasing any tentative reservation made on the parity protection chunks reserved by their put response message with the exception of the parity protection chunk selected to be the primary parity protection chunk;
- the gateway delivering the payload chunk to each of the selected targets either by multicast or unicast messaging;
- the storage target assigned the role of providing the primary replica saving the received chunk as a whole replica of the chunk to persistent memory before acknowledging the transaction;
- the storage target assigned the role of providing the primary parity protection creating a new parity protection chunk with a parity protection conglomerate identifier (PPCID);
- the storage targets assigned the role of providing non-primary parity protection selecting parity protection chunks, wherein eligibility sets for the second set of storage servers contain no more than one common failure domain;
- second role to a second storage server within the second set of storage servers to store a primary parity protection chunk protecting the chunk;
- assigning, but the gateway, a third role to the remaining storage servers within the second set of storage servers to store a parity protection chunk protecting the chunk;
- and
- sending, by the gateway, a message to the second set of storage servers identifying the role assigned to each storage server within the second set of storage servers.
A method of retrieving a protected chunk from a parity protection chunk;
- the method comprising:
- receiving a get request for a requested chunk;
- determining that a whole replica of the requested chunk is not available during a predetermined time period;
- identifying a parity protection chunk protecting the requested chunk, wherein each portion of the parity protection chunk is available for retrieval;
- retrieving the parity protection chunk;
- obtaining the requested chunk from the parity protection chunk by performing a Galois transformation on the parity protection chunk and whole replicas of other chunks protected by the parity protection chunk;
- and
- providing the requested chunk to satisfy the get request.
Dependencies are inferred from the claim text.