Predictive caching and fetch priority

• US 9,766,791 B2
• Filed: 07/20/2016
• Issued: 09/19/2017
• Est. Priority Date: 01/06/2014
• Status: Active Grant

• Current Assignee: Dropbox, Inc.
• Original Assignee: Dropbox, Inc.
• Inventors: Kluesing, Daniel, Andersson, Rasmus
• Primary Examiner(s): NGUYEN, HIEP T
• Application Number:
  US15/214,873
• Publication Number:
  US 20160357678A1
• Time in Patent Office: 426 Days
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence

Abstract

Predicting what content items a user finds important and sending those items to a cache on the user'"'"'s device at times when doing so will not drain resources and will not result in expensive data rates. Applying a ranking function that examines recency and other content metadata associated with the user'"'"'s content items stored in a synchronized content management system. Determining how much of a ranked list of content items to cache and deciding when is a good time to send content items to the local cache.

Claims

1. A computer-implemented method comprising:

receiving, from a client device authorized on a user account of a content management system, an amount of free memory space available on the client device for caching one or more content items associated with the user account, wherein each content item associated with the user account has associated metadata;

defining, based on the amount of free memory space available, a subset of the amount of free memory space to use for caching the one or more content items;

generating, by the content management system, for each content item associated with the user account, a Fetch Priority score based on the associated metadata; and

selecting a subset of content items from the content items associated with the user account based on the generated Fetch Priority scores and the subset of the amount of free space on the client device.

2. The method of claim 1, wherein selecting a subset of content items from the content items associated with the user account comprises:

generating a ranked list of content items from the content items associated with the user account based on the generated Fetch Priority scores, wherein a content item with a higher Fetch Priority score has a higher rank in the ranked list; and

selecting one or more content items from the ranked list beginning with higher ranked content items until an amount of space required to cache the selected content items fills the subset of the amount of available caching space.

3. The method of claim 1 further comprising:

automatically caching the selected subset of content items to the client device when the client device has available caching space.

4. The method of claim 1, wherein the subset of the amount of available caching space is calculated by the content management system based on a predetermined percentage of a total amount of storage space on the client device and the received amount of free memory available on the client device.

5. The method of claim 1, wherein metadata associated with a content item comprises at least one of a file size, a user indication of importance of a content item, a content management system-wide item score, a score reflecting how likely a content item is to be updated, or a quality score reflecting the quality of a content item compared to an original of the content item.

6. The method of claim 1 further comprising:

transcoding one or more content items associated with the user account into one or more varying quality representations.

7. The method of claim 1, wherein the selected subset of content items includes a content item with a quality representation less than a maximum quality level for the content item.

8. The method of claim 1 comprising:

synchronizing the client device with the content management system, wherein the synchronizing causes the addition of a new file or modification of an existing file at the content management system; and

calculating a Fetch priority score for the new file or modified existing file after the synchronizing.

9. The method of claim 8, comprising:

selecting at least one content item that was previously cached to be deleted when the Fetch priority score for the new file or modified existing file is ranked higher on a ranked list of content items from the content items associated with the user account based on respective Fetch Priority scores of each of the content items.

10. A non-transitory computer-readable medium comprising instructions stored on the computer readable medium that when executed are effective to cause a computing device to:

generate, by a content management system, for each content item associated with a user account a Fetch Priority score based on associated metadata;

receive, from a first client device authorized on a user account of the content management system, a first amount of free memory available on the first client device for caching one or more content items associated with the user account, wherein each content item associated with the user account has the associated metadata;

defining, based on the first amount of free memory space available, a subset of the first amount of free space to use for caching the one or more content items; and

select a first subset of content items from the content items associated with the user account based on the generated Fetch Priority scores and a first amount of available caching space, wherein the first amount of available caching space is less than or equal to the subset of the first amount of free memory space available on the first client device.

11. The non-transitory computer-readable medium of claim 10 further comprising:

receive, from a second client device authorized on the user account of the content management system, a second amount of free memory available on the second client device for caching one or more content items associated with the user account; and

select a second subset of content items from the content items associated with the user account based on the generated Fetch Priority scores and a second amount of available caching space on the client device.

12. The non-transitory computer-readable medium of claim 11, wherein the first amount of available caching space differs from the second amount of available caching space and a number of content items in the first subset of content items differs from a number of content items in the second subset of content items.

13. The non-transitory computer-readable medium of claim 12, wherein the subset of the first amount of available caching space is calculated by the content management system based on a predetermined percentage and the received first amount of free memory space available on the first client device and the second amount of available caching space is calculated by the content management system based on the predetermined percentage and the received second amount of free memory available on the second client device.

14. The non-transitory computer-readable medium of claim 11 further comprising:

prior to selecting the second subset of content items, update, by the content management system, for each content item associated with a user account, the Fetch Priority score based on the associated metadata.

15. The non-transitory computer-readable medium of claim 10, wherein selecting a subset of content items from the content items associated with the user account comprises:

generate a ranked list of content items from the content items associated with the user account based on the generated Fetch Priority scores, wherein a content item with a higher Fetch Priority score has a higher rank in the ranked list; and

select one or more content items from the ranked list beginning with higher ranked content items until an amount of space required to cache the selected content items fills the amount of available caching space.

16. The non-transitory computer-readable medium of claim 11 comprising:

synchronize the first client device or the second client device with the content management system, wherein the synchronizing causes the addition of a new file or modification of an existing file at the content management system; and

calculate a Fetch priority score for the new file or modified existing file after the synchronizing.

17. The non-transitory computer-readable medium of claim 16, comprising:

select at least one content item that was previously cached on the first client device or the second client device to be deleted when the Fetch priority score for the new file or modified existing file is ranked higher on a ranked list of content items from the content items associated with the user account based on respective Fetch Priority scores of each of the content items.

18. The non-transitory computer-readable medium of claim 10, wherein the Fetch Priority score ranks content items over maximum file size low so that they are not cached.

19. A system comprising:

a first client device having configured to store and synchronize local copies of content items stored on a content management system, the client device having a first amount of available caching space; and

the content management system configured to;

generate, by the content management system, for each content item associated with a user account a Fetch Priority score based on associated metadata;

receive, from the first client device authorized on a user account of the content management system, a first amount of free memory space available on the first client device for caching one or more content items associated with the user account, wherein each content item associated with the user account has the associated metadata;

defining, based on the first amount of free memory space available, a subset of the first amount of free memory space to use for caching the one or more content items; and

select a first subset of content items from the content items associated with the user account based on the generated Fetch Priority scores and the subset of the first amount of free memory space, wherein the subset of the first amount of free space is less than or equal to the first amount of free memory available on the first client device.

20. The system of claim 19 further wherein the content management system configured to:

receive, from a second client device authorized on the user account of the content management system, a second amount of free memory available on the second client device for caching one or more content items associated with the user account; and

select a second subset of content items from the content items associated with the user account based on the generated Fetch Priority scores and a second amount of available caching space on the client device.