Space-efficient approximated LFU implementation

[arpitbbhayani]

Let's put in relevant approaches and papers to converge upon an implementation. Key pointers

• has to be space efficient
• may not evict the best candidate
• should be fair

[mrchocha]

Nice explanation of LFU approximation
Redis Doc: https://redis.io/docs/manual/eviction/
Article: http://antirez.com/news/109

[Rits1272]

This paper for LFU cache is used by caffeine: https://arxiv.org/pdf/1512.00727 known as TinyLFU
have some interesting ideas apart from small counters and decay mechanism which are mostly the same as those used in Redis

Another interesting paper on cache design that is used by DragonFly: https://arxiv.org/pdf/2003.07302 which maintains a global pool for eviction instead of random pool used in redis