Editing Cache replacement policies (section)

=== Simple queue-based policies ===

==== First in first out (FIFO) ====
With this algorithm, the cache behaves like a [[FIFO (computing and electronics)|FIFO queue]]; it evicts blocks in the order in which they were added, regardless of how often or how many times they were accessed before.

==== Last in first out (LIFO) or First in last out (FILO) ====
The cache behaves like a [[Stack (abstract data type)|stack]], and unlike a FIFO queue. The cache evicts the block added most recently first, regardless of how often or how many times it was accessed before.

==== SIEVE ====
'''SIEVE''' is a simple eviction algorithm designed specifically for web caches, such as key-value caches and Content Delivery Networks. 
It uses the idea of lazy promotion and quick demotion.<ref>{{Cite book |last1=Yang |first1=Juncheng |last2=Qiu |first2=Ziyue |last3=Zhang |first3=Yazhuo |last4=Yue |first4=Yao |last5=Rashmi |first5=K. V. |chapter=FIFO can be Better than LRU: The Power of Lazy Promotion and Quick Demotion |date=2023-06-22 |title=Proceedings of the 19th Workshop on Hot Topics in Operating Systems |chapter-url=https://dl.acm.org/doi/10.1145/3593856.3595887 |series=HOTOS '23 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=70–79 |doi=10.1145/3593856.3595887 |isbn=979-8-4007-0195-5}}</ref> Therefore, SIEVE does not update the global data structure at cache hits and delays the update till eviction time; meanwhile, it quickly evicts newly inserted objects because cache workloads tend to show high one-hit-wonder ratios, and most of the new objects are not worthwhile to be kept in the cache. SIEVE uses a single FIFO queue and uses a moving hand to select objects to evict. Objects in the cache have one bit of metadata indicating whether the object has been requested after being admitted into the cache. The eviction hand points to the tail of the queue at the beginning and moves toward the head over time. Compared with the CLOCK eviction algorithm, retained objects in SIEVE stay in the old position. Therefore, new objects are always at the head, and the old objects are always at the tail. As the hand moves toward the head, new objects are quickly evicted (quick demotion), which is the key to the high efficiency in the SIEVE eviction algorithm. SIEVE is simpler than LRU, but achieves lower miss ratios than LRU on par with state-of-the-art eviction algorithms. Moreover, on stationary skewed workloads, SIEVE is better than existing known algorithms including LFU.<ref>{{Cite book |last1=Zhang |first1=Yazhuo |last2=Yang |first2=Juncheng |last3=Yue |first3=Yao |last4=Vigfusson |first4=Ymir |last5=Rashmi |first5=K. V. |date=2024 |title={SIEVE} is Simpler than {LRU}: an Efficient {Turn-Key} Eviction Algorithm for Web Caches |url=https://www.usenix.org/conference/nsdi24/presentation/zhang-yazhuo |language=en |pages=1229–1246 |isbn=978-1-939133-39-7}}</ref>