Cache updating

• US 8,949,535 B1
• Filed: 02/04/2013
• Issued: 02/03/2015
• Est. Priority Date: 02/04/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Hunter, Jamie
• Primary Examiner(s): Elmore, Stephen
• Application Number:
  US13/758,920
• Time in Patent Office: 729 Days
• Field of Search: 711/119, 711/154, 711/156, 711/158
• US Class Current: 711/119
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 2212/50 Control mechanisms for virtual memory, cache or TLB
• CPC Class Codes: G06F 8/454 Consistency cache consistency protocols in hierarchically structured memory systems G06F12/0815

Abstract

Technology is described for performing cache data invalidations. The method may include identifying cache update information at a first cache. The cache update information may identify a cache entry (e.g., a trending cache entry). A second cache may be selected to receive the cache update information from the first cache. The cache update information identifying the cache entry may be sent from the first cache to the second cache. For example, the second cache may be populated by adding the trending cache entry into the second cache.

Claims

1. A method for performing cache updates, the method comprising:

under the control of one or more computer systems configured with executable instructions;

identifying cache update information stored on a source server, the cache update information identifying an invalid cache entry;

selecting a receiving server to receive the cache update information from the source server, the source server selecting the receiving server by using a gossip protocol;

sending the cache update information identifying the invalid cache entry from the source server to the receiving server; and

invalidating the invalid cache entry by marking the invalid cache entry on the receiving server based on the cache update information exchanged between the source server and the receiving server.

2. The method of claim 1, further comprising:

sending an updated cache entry that is trending from the source server to the receiving server; and

populating the receiving server by adding a cache entry that is trending based on the cache update information received from the source server.

3. The method of claim 1, further comprising:

receiving a second cache entry associated with the receiving server, the second cache entry having a second version number;

comparing the second version number of the second cache entry with a first version number of a first cache entry on the source server; and

determining the second cache entry is stale based on the second version number being older than the first version number.

4. The method of claim 3, further comprising invalidating the second cache entry by deleting the second cache entry that is stale and replacing the second cache entry with the first cache entry.

5. The method of claim 1, wherein the invalid cache entry included in the cache update information relates to at least one of the following:

an authorization permission;

a trending cache entry;

product information;

audio information; and

video information.

6. The method of claim 1, further comprising sending the cache update information from the source server to a plurality of receiving servers.

7. A method for performing cache updates, the method comprising:

under the control of one or more computer systems configured with executable instructions;

identifying cache update information at a first cache, the cache update information including a cache entry;

selecting a second cache at random to receive the cache update information from the first cache; and

sending the cache update information identifying the cache entry from the first cache to the second cache.

8. The method of claim 7, further comprising sending the cache update information to a plurality of additional caches based on a gossip protocol.

9. The method of claim 7, further comprising invalidating the cache entry at the second cache by marking the cache entry as invalid based on the cache update information received from the first cache.

10. The method of claim 7, wherein selecting a second cache to receive the cache update information from the first cache is performed by the first cache based on a gossip protocol.

11. The method of claim 7, further comprising:

exchanging cache update information between the second cache and the first cache, the cache update information including a cache entry that has trending information; and

populating the second cache by adding the cache entry into the second cache, the cache entry including the trending information based on the cache update information received from the first cache.

12. The method of claim 11, wherein exchanging the cache update information between the second cache and the first cache comprises exchanging cache update information between a second cache server associated with the second cache and a first cache server associated with the first cache.

13. The method of claim 7, further comprising:

receiving a first cache entry from the first cache, at the second cache, the first cache entry having a first version value;

comparing the first version value of the first cache entry with a second version value, the second version value being associated with a second cache entry of the second cache; and

invalidating the second cache entry by replacing the second cache entry with the first cache entry, based on the second version value of the second cache entry being older than the first version value of the first cache entry.

14. The method of claim 7, further comprising:

receiving a request to access a cache entry stored on the first cache;

determining whether the cache entry requested is valid based on a staleness timeout period of the cache entry requested; and

providing a valid cache entry in response to the request received upon determining that the cache entry requested is within the staleness timeout period.

15. The method of claim 7, wherein selecting a second cache to receive the cache update information from the first cache comprises selecting the second cache using a random time period based on a gossip protocol.

16. The method of claim 7, wherein selecting a second cache to receive the cache update information from the first cache comprises selecting the second cache at random based on a gossip protocol.

17. The method of claim 7, wherein selecting a second cache to receive the cache update information from the first cache comprises:

registering the second cache to be included in a host class; and

selecting the second cache at random from the host class.

18. The method of claim 8, wherein invalidating the cache entry at the second cache further comprises:

storing the cache entry that is invalid at the second cache; and

deleting the cache entry from the second cache upon exceeding a threshold number of stored cache entries that are invalid.

19. The method of claim 7, wherein the cache entry included in the cache update information relates to at least one of the following:

an authorization permission;

audio information;

video information; and

product data.

20. A method for accessing cache data, the method comprising:

under the control of one or more computer systems configured with executable instructions;

identifying cache update information at an information source server, the cache update information identifying an invalid cache entry;

selecting a first server to receive the cache update information from the information source server, the information source server selecting the first server by using a gossip protocol; and

sending the cache update information identifying the invalid cache entry to the first server from the information source server.

21. The method of claim 20, further comprising:

receiving the cache update information identifying the invalid cache entry at the first server as sent from the information source server;

selecting a second server to receive the cache update information from the first server, the first server selecting the second server by using the gossip protocol; and

sending the cache update information identifying the invalid cache entry from the first server to the second server.

22. The method of claim 20, further comprising:

receiving the cache update information identifying an updated cache entry that is trending at the first server from the information source server; and

populating the first server by adding a cache entry that is trending from the cache update information received from the information source server.

23. The method of claim 20, further comprising:

receiving a request from an application to access a cache entry stored on the first server;

querying the information source server to determine whether the cache entry requested is valid;

receiving a response from the information source server verifying that the cache entry requested is valid; and

providing a valid cache entry from the first server to the application in response to the request received.

24. A system for performing cache data invalidation, the system comprising:

a processor;

a memory device including a cache data store to store a plurality of cache entries of data, and instructions that, when executed by the processor, cause the processor to execute;

an identification module configured to identify cache update information stored on a cache data store, the cache update information identifying an invalid cache entry, an updated cache entry, or a cache entry that is trending;

a selection module configured to randomly select a receiving server to receive the cache update information from the cache data store using a gossip protocol; and

an exchange module configured to exchange the cache update information identifying the invalid cache entry with the receiving server.

25. The system of claim 24, further comprising a cache data invalidation module configured to mark the invalid cache entry as invalid based on the cache update information received from the receiving server.

26. The system of claim 24, further comprising a cache population module configured to add a trending cache entry or an updated cache entry to a second cache data store based on the cache update information exchanged.

27. The system of claim 24, wherein the exchange module is further configured to:

exchange a first cache entry from the cache data store and a second cache entry from the receiving server, the first cache entry having a first version number and the second cache entry having a second version number;

compare the first version number from the cache data store with the second version number of the second cache entry; and

determine that the second cache entry is stale based on the second version number being older than the first version number.