Multicast collaborative erasure encoding and distributed parity protection

• US 9,923,970 B2
• Filed: 08/21/2015
• Issued: 03/20/2018
• 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
• Application Number:
  US14/832,075
• Publication Number:
  US 20160057226A1
• Time in Patent Office: 942 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 multicast collaborative erasure encoding of a chunk stored in a distributed object storage cluster, the method comprising:

multicasting a roll-call request to every storage server in a negotiating group for the chunk;

generating and multicasting roll-call inventory responses by every storage server in the negotiating group; and

collecting the roll-call inventory responses 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;

processing the set of roll-call inventory responses by every storage server in the negotiating group, wherein the processing diagnoses a state with a whole replica of the chunk held by at least one storage server and a replication count for erasure-encoded slices that is less than a target number of erasure-encoded slices; and

assigning actions to the storage servers holding a whole replica of the chunk to generate erasure-encoded slices and replicate the erasure-encoded slices to storage servers in the negotiating group that are selected to hold the slices.

2. The method of claim 1, wherein the roll-call request comprises:

an identifier for the negotiating group;

an identifier for the chunk; and

an identifier for the roll-call request.

3. The method of claim 2, wherein the roll-call request further comprises:

identification of a specific erasure-encoding algorithm to be used.

4. The method of claim 2, wherein a roll-call inventory response multicast by a storage server comprises:

the identifier for the roll-call request;

an identifier for the storage server;

whether a whole replica of the chunk is stored at the storage server; and

which, if any, erasure-encoded slices of the chunk are stored at the storage server.

5. The method of claim 1, wherein a roll-call inventory response that is missing due to not being collected by a storage server is ignored without a retransmission request.

6. The method of claim 1, wherein the processing begins after the roll-call inventory responses have been received from every storage server in the negotiating group or a predetermined time has elapsed.

7. The method of claim 1, further comprising:

each storage server in the negotiating group determining a subset of the actions to be performed by itself based on the set of roll-call inventory responses; and

each storage server in the negotiating group performing the subset of the actions to be performed by itself.

8. The method of claim 7, further comprising:

selection of a storage server in the negotiating group to multicast a new roll-call request for the chunk.

9. The method of claim 8, wherein the selection of the storage server in the negotiating group to multicast the new roll-call request comprises:

each storage server in the negotiating group pseudo-randomly selecting a time to multicast a new roll-call request for the chunk, wherein the new roll-call request is not issued if pre-empted by receipt of the new roll-call request as multicast by another storage server.

10. A distributed object storage system that stores objects in chunks, the system comprising:

a plurality of storage servers communicatively interconnected by a network; and

negotiating groups for the chunks,

wherein a negotiating group for a chunk comprises a group of the storage servers that are assigned to store and provide access to the chunk, and

wherein a storage server in the negotiating group for the chunk includes executable code that performs steps including;

multicasting a roll-call request to other storage servers in the negotiating group for the chunk;

collecting roll-call inventory responses received from the other storage servers in the negotiating group for the chunk to form a set of roll-call inventory responses;

processing the set of roll-call inventory responses, wherein the processing diagnoses a state with a whole replica of the chunk held by at least one storage server and a replication count for erasure-encoded slices that is less than a target number of erasure-encoded slices; and

assigning an action to the at least one storage server holding a whole replica of the chunk to generate an erasure-encoded slice and replicate the erasure-encoded slice to a storage server in the negotiating group that is selected to hold the slices.

11. The system of claim 10, wherein the executable code performs further steps including:

receiving the roll-call request from another storage server in the negotiating group; and

multicasting a roll-call inventory response to the negotiating group in response to the roll-call request.

12. The system of claim 11, wherein the roll-call request comprises:

an identifier for the negotiating group;

an identifier for the chunk;

an identifier for the roll-call request; and

identification of a specific erasure-encoding algorithm to be used.

13. The system of claim 11, wherein the roll-call inventory response comprises:

the identifier for the roll-call request;

an identifier for the storage server;

whether a whole replica of the chunk is stored at the storage server; and

which, if any, erasure-encoded slices of the chunk are stored at the storage server.

14. The system of claim 10, wherein the processing begins after the roll-call inventory responses have been collected from every storage server in the negotiating group or a predetermined time has elapsed.

15. The system of claim 10, wherein the executable code performs further steps including:

determining a subset of the actions to be performed by the storage server based on the set of roll-call inventory responses; and

performing the subset of the actions.

16. The system of claim 15, wherein one storage server in the negotiating group is selected to multicast a new roll-call request for the chunk.

17. The system of claim 16, wherein the selection of the one storage server in the negotiating group to multicast the new roll-call request comprises:

each storage server in the negotiating group pseudo-randomly selecting a time to multicast a new roll-call request for the chunk, wherein the new roll-call request is not issued if pre-empted by receipt of the new roll-call request as multicast by another storage server.