Multicast collaborative erasure encoding and distributed parity protection

• US 10,244,053 B2
• Filed: 01/31/2018
• Issued: 03/26/2019
• Est. Priority Date: 08/22/2014
• Status: Active Grant

• Current Assignee: Nexenta by DDN, Inc.
• Original Assignee: Nexenta Systems Incorporated (DataDirect Networks Incorporated)
• Inventors: Bestler, Caitlin, Aizman, Alexander, Novak, Robert E.
• Primary Examiner(s): Hoang, Hieu T
• Application Number:
  US15/884,697
• Publication Number:
  US 20180152516A1
• Time in Patent Office: 419 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 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol

Abstract

The present disclosure provides methods and systems for multicast collaborative erasure encoding and methods and systems for distributed parity protection. One embodiment relates to a method of multicast collaborative erasure encoding of a chunk stored in a distributed object storage cluster. A roll-call request is multicast to every storage server in a negotiating group for the chunk. Roll-call inventory responses are generated and multicast by every storage server in the negotiating group. The roll-call inventory responses are collected by every storage server in the negotiating group from other storage servers in the negotiating group to form a set of roll-call inventory responses. A logical evaluation of the set of roll-call inventory responses may then be performed by every storage server in the negotiating group. Other embodiments, aspects and features are also disclosed.

Claims

1. A method of distributed parity protection of a chunk stored in an object storage cluster, the method comprising:

performing a process including sending a roll call request to store the chunk in a plurality of erasure-encoded slices at different storage servers in the object storage cluster, wherein the plurality of erasure-encoded slices include a plurality of data stripes and at least one parity stripe, wherein the roll call request is multicast to a sub-group of the plurality of storage servers, and wherein the roll call request identifies the chunk and requests identification of the erasure-encoded slices which are stored at the storage server receiving the request;

each storage server in the sub-group multicasting a roll-call inventory response to the sub-group, wherein the roll-call inventory response identifies which, if any, of the erasure-encoded slices are stored at the storage server which is responding;

collecting the roll-call inventory responses to the roll call request;

determining that a data stripe of the plurality of data stripes is lost;

determining surviving erasure-encoded slices of the plurality of erasure-encoded slices;

grouping the surviving erasure-encoded slices into a first set of pairs, wherein a first storage server holding a first slice of each pair sends the first slice to a second storage server holding a second slice of the pair; and

operating on first and second slices of each pair in the first set of pairs to generate a set of resultant slices, wherein the second storage server applies an operation on the first and second slices to generate a resultant slice.

2. The method of claim 1, further comprising:

further grouping slices in the set of resultant slices into a new set of pairs, wherein one storage server holding a first resultant slice of each pair sends the first resultant slice to a different storage server holding a second resultant slice of the pair; and

further operating on the first and second resultant slices of each pair in the new set of pairs to generate a new set of resultant slices, wherein said different storage server applies the operation on the first and second resultant slices to generate a new resultant slice.

3. The method of claim 2, further comprising:

repeating the further grouping and further operating steps a plurality of times until a single slice is generated, wherein the single slice is the data stripe that was lost.

4. The method of claim 1, wherein the operation is an exclusive-or operation.

5. The method of claim 1 further comprising:

each storage server in the sub-group receiving a set of roll-call inventory responses from other storage servers in the sub-group; and

each storage server in the sub-group determining actions to be performed by itself based on the set of roll-call inventory responses.

6. A distributed object storage system with distributed parity protection, the system comprising:

a network; and

a plurality of storage servers communicatively interconnected by the network,

wherein the plurality of storage servers includes executable code that performs steps including;

performing a process including sending a roll call request to store a chunk in a plurality of erasure-encoded slices at different storage servers, wherein the plurality of erasure-encoded slices include a plurality of data stripes and at least one parity stripe, wherein the roll call request is multicast to a sub-group of the plurality of storage servers, and wherein the roll call request identifies the chunk and requests identification of the erasure-encoded slices which are stored at the storage server receiving the request;

each storage server in the sub-group multicasting a roll-call inventory response to the sub-group, wherein the roll-call inventory response identifies which, if any, of the erasure-encoded slices are stored at the storage server which is responding;

collecting the roll-call inventory responses to the roll call request;

determining that a data stripe of the plurality of data stripes is lost;

determining surviving erasure-encoded slices of the plurality of erasure-encoded slices;

grouping the surviving erasure-encoded slices into a first set of pairs by sending a first erasure-encoded slice of each pair from a first storage server to a second storage server that holds a second erasure-encoded slice of each pair; and

operating on first and second slices of each pair in the first set of pairs to generate a set of resultant slices at the second storage server.

7. The system of claim 6, wherein the executable code performs further steps including:

further grouping slices in the set of resultant slices into a new set of pairs by sending a first erasure-encoded slice of each pair in the new set of pairs from one storage server to a different storage server that holds a second erasure-encoded slice of the pair; and

further operating on first and second slices of each pair in the new set of pairs to generate a new set of resultant slices at said different storage server.

8. The system of claim 7, wherein the executable code performs further steps including:

repeating the further grouping and further operating steps a plurality of times until a single slice is generated, wherein the single slice is the data stripe that was lost.

9. The system of claim 6, wherein the operation is an exclusive-or operation.

10. The system of claim 6, wherein each storage server in the sub-group receives a set of roll-call inventory responses from other storage servers in the sub-group and determines actions to be performed by itself based on the set of roll-call inventory responses.