Systems and methods for reliably storing data using liquid distributed storage

• US 9,582,355 B2
• Filed: 12/11/2014
• Issued: 02/28/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): DUNCAN, MARC M
• Application Number:
  US14/567,203
• Publication Number:
  US 20160011935A1
• Time in Patent Office: 810 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/505 considering the load

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 a portion of a source object of the one or more source objects to repair, wherein the portion of the source object to repair comprises data of at least one fragment of the multiple fragments;

reading data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes;

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

writing the data of the at least one additional fragment to at least one storage node of the multiple storage nodes;

provisioning a repair policy process with a repair bandwidth metric (R) to control the reading data of the plurality of fragments and writing the data of the at least one additional fragment for repair of source data within the storage system, wherein R is calculated as a function of data redundancy of the storage system provided by the one or more fragments including redundant data (β

); and

implementing the repair policy process with respect to the reading data of the plurality of fragments and writing the data of the at least one additional fragment, wherein repair bandwidth used by the repair policy process is controlled by the repair policy process to average to at most R over a window of time (W).

2. The method of claim 1, wherein the repair bandwidth controlled by the repair policy is a reading bandwidth for repair of source data within the storage system.

3. The method of claim 1, wherein the repair bandwidth controlled by the repair policy is a reading and writing bandwidth for repair of source data within the storage system.

4. The method of claim 1, wherein the repair bandwidth used by the repair policy process is varied over time independent of a timing of storage node failures.

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

6. The method of claim 1, wherein controlling the repair bandwidth used by the repair policy process provides a repair rate with respect to the one or more source objects to repair which is determined to provide completion of a repair policy process cycle through all source objects of the one or more source objects to repair without loss of source data from any of the one or more source objects to repair.

7. The method of claim 6, further comprising:

determining the repair rate based on a target minimum mean time to loss of any source object of the one or more source objects, wherein a source object is lost if the source object cannot be erasure decoded from the data comprising the plurality of fragments stored on the plurality of storage nodes.

8. The method of claim 6, wherein calculating R as a function of β

comprises;

calculating R as a function of β and

μ

, wherein μ

comprises a rate at which data is being lost from the multiple storage nodes of the storage system.

9. The method of claim 8, wherein calculating R as a function of β

and μ

comprises constraining R such that R·

β

≈

μ

.

10. The method of claim 8, wherein μ

=λ

·

D_ALL, wherein R comprises an aggregate read and write repair bandwidth, wherein λ

comprises a failure rate of individual storage nodes of the multiple storage nodes, whereby each storage node is assumed to fail independently of other nodes at same rate λ

, and wherein D_SRC comprises a total amount of source data stored in the storage system and D_ALL=D_SRC/(1−

β

).

11. The method of claim 8, wherein μ

=λ

·

D_SRC, wherein R comprises a read repair bandwidth, wherein λ

comprises a failure rate of individual storage nodes of the multiple storage nodes, whereby each storage node is assumed to fail independently of other nodes at same rate λ

, and wherein D_SRC comprises a total amount of source data stored in the storage system.

12. The method of claim 8, wherein μ

=Σ

_i λ

_i·

D_i, wherein the sum (Σ

_i) is over all storage nodes of the multiple storage nodes, where λ

_icomprises a failure rate of storage node i, whereby each storage node is assumed to fail independently of other nodes, and D_i comprises a total amount of data stored at storage node i.

13. The method of claim 6, wherein R comprises an aggregate read and write repair bandwidth, wherein calculating R as a function of β

comprises;

constraining R such that R times T_FAIL is at least D_ALL (R·

T_FAIL≧

D_ALL), wherein T_FAIL comprises an amount of time for which it is unlikely that more than β

·

M storage nodes fail, and wherein M comprises a number of storage nodes, and D_SRC comprises a total amount of source data stored in the storage system and D_ALL=D_SRC/(1−

β

).

14. The method of claim 6, wherein R comprises a read repair bandwidth, wherein calculating R as a function of β

comprises;

constraining R such that R times T_FAIL is at least D_SRC (R·

T_FAIL≧

D_SRC), wherein T_FAIL comprises an amount of time for which it is unlikely that more than β

·

M storage nodes fail, and wherein M comprises the number of storage nodes, and D_SRC comprises a total amount of source data stored in the storage system.

15. The method of claim 6, further comprising:

dynamically adjusting R based on an amount of repair instances in a repair queue and a predicted data loss rate for the multiple storage nodes.

16. The method of claim 15, wherein the repair policy process providing the reading data of a plurality of fragments of the multiple fragments and writing the data of the at least one additional fragment dynamically produces predictions of a time to data loss from failed storage nodes of the storage system and operates to adjust R based on the predictions.

17. The method of claim 1, wherein the processing the plurality of fragments read from the plurality of storage nodes to provide data of at least one additional fragment for the multiple fragments comprises:

generating an intermediate block from the data of the plurality of fragments read from the plurality of storage nodes; and

generating data of at least one additional fragment for the multiple fragments from the intermediate block.

18. The method of claim 1, wherein the processing the plurality of fragments read from the plurality of storage nodes to provide data of at least one additional fragment for the multiple fragments comprises:

erasure decoding the portion of the source object to repair from the data of the plurality of fragments read from the plurality of storage nodes; and

erasure encoding data from the decoded portion of source object to the provide data of at least one additional fragment for the multiple fragments.

19. The method of claim 18, wherein the erasure decoding and the erasure encoding comprises:

utilizing an erasure code with parameters (n;

k;

r), wherein k is a number of source fragments per source object, wherein r is a number of repair fragments per source object, and wherein 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.

20. The method of claim 19, 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.

21. The method of claim 19, 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.

22. The method of claim 19, wherein a number of the multiple storage nodes of the storage system is M, and wherein n is at least 30 determined independently of M.

23. The method of claim 1, wherein the repair policy process providing the reading data of a plurality of fragments of the multiple fragments and writing the data of the at least one additional fragment is distributed across multiple servers, and wherein R is an aggregate bandwidth used by the repair process across all the servers.

24. The method of claim 1, further comprising:

maintaining a repair queue, wherein an identifying instance for the source object is added to the repair queue in response to the determining a portion of the source object to repair.

25. The method of claim 24, wherein source objects are processed from the queue by the repair policy process providing the reading data of a plurality of fragments of the multiple fragments and writing the data of the at least one additional fragment in priority order, 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.

26. The method of claim 24, wherein particular source objects of the one or more source objects are provided prioritized repair operation in the repair queue to provide a higher level of reliability with respect to the particular source objects.

27. The method of claim 24, wherein particular source objects of the one or more source objects are provided prioritized repair operation in the repair queue to provide a higher quality of service to a client associated with the particular source objects.

28. The method of claim 1, wherein the repair process providing the reading data of a plurality of fragments of the multiple fragments and writing the data of the at least one additional fragment implements a lazy repair policy such that there is significant time between when data is lost for a source object and when the data of the at least one additional fragment for the source object is written to the at least one storage node of the multiple storage nodes.

29. The method of claim 1, wherein the data of the at least one fragment of the multiple fragments is stored by the at least one storage node of the multiple storage nodes using a data organization that concatenates multiple source blocks from the source object for inclusion of a symbol of each source block in each of a plurality of the multiple fragments of the source object.

30. The method of claim 29, wherein the reading data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes comprises:

reading data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes to access a portion of data, wherein an amount of the data read by the reading data of a plurality of fragments is substantially equal to a size of a requested portion of the source data.

31. The method of claim 30, wherein the writing the data of the at least one additional fragment comprises:

writing a plurality of output fragment streams to storage nodes as the output fragment streams are being produced, wherein a first portion of each of the output fragment streams corresponds to a first portion of the source object and are written to the storage nodes before a second portion of the source object has been processed by a repair policy process controlling the reading and writing.

32. The method of claim 29, further comprising:

accessing data of the one or more fragments of the multiple fragments from the storage system by an end user (EU) device, wherein the EU device comprises a plurality connections and operates to download at least a portion of the one or more fragments of the multiple fragments through the plurality of connections, and wherein the EU device comprises erasure decoding logic and operates to erasure decode the downloaded at least a portion of the one or more fragments to obtain data of the source object therefrom.

33. The method of claim 29, further comprising:

storing data of the one or more fragments of the multiple fragments to the storage system by an end user (EU) device, wherein the EU device comprises a plurality connections and operates to upload at least a portion of the one or more fragments of the multiple fragments through the plurality of connections, and wherein the EU device comprises erasure encoding logic and operates to erasure encode data of the source object to provide the one or more fragment uploaded for storage to the storage system.

34. The method of claim 29, further comprising:

accessing data of the one or more fragments of the multiple fragments from the storage system using a first access server, wherein the first access server comprises a first plurality of connections to a plurality of second access servers and operates to download at least a portion of the one or more fragments of the multiple fragments through the first plurality of connections, and wherein the plurality of second access servers comprise a second plurality of connections to storage nodes and operates to download at least a portion of the one or more fragments of the multiple fragments through the second plurality of connections from the storage nodes and provide the downloaded portions to the first access server through the first plurality of connections, and wherein the first access server comprises erasure decoding logic and operates to erasure decode the downloaded at least a portion of the one or more fragments to obtain data of the source object therefrom.

35. The method of claim 29, further comprising:

storing data of the one or more fragments of the multiple fragments to the storage system using a first access server, wherein the first access server comprises a first plurality of connections to a plurality of second access servers and operates to upload at least a portion of the one or more fragments of the multiple fragments through the first plurality of connections to the plurality of second access servers, and wherein the plurality of second access servers comprise a second plurality of connections to storage nodes and operates to upload at least a portion of the one or more fragments of the multiple fragments through the second plurality of connections to the storage nodes in response to the uploaded portions from the first access server through the first plurality of connections, and wherein the first access server comprises erasure encoding logic and operates to erasure encode data of the source object to provide the one or more fragment uploaded for storage to the storage system.

36. The method of claim 1, wherein W is a window of time that is sufficient for the repair policy process to achieve a provisioned mean time to loss of any source data.

37. 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 a portion of a source object of the one or more source objects to repair, wherein the portion of the source object to repair comprises data of at least one fragment of the multiple fragments;

reading data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes;

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

writing the data of the at least one additional fragment to at least one storage node of the multiple storage nodes; and

provisioning a repair policy process with a repair bandwidth metric (R) to control the reading the data of the plurality of fragments and writing the data of the at least one additional fragment for repair of source data within the storage system, wherein R is calculated as a function of data redundancy of the storage system provided by the one or more fragments including redundant data (β

); and

implementing the repair policy process with respect to the reading data of the plurality of fragments and writing the data of the at least one additional fragment, wherein repair bandwidth used by the repair policy process is controlled by the repair policy process to average to at most R over a window of time (W).

38. The apparatus of claim 37, wherein the repair bandwidth used by the repair policy process is varied over time independent of a timing of storage node failures.

39. The apparatus of claim 37, wherein controlling the repair bandwidth used by the repair policy process provides a repair rate with respect to the one or more source objects to repair which is determined to provide completion of a repair policy process cycle through all source objects of the one or more source objects to repair without loss of source data from any of the one or more source objects to repair.

40. The apparatus of claim 39, wherein calculating R as a function of β

comprises calculating R as a function of β and

μ

, wherein μ

comprises a rate at which data is being lost from the multiple storage nodes of the storage system.

41. The apparatus of claim 40, wherein R comprises an aggregate read and write repair bandwidth, wherein μ

=λ

·

D_ALL, wherein λ

comprises a failure rate of individual storage nodes of the multiple storage nodes, whereby each storage node is assumed to fail independently of other nodes at same rate λ

, and wherein D_SRC comprises a total amount of source data stored in the storage system and D_ALL=D_SRC/(1−

β

).

42. The apparatus of claim 40, wherein R comprises a read repair bandwidth, wherein μ

=λ

·

D_SRC, wherein λ

comprises a failure rate of individual storage nodes of the multiple storage nodes, whereby each storage node is assumed to fail independently of other nodes at same rate λ

, and wherein D_SRC comprises a total amount of source data stored in the storage system.

43. The apparatus of claim 39, wherein R comprises an aggregate read and write repair bandwidth, wherein calculating R as a function of β

constrains R such that R times T_FAIL is at least D_ALL (R ·

T_FAIL≧

D_ALL) wherein T_FAIL comprises an amount of time for which it is unlikely that more than β

·

M storage nodes fail, and wherein M comprises a number of storage nodes, and D_SRC comprises a total amount of source data stored in the storage system and D_ALL=D_SRC/(1−

β

).

44. The apparatus of claim 39, wherein R comprises a read repair bandwidth, wherein calculating R as a function of β

constrains R such that R times T_FAIL is at least D_SRC (R·

T_FAIL ≧

D_SRC), wherein T_FAIL comprises an amount of time for which it is unlikely that more than β

·

M storage nodes fail, and wherein M comprises a number of storage nodes, and D_SRC comprises a total amount of source data stored in the storage system.

45. The apparatus of claim 39, wherein the operations performed by the one or more data processors further includes:

dynamically adjusting R based on an amount of repair instances in a repair queue and a predicted data loss rate for the multiple storage nodes.

46. The apparatus of claim 37, wherein the processing the plurality of fragments read from the plurality of storage nodes to provide data of at least one additional fragment for the multiple fragments comprises:

utilizing an erasure code with parameters (n;

k;

r), wherein k is a number of source fragments per source object, wherein r is a number of repair fragments per source object, and wherein 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.

47. The apparatus of claim 37, wherein a repair process providing the reading data of a plurality of fragments of the multiple fragments and writing the data of the at least one additional fragment is distributed across multiple servers, and wherein R is an aggregate bandwidth used by the repair process across all the servers.

48. The apparatus of claim 37, wherein the operations performed by the one or more data processors further includes:

maintaining a repair queue, wherein an identifying instance for the source object is added to the repair queue in response to determining a portion of the source object to repair.

49. The apparatus of claim 48, wherein source objects are processed from the queue by the repair policy process providing the reading of the data of a plurality of fragments of the multiple fragments and the writing of the data of the at least one additional fragment in priority order, 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.

50. The apparatus of claim 37, wherein the repair process providing the reading of the data of a plurality of fragments of the multiple fragments and the writing of the data of the at least one additional fragment implements a lazy repair policy such that there is significant time between when data is lost for a source object and when the data of the at least one additional fragment for the source object is written to the at least one storage node of the multiple storage nodes.

51. The apparatus of claim 37, wherein the data of the at least one fragment of the multiple fragments is stored by the at least one storage node of the multiple storage nodes using a data organization that concatenates multiple source blocks from the source object for inclusion of a symbol of each source block in each of a plurality of the multiple fragments of the source object.

52. The apparatus of claim 51, wherein the reading the data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes comprises:

reading data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes to access a portion of data, wherein an amount of the data read is substantially equal to a size of a requested portion of the source data.

53. The apparatus of claim 52, wherein the writing the data of the at least one additional fragment comprises:

writing a plurality of output fragment streams to storage nodes as the output fragment streams are being produced, wherein a first portion of each of the output fragment streams corresponds to a first portion of the source object and are written to the storage nodes before a second portion of the source object has been processed by the repair policy process controlling the reading and writing.

54. The apparatus of claim 37, wherein W is a window of time that is sufficient for the repair policy process to achieve a provisioned mean time to loss of any source data.

55. 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 a portion of a source object of the one or more source objects to repair, wherein the portion of the source object to repair comprises data of at least one fragment of the multiple fragments;

means for reading data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes;

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

means for writing the data of the at least one additional fragment to at least one storage node of the multiple storage nodes;

means for provisioning a repair policy process with a repair bandwidth metric (R) to control reading data of the plurality of fragments and writing data of the at least one additional fragment for repair of source data within the storage system, wherein R is calculated as a function of data redundancy of the storage system provided by the one or more fragments including redundant data (β

); and

means for implementing the repair policy process with respect to reading data of the plurality of fragments and writing the data of the at least one additional fragment, wherein repair bandwidth used by the repair policy process is controlled by the repair policy process to average to at most R over a window of time (W).

56. The apparatus of claim 55, wherein the means for processing the plurality of fragments read from the plurality of fragments comprises:

means for utilizing an erasure code with parameters (n;

k;

r), wherein k is a number of source fragments per source object, wherein r is a number of repair fragments per source object, and wherein 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.

57. The apparatus of claim 55, wherein the repair process utilizing the means for reading of the data of a plurality of fragments of the multiple fragments and the means for writing of the data of the at least one additional fragment implements a lazy repair policy such that there is significant time between when data is lost for a source object and when the data of the at least one additional fragment for the source object is written to the at least one storage node of the multiple storage nodes.

58. The apparatus of claim 55, wherein the data of the at least one fragment of the multiple fragments is stored by the at least one storage node of the multiple storage nodes using a data organization that concatenates multiple source blocks from the source object for inclusion of a symbol of each source block in each of a plurality of the multiple fragments of the source object.

59. The apparatus of claim 55, wherein W is a window of time that is sufficient for the repair policy process to achieve a provisioned mean time to loss of any source data.

60. 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 a portion of a source object of the one or more source objects to repair, wherein the portion of the source object to repair comprises data of at least one fragment of the multiple fragments;

read data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes;

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

write the data of the at least one additional fragment to at least one storage node of the multiple storage nodes;

provision a repair policy process with a repair bandwidth metric (R) to control reading data of the plurality of fragments and writing data of the at least one additional fragment for repair of source data within the storage system, wherein R is calculated as a function of data redundancy of the storage system provided by the one or more fragments including redundant data (β

); and

implement the repair policy process with respect to reading data of the plurality of fragments and writing the data of the at least one additional fragment, wherein repair bandwidth used by the repair policy process is controlled by the repair policy process to average to at most R over a window of time (W).

61. The non-transitory computer-readable medium of claim 60, wherein the codes causing the computer to process the plurality of fragments read from the plurality of fragments comprise codes causing the computer to:

utilize an erasure code with parameters (n;

k;

r), wherein k is a number of source fragments per source object, wherein r is a number of repair fragments per source object, and wherein 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.

62. The non-transitory computer-readable medium of claim 60, wherein the repair process of the codes causing the computer to read the data of a plurality of fragments of the multiple fragments and write the data of the at least one additional fragment implements a lazy repair policy such that there is significant time between when data is lost for a source object and when the data of the at least one additional fragment for the source object is written to the at least one storage node of the multiple storage nodes.

63. The non-transitory computer-readable medium of claim 60, wherein the data of the at least one fragment of the multiple fragments is stored by the at least one storage node of the multiple storage nodes using a data organization that concatenates multiple source blocks from the source object for inclusion of a symbol of each source block in each of a plurality of the multiple fragments of the source object.

64. The non-transitory computer-readable medium of claim 60, wherein W is a window of time that is sufficient for the repair policy process to achieve a provisioned mean time to loss of any source data.