PROBABILISTIC TECHNIQUE FOR CONSISTENCY CHECKING CACHE ENTRIES

• US 20090083494A1
• Filed: 12/01/2008
• Published: 03/26/2009
• Est. Priority Date: 08/21/2006
• Status: Active Grant

• Current Assignee: Hermant Madhav Bhanoo, Nevil A. Shah, Ozgun A. Erdogan, Ryan J. Snodgrass, Tobias Hogers
• Original Assignee: Hermant Madhav Bhanoo, Nevil A. Shah, Ozgun A. Erdogan, Ryan J. Snodgrass, Tobias Hogers
• Inventors: Hogers, Tobias, Bhanoo, Hermant Madhav, Snodgrass, Ryan J., Shah, Nevil A., Erdogan, Ozgun A.
• Granted Patent: US 7,734,872 B2
• Time in Patent Office: Days
• US Class Current: 711/141
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

A facility for determining whether to consistency-check a cache entry is described. The facility randomly or pseudorandomly selects a value in a range. If the selected value satisfies a predetermined consistency-checking threshold within the range, the facility consistency-checks the entry, and may decide to propagate this knowledge to other cache managers. If, on the other hand, the selected value does not satisfy the consistency-checking threshold, the facility determines not to consistency-check the entry.

Claims

1. A computer-readable medium whose contents caused a computer system to perform a method for managing objects comprising:

obtaining a request for an object; and

if a cache contains a version of the object;

determining whether a probability threshold has been exceeded, the probability threshold associated with exceeding a minimum lifetime attributable to the cached version of the object;

using the cached version of the object to respond to the received request if the probability threshold has not been exceeded; and

transmitting a request for a current version of the cached object from a source associated with the object if the probability threshold has been exceeded.

2. The computer-readable medium as recited in claim 1 further comprising causing the invalidation of the cached version of the object if a maximum lifetime attributable to the cached version of the object has been exceeded.

3. The computer-readable medium as recited in claim 1, wherein determining whether the probability threshold has been exceeded includes calculating a comparison number and determining whether the comparison number exceeds the probability threshold, wherein the comparison number is a random or pseudo random number.

4. The computer-readable medium as recited in claim 1, wherein the probability threshold is dynamically calculated.

5. The computer-readable medium as recited in claim 1, wherein the probability threshold is calculated as a function of at least one of a property of the object and a total time the object has been cached.

6. The computer-readable medium as recited in claim 1, wherein the probability threshold increases as a function of a total time the object has been cached.

7. The computer-readable medium as recited in claim 1, wherein the probability threshold decreases as a function of the total time the object has been cached.

8. The computer-readable medium as recited in claim 1 further comprising:

obtaining an updated version of the object from the source;

determining whether the obtained updated version of the object differs from the cached version of the object; and

transmitting an invalidation notification if the updated version of the object differs from the cached version of the object.

9. The computer-readable medium as recited in claim 1, wherein the probability threshold is associated for a class of objects.

10. A computer-readable medium whose contents caused a computing system to perform a method for managing objects comprising:

obtaining a notification corresponding to a determination from a peer computing device that a cached object version differs from a current version of the object, the current version of the object provided by a source; and

determining whether to transmit a request to the source for the updated version of the object based on the obtained notification;

wherein the current version of the object is associated with a minimum lifetime that has not been exceeded.

11. The computer-readable medium as recited in claim 10, wherein determining whether to transmit a request to the source for the updated version of the object includes:

obtaining a digest indicative of an invalid version of the object; and

determining whether the digest matches the cached version of the object.

12. The computer-readable medium as recited in claim 10, wherein determining whether to transmit a request to the source for the updated version of the object includes:

obtaining a digest indicative of a valid version of the object; and

determining whether the digest matches the cached version of the object.

13. The computer-readable medium as recited in claim 12 further comprising resetting the minimum lifetime associated with the cached version of the object if the digest matches the cached version of the object.

14. A computer-readable medium whose contents caused a computing system to perform a method for managing objects comprising:

obtaining a request for an object from a client computing device;

transmitting a request for the object from a source associated with the object;

obtaining the requested object from the source;

storing the obtained requested object, wherein storing the obtained requested object includes associating a minimum lifetime in which the cached version of the object will be provided in response to client computing device request and wherein storing the obtained requested object includes associating a maximum lifetime in which the cached version of the object will not be provided in response to client computing device requests; and

transmitting the requested object to the client computing device.

15. The computer-readable medium as recited in claim 14 further comprising:

obtaining a subsequent request for the object from a client computing device;

if the minimum lifetime associated with the cached version of the object has been exceeded, determining whether a probability threshold has also been exceeded; and

transmitting the requested object to the client computing device if the probability threshold has not been exceeded.

16. The computer-readable medium as recited in claim 15 further comprising, if the probability threshold has been exceeded:

transmitting a subsequent request for the object from the source associated with the object; and

obtaining the requested object from the source.