Shared file system predictive storage techniques

• US 9,727,423 B2
• Filed: 12/31/2014
• Issued: 08/08/2017
• Est. Priority Date: 09/30/2014
• Status: Active Grant

• Current Assignee: Crashplan Group LLC
• Original Assignee: Code 42 Software Incorporated
• Inventors: Dornquast, Matthew, Bispala, Brian, Schroeder, Samuel, Gwinn, Christopher, Grammens, Justin, Lindquist, Thomas (Tony), Lindquist, Peter
• Primary Examiner(s): Hill, Stanley K
• Assistant Examiner(s): Bharadwaj, Kalpana
• Application Number:
  US14/587,142
• Publication Number:
  US 20160092465A1
• Time in Patent Office: 951 Days
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/183 Provision of network file services by network file servers, e.g. by using NFS, CIFS network file access protocols H04L67/1097
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/604 Tools and structures for managing or administering access control systems
• CPC Class Codes: G06F 2221/2111 Location-sensitive, e.g. geographical location, GPS
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Disclosed in some examples are predictive storage techniques for use in a distributed data system. The predictive storage techniques may be used to manage locally stored elements of a shared data collection, such as the storage of files on nodes of the distributed data system that are limited in local storage space. The predictive storage techniques may achieve a balance between consumption of local resources and timely access of important elements in the shared data collection. For example, the predictive storage techniques may be used for keeping or pre-caching certain items of a collection that are determined as likely to be used in local storage for convenient access, and allowing access the remaining items on request over a network.

Claims

1. A method of predictive data storage for a node device in a data distribution system, the method comprising using at least one processor to perform operations of:

scoring each particular file system element of a plurality of file system elements of a collection of the data distribution system, the scoring using a calculated probability that a user of the node device is likely to interact with the particular file system element;

calculating an on-demand subset of the collection based upon the scores of the plurality of file system elements, wherein the on-demand subset includes fewer elements than the collection, wherein calculating the on-demand subset includes selecting a combination of the plurality of file system elements that results in a highest combined score of selected file system elements given a file system element size constraint on a maximum total size of the elements in the on-demand subset; and

causing at least one file system element of the on-demand subset to be placed in local storage of the node device in response to a determination that the at least one file system element of the on-demand subset is not already in the local storage of the node device.

2. The method of claim 1, wherein scoring each particular element of the plurality of file system elements includes utilizing prior usage history corresponding to at least one of the plurality of file system elements.

3. The method of claim 2, wherein the prior usage history includes information describing interactions of all users of the collection with the at least one of the plurality of file system elements.

4. The method of claim 3, wherein a component of the prior usage history corresponding to the user of the node device is weighted greater than a component of the prior usage history corresponding to other users of the collection.

5. The method of claim 1, wherein scoring each particular element of the plurality of file system elements includes utilizing contextual data specifying a context corresponding to a prior usage history.

6. The method of claim 5, wherein the prior usage history indicates an interaction by a particular user of the collection with one of the plurality of file system elements in the collection and wherein the contextual data signals a particular situation in which the particular user was in when the particular user interacted with the one of the plurality of file system elements.

7. The method of claim 1, the operations further including:

building a machine learning model;

wherein scoring includes using the machine learning model.

8. The method of claim 1, wherein causing the at least one file system element to be placed in local storage on the node device includes:

requesting the at least one file system element from a second node device in the data distribution system over a computer network;

receiving the at least one file system element from the second node device; and

responsive to receiving the at least one file system element from the second node device, storing the at least one file system element in the local storage of the node device.

9. A system for predictive data storage for a node device in a data distribution system, the system comprising:

a prediction module comprising circuitry to;

score each particular file system element of a plurality of file system elements of a collection of the data distribution system, the score based upon a calculated probability that a user of the node device is likely to interact with the particular file system element;

a control module comprising circuitry to;

calculate an on-demand subset of the collection based upon the scores of the plurality of file system elements, wherein the on-demand subset includes fewer elements than the collection, wherein calculating the on-demand subset includes selecting a combination of the plurality of file system elements that results in a highest combined score of selected file systems elements given a file system element size constraint on a maximum total size of the elements in the on-demand subset; and

cause at least one file system element of the on-demand subset to be placed in local storage of the node responsive to a determination that the at least one file system element of the on-demand subset is not already in the local storage of the node device.

10. The system of claim 9, wherein the prediction module s configured to score each particular element of the plurality of file system elements by at least utilizing prior usage history corresponding to at least one of the plurality of file system elements.

11. The system of claim 9, wherein the prediction module is configured to score each particular element of the plurality of file system elements by at least utilizing contextual data specifying a context corresponding to a prior usage history.

12. The system of claim 11, wherein the prior usage history indicates an interaction by a particular user of the collection with one of the plurality of file system elements in the collection, and wherein the contextual data signals a particular situation in which the particular user was in when the particular user interacted with the one of the plurality of file system elements.

13. The system of claim 9, wherein the prediction module is configured to build a machine learning model, and wherein the prediction module is configured to score by at least using the machine learning model.

14. A non-transitory machine-readable medium, for predictive data storage for a node device in a data distribution system, the machine-readable medium including instructions, which when performed by the machine, cause the machine to perform operations of:

scoring each particular file system element of a plurality of file system elements of a collection of the data distribution system, the scoring using a calculated probability that a user of the node device is likely to interact with the particular file system element;

calculating an on-demand subset of the collection based upon the scores of the plurality of file system elements, wherein the on-demand subset includes fewer elements than the collection, wherein calculating the on-demand subset includes selecting a combination of the plurality of file system elements that results in a highest combined score of selected file system elements given a file system element size constraint on a maximum total size of the elements in the on-demand subset; and

causing at least one file system element of the on-demand subset to be placed in local storage of the node device in response to a determination that the at least one file system element of the on-demand subset is not already in the local storage of the node device.

15. The machine-readable medium of claim 14, wherein the operations of scoring each particular element includes utilizing prior usage history corresponding to at least one of the plurality of file system elements.

16. The machine-readable medium of claim 15, wherein the prior usage history includes information describing interactions of all users of the collection with the at least one of the plurality of file system elements.

17. The machine-readable medium of claim 16, wherein a component of the prior usage history corresponding to the user of the node is weighted greater than a component of the prior usage history corresponding to other users of the collection.

18. The machine-readable medium of claim 14, wherein the operations of scoring each particular element includes utilizing contextual data specifying a context corresponding to a prior usage history.

19. The machine-readable medium of claim 18, wherein the prior usage history indicates an interaction by a particular user of the collection with one of the plurality of file system elements in the collection and wherein the contextual data signals a particular situation in which the particular user was in when the particular user interacted with the one of the plurality of elements.

20. The machine-readable medium of claim 14, wherein the operations include building a machine learning model;

and

wherein the operations of scoring include using the machine learning model.

21. The machine-readable medium of claim 14, wherein the operations of causing the at least one file system element to be placed in local storage on the node includes:

requesting the at least one file system element from a second node device in the data distribution system over a computer network;

receiving the at least one file system element from the second node device; and

responsive to receiving the at least one file system element from the second node device, storing the at least one file system element in the local storage of the node device.