This paper showed that, contrary to common beliefs, FIFO can outperform LRU on cache misses, as well as throughput and scalability.
A cache can be viewed as a logically total-ordered queue with four operations: insertion, removal, promotion, and demotion. Objects in the cache can be compared and ordered based on some metric (e.g., time since the last request), and the eviction algorithm evicts the least valuable object based on the metric. Insertion and removal are user-controlled operations, where removal can either be directly invoked by the user or indirectly via the use of time-to-live (TTL). Promotion and demotion are internal operations of the cache used to maintain the logical ordering between objects.
The key to high cache efficiency is keeping popular objects in cache AND removing unpopular objects faster. Most eviction algorithms are based on LRU. They rely on eager promotion, i.e. promotion to cache head on cache hit. Demotion is performed implicitly: when an object is promoted, other objects are passively demoted, slowly traversing through the cache queue before being evicted.
Since most workloads are powerlaw-distributed, this paper suggests to invert the common wisdom: use lazy promotion with quick demotion. Lazy promotion (LP) comes with several benefits:
In passive demotion, X is demoted by 1) new objects inserted after X and (2) cached objects requested after X. In addition to these two, LP allows cached objects requested before X to also demote X.
Better preserves insertion order, which plays well with the short-lived and quick popularity decay of workloads surveyed.
CLOCK(N), FIFO-Reinsertion, Second-Chance are existing eviction algorithms that uses LP, i.e. promoting only at eviction time. These algorithms are FIFO-based and have low overhead compared to LRU-based eviction algorithms. Despite performing better than LRU on cache efficiency, they weren't able to beat SOTA algorithms.
This paper proposes a QD technique using a probationary FIFO queue and a ghost FIFO queue of the same size as the main cache. It is key that the probationary FIFO queue is tiny (10% in the paper).
This technique demotes quicker because it separates popular objects (i.e. objects visited before being evicted from the small FIFO queue) into main cache and unpopular objects into the ghost queue.
The FIFO ghost queue "evicts" quicker than the main cache.
Objects that are in the ghost queue when requested have gone through the probationary FIFO queue, and hence are directly inserted into the main queue.
Possible caveats: If the working set exhibits abrupt changes, CLOCK might perform worse than LRU.
benclmnt
commented
10 months ago
This paper showed that, contrary to common beliefs, FIFO can outperform LRU on cache misses, as well as throughput and scalability.
The key to high cache efficiency is keeping popular objects in cache AND removing unpopular objects faster. Most eviction algorithms are based on LRU. They rely on eager promotion, i.e. promotion to cache head on cache hit. Demotion is performed implicitly: when an object is promoted, other objects are passively demoted, slowly traversing through the cache queue before being evicted.
Since most workloads are powerlaw-distributed, this paper suggests to invert the common wisdom: use lazy promotion with quick demotion. Lazy promotion (LP) comes with several benefits:
CLOCK(N), FIFO-Reinsertion, Second-Chance are existing eviction algorithms that uses LP, i.e. promoting only at eviction time. These algorithms are FIFO-based and have low overhead compared to LRU-based eviction algorithms. Despite performing better than LRU on cache efficiency, they weren't able to beat SOTA algorithms.
This paper proposes a QD technique using a probationary FIFO queue and a ghost FIFO queue of the same size as the main cache. It is key that the probationary FIFO queue is tiny (10% in the paper).
Possible caveats: If the working set exhibits abrupt changes, CLOCK might perform worse than LRU.
Eviction algorithms: