[HN Gopher] FIFO-Reinsertion is better than LRU [pdf]
       ___________________________________________________________________
        
       FIFO-Reinsertion is better than LRU [pdf]
        
       Author : 1a1a11a
       Score  : 33 points
       Date   : 2023-06-22 16:09 UTC (6 hours ago)
        
 (HTM) web link (jasony.me)
 (TXT) w3m dump (jasony.me)
        
       | 1a1a11a wrote:
       | slides here https://jasony.me/slides/hotos23-qdlp.pdf
        
       | ramses0 wrote:
       | Rough Summary:
       | 
       | Start with a dumb-cache using "FIFO" (first in/first out)
       | 
       | Keep track of anything with "hits" while in the cache (simple
       | boolean/bitmap instead of complicated locks/data structures)
       | 
       | Re-insert "hit" items when they would normally be evicted/age out
       | (Lazy Promotion).
       | 
       | BTW, also have a mini-cache in front of the main cache (10% of
       | cache size) which tries to "drop off quickly" (effectively: must
       | have a "hit" within first 10% of being cached).
       | 
       | BTW, also keep track of a "ghost cache" ("hits only", not
       | contents??) for the duration of the overall FIFO-cache, and use
       | that to guide eviction/re-insertion. I'm a little bit unclear on
       | this aspect, but it seems like an "obvious in retrospect" set of
       | guidance.
        
       | singron wrote:
       | Beating plain LRU isn't very interesting, but they also evaluated
       | a bunch of other algorithms (e.g. ARC) and concluded that it
       | performed better than those as well.
       | 
       | I know the ARC paper discusses that other algorithms are often
       | better if properly tuned, although ARC is usually consistently
       | decent in a variety of situations without tuning. It would be
       | awesome to have a new algorithm in that space.
        
       | 1a1a11a wrote:
       | A recent study on over 5000 (key-value, block, object) cache
       | traces from 2007 to 2020 shows that FIFO-Reinsertion is not only
       | faster and more scalable, it is also more efficient (has a lower
       | miss ratio). Maybe it is time to drop LRU from our classroom?
        
       ___________________________________________________________________
       (page generated 2023-06-22 23:02 UTC)