Systems and methods for reliably storing data using liquid distributed storage

• US 9,594,632 B2
• Filed: 12/11/2014
• Issued: 03/14/2017
• Est. Priority Date: 07/09/2014
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Luby, Michael George
• Primary Examiner(s): Guyton, Philip
• Application Number:
  US14/567,249
• Publication Number:
  US 20160011939A1
• Time in Patent Office: 824 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• 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 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

Embodiments provide methodologies for reliably storing data within a storage system using liquid distributed storage control. Such liquid distributed storage control operates to compress repair bandwidth utilized within a storage system for data repair processing to the point of operating in a liquid regime. Liquid distributed storage control logic of embodiments may employ a lazy repair policy, repair bandwidth control, a large erasure code, and/or a repair queue. Embodiments of liquid distributed storage control logic may additionally or alternatively implement a data organization adapted to allow the repair policy to avoid handling large objects, instead streaming data into the storage nodes at a very fine granularity.

Claims

1. A method for repair of source data comprising one or more source objects stored as multiple fragments distributed across multiple storage nodes of a storage system, wherein one or more fragments of the multiple fragments includes redundant data for the one or more source objects, the method comprising:

determining that at least one fragment of the multiple fragments is missing from the storage system for a source object of the one or more source objects for which there is no corresponding object instance in a repair queue;

adding a corresponding object instance to the repair queue for the source object, wherein the repair queue includes object instances for a plurality of source objects having at least one fragment missing from the storage system; and

performing repair processing according to a lazy repair policy, wherein repair operation according to the lazy repair policy allows object instances to accumulate in the repair queue for performing repairs at an average repair rate, R, wherein the average repair rate, R, is selected such that the performing repairs at the average repair rate, R, results in processing source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object of the one or more source objects, wherein k is a number of source fragments per source object.

2. The method of claim 1, wherein repair bandwidth is used at a steady rate of at most R.

3. The method of claim 1, wherein repair bandwidth is used at a rate that is scheduled independently of storage node failures and where the repair bandwidth averages to at most R over a period of time sufficient for the repair processing to achieve a provisioned mean time to loss of any source data (MTTDL).

4. The method of claim 1, wherein the average repair rate R comprises an average aggregate read and write repair rate.

5. The method of claim 1, wherein the average repair rate R comprises an average read repair rate.

6. The method of claim 1, wherein the repair queue contains corresponding object instances for a fraction of the one or more source objects stored in the storage system as allowed to accumulate by the lazy repair policy.

7. The method of claim 6, wherein the large fraction of the one or more source objects stored in the storage system comprises a value that is greater than or equal to 1−

c/r, wherein r is a number of repair fragments of the multiple fragments of source objects of the one or more source objects, and c is a positive, non-zero constant value.

8. The method of claim 6, wherein the large fraction of the one or more source objects stored in the storage system comprises 50% or greater of the one or more source objects.

9. The method of claim 6, wherein the large fraction of the one or more source objects stored in the storage system comprises 70% or greater of the one or more source objects.

10. The method of claim 6, wherein the large fraction of the one or more source objects stored in the storage system comprises 90% or greater of the one or more source objects.

11. The method of claim 1, wherein the performing repair processing according to the lazy repair policy comprises:

selecting the object instance from the repair queue based on a priority of the object instance relative to other object instances in the repair queue;

reading a plurality of fragments of the multiple fragments corresponding to the selected object instance from a plurality of storage nodes of the multiple storage nodes;

processing the plurality of fragments read from the plurality of storage nodes to provide data of one or more additional fragment for the multiple fragments;

writing the one or more additional fragments to storage nodes of the storage system; and

deleting the selected object instance from the repair queue.

12. The method of claim 11, wherein the processing the plurality of fragments read from the plurality of storage nodes comprises:

erasure decoding and the erasure encoding utilizing an erasure code with parameters (n;

k;

r), where k is a number of source fragments per source object, r is a number of repair fragments per source object, n is a total number of fragments per source object whereby n=k+r, and β

=r/n, wherein n is selected to provide a large erasure code configuration.

13. The method of claim 12, wherein a number of the multiple storage nodes of the storage system is M, and wherein n=M, whereby there is a fragment of the one or more source objects stored on each storage node of the storage system.

14. The method of claim 12, wherein a number of the multiple storage nodes of the storage system is M, and wherein n is a significant fraction of M, whereby there is a fragment of the one or more source objects stored on a significant fraction of the storage nodes of the storage system.

15. The method of claim 1, wherein the average repair rate, R, is selected to provide a target mean time to loss of any source data (MTTDL).

16. The method of claim 1, wherein the determining that at least one fragment of the multiple fragments is missing from the storage system for a source object comprises:

determining that a predetermined minimum number of fragments for the source object are lost due to node storage failures.

17. The method of claim 1, wherein performing repair processing according to the lazy repair policy comprises:

cycling through each source object of a plurality of source objects to implement repairs with respect to missing fragments, wherein the plurality of source objects includes the one or more source objects.

18. The method of claim 17, the cycling through each source object at the average repair rate, R, results in the processing the source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object.

19. The method of claim 1, wherein performing repair processing according to the lazy repair policy comprises:

processing source objects corresponding to the object instances in the repair queue in order of a predetermined priority, wherein source objects that have a least amount of available fragments have a highest priority, and wherein among those source objects with a same number of available fragments those source objects added to the repair queue earlier have priority over those added to the repair queue later.

20. The method of claim 1, wherein performing repair processing according to the lazy repair policy is operated to provide redistributing repair data for source data redundantly stored in the storage system as fragment data distributed across multiple storage nodes, wherein the repair data is generated from the source data using an (n;

k;

r) erasure code.

21. The method of claim 20, wherein the source data is organized as consecutive source blocks of source data, wherein a size of the source data is much greater than a size of the source blocks, and wherein the source data stored on each storage node of the multiple storage nodes is organized as consecutive portions of fragment data, wherein the consecutive portions of fragment data are generated from the consecutive portions of source data.

22. The method of claim 20, wherein the redistributing the repair data comprises:

processing each existing source block of source data in order, wherein the processing includes;

determining, for the existing source block of source data, parameters (n;

k;

r) of the erasure code used for generating and storing existing portions of the fragment data;

for each of at least k nodes, accessing the existing portions of fragment data stored on the storage node corresponding to the existing source block of source data;

recovering the existing source block of source data from the accessed existing portions of fragment data using erasure decoding and placing the existing source block into a FIFO buffer;

determining, for a new source block of source data, parameters (n′

;

k′

;

r′

) of new portions of fragment data to generate for the source block of source data;

removing a new source block from the FIFO buffer;

generating n′

new portions of fragment data from the new source block of source data using erasure encoding, wherein k′

of the new portions of the fragment data comprise data from the new source block of source data;

for each storage node for which a new portion of fragment data is generated, storing the generated new portion of fragment data on the storage node; and

releasing the storage space on storage nodes that was used to store the existing portions of fragment data for the existing source block of source data.

23. The method of claim 22, wherein n′

is greater than n for at least some source blocks of the source data.

24. The method of claim 22, wherein the parameters (n;

k;

r) are different for at least two source blocks of the source data.

25. The method of claim 22, wherein the parameters (n′

;

k′

;

r′

) are different for at least two source blocks of the source data.

26. The method of claim 22, wherein at least some of n existing portions of fragments are lost or are not available.

27. The method of claim 22, wherein the repair process is concurrently processing more than one source block of the source data.

28. The method of claim 1, wherein only repair fragments are stored in the storage system.

29. An apparatus for repair of source data comprising one or more source objects stored as multiple fragments distributed across multiple storage nodes of a storage system, wherein one or more fragments of the multiple fragments includes redundant data for the one or more source objects, the apparatus comprising:

one or more data processors; and

one or more non-transitory computer-readable storage media containing program code configured to cause the one or more data processors to perform operations including;

determining that at least one fragment of the multiple fragments is missing from the storage system for a source object of the one or more source objects for which there is no corresponding object instance in a repair queue;

adding a corresponding object instance to the repair queue for the source object, wherein the repair queue includes object instances for a plurality of source objects having at least one fragment missing from the storage system; and

performing repair processing according to a lazy repair policy, wherein repair operation according to the lazy repair policy allows object instances to accumulate in the repair queue for performing repairs at an average repair rate, R, wherein the average repair rate, R, is selected such that the performing repairs at the average repair rate, R, results in processing source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object of the one or more source objects, wherein k is a number of source fragments per source object.

30. The apparatus of claim 29, wherein repair bandwidth is used at a steady rate of at most R.

31. The apparatus of claim 29, wherein repair bandwidth is used at a rate that is scheduled independently of storage node failures and where the repair bandwidth averages to at most R over a period of time sufficient for the repair processing to achieve a provisioned mean time to loss of any source data (MTTDL).

32. The apparatus of claim 29, wherein the average repair rate R comprises an average aggregate read and write repair rate.

33. The apparatus of claim 29, wherein the average repair rate R comprises an average read repair rate.

34. The apparatus of claim 29, wherein the repair queue contains corresponding object instances for a fraction of the one or more source objects stored in the storage system as allowed to accumulate by the lazy repair policy.

35. The apparatus of claim 34, wherein the large fraction of the one or more source objects stored in the storage system comprises a value that is greater than or equal to 1−

c/r, wherein r is a number of repair fragments of the multiple fragments of source objects of the one or more source objects, and c is a positive, non-zero constant value.

36. The apparatus of claim 29, wherein the performing repair processing according to the lazy repair policy comprises:

selecting the object instance from the repair queue based on a priority of the object instance relative to other object instances in the repair queue;

reading a plurality of fragments of the multiple fragments corresponding to the selected object instance from a plurality of storage nodes of the multiple storage nodes;

processing the plurality of fragments read from the plurality of storage nodes to provide data of one or more additional fragment for the multiple fragments;

writing the one or more additional fragments to storage nodes of the storage system; and

deleting the selected object instance from the repair queue.

37. The apparatus of claim 36, wherein the processing the plurality of fragments read from the plurality of storage nodes comprises:

erasure decoding and the erasure encoding utilizing an erasure code with parameters (n;

k;

r), where k is a number of source fragments per source object, r is a number of repair fragments per source object, n is a total number of fragments per source object whereby n=k+r, and β

=r/n, wherein n is selected to provide a large erasure code configuration.

38. The apparatus of claim 37, wherein a number of the multiple storage nodes of the storage system is M, and wherein n=M, whereby there is a fragment of the one or more source objects stored on each storage node of the storage system.

39. The apparatus of claim 37, wherein a number of the multiple storage nodes of the storage system is M, and wherein n is a significant fraction of M, whereby there is a fragment of the one or more source objects stored on a significant fraction of the storage nodes of the storage system.

40. The apparatus of claim 29, wherein performing repair processing according to the lazy repair policy comprises:

cycling through each source object of a plurality of source objects to implement repairs with respect to missing fragments, wherein the plurality of source objects includes the one or more source objects.

41. The apparatus of claim 40, wherein the average repair rate, R, is selected such that the cycling through each source object at the average repair rate, R, results in processing the source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object, wherein k is a number of source fragments per source object.

42. The apparatus of claim 29, wherein the performing repair processing according to the lazy repair policy comprises:

processing source objects corresponding to the object instances in the repair queue in order of a predetermined priority, wherein source objects that have a least amount of available fragments have a highest priority, and wherein among those source objects with a same number of available fragments those source objects added to the repair queue earlier have priority over those added to the repair queue later.

43. The apparatus of claim 29, wherein performing repair processing according to the lazy repair policy is operated to provide redistributing repair data for source data redundantly stored in the storage system as fragment data distributed across multiple storage nodes, wherein the repair data is generated from the source data using an (n;

k;

r) erasure code.

44. The apparatus of claim 43, wherein the source data is organized as consecutive source blocks of source data, wherein a size of the source data is much greater than a size of the source blocks, and wherein the source data stored on each storage node of the multiple storage nodes is organized as consecutive portions of fragment data, wherein the consecutive portions of fragment data are generated from the consecutive portions of source data.

45. The apparatus of claim 43, wherein the redistributing the repair data comprises:

processing each existing source block of source data in order, wherein the processing includes;

determining, for the existing source block of source data, parameters (n;

k;

r) of the erasure code used for generating and storing existing portions of the fragment data;

for each of at least k nodes, accessing the existing portions of fragment data stored on the storage node corresponding to the existing source block of source data;

recovering the existing source block of source data from the accessed existing portions of fragment data using erasure decoding and placing the existing source block into a FIFO buffer;

determining, for a new source block of source data, parameters (n′

;

k′

;

r′

) of new portions of fragment data to generate for the source block of source data;

removing a new source block from the FIFO buffer;

generating n′

new portions of fragment data from the new source block of source data using erasure encoding, wherein k′

of the new portions of the fragment data comprise data from the new source block of source data;

for each storage node for which a new portion of fragment data is generated, storing the generated new portion of fragment data on the storage node; and

releasing the storage space on storage nodes that was used to store the existing portions of fragment data for the existing source block of source data.

46. An apparatus for repair of source data comprising one or more source objects stored as multiple fragments distributed across multiple storage nodes of a storage system, wherein one or more fragments of the multiple fragments includes redundant data for the one or more source objects, the apparatus comprising:

means for determining that at least one fragment of the multiple fragments is missing from the storage system for a source object of the one or more source objects for which there is no corresponding object instance in a repair queue;

means for adding a corresponding object instance to the repair queue for the source object, wherein the repair queue includes object instances for a plurality of source objects having at least one fragment missing from the storage system; and

means for performing repair processing according to a lazy repair policy, wherein repair operation according to the lazy repair policy allows object instances to accumulate in the repair queue for performing repairs at an average repair rate, R, wherein the average repair rate, R, is selected such that the performing repairs at the average repair rate, R, results in processing source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object of the one or more source objects, wherein k is an number of source fragments per source object.

47. The apparatus of claim 46, wherein repair bandwidth is used at a steady rate of at most R.

48. The apparatus of claim 46, wherein repair bandwidth is used at a rate that is scheduled independently of storage node failures and where the repair bandwidth averages to at most R over a period of time sufficient for the repair processing to achieve a provisioned mean time to loss of any source data (MTTDL).

49. The apparatus of claim 46, wherein the repair queue contains corresponding object instances for a large fraction of the one or more source objects stored in the storage system as allowed to accumulate by the lazy repair policy, wherein the large fraction of the one or more source objects stored in the storage system comprises a value that is greater than or equal to 1−

c/r, wherein r is a number of repair fragments of the multiple fragments of source objects of the one or more source objects, and c is a positive, non-zero constant value.

50. The apparatus of claim 46, wherein the means for performing repair processing according to the lazy repair policy comprises:

means for selecting the object instance from the repair queue based on a priority of the object instance relative to other object instances in the repair queue;

means for reading a plurality of fragments of the multiple fragments corresponding to the selected object instance from a plurality of storage nodes of the multiple storage nodes;

means for processing the plurality of fragments read from the plurality of storage nodes to provide data of one or more additional fragment for the multiple fragments;

means for writing the one or more additional fragments to storage nodes of the storage system; and

means for deleting the selected object instance from the repair queue.

51. The apparatus of claim 50, wherein the means for processing the plurality of fragments read from the plurality of storage nodes comprises:

means for erasure decoding and the erasure encoding utilizing an erasure code with parameters (n;

k;

r), where k is a number of source fragments per source object, r is a number of repair fragments per source object, n is a total number of fragments per source object whereby n=k+r, and β

=r/n, wherein n is selected to provide a large erasure code configuration.

52. The apparatus of claim 46, wherein means for performing repair processing according to the lazy repair policy comprises:

means for cycling through each source object of a plurality of source objects to implement repairs with respect to missing fragments, wherein the plurality of source objects includes the one or more source objects, wherein the cycling through each source object at the average repair rate, R, results in the processing the source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object.

53. A non-transitory computer-readable medium comprising codes for repair of source data comprising one or more source objects stored as multiple fragments distributed across multiple storage nodes of a storage system, wherein one or more fragments of the multiple fragments includes redundant data for the one or more source objects, the codes causing a computer to:

determine that at least one fragment of the multiple fragments is missing from the storage system for a source object of the one or more source objects for which there is no corresponding object instance in a repair queue;

add a corresponding object instance to the repair queue for the source object, wherein the repair queue includes object instances for a plurality of source objects having at least one fragment missing from the storage system; and

perform repair processing according to a lazy repair policy, wherein repair operation according to the lazy repair policy allows object instances to accumulate in the repair queue for performing repairs at an average repair rate, R, wherein the average repair rate, R, is selected such that the performing repairs at the average repair rate, R, results in processing source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object of the one or more source objects, wherein k is an number of source fragments per source object.

54. The non-transitory computer-readable medium of claim 53, wherein repair bandwidth is used at a steady rate of at most R.

55. The non-transitory computer-readable medium of claim 53, wherein repair bandwidth is used at a rate that is scheduled independently of storage node failures and where the repair bandwidth averages to at most R over a period of time sufficient for the repair processing to achieve a provisioned mean time to loss of any source data (MTTDL).

56. The non-transitory computer-readable medium of claim 53, wherein the repair queue contains corresponding object instances for a large fraction of the one or more source objects stored in the storage system as allowed to accumulate by the lazy repair policy, wherein the large fraction of the one or more source objects stored in the storage system comprises a value that is greater than or equal to 1−

c/r, wherein r is a number of repair fragments of the multiple fragments of source objects of the one or more source objects, and c is a positive, non-zero constant value.

57. The non-transitory computer-readable medium of claim 53, wherein the codes causing a computer to perform repair processing according to the lazy repair policy comprise codes causing the computer to:

select the object instance from the repair queue based on a priority of the object instance relative to other object instances in the repair queue;

read a plurality of fragments of the multiple fragments corresponding to the selected object instance from a plurality of storage nodes of the multiple storage nodes;

process the plurality of fragments read from the plurality of storage nodes to provide data of one or more additional fragment for the multiple fragments;

write the one or more additional fragments to storage nodes of the storage system; and

delete the selected object instance from the repair queue.

58. The non-transitory computer-readable medium of claim 57, wherein the codes causing a computer to process the plurality of fragments read from the plurality of storage nodes comprise codes causing the computer to:

erasure decode and the erasure encode utilizing an erasure code with parameters (n;

k;

r), where k is a number of source fragments per source object, r is a number of repair fragments per source object, n is a total number of fragments per source object whereby n=k+r, and β

=r/n, wherein n is selected to provide a large erasure code configuration.

59. The non-transitory computer-readable medium of claim 53, wherein the codes causing a computer to perform repair processing according to the lazy repair policy comprise codes causing the computer to:

cycle through each source object of a plurality of source objects to implement repairs with respect to missing fragments, wherein the plurality of source objects includes the one or more source objects, wherein the cycling through each source object at the average repair rate, R, results in the processing the source objects associated with the queued object instances to complete before a loss rate of fragments results in fewer than k fragments being available in the storage system for any source object.