Erasure coding for elastic cloud storage

Patent metadata

Field	Value
Publication number	US-10152248-B2
Application number	US-201615193407-A
Country	US
Kind code	B2
Filing date	Jun 27, 2016
Priority date	Dec 25, 2015
Publication date	Dec 11, 2018
Grant date	Dec 11, 2018

Abstract

Systems and methods for efficiently protecting data within a distributed storage system using erasure coding. Unnecessary network traffic can be eliminated by scheduling executing erasure coding tasks on storage nodes that have local copies of data. Encoding may be performed in parallel by multiple nodes to reduce elapsed encoding time.

First claim

What is claimed is:

1. A method for use with a distributed storage system comprising a plurality of storage nodes each having attached storage devices, the method comprising:
receiving a request from a client to store data;
storing a copy of the data within the storage devices attached to a first storage node;
storing a copy of the data within the storage devices attached to a second storage node;
returning an acknowledgement to the client in response to the request the acknowledgment being returned after a threshold number of copies is stored on storage devices attached to at least some of the plurality of storage nodes, the threshold number being greater than one;
scheduling a first erasure encoding task on the first storage node;
scheduling a second erasure encoding task on the second storage node;
executing, on the first storage node, the first erasure encoding task to generate a first plurality of coded fragments using the copy of the data stored within attached storage devices, the first erasure encoding task being executed after the acknowledgement is returned;
executing, on the second storage node, the second erasure encoding task to generate a second plurality of coded fragments using the copy of the data stored within attached storage devices, the second erasure encoding task being executed after the acknowledgement is returned; and
storing the first and second pluralities of coded fragments within storage devices attached to at least two different storage nodes.

2. The method of claim 1 wherein returning an acknowledgement to the client occurs before scheduling the first or second erasure encoding tasks.

3. The method of claim 1 further comprising:
dividing the data into a plurality of data fragments; and
storing the plurality of data fragments within storage devices attached to at least two different storage nodes.

4. The method of claim 3 wherein the at least two different storage nodes in which the data fragments are stored are each different from the at least two different storage nodes in which the first and second pluralities of coded fragments are stored.

5. The method of claim 3 wherein the data fragments each have the same size.

6. The method of claim 1 further comprising:
deleting the copy of the data from the storage devices attached to the first storage node; and
deleting the copy of the data from the storage devices attached to the second storage node.

7. The method of claim 1 wherein the first and second erasure encoding tasks are executed in parallel.

8. The method of claim 1 wherein scheduling the first erasure encoding task on the first storage node comprises adding the first erasure encoding task to a queue within the first storage node.

9. The method of claim 1 , wherein the first erasure encoding task is executed based on a distribution matrix including one or more first portions and one or more second portions, each of the first portions including a respective identity matrix, and each of the second portions including a respective coding matrix.

10. A distributed storage system, comprising:
a plurality of storage nodes having attached storage devices;
a first storage node from the plurality of storage nodes having attached storage devices and configured to:
receive a request from a client to store data;
store a copy of the data within the storage devices attached to a second storage node;
store a copy of the data within the storage devices attached to a third storage node;
return an acknowledgement to the client in response to the request, the acknowledgment being returned after a threshold number of copies is stored on storage devices attached to at least some of the plurality of storage nodes the threshold number being greater than one;
schedule a first erasure encoding task on the second storage node; and
schedule a second erasure encoding task on the third storage node;
the second storage node from the plurality of storage nodes having attached storage devices and configured to:
execute the first erasure encoding task to generate a first plurality of coded fragments using the copy of the data stored within attached storage devices, the first erasure encoding task being executed after the acknowledgement is returned; and
store the first plurality of coded fragments within storage devices attached to at least two different storage nodes; and
the third storage node from the plurality of storage nodes having attached storage devices and configured to:
execute the second erasure encoding task to generate a second plurality of coded fragments using the copy of the data stored within attached storage devices, the second erasure encoding task being executed after the acknowledgement is returned; and
store the second plurality of coded fragments within storage devices attached to at least two different storage nodes.

11. The distributed storage system of claim 10 wherein the first storage node is configured to return an acknowledgement to the client occurs before scheduling the first or second erasure encoding tasks.

12. The distributed storage system of claim 10 wherein the first storage node is configured to:
divide the data into a plurality of data fragments; and
store the plurality of data fragments within storage devices attached to at least two different storage nodes.

13. The distributed storage system of claim 12 wherein the at least two different storage nodes in which the data fragments are stored are each different from the at least two different storage nodes in which the first and second pluralities of coded fragments are stored.

14. The distributed storage system of claim 12 wherein the data fragments each have the same size.

15. The distributed storage system of claim 10 wherein the second storage node is further configured to delete the copy of the data from the storage devices attached to the first storage node and wherein the third storage node is further configured to delete the copy of the data from the storage devices attached to the second storage node.

16. The distributed storage system of claim 10 wherein the first and second erasure encoding tasks are executed in parallel.

17. The distributed storage system of claim 10 wherein the first storage node is configured to add the first erasure encoding task to a queue within the second storage node.

18. The system of claim 10 , wherein the first erasure encoding task is executed based on a distribution matrix including one or more first portions and one or more second portions, each of the first portions including a respective identity matrix, and each of the second portions including a respective coding matrix.

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Trusov Maxim
• Tchoub Ivan
• Skripko Gregory
• Prikhodko Vladimir

Classifications

• H04L67/32

  Electricity · mapped topic

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0619 Primary

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F3/065

  Replication mechanisms · CPC title

• H04L67/1097 Primary

  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 title