Granted Patent B2

US 10,019,317 · App. 15/137,920 · Granted Jul 10, 2018

Inventors: Ilya Usvyatsky (Northborough, MA); Caitlin Bestler (Sunnyvale, CA); Dmitry Yusupov (Cupertino, CA)

Assignee: Nexenta Systems, Inc.

G06F11/1092G06F11/1435G06F11/1453H03M13/1505H04L67/1095H04L67/1097

Abstract

Claims (52)

1. A method of generating a parity protection set in a distributed storage system containing a plurality of replicas of payload chunks, each of the replicas of payload chunks associated with a back-reference to one or more content manifests, the method comprising:

selecting a content manifest to be protected;

selecting a subset of all payload chunks referenced by the content manifest, wherein the subset is generated based on failure domain information;

generating one or more parity chunks using the subset of payload chunks;

generating a parity protection content manifest that refers to the parity protection set comprising the subset of payload chunks and the one or more parity chunks;

generating and storing a back-reference for the replica cited in the parity protection set for each payload chunk, wherein the back-reference is to the parity protection content manifest; and

erasing each back-reference to the content manifest for all remaining replicas of the subset of payload chunks, thereby enabling storage space in which the remaining replicas are stored to be used for future put requests.

2. The method of claim 1 , wherein the parity protection content manifest comprises one or more parity protection sets, each specifying a set of protected payload chunks, where for each protected payload chunk the following is specified:

an identifier for the protected payload chunk, including any scoping identifier which will optimize retrieval of this chunk;

an identifier for a failure domain where the protected payload chunk will be retained; and

the original length for the protected payload chunk.

3. The method of claim 2 , wherein the parity protection set further comprises:

an identifier of an algorithm used to generate each of the one or more parity protection chunks;

an identifier for each parity protection chunk, including any scoping identifiers required to optimize retrieval of the parity protection chunk; and

an identifier for a failure domain where the parity protection chunk will be retained.

4. The method of claim 3 , wherein each protected payload chunk and each parity protection chunk in the parity protection set are assigned to separate failure domains.

5. A method of generating a plurality of parity protection sets, the method comprising: performing the method of claim 1 for a plurality of content manifests.

6. A method of generating a parity protection set in a distributed storage system containing a plurality of replicas of payload chunks, each of the replicas of payload chunks associated with a back-reference to one or more content manifests, the method comprising:

identifying a content manifest to be protected;

identifying a subset of all payload chunks referenced by the content manifest, wherein the subset is generated based on failure domain information;

generating one or more parity chunks using the subset of payload chunks;

generating a parity protection content manifest that refers to the parity protection set comprising the subset of payload chunks and the one or more parity chunks;

generating a back-reference for the replica cited in the parity protection set for each payload chunk, wherein the back-reference is to the parity protection content manifest;

erasing each back-reference to the content manifest for all remaining replicas of the subset of payload chunks, thereby enabling storage space in which the remaining replicas are stored to be used for future put requests;

identifying a failure that invalidates a payload chunk in the parity protection set; and

regenerating the invalidated payload chunk using the remaining payload chunks and the one or more parity protection chunks in the parity protection set.

7. The method of claim 1 , wherein the step of generating one or more parity chunks comprising applying a Galois transformation using part or all of the subset of payload chunks.

8. The method of claim 5 , wherein the Galois transformation comprises applying an XOR operation to the subset of payload chunks.

9. A method of regenerating one or more invalidated payload chunks in each of a plurality of parity protection sets, the method comprising: performing the method of claim 6 for a plurality of parity protection sets.

10. A method of recovering a payload chunk in a distributed storage system, the method comprising:

determining that a payload chunk cannot be retrieved or validated in response to a get transaction associated with a content manifest referring to the payload chunk;

identifying a parity protection content manifest that refers to the payload chunk by using the content manifest or by analyzing back-references associated with the payload chunk;

selecting a first parity protection set which includes the payload chunk from the parity protection contest manifest;

attempting to regenerate the payload chunk using other payload chunks in the first parity protection set and one or more parity protection chunks in the parity protection set; and

if the attempting step fails, repeating the attempting step with other parity protection sets which include the payload chunk until the payload chunk is regenerated.

11. The method of claim 10 further comprising:

if the payload chunk is not regenerated after performing the attempting step with all parity protection sets containing the payload chunk referred to by the parity protection content manifest, declaring the payload chunk to be permanently lost to a client that initiated the get transaction.

12. A method of updating the retention tracking metadata for a parity protected chunk:

replace all back-references to the parity protection content manifest with a verified back-reference to the corresponding manifest;

generating one or more replicas of each payload chunk in the set of payload chunks; and

for each of the one or more replicas of the payload chunk, generating one or more back-references to the same content manifests referred to by back-references for the payload chunk.

13. A method for generating replica protection for a plurality of payload chunks referenced in a parity protection content manifest, the method comprising: performing the method of claim 12 for each protected chunk referenced in the parity protection content manifest.

14. A method of creating a new version of a parity-protected object in a distributed storage system, comprising:

generating a version manifest for the new version of the parity-protected object, wherein the version manifest refers to one or more payload chunks associated with the parity-protected object;

generating a put request for each of the one or more payload chunks associated with the parity-protected object;

in response to the put request for each of the one or more payload chunks associated with the parity-protected object, creating a speculative hold or extending a speculative hold on the payload chunk; and

for each of the one or more payload chunks associated with the parity-protected object, adding a back-reference to the version manifest for the new version of the parity-protected object.

15. A method of creating a new version of a parity-protected object in a distributed storage system, comprising:

generating a version manifest for the new version of the parity-protected object, wherein the version manifest refers to one or more payload chunks associated with the parity-protected object;

generating a put request for each of the chunks representing modified portions of the object, but not initiating put transactions for unmodified retained chunks;

creating a speculative hold on the prior version manifest to prevent the prior version manifest from being expunged until the process of protecting the retained chunks has been completed; and

for each of the one or more payload chunks associated with the parity-protected object, adding a back-reference to the version manifest for the new version of the parity-protected object.

Assignments (4)

Continuity (1)

Cited By (48)

US 12,197,390 US 12,204,413 US 12,204,768 US 12,204,788 US 12,212,624 US 12,216,903 US 12,229,402 US 12,229,437 US 12,235,743 US 12,236,117 US 12,242,425 US 12,253,922 US 12,253,941 US 12,271,264 US 12,271,359 US 12,277,106 US 12,282,799 US 12,293,111 US 12,314,131 US 12,314,163 US 12,314,170 US 12,314,183 US 12,340,107 US 12,341,848 US 12,366,972 US 12,373,289 US 12,373,340 US 12,379,854 US 12,393,340 US 12,393,353 US 12,430,053 US 12,430,059 US 12,439,544 US 12,475,041 US 12,481,442 US 12,487,920 US 12,511,239 US 12,524,309 US 12,547,317 US 12,561,093 US 12,572,421 US 12,619,469 US 12,682,949 US 12,687,973 US 12,699,512 US 12,717,709 US 12,724,670 US 12,730,571