Dynamic cache eviction

• US 8,533,393 B1
• Filed: 12/14/2010
• Issued: 09/10/2013
• Est. Priority Date: 12/14/2010
• Status: Active Grant

• Current Assignee: Expedia Inc. (Expedia Group, Inc.)
• Original Assignee: Expedia Inc. (Expedia Group, Inc.)
• Inventors: Cote, Pierre Paul, Antosz, Waclaw T, Hammer, Eric
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): Thammavong, Prasith
• Application Number:
  US12/967,727
• Time in Patent Office: 1,001 Days
• Field of Search: 711/135, 711/118
• US Class Current: 711/118
• CPC Class Codes: G06F 11/3442 for planning or managing the needed capacity
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A cache manager monitors storage capacity levels of a cache node storing data as cache entries. Upon determining a storage capacity threshold is reached, the cache manager begins evicting cache entries. In evicting the cache entries, the cache manager identifies a reduction level, and configures one or more time steps. The cache manager evicts cache entries within the one or more time steps until the reduction level is achieved.

Claims

1. A computer-implemented method for evicting cache entries from a cache node, the method comprising:

under the control of one or more computing devices;

monitoring storage capacity levels of a cache node storing a plurality of cache entries;

determining a storage capacity threshold of the cache node has been reached;

upon determining that the storage capacity threshold has been reached;

identifying a cache reduction level, the cache reduction level indicating a target cache reduction;

identifying a first cache entry from the one or more cache entries;

configuring a plurality of time steps, each time step indicating a range of time, the plurality of time steps including a first time step beginning with the first cache entry and indicating a first range of time;

identifying one or more time steps of the plurality of time steps in which the plurality of cache entries are located;

evicting one or more cache entries within the first time step from the cache;

determining the cache reduction level has not been achieved upon evicting the one or more cache entries within the first time step;

altering a size of one or more additional time steps based at least on a percentage of the plurality cache entries within the first time step; and

evicting one or more cache entries within the one or more additional time steps until the cache reduction level is achieved.

2. The computer-implemented method of claim 1, wherein monitoring the storage capacity levels comprises monitoring at least one of an amount of data stored by the one or more cache entries, a number of cache entries, a number of evictions, and an amount of data removed with each eviction.

3. The computer-implemented method of claim 1, wherein the target cache reduction is at least one of a percentage of the storage capacity, and an amount of the storage capacity.

4. The computer-implemented method of claim 1, wherein each cache entry comprises a time stamp and the first cache entry is identified as the cache entry with the oldest time stamp.

5. The computer-implemented method of claim 4, wherein

evicting the one or more cache entries within the first time step comprises:

comparing the time stamp of each cache entry stored in the cache node with the first range of time; and

evicting each cache entry with a time stamp within the first range of time.

6. The computer-implemented method of claim 4, wherein for each of the one or more additional time steps, evicting one or more cache entries comprises:

comparing the time stamp of each cache entry stored in the cache node with the range of time of an additional time step; and

evicting each cache entry with a time stamp within the range of time of the additional time step.

7. The computer-implemented method of claim 1, wherein the number of the plurality of time steps is predefined.

8. The computer-implemented method of claim 1, wherein the size of the plurality of time steps is uniform.

9. The computer-implemented method of claim 1, wherein the cache reduction level is predefined.

10. The computer-implemented method of claim 1, wherein the step size of the plurality of time steps is determined based at least in part on an eviction cost and a cache miss cost.

11. A system comprising:

one or more cache nodes configured to store a plurality of cache entries; and

a computing device in communication with the one or more cache nodes, the computing device configured to;

monitor a storage capacity level of at least one cache node;

determine a storage capacity threshold of the at least one cache node has been reached;

upon determining that the storage capacity threshold has been reached;

identify a cache reduction level, the cache reduction level indicating a target reduction of cache entries in the cache node;

configure a plurality of time steps, each time step indicating a range of time;

evict one or more cache entries within a first time step of the plurality of time steps;

determine the cache reduction level has not been achieved upon evicting the one or more cache entries within the first time step;

alter a size of one or more additional time steps based at least on a percentage of the plurality cache entries within the first time step; and

evict one or more cache entries within the one or more additional time steps until the cache reduction level is achieved.

12. The system of claim 11, wherein the computing device is further configured to evict all cache entries within a previous time step before evicting any cache entries within a subsequent time step.

13. The system of claim 11, wherein each cache entry comprises a time stamp.

14. The system of claim 13, wherein to evict the one or more cache entries within the one or more additional time steps, the computing device is configured to:

compare the time stamp of each cache entry with the range of time of a current time step; and

evict each cache entry with a time stamp within the range of time of the current time step.

15. The system of claim 11, wherein the cache reduction level is based at least in part on at least one of cost of a cache miss, the storage capacity of the at least one cache node, the amount of traffic experienced by the at least one cache node, and the processing speed of the at least one cache node.

16. The system of claim 11, wherein the storage capacity threshold is based at least in part on at least one of cost of a cache miss, the storage capacity of the at least one cache node, the amount of traffic experienced by the at least one cache node, and the processing speed of the at least one cache node.

17. The system of claim 11, wherein to monitor the storage capacity level the computing device is configured to monitor at least one of an amount of data stored by the one or more cache entries, a number of cache entries, a number of evictions, and an amount of data removed with each eviction.

18. The system of claim 11, wherein the step size of the plurality of time steps is determined based at least in part on an eviction cost and a cache miss cost.

19. A computer-readable, non-transitory storage medium having a computer-executable component for evicting cache entries from a cache node, the computer-executable component comprising:

a cache manager component operable to;

monitor a storage capacity level of a cache node storing one or more cache entries;

determine if a storage capacity threshold of the cache node has been reached;

upon determining that the storage capacity threshold has been reached;

configure a plurality of time steps, each time step indicating a range of time;

evict one or more cache entries within a first time step of the plurality of time steps;

determine the cache reduction level has not been achieved upon evicting the one or more cache entries within the first time step;

alter a size of one or more additional time steps based at least on a percentage of the plurality cache entries within the first time step; and

evict each cache entry within the one or more additional time steps until a cache reduction level is achieved.

20. The computer-readable non-transitory storage medium of claim 19, wherein the cache manager component is further operable to evict all cache entries within a previous time step before evicting any cache entries within a subsequent time step.

21. The computer-readable non-transitory storage medium of claim 19, wherein each cache entry comprises a time stamp.

22. The computer-readable, non-transitory storage medium of claim 21, wherein to evict the one or more cache entries within the one or more additional time steps, the cache manager component is further operable to:

compare the time stamp of each cache entry with the range of time of a current time step; and

evict each cache entry with a time stamp within the range of time of the current time step.

23. The computer-readable, non-transitory storage medium of claim 19, wherein the cache reduction level is based at least in part on at least one of the storage capacity of the cache node, the amount of traffic experienced by the cache node, and the processing speed of the cache node.

24. The computer-readable, non-transitory storage medium of claim 19, wherein the storage capacity threshold is based at least in part on at least one of the storage capacity of the cache node, the amount of traffic experienced by the cache node, and the processing speed of the cache node.

25. The computer-readable, non-transitory storage medium of claim 19, wherein the cache manager component is further operable to determine the step size of the plurality of time steps based at least in part on an eviction cost and a cache miss cost.