an adaptive replacement cache policy dynamically maintains two lists of pages , a recency list and a frequency list , in addition to a cache directory . the policy keeps these two lists to roughly the same size , the cache size c . together , the two lists remember twice the number of pages that would fit in the cache . at any time , the policy selects a variable number of the most recent pages to exclude from the two lists . the policy adaptively decides in response to an evolving workload how many top pages from each list to maintain in the cache at any given time . it achieves such online , on - the - fly adaptation by using a learning rule that allows the policy to track a workload quickly and effectively . this allows the policy to balance between recency and frequency in an online and self - tuning fashion , in response to evolving and possibly changing access patterns . the policy is also scan - resistant . it allows one - time - only sequential read requests to pass through the cache without flushing pages that have temporal locality . the policy is extremely simple to implement and requires only constant - time overhead per request . the policy has negligible space overhead .