Delay cache method and apparatus

• US 20040034744A1
• Filed: 08/13/2002
• Published: 02/19/2004
• Est. Priority Date: 08/13/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Karlsson, Magnus, Mahalingam, Mallik
• Granted Patent: US 6,836,827 B2
• Time in Patent Office: Days
• US Class Current: 711/133
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Delayed caching receives an evaluation interval to delay updating the objects stored in a delayed cache, delays a time period corresponding to the evaluation interval, and updates the objects stored in the contents of the delayed cache when the time period delay has completed. The configuration operation for the delayed cache selects a time interval to sample a trace having object access frequencies for objects stored in a cache, creates a first working set of objects accessed during the time interval and a second working set of objects accessed during a subsequent time interval based on the historical trace, determines that the difference between the objects contained in the first and second working sets does not exceed a maximum threshold with the selected time interval, and sets a evaluation interval for evaluating the contents of the cache to the selected time interval.

Claims

1. A method of caching objects comprising:

receiving an evaluation interval to delay updating the objects to be stored in a delay cache;

delaying a time period corresponding to the evaluation interval; and

updating the objects stored in the contents of the delayed cache when the time period delay has completed.

2. The method of claim 1 further comprising:

communicating an object list identifying the current objects stored in the delayed cache over a network when the contents of the delayed cache have been updated.

3. The method of claim 1 wherein the evaluation interval corresponds to a time period that the delay cache is likely to have one or more objects being requested.

4. The method of claim 3 wherein updating the objects to be stored in the delayed cache is performed in accordance with a caching algorithm.

5. The method of claim 4 wherein the caching algorithm replaces objects in the delayed cache according to a caching operation selected from a set of caching operations including:

a least recently used (LRU) analysis, a greedy dual analysis (GD), and a greedy dual size (GDS) analysis.

6. The method of claim 1 wherein the time period for the evaluation interval is a single value for one or more delayed cache used over a network.

7. The method of claim 1 wherein the time period for the evaluation interval can be different for each of the one or more delayed cache used over a network.

8. The method of claim 1 wherein the time period for the evaluation interval can be reset to different values.

9. The method of claim 1 wherein the evaluation interval is determined by analyzing requests for objects over one or more previous time periods and the contents of the delayed cache during the one or more time periods.

10. A method of configuring a cache, comprising:

selecting a time interval to sample a historical trace having object access frequencies for objects stored in a cache;

creating a first working set of objects accessed during the time interval and a second working set of objects accessed during a subsequent time interval based on information from the historical trace;

determining that the difference between the objects contained in the first working set of objects and the objects contained in the second working set does not exceed a maximum threshold based upon the selected time interval; and

setting a evaluation interval in the cache for evaluating the contents of the cache to the selected time interval.

11. The method of claim 10 implemented using two or more working sets of objects when determining the differences.

12. The method of claim 10 further comprising:

selecting the time interval to sample the historical trace from a series of time intervals; and

utilizing the largest time interval from the series of time intervals that also produces at least a minimum number of objects common to both the first working set of objects and the second working set of objects.

13. The method of claim 12 wherein the series of time intervals are based upon a Fibonacci sequence.

14. The method of claim 12 wherein the series of time intervals have a linear relationship to each other.

15. The method of claim 12 wherein the series of time intervals have an exponential relationship to each other.

16. The method of claim 12 wherein the series of time intervals are generated randomly.

17. An apparatus for caching objects comprising:

a storage area configured to receive an evaluation interval to delay updating the objects to be stored in a delay cache;

a timer that delays a time period corresponding to the evaluation interval; and

an update component that updates the objects stored in the contents of the delayed cache when the timer delaying the time period has completed.

18. The apparatus of claim 17 further comprising:

a communication component that communicates an object list identifying the current objects stored in the delayed cache over a network when the contents of the delayed cache have been updated.

19. The apparatus of claim 17 wherein the evaluation interval corresponds to a time period that the delay cache is likely to have one or more of the objects being requested..

20. An apparatus for configuring a cache, comprising:

a processor that executes instructions;

a memory that stores instructions capable of being executed on the processor that select a time interval to sample a historical trace having object access frequencies for objects stored in a cache, create a first working set of objects accessed during the time interval and a second working set of objects accessed during a subsequent time interval based on information from the historical trace, determine that the difference between the objects contained in the first working set of objects and the objects contained in the second working set does not exceed a maximum threshold based upon the selected time interval, and set an evaluation interval in the cache for evaluating the contents of the cache to the selected time interval.

21. The apparatus of claim 20 further comprising instructions in memory that,

select the time interval to sample the historical trace from a series of time intervals;

and

utilize the largest time interval from the series of time intervals that also produces at least a minimum number of objects common to both the first working set of objects and the second working set of objects.

22. The apparatus of claim 20 wherein the series of time intervals are based upon a Fibonacci sequence.

23. The apparatus of claim 20 wherein the series of time intervals have a linear relationship to each other.

24. The apparatus of claim 20 wherein the series of time intervals are generated randomly.

25. The apparatus of claim 20 wherein the series of time intervals have an exponential relationship to each other.

26. A method of caching objects, comprising:

receiving a request for an object;

determining if the requested object is in a delayed cache;

retrieving the object from the delayed cache based upon the determination, wherein the contents of the delayed cache are evaluated according to a caching algorithm after an evaluation interval passes; and

accessing the object from a neighboring cache associated with a nearby node based upon the determination and according to a cache list.

27. The method of claim 26 further comprising,

delivering the requested object to the client that made the request.

28. The method of claim 26 wherein the caching algorithm replaces objects in the delayed cache according to a caching operation selected from a set of caching operations including:

a least recently used (LRU) analysis, a greedy dual analysis (GD), and a greedy dual size (GDS) analysis.

29. The method of claim 26 wherein retrieving the object further includes,

copying the object from delayed cache and providing the results to the requesting client.

30. The method of claim 26 wherein accessing the object further includes directing a client requesting the object to the node and corresponding delayed cache having the requested object.

31. The method of claim 26 wherein the neighboring cache is the nearest cache with the requested object.

32. The method of claim 26 wherein the neighboring cache has the fastest response time for the requested object.

33. The method of claim 26 wherein the requested object is retrieved from the original node based on the determination.