Cache updating

Patent metadata

Field	Value
Publication number	US-8949535-B1
Application number	US-201313758920-A
Country	US
Kind code	B1
Filing date	Feb 4, 2013
Priority date	Feb 4, 2013
Publication date	Feb 3, 2015
Grant date	Feb 3, 2015

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.

First claim

What is claimed is:

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

Assignees

• Amazon Tech Inc

Inventors

• Hunter Jamie

Classifications

• G06F12/0891 Primary

  using clearing, invalidating or resetting means · CPC title

• G06F8/454 Primary

  Consistency (cache consistency protocols in hierarchically structured memory systems G06F12/0815) · CPC title

• G06F2212/50

  Control mechanisms for virtual memory, cache or TLB · CPC title

• G06F11/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 title

• G06F16/9574 Primary

  of access to content, e.g. by caching · CPC title