ADAPTIVE SCHEDULED PERIODIC CACHING

• US 20140143219A1
• Filed: 11/19/2013
• Published: 05/22/2014
• Est. Priority Date: 08/16/2012
• Status: Active Grant

• Current Assignee: ExaGrid Systems, Inc.
• Original Assignee: ExaGrid Systems, Inc.
• Inventors: Therrien, David G., VanderSpek, Adrian, Poirier, Jamey C., Chao, Yee-ching
• Granted Patent: US 9,223,812 B2
• Time in Patent Office: Days
• US Class Current: 707/695
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477

Abstract

A system, a method, and a computer program product for adaptive scheduled periodic caching are disclosed. A data stream is received. The data stream contains a plurality of versions of data arranged in a plurality of data clusters. Each data cluster includes an anchor version having a plurality of versions of data dependent on the anchor version. A size of each anchor version of each data cluster is determined. A number of versions of data dependent on each anchor version is also determined. For each anchor version, a ratio of the determined number of dependent versions of data to the determined size of each anchor is computed. At least one anchor version for storing in a memory location is selected based on the computed ratio.

Claims

1. A computer-implemented method, comprising:

receiving a data stream containing a plurality of versions of data arranged in a plurality of data clusters, wherein each data cluster in the plurality of clusters includes an anchor version having a plurality of versions of data dependent on the anchor version;

determining a size of each anchor version of each data cluster;

determining a number of versions of data dependent on each anchor version;

computing, for each anchor version, a ratio of the determined number of dependent versions of data to the determined size of each anchor; and

selecting, based on the computed ratio, at least one anchor version for storing in a memory location;

wherein at least one of the receiving, the determining the size, the determining the number, the computing, and the selecting is performed by at least one processor of at least one computing system.

2. The method according to claim 1, wherein the selecting further comprises:

storing the computed ratios for each anchor version in a database table;

sorting the computed ratios in the database table;

determining, based on the sorted computed ratios, the anchor versions having the highest computed ratios;

determining sizes for the anchor versions having highest computed ratios, the total size of the anchor versions having highest computed ratios, and whether the total size of the anchor versions having highest computed ratios is less than a size of the memory location; and

selecting the anchor versions having the highest computed ratios for storage in the memory location.

3. The method according to claim 2, wherein the selecting the anchor versions further comprises deleting anchor versions having the lowest computed ratios from storage in the memory location.

4. The method according to claim 1, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version within a predetermined period of time.

5. The method according to claim 4, wherein the predetermined period of time is a most recent period of time in relation to the received data stream.

6. The method according to claim 1, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during a predetermined periodic time interval.

7. The method according to claim 6, wherein the predetermined periodic time interval is determined based on a periodicity of a backup of a data received in the data stream.

8. The method according to claim 1, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during all periods of time when a backup of data was received.

9. The method according to claim 1, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during at least one predetermined prior period of time during receiving of the data stream.

10. The method according to claim 1, wherein the ratio is computed based on a number of versions of data that are associated with an anchor version during a repeating previous period of time during receiving of the data stream.

11. The method according to claim 1, wherein the ratio is computed based on a number of versions of data that are associated with an anchor version during every predetermined repeating period of time during receiving of the data stream.

12. The method according to claim 1, wherein the memory location is a solid state disk location.

13. A non-transitory computer program product comprising machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one processor to perform operations comprising:

receiving a data stream containing a plurality of versions of data arranged in a plurality of data clusters, wherein each data cluster in the plurality of clusters includes an anchor version having a plurality of versions of data dependent on the anchor version;

determining a size of each anchor version of each data cluster;

determining a number of versions of data dependent on each anchor version;

computing, for each anchor version, a ratio of the determined number of dependent versions of data to the determined size of each anchor; and

selecting, based on the computed ratio, at least one anchor version for storing in a memory location.

14. The computer program product according to claim 13, wherein the selecting further comprises:

storing the computed ratios for each anchor version in a database table;

sorting the computed ratios in the database table;

determining, based on the sorted computed ratios, the anchor versions having the highest computed ratios;

determining sizes for the anchor versions having highest computed ratios, the total size of the anchor versions having highest computed ratios, and whether the total size of the anchor versions having highest computed ratios is less than a size of the memory location; and

selecting the anchor versions having the highest computed ratios for storage in the memory location.

15. The computer program product according to claim 14, wherein the selecting the anchor versions further comprises deleting anchor versions having the lowest computed ratios from storage in the memory location.

16. The computer program product according to claim 13, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version within a predetermined period of time.

17. The computer program product according to claim 16, wherein the predetermined period of time is a most recent period of time in relation to the received data stream.

18. The computer program product according to claim 13, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during a predetermined periodic time interval.

19. The computer program product according to claim 18, wherein the predetermined periodic time interval is determined based on a periodicity of a backup of a data received in the data stream.

20. The computer program product according to claim 13, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during all periods of time when a backup of data was received.

21. The computer program product according to claim 13, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during at least one predetermined prior period of time during receiving of the data stream.

22. The computer program product according to claim 13, wherein the ratio is computed based on a number of versions of data that are associated with an anchor version during a repeating previous period of time during receiving of the data stream.

23. The computer program product according to claim 13, wherein the ratio is computed based on a number of versions of data that are associated with an anchor version during every predetermined repeating period of time during receiving of the data stream.

24. The computer program product according to claim 13, wherein the memory location is a solid state disk location.

25. A system, comprising:

at least one processor; and

at least one machine-readable medium storing instructions that, when executed by the at least one processor, cause the at least one processor to perform operations comprising;

receiving a data stream containing a plurality of versions of data arranged in a plurality of data clusters, wherein each data cluster in the plurality of clusters includes an anchor version having a plurality of versions of data dependent on the anchor version;

determining a size of each anchor version of each data cluster;

determining a number of versions of data dependent on each anchor version;

computing, for each anchor version, a ratio of the determined number of dependent versions of data to the determined size of each anchor; and

selecting, based on the computed ratio, at least one anchor version for storing in a memory location.

26. The system according to claim 25, wherein the selecting further comprises:

storing the computed ratios for each anchor version in a database table;

sorting the computed ratios in the database table;

determining, based on the sorted computed ratios, the anchor versions having the highest computed ratios;

determining sizes for the anchor versions having highest computed ratios, the total size of the anchor versions having highest computed ratios, and whether the total size of the anchor versions having highest computed ratios is less than a size of the memory location; and

selecting the anchor versions having the highest computed ratios for storage in the memory location.

27. The system according to claim 26, wherein the selecting the anchor versions further comprises deleting anchor versions having the lowest computed ratios from storage in the memory location.

28. The system according to claim 25, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version within a predetermined period of time.

29. The system according to claim 28, wherein the predetermined period of time is a most recent period of time in relation to the received data stream.

30. The system according to claim 25, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during a predetermined periodic time interval.

31. The system according to claim 30, wherein the predetermined periodic time interval is determined based on a periodicity of a backup of a data received in the data stream.

32. The system according to claim 25, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during all periods of time when a backup of data was received.

33. The system according to claim 25, wherein the ratio is computed based on a number of versions of data that were associated with an anchor version during at least one predetermined prior period of time during receiving of the data stream.

34. The system according to claim 25, wherein the ratio is computed based on a number of versions of data that are associated with an anchor version during a repeating previous period of time during receiving of the data stream.

35. The system according to claim 25, wherein the ratio is computed based on a number of versions of data that are associated with an anchor version during every predetermined repeating period of time during receiving of the data stream.

36. The system according to claim 25, wherein the memory location is a solid state disk location.