Systems and methods for reliably storing data using liquid distributed storage

• US 9,734,007 B2
• Filed: 12/11/2014
• Issued: 08/15/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): Le, Dieu-Minh
• Application Number:
  US14/567,303
• Publication Number:
  US 20160011936A1
• Time in Patent Office: 978 Days
• Field of Search: 714 621, 714 622, 714 623, 714754, 714755
• 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]

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 accessing source data of a source object 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 source object, the method comprising:

receiving the source data as a stream of data;

erasure encoding the stream of data to generate a stream of encoded data as the stream of data is arriving, wherein the redundant data is generated from the source data using an (n ;

k;

r) erasure code;

producing the multiple fragments as a plurality of output fragment streams from the stream of encoded data as the stream of encoded data is being generated;

writing, by an access server having a processor and memory, the multiple fragments to the storage nodes as each of the plurality of output fragment streams 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 received, and wherein data of at least one fragment of the multiple fragments is stored by the multiple storage nodes using a data organization that concatenates symbols of multiple source blocks from the source object for inclusion of a symbol of each source block in each of two or more fragments of the multiple fragments of the source object;

reading, by the access server, data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes to access a requested portion of the source data, wherein the reading data of a plurality of fragments comprises reading each of at least k fragments of the plurality of output fragments written to storage nodes as an input fragment stream; and

erasure decoding, by the access server, the portion of the source data from the data of the plurality of fragments read from the plurality of storage nodes, wherein the erasure decoding the portion of source data comprises erasure decoding the input fragment stream to generate a stream of source data for the source object as the input fragment stream is being read.

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

3. The method of claim 1, wherein an amount of the data of the plurality of fragments read from the plurality of storage nodes is substantially equal to a size of the requested portion of the source data.

4. The method of claim 3, wherein at least one fragment of the multiple fragments which is not also of the plurality of fragments comprises at least a part of the requested portion of source data, whereby the reading data of the plurality of fragments does not read data from the at least one fragment.

5. The method of claim 1, wherein the erasure decoding provides a decoded part of the requested portion of the source data before at least some of the data for the requested portion of the source data is read.

6. The method of claim 1, wherein the requested portion of the source data is requested by an end user (EU) device, the method further comprising:

receiving a request to access a portion of the source data from the EU device; and

providing the portion of the source data to the EU device in response to the request.

7. The method of claim 1, wherein a size of the source object is not known when a part of the plurality of fragment streams corresponding to the first portion of the source object has been written to storage nodes.

8. The method of claim 1, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code, wherein a number of fragment streams of the plurality of output fragment streams is n.

9. The method of claim 1, wherein the reading data of a plurality of fragments to access a requested portion of source data is in response to a request to generate repair data for the source object from the repair process, wherein a part of the output fragment streams corresponding to the first portion of the source object are written to storage nodes before a portion of the input fragment stream corresponding to the second portion of the object is read from the nodes.

10. The method of claim 1, wherein the source object further comprises a third portion, wherein the third portion of the source object is subsequent to the first portion of the object and previous to the second portion of the source object, wherein the third portion of the source object is erasure encoded after the first portion is written to the storage nodes and before the second portion of the source object has been received, and wherein a size of the third portion of the source object is substantially smaller than a size of the source object.

11. The method of claim 1, wherein the reading data of a plurality of fragments to access a requested portion of source data is by a repair process for generating repair data for the source object, the method further comprising:

generating the repair data from the source data using an (n;

k;

r) erasure code, 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, wherein a repair process processes each of the source blocks of source data in order, wherein the processing by the repair process includes;

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

recovering the source block of the source data from the accessed portions of the fragment data using erasure decoding;

generating at least one portion of fragment data from the source block of the source data using erasure encoding; and

for each storage node for which a portion of fragment data is generated, storing the generated portion of fragment data on the storage node, wherein data of the source data stored on each 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 source blocks of the source data.

12. The method of claim 11, wherein when the repair process starts again at a first source block of the source data after the repair process has completed processing of a last source block of the source data.

13. The method of claim 11, where an aggregate rate at which the repair process accesses and stores data on the storage nodes is constrained below a value R that depends on a value β

and a value μ

, wherein β

is a fraction of data redundancy of the storage system, and wherein μ

is an average rate at which data is being lost from the storage nodes of the storage system.

14. The method of claim 13, wherein the aggregate rate is an aggregate read and write rate.

15. The method of claim 13, wherein the aggregate rate is an aggregate read rate.

16. The method of claim 11, wherein the processing by the repair process of a particular source block of the source data is skipped for the particular source block of the source data if there are more than a predetermined number of portions of fragment data corresponding to the particular source block of source data that are available on the storage nodes.

17. The method of claim 1, wherein the storage system comprises a peer-to-peer storage system configuration, and wherein the multiple storage nodes comprise peer devices to a device accessing the source data.

18. The method of claim 17, wherein the reading data of a plurality of fragments of the multiple fragments includes recovering and storing locally each of the plurality of fragments at a peer device, wherein the erasure decoding the portion of source data includes accessing portions of the plurality of fragments stored locally at the peer device, wherein an aggregate size of accessed portions of the plurality of fragments is substantially equal in size to the portion of source data, and wherein the erasure decoding the portion of source data includes erasure decoding at the peer device the portion of source data from the accessed portions of the plurality of fragments, wherein memory used by the peer device to erasure decode is substantially smaller than the size of the portion of source data.

19. The method of claim 1, wherein the storage system is a combined storage system configuration including a redundant data storage system storing the source object as multiple fragments distributed across the multiple storage nodes and a complementary storage system storing the source object in its original unmodified form.

20. The method of claim 19, wherein the reading data of the plurality of fragments and the erasure decoding the portion of source data from the data of the plurality of fragments read provides the complementary storage system access to a backup copy of data of the source object stored by the redundant data storage system.

21. The method of claim 20, wherein an end user (EU) device accesses data of the source object via the complementary storage system.

22. The method of claim 19, wherein the complementary storage system executes individual jobs with respect to the source object in a distributed fashion across storage nodes of the complementary storage system.

23. The method of claim 19, further comprising:

deleting the source object from the complementary storage system after a backup copy of the source object has been reliably stored in the redundant data storage system.

24. An apparatus for accessing source data of a source object 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 source object, 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;

receiving the source data as a stream of data;

erasure encoding the stream of data to generate a stream of encoded data as the stream of data is arriving, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code;

producing the multiple fragments as a plurality of output fragment streams from the stream of encoded data as the stream of encoded data is being generated;

writing the multiple fragments to the storage nodes as each of the plurality of output fragment streams 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 received, wherein data of at least one fragment of the multiple fragments is stored by the multiple storage nodes using a data organization that concatenates symbols of multiple source blocks from the source object for inclusion of a symbol of each source block in each of a plurality two or more fragments of the multiple fragments of the source object;

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 requested portion of the source data, wherein the reading data of a plurality of fragments comprises reading each of at least k fragments of the plurality of output fragments written to storage nodes as an input fragment stream; and

erasure decoding the portion of the source data from the data of the plurality of fragments read from the plurality of storage nodes, wherein the erasure decoding the portion of source data comprises erasure decoding the input fragment stream to generate a stream of source data for the source object as the input fragment stream is being read.

25. The apparatus of claim 24, wherein an amount of the data of the plurality of fragments read from the plurality of storage nodes is substantially equal to a size of the requested portion of the source data.

26. The apparatus of claim 25, wherein at least one fragment of the multiple fragments which is not also of the plurality of fragments comprises at least a part of the requested portion of source data, whereby the reading data of the plurality of fragments does not read data from the at least one fragment.

27. The apparatus of claim 24, wherein the erasure decoding provides a decoded part of the requested portion of the source data before at least some of the data for the requested portion of the source data is read.

28. The apparatus of claim 24, wherein the reading data of a plurality of fragments to access a requested portion of source data is by an end user (EU) device, wherein the program code is configured to cause the one or more data processors to further perform operations including:

receiving a request to access a portion of the source data from the EU device; and

providing the portion of the source data to the EU device in response to the request.

29. The apparatus of claim 24, wherein a size of the source object is not known when a part of the plurality of fragment streams corresponding to the first portion of the source object has been written to storage nodes.

30. The apparatus of claim 24, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code, wherein a number of fragment streams of the plurality of output fragment streams is n.

31. The apparatus of claim 24, wherein the reading data of a plurality of fragments to access a requested portion of source data is in response to a request to generate repair data for the source object from a repair process, wherein a part of the output fragment streams corresponding to the first portion of the source object are written to storage nodes before a portion of the input fragment stream corresponding to the second portion of the object is read from the nodes.

32. The apparatus of claim 24, wherein the source object further comprises a third portion, wherein the third portion of the source object is subsequent to the first portion of the object and previous to the second portion of the source object, wherein the third portion of the source object is erasure encoded after the first portion is written to the storage nodes and before the second portion of the source object has been received, and wherein a size of the third portion of the source object is substantially smaller than a size of the source object.

33. The apparatus of claim 24, wherein the reading data of a plurality of fragments to access a requested portion of source data is by a repair process for generating repair data for the source object, wherein the program code is configured to cause the one or more data processors to further perform operations including:

generating the repair data from the source data using an (n;

k;

r) erasure code, 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, wherein the repair process processes each of the source blocks of source data in order, wherein the processing by a repair process includes;

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

recovering the source block of the source data from the accessed portions of the fragment data using erasure decoding;

generating at least one portion of fragment data from the source block of the source data using erasure encoding; and

for each storage node for which a portion of fragment data is generated, storing the generated portion of fragment data on the storage node, wherein data of the source data stored on each 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 source blocks of the source data.

34. The apparatus of claim 33, where an aggregate rate at which the repair process accesses and stores data on the storage nodes is constrained below a value R that depends on a value β

and a value μ

, wherein β

is a fraction of data redundancy of the storage system, and wherein μ

is an average rate at which data is being lost from the storage nodes of the storage system.

35. The apparatus of claim 34, wherein the aggregate rate is an aggregate read and write rate.

36. The apparatus of claim 34, wherein the aggregate rate is an aggregate read rate.

37. The apparatus of claim 33, wherein the processing by the repair process of a particular source block of the source data is skipped for the particular source block of the source data if there are more than a predetermined number of portions of fragment data corresponding to the particular source block of source data that are available on the storage nodes.

38. The apparatus of claim 24, wherein the storage system comprises a peer-to-peer storage system configuration, and wherein the multiple storage nodes comprise peer devices to a device accessing the source data.

39. The apparatus of claim 38, wherein the reading data of a plurality of fragments of the multiple fragments includes recovering and storing locally each of the plurality of fragments at a peer device, wherein the erasure decoding the portion of source data includes accessing portions of the plurality of fragments stored locally at the peer device, wherein an aggregate size of accessed portions of the plurality of fragments is substantially equal in size to the portion of source data, and wherein the erasure decoding the portion of source data includes erasure decoding at the peer device the portion of source data from the accessed portions of the plurality of fragments, wherein memory used by the peer device to erasure decode is substantially smaller than the size of the portion of source data.

40. The apparatus of claim 24, wherein the storage system is a combined storage system configuration including a redundant data storage system storing the source object as multiple fragments distributed across the multiple storage nodes and a complementary storage system storing the source object in its original unmodified form.

41. The apparatus of claim 40, wherein the reading data of the plurality of fragments and the erasure decoding the portion of source data from the data of the plurality of fragments read provides the complementary storage system access to a backup copy of data of the source object stored by the redundant data storage system.

42. The apparatus of claim 41, wherein an end user (EU) device accesses data of the source object via the complementary storage system.

43. The apparatus of claim 40, wherein the complementary storage system executes individual jobs with respect to the source object in a distributed fashion across storage nodes of the complementary storage system.

44. The apparatus of claim 40, wherein the program code is configured to cause the one or more data processors to further perform operations including:

deleting the source object from the complementary storage system after a backup copy of the source object has been reliably stored in the redundant data storage system.

45. An apparatus for accessing source data of a source object 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 source object, the apparatus comprising:

means for receiving the source data as a stream of data;

means for erasure encoding the stream of data to generate a stream of encoded data as the stream of data is arriving, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code;

means for producing the multiple fragments as a plurality of output fragment streams from the stream of encoded data as the stream of encoded data is being generated;

means for writing the multiple fragments to the storage nodes as each of the plurality of output fragment streams 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 received, wherein data of at least one fragment of the multiple fragments is stored by the multiple storage nodes using a data organization that concatenates symbols of multiple source blocks from the source object for inclusion of a symbol of each source block in each of two or more fragments of the multiple fragments of the source object;

means for reading, by an access server having a processor and memory, data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes to access a requested portion of the source data, wherein the reading data of a plurality of fragments comprises reading each of at least k fragments of the plurality of output fragments written to storage nodes as an input fragment stream; and

means for erasure decoding, by the access server, the portion of the source data from the data of the plurality of fragments read from the plurality of storage nodes, wherein the erasure decoding the portion of source data comprises erasure decoding the input fragment stream to generate a stream of source data for the source object as the input fragment stream is being read.

46. The apparatus of claim 45, wherein an amount of the data of the plurality of fragments read from the plurality of storage nodes is substantially equal to a size of the requested portion of the source data.

47. The apparatus of claim 45, wherein the erasure decoding provides a decoded part of the requested portion of the source data before at least some of the data for the requested portion of the source data is read.

48. The apparatus of claim 45, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code, wherein a number of fragment streams of the plurality of output fragment streams is n.

49. The apparatus of claim 45, wherein the means for reading data of a plurality of fragments to access a requested portion of source data accesses the requested portion of the source data in response to a request to generate repair data for the source object from the repair process, wherein a part of the output fragment streams corresponding to the first portion of the source object are written to storage nodes before a portion of the input fragment stream corresponding to the second portion of the object is read from the nodes.

50. The apparatus of claim 45, wherein the means for reading data of a plurality of fragments to access a requested portion of source data accesses the requested portion of the source data as part of a repair process for generating repair data for the source object, the apparatus further comprising:

means for generating the repair data from the source data using an (n;

k;

r) erasure code, 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, wherein a repair process processes each of the source blocks of source data in order, wherein the processing by the repair process includes;

means for accessing a portion of the fragment data stored on the storage node corresponding to the source block of the source data for each of at least k storage nodes;

means for recovering the source block of the source data from the accessed portions of the fragment data using erasure decoding;

means for generating at least one portion of fragment data from the source block of the source data using erasure encoding; and

means for storing the generated portion of fragment data on the storage node for each storage node for which a portion of fragment data is generated, wherein data of the source data stored on each 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 source blocks of the source data.

51. A non-transitory computer-readable medium comprising codes for accessing source data of a source object 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 the source object, the codes causing a computer to:

receive the source data as a stream of data;

erasure encode the stream of data to generate a stream of encoded data as the stream of data is arriving, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code;

produce the multiple fragments as a plurality of output fragment streams from the stream of encoded data as the stream of encoded data is being generated;

write the multiple fragments to the storage nodes as each of the plurality of output fragment streams 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 received, and wherein data of at least one fragment of the multiple fragments is stored by the multiple storage nodes using a data organization that concatenates symbols of multiple source blocks from the source object for inclusion of a symbol of each source block in each of two or more fragments of the multiple fragments of the source object;

read data of a plurality of fragments of the multiple fragments from a plurality of storage nodes of the multiple storage nodes to access a requested portion of the source data, wherein reading data of a plurality of fragments comprises reading each of at least k fragments of the plurality of output fragments written to storage nodes as an input fragment stream; and

decode the portion of the source data from the data of the plurality of fragments read from the plurality of storage nodes, wherein erasure decoding the portion of source data comprises erasure decoding the input fragment stream to generate a stream of source data for the source object as the input fragment stream is being read.

52. The non-transitory computer-readable medium of claim 51, wherein an amount of the data of the plurality of fragments read from the plurality of storage nodes is substantially equal to a size of the requested portion of the source data.

53. The non-transitory computer-readable medium of claim 51, wherein the erasure decoding provides a decoded part of the requested portion of the source data before at least some of the data for the requested portion of the source data is read.

54. The non-transitory computer-readable medium of claim 51, wherein the redundant data is generated from the source data using an (n;

k;

r) erasure code, wherein a number of fragment streams of the plurality of output fragment streams is n.

55. The non-transitory computer-readable medium of claim 51, wherein accessing source data is in response to a request to generate repair data for the source object from the repair process, wherein a part of the output fragment streams corresponding to the first portion of the source object are written to storage nodes before a portion of the input fragment streams corresponding to the second portion of the object is read from the nodes.

56. The non-transitory computer-readable medium of claim 51, wherein accessing source data is by a repair process for generating repair data for the source object, wherein the codes further cause the computer to:

generate the repair data from the source data using an (n;

k;

r) erasure code, 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, wherein the repair process processes each of the source blocks of source data in order, wherein processing by the repair process utilizes codes causing the computer to;

access a portion of the fragment data stored on the storage node corresponding to the source block of the source data for each of at least k storage nodes;

recover the source block of the source data from the accessed portions of the fragment data using erasure decoding;

generate at least one portion of fragment data from the source block of the source data using erasure encoding; and

store the generated portion of fragment data on the storage node for each storage node for which a portion of fragment data is generated, wherein data of the source data stored on each 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 source blocks of the source data.