Multicast raid: distributed parity protection

• US 10,216,577 B2
• Filed: 07/14/2016
• Issued: 02/26/2019
• Est. Priority Date: 07/14/2016
• Status: Active Grant

• Current Assignee: Nexenta by DDN, Inc.
• Original Assignee: Nexenta Systems Incorporated (DataDirect Networks Incorporated)
• Inventors: Bestler, Caitlin, Aizman, Alexander
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US15/210,501
• Publication Number:
  US 20180018229A1
• Time in Patent Office: 957 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

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.

Claims

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.