System and method for erasure encoding

• US 8,099,549 B1
• Filed: 12/31/2007
• Issued: 01/17/2012
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Madnani, Kiran, Shain, Randall H., Clark, Roy E.
• Primary Examiner(s): Ellis, Kevin
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US11/967,898
• Time in Patent Office: 1,478 Days
• Field of Search: 370/312, 370/390, 707/999.01, 711/114, 711/162
• US Class Current: 711/114
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• 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]

Abstract

A method and computer program product for defining a multicast group within a local area network. The multicast group includes a storage initiator device, a plurality of storage targets, and one or more coded targets. A write request for storing a data segment within the multicast group is received on the storage initiator device. The data segment is multicast to the plurality of storage targets and the one or more coded targets included within the multicast group. A unique data chunk of the data segment is stored on each of the plurality of storage targets. A unique coded chunk of the data segment is generated and stored on each of the one or more coded targets.

Claims

1. A multicast data striping method comprising:

defining a multicast group within a local area network, wherein the multicast group includes a storage initiator device, a plurality of storage targets, and one or more coded targets, wherein the one or more coded targets includes a distributed coded target;

receiving, on the storage initiator device, a write request for storing a data segment within the multicast group;

multicasting the data segment to the plurality of storage targets and the one or more coded targets included within the multicast group;

storing a unique data chunk of the data segment on each of the plurality of storage targets; and

generating and storing a unique coded chunk of the data segment on each of the one or more coded targets.

2. The multicast data striping method of claim 1 wherein defining the multicast group includes one or more of:

defining a group of IP addresses to be addressable as a whole by a single multicast IP address; and

defining a group of MAC addresses to be addressable as a whole by a single multicast IP address.

3. The multicast data striping method of claim 1 further comprising:

generating the unique coded chunk using one or more of the unique data chunks.

4. The multicast data striping method of claim 3 wherein generating the unique coded chunk using one or more of the unique data chunks includes:

generating, on the one or more coded targets, the unique coded chunk using one or more of the unique data chunks.

5. The multicast data striping method of claim 1 wherein at least one of the plurality of storage targets is chosen from the group consisting of:

a hard drive;

a RAID array of hard drives;

a computer device including one or more hard drives; and

a server computer.

6. A computer program product residing on a computer readable medium having a plurality of instructions stored thereon which, when executed by a processor, cause the processor to perform operations comprising:

defining a multicast group within a local area network, wherein the multicast group includes a storage initiator device, a plurality of storage targets, and one or more coded targets, wherein the one or more coded targets includes a distributed coded target;

receiving, on the storage initiator device, a write request for storing a data segment within the multicast group;

multicasting the data segment to the plurality of storage targets and the one or more coded targets included within the multicast group;

storing a unique data chunk of the data segment on each of the plurality of storage targets; and

generating and storing a unique coded chunk of the data segment on each of the one or more coded targets.

7. The computer program product of claim 6 wherein the instructions for defining the multicast group include instructions for one or more of:

defining a group of IP addresses to be addressable as a whole by a single multicast IP address; and

defining a group of MAC addresses to be addressable as a whole by a single multicast IP address.

8. The computer program product of claim 6 further comprising instructions for:

generating the unique coded chunk using one or more of the unique data chunks.

9. The computer program product of claim 8 wherein the instructions for generating the unique coded chunk using one or more of the unique data chunks include instructions for:

generating, on the one or more coded targets, the unique coded chunk using one or more of the unique data chunks.

10. The computer program product of claim 6 wherein at least one of the plurality of storage targets is chosen from the group consisting of:

a hard drive;

a RAID array of hard drives;

a computer device including one or more hard drives; and

a storage area network.

11. A multicast data striping method comprising:

defining a multicast group within a local area network, wherein the multicast group includes a storage initiator device, a plurality of storage targets, and one or more coded targets, wherein the one or more coded targets includes a distributed coded target;

receiving, on the storage initiator device, a read request for reading a data segment from the multicast group;

multicasting the read request to the plurality of storage targets and the one or more coded targets included within the multicast group;

receiving, on the storage initiator device, one or more unique data chunks of the data segment from the plurality of storage targets; and

receiving, on the storage initiator device, a unique coded chunk of the data segment from each of the one or more coded targets.

12. The multicast data striping method of claim 11 wherein defining the multicast group includes one or more of:

defining a group of IP addresses to be addressable as a whole by a single multicast IP address; and

defining a group of MAC addresses to be addressable as a whole by a single multicast IP address.

13. The multicast data striping method of claim 11 wherein at least one of the plurality of storage targets is chosen from the group consisting of:

a hard drive;

a RAID array of hard drives;

a computer device including one or more hard drives; and

a storage area network.

14. The multicast data striping method of claim 11 further comprising:

combining, on the storage initiator device, the unique data chunks received from the plurality of storage targets to reconstruct the data segment.

15. The multicast data striping method of claim 11 further comprising:

if the unique data chunks received from the plurality of storage targets are insufficient to reconstruct the data segment, regenerating one or more missing data chunks using one or more of;

the unique data chunks received from the plurality of storage targets; and

the unique coded chunk received from each of the one or more coded targets.

16. A computer program product residing on a computer readable medium having a plurality of instructions stored thereon which, when executed by a processor, cause the processor to perform operations comprising:

defining a multicast group within a local area network, wherein the multicast group includes a storage initiator device, a plurality of storage targets, and one or more coded targets, wherein the one or more coded targets includes a distributed coded target;

receiving, on the storage initiator device, a read request for reading a data segment from the multicast group;

multicasting the read request to the plurality of storage targets and the one or more coded targets included within the multicast group;

receiving, on the storage initiator device, one or more unique data chunks of the data segment from the plurality of storage targets; and

receiving, on the storage initiator device, a unique coded chunk of the data segment from each of the one or more coded targets.

17. The computer program product of claim 16 wherein the instructions for defining the multicast group include one or more of:

defining a group of IP addresses to be addressable as a whole by a single multicast IP address; and

defining a group of MAC addresses to be addressable as a whole by a single multicast IP address.

18. The computer program product of claim 16 wherein at least one of the plurality of storage targets is chosen from the group consisting of:

a hard drive;

a RAID array of hard drives;

a computer device including one or more hard drives; and

a storage area network.

19. The computer program product of claim 16 further comprising instructions for:

combining, on the storage initiator device, the unique data chunks received from the plurality of storage targets to reconstruct the data segment.

20. The computer program product of claim 16 further comprising instructions for:

if the unique data chunks received from the plurality of storage targets are insufficient to reconstruct the data segment, regenerating one or more missing data chunks using one or more of;

the unique data chunks received from the plurality of storage targets; and

the unique coded chunk received from each of the one or more coded targets.