Caching protocol method and system based on request frequency and relative storage duration

• US 6,425,057 B1
• Filed: 08/27/1998
• Issued: 07/23/2002
• Est. Priority Date: 08/27/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Arlitt, Martin F., Friedrich, Richard J., Jin, Tai, Cherkasova, Ludmila
• Primary Examiner(s): COURTENAY III, ST JOHN
• Application Number:
  US09/140,977
• Time in Patent Office: 1,426 Days
• Field of Search: 709/310-320, 709/219, 707/205, 711/118-146
• US Class Current: 711/134
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 16/289 Object oriented databases

Abstract

A method and system for caching objects and replacing cached objects in an object-transfer environment maintain a dynamic indicator (Pr(f)) for each cached object, with the dynamic indicator being responsive to the frequency of requests for the object and being indicative of the time of storing the cached object relative to storing other cached objects. In a preferred embodiment, the size of the object is also a factor in determining the dynamic indicator of the object. In the most preferred embodiment, the cost of obtaining the object is also a factor. A count of the frequency of requests and the use of the relative time of storage counterbalance each other with respect to maintaining a cached object in local cache. That is, a high frequency of requests favors maintaining the object in cache, but a long period of cache favors evicting the object. Thus, cache pollution is less likely to occur.

Claims

1. A method of caching objects and replacing cached objects comprising:

receiving a plurality of objects from remote sites via network connections, the objects being directed to target devices,

storing at least some of the objects in local cache, thereby providing cached objects that are accessible without reconnecting to the remote sites;

maintaining dynamic indicators for at least some of the cached objects, where different dynamic indicators correspond to different cached objects, each dynamic indicator being responsive to a frequency of requests for a corresponding cached object by the target devices and being indicative of a time of storing the corresponding cached object in the local cache relative to storing other cached objects in the local cache such that a determination for each dynamic indicator is at least partially based on a storage occurrence of the corresponding cached object relative to storage occurrences of other cached objects; and

selectively replacing cached objects with recently received objects based upon the dynamic indicators such that the cached objects are removed from the local cache on the basis of frequencies of requests and relative times of storing said cached objects.

2. A method according to claim 1 wherein maintaining the dynamic indicators and selectively replacing the cached objects are performed such that (1) cached objects having higher frequencies of requests are less likely to be replaced than cached objects having lower frequencies, and (2) cached objects with shorter relative times are less likely to be e replaced than cached objects having longer relative times.

3. A method according to claim 1 wherein maintaining the dynamic indicators includes factoring a size of the corresponding cached object into each dynamic indicator, each cached object thereby being associated with a dynamic indicator that is specific to frequency of requests and is indicative of size and relative time of storing the corresponding cached object.

4. A method according to claim 3 wherein maintaining the dynamic indicators and selectively replacing cached objects are performed such that (1) cached objects having higher frequencies of requests are less likely to be replaced than cached objects having lower frequencies, (2) cached objects having smaller sizes are less likely to be replaced than cached objects having larger sizes, and (3) cached objects with shorter relative times are less likely to be replaced than cached objects having longer relative times.

5. A method according to claim 1 wherein maintaining the dynamic indicators includes factoring into the dynamic indicator a cost of acquiring a corresponding cached object from a remote site, the cost related to latency in receiving the corresponding cached object.

6. A method according to claim 1 wherein receiving a plurality of objects includes accessing objects from servers via the Internet, the local cache being located at a proxy.

7. A method according to claim 1 wherein maintaining the dynamic indicators includes factoring into a dynamic indicator for a recently received object a dynamic indicator for an object that has been selectively replaced.

8. A method according to claim 1 wherein maintaining the dynamic indicators includes establishing assigning a value, the value being substantially fixed with respect to a corresponding cached object, but being adjusted each time that selective replacement of a cached object occurs, such that the assigned value is indicative of an order in which cached objects were placed in the local cache.

9. A method according to claim 1 further comprising determining whether a recently received object is to be stored in local cache, including assigning a specific dynamic indicator to the recently received object and comparing the specific dynamic indicator to dynamic indicators of other cached objects.

10. A method according to claim 9 wherein selectively replacing cached objects includes selectively replacing cached objects only when (1) a preselected portion of a capacity of local cache would be exhausted by storing the recently received object and (2) comparison of the specific indicator to the dynamic indicators favors storing the recently received object to one or more cached objects.

11. A method of caching objects and replacing cached objects comprising:

establishing a protocol for replacing objects stored in local cache, the protocol being dependent upon indications of frequency of requests (Fr) for an object (f), cost (Cost) of acquiring the object from at least one source, and a time (Clock) of accessing the object in the local cache, such that each object has a priority key (Pr(f)) that is indicative of

12. A method according to claim 11 wherein establishing the protocol includes defining Clock to be indicative of priority keys (Pr(f)_evicted) of objects previously replaced according to the protocol.

13. A method according to claim 11 wherein forming the protocol includes providing a tunable coefficient (Alpha) such that

14. A method of caching objects and replacing cached objects comprising:

establishing a protocol for replacing objects stored in local cache, the protocol being dependent upon indications of frequency of requests (Fr) for an object (f) and a time (Clock) of accessing the object in the local cache, such that each object has a priority key (Pr(f)) that is indicative of

15. A method according to claim 14 wherein establishing the protocol includes defining Clock to be indicative of priority keys (Pr(f)_evicted) of objects previously replaced according to the protocol.

16. A method according to claim 14 wherein forming the protocol includes providing a tunable coefficient (Alpha) such that

17. A method of caching objects and replacing cached objects comprising:

establishing a protocol for replacing objects stored in local cache of a proxy cache, the protocol being dependent upon indications of frequency of requests (Fr) for an object (f), size (Size) of the object and duration (Clock) of storing the object in the local cache, such that each object has a priority key (Pr(f)) that is indicative of $\mathrm{Pr}<br><br>\left(f\right)=\mathrm{Clock}+\frac{\mathrm{Fr}<br><br>\left(f\right)}{\mathrm{Size}<br><br>\left(f\right)};<br><br>$

storing a plurality of the objects in the local cache, each object having an assigned priority key Pr(f);

adjusting the indication of frequency Fr(f) for a specific object upon receiving a request for the specific object; and

selectively replacing the objects in the local cache with recently received objects based upon the replacement protocol.

18. A method according to claim 17 wherein forming the replacement protocol further includes providing an indication of the cost (Cost(f)) of resources in obtaining a corresponding object such that $\mathrm{Pr}$

(f)=Clock+Fr

(f)×

Cost

(f)Size

(f).

19. A method according to claim 17 wherein forming the protocol includes providing a tunable coefficient (Alpha) that is selected for a corresponding object according to at least one of (1) an object type of the corresponding object within a set of different object types, (2) a time of day at which the corresponding object was stored in the local cache, (3) a protocol used in receiving the corresponding object from a source, and (4) the source of the corresponding object prior to storage in the local cache.

20. A method according to claim 17 wherein forming the replacement protocol further includes utilizing a tunable coefficient (Alpha) such that $\mathrm{Pr}$

(f)=Clock+Alpha×

Fr

(f)Size

(f).

21. A method according to claim 17 further comprising, when an un-cached object is received at the cache, determining whether to replace objects based upon the protocol.

22. A method according to claim 17 wherein storing the objects includes receiving the objects via the Internet.

23. A system for caching objects and replacing cached objects comprising:

switching means for providing connectivity between a plurality of remote servers of objects and a plurality of clients requesting the objects;

local cache means for selectively storing objects requested by the clients via the switching means; and

replacement protocol controller means for governing caching of objects based on values of dynamic indicators that are specific to corresponding objects in the local cache means, each dynamic indicator being responsive to a frequency of requests for the corresponding object by the plurality of clients and a clock indicative of a relative time of storing the corresponding object in the local cache means in relation to storing other objects, the replacement protocol controller means replacing cached objects with recently requested objects in an order determined by the dynamic indicators.

24. A system according to claim 23 further comprising means for assigning the dynamic indicators to the objects on a one-to-one basis in response to cost of resources in obtaining the objects.

25. A system according to claim 23 further comprising means for updating the dynamic indicators when requests for objects stored in the local cache means are received from the clients.