PROBABILISTIC TECHNIQUE FOR CONSISTENCY CHECKING CACHE ENTRIES

• US 20080046655A1
• Filed: 08/21/2006
• Published: 02/21/2008
• Est. Priority Date: 08/21/2006
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Bhanoo, Hemant Madhav, Snodgrass, Ryan J., Shah, Nevil A., Holgers, Tobias, Erdogan, Ozgun A.
• Granted Patent: US 7,461,206 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
• 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 cause a computing system to perform a method for managing a cache, the method comprising:

receiving a request for an object;

if the cache does not contain a cached version of the object;

obtaining a current version of the object from a source associated with the object;

storing the obtained current version of the object in the cache;

attributing a minimum lifetime and a maximum lifetime to the current version of the object based upon the time at which the current version of the object was stored in the cache;

using the current version of the object to respond the received request;

if the cache contains a cached version of the object;

if a minimum lifetime attributed to the cached version of the object has not expired, using the cached version of the object to respond the received request;

if the minimum lifetime attributed to the cached version of the object has expired, but a maximum lifetime attributed to the cached version of the object has not expired;

determining a random or pseudorandom number within a range;

if the determined number exceeds a probability threshold determined with respect to the range, using the cached version of the object to respond the received request;

if the maximum lifetime attributed to the cached version of the object has expired, or if the determined number does not exceed the probability threshold;

obtaining a current version of the object from the source associated with the object;

storing the current version of the object in the cache;

attributing a minimum lifetime and a maximum lifetime to the current version of the object based upon the time at which the current version of the object was stored in the cache; and

using the current version of the object to respond the received request.

2. The computer-readable medium of claim 1, further comprising, if the determined number does not exceed the probability threshold:

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

if the obtained current version of the object differs from the cached version of the object, sending an invalidation notification to managers of one or more peer caches.

3. A method in a computing system for determining whether to invalidate at a first time a cache entry whose existing contents were stored at a second time, comprising:

adding to the second time a first amount of time to obtain a third time;

adding to the second time a second amount of time that is longer than the first amount of time to obtain a fourth time;

if the first time is before the third time, determining to use the cache entry without consistency-checking the cache entry;

if the first time is after the fourth time, expiring the cache entry;

if the first time is between the third and fourth times;

randomly or pseudorandomly selecting a value in a range;

if the selected value satisfies a consistency-checking threshold within the range, consistency-checking the cache entry; and

if the selected value does not satisfy the consistency checking threshold, determining to use the cache entry without consistency-checking the cache entry.

4. The method of claim 3, further comprising determining the consistency-checking threshold to reflect the extent of progression of the first time from the third time to the fourth time.

5. The method of claim 3, further comprising:

determining that an explicit invalidation notification has been received from a source associated with the contents of the cache entry; and

in response to so determining, irrespective of the relationship between the first time and the third and fourth times, invalidating the cache entry.

6. The method of claim 3 wherein consistency-checking the cache entry comprises:

obtaining a current version of the contents of the cache entry from a source associated with the contents of the cache entry; and

storing the obtained current version of the contents of the cache entry in the cache entry.

7. The method of claim 6, further comprising, before storing the obtained current version of the contents of the cache entry:

comparing the obtained current version of the contents of the cache entry with the existing contents of the cache entry; and

if the obtained current version of the contents of the cache entry differ from the existing contents of the cache entry, transmitting an invalidation notification to a manager of a peer cache.

8. The method of claim 7 wherein the invalidation notification identifies a datum for which the contents of the cache entry constitute a value, but does not contain any representation of a value of the datum.

9. The method of claim 8 wherein the manager of the peer cache invalidates a cache entry in the peer cache containing a value for the datum identified by the invalidation notification in response to receiving the invalidation notification.

10. The method of claim 7 wherein the invalidation notification identifies a datum for which the contents of the cache entry constitute a value and a digest representation of the current contents of the cache entry, but does not contain a complete representation of a value of the datum.

11. The method of claim 10 wherein the manager of the peer cache invalidates a cache entry in the peer cache containing a value for the datum identified by the invalidation notification in response to receiving the invalidation notification only if the contents of this cache entry in the peer cache has a digest representation that matches the digest representation contained by the invalidation notification.

12. The method of claim 7 wherein the invalidation notification identifies a datum for which the contents of the cache entry constitute a value and a digest representation of the obtained current version of the contents of the cache entry, but does not contain a complete representation of a value of the datum.

13. The method of claim 12 wherein the manager of the peer cache invalidates a cache entry in the peer cache containing a value for the datum identified by the invalidation notification in response to receiving the invalidation notification only if the contents of this cache entry in the peer cache has a digest representation that differs from the digest representation contained by the invalidation notification.

14. The method of claim 7 wherein the invalidation notification identifies a datum for which the contents of the cache entry constitute a value and a complete representation of the obtained current version of the contents of the cache entry.

15. The method of claim 7, further comprising determining whether to include a complete representation of the obtained current version of the contents of the cache entry based upon the size of the obtained current version of the contents of the cache entry.

16. The method of claim 7, further comprising:

determining an amount of time required to obtain a current version of the contents of the cache entry from a source associated with the contents of the cache entry; and

determining whether to include a complete representation of the obtained current version of the contents of the cache entry based upon the determined amount of time.

17. The method of claim 7, further comprising determining whether to include a complete representation of the obtained current version of the contents of the cache entry based upon a cost associated with obtaining a current version of the contents of the cache entry from a source associated with the contents of the cache entry.

18. The method of claim 14 wherein the manager of the peer cache, in response to receiving the invalidation notification:

identifies a cache entry in the peer cache containing a value for the datum identified by the invalidation notification; and

storing the obtained current version of the contents of the cache entry contained in the invalidation notification in the identified cache entry of the peer cache.

19. A computer-readable medium whose contents cause a computing system to perform a method for determining whether to check the consistency of a cache entry, the method comprising:

randomly or pseudorandomly selecting a value in a range;

if the selected value satisfies a consistency-checking threshold within the range, consistency-checking the entry; and

if the selected value does not satisfy the consistency-checking threshold, determining not to consistency-checking the entry.

20. One or more computer memories collectively containing a cache management data structure for use in managing a cache entry, comprising:

information identifying a time at which a minimum lifetime for the cache entry expires; and

information identifying a time at which a maximum lifetime for the cache entry expires,

such that it can be determined whether a time at which the cache entry is accessed is before the expiration of the minimum lifetime, after the expiration of the minimum lifetime but before the expiration of the maximum lifetime, or after the expiration of the maximum lifetime,

and such that the cache entry may be unconditionally used when accessed before the expiration of the minimum lifetime, the cache entry may be probabilistically consistency-checked when accessed after the expiration of the minimum lifetime but before the expiration of the maximum lifetime, and the cache entry may be unconditionally expired when accessed after the expiration of the maximum lifetime.

21. The computer memories of claim 20 wherein the data structure further comprises information specifying an consistency-checking probability value, such that, when the cache entry is accessed after the expiration of the minimum lifetime but before the expiration of the maximum lifetime, the cache entry may be probabilistically consistency-checked by:

generating a random or pseudorandom value;

if the generated value does not exceed the specified consistency-checking probability value, consistency-checking the cache entry; and

if the generated value exceeds the specified consistency-checked probability value, using the cache entry.