changed:
-
The idea is similar to LFU cache expiry;

http://en.wikipedia.org/wiki/Least_Frequently_Used

Except you add an exponential decay to the access counter. At every request all the counters are decayed before the new access is incremented. This means the access counters represent the exponentially decaying average access count over the last N cache accesses, where N is the timeconstant of the exponential decay used. This should prevent the scan cache-thrashing of LRU, while also preventing the page-burst cache sticking of LFU. The decay could be time based, but it probably makes sense to decay per cache access.

Note that this is similar to http://en.wikipedia.org/wiki/Page_replacement_algorithm#Aging, but more generalized.

An inverted priority queue can be used to keep the expiry order. Before any access all counters are decayed. On a hit, the page is pulled, incremented, and pushed back into the priority queue. On a miss the lowest count in the queue is pulled, and the new loaded page pushed in with a counter of 1. Note that decaying all the counters does not effect their order in the priority queue, since they all decay at the same rate.

To avoid decaying all the counters every access, it is possible to also keep a "time" with every access counter that records when it was last accessed, and the decay calculation can be deferred until that node is updated/compared. Note that the comparison function used in the priority queue needs to calculate the decayed value for comparing. This doubles the metadata size, makes the O(log(N)) pqueue insert/remove operations a bit more expensive, but removes the O(N) count decaying step on each access.

The decay rate could be fixed, but it might make sense to have it dynamically adjust based on the performance of the cache. The overall performance of the cache can be calculated as the average of all the access counters. A number below 1 suggests very bad performance, with less than 1 access per cache entry average over the last N timeconstant accesses. A number >1 suggests good cache hitrates. Note that the cache performance can be incrementally updated every cache access without having to scan all the cache entries. The average is just decayed the same as each 
counter, if there was a miss, decrement it by the flushed page counter, then add 1 for the new page access.

Note that dynamically adjusting the decay timeconstant messes a bit with deferred delay calculations, since very old pages in the cache are likely to have "decayed" at different rates. It's also possible that the order in the pqueue could be wrong.

In python;

class Cache(object):

  def __init__(self, size):
    self.size=size
    self.pqueue

etc.