Random notes on improving the Redis LRU algorithm
Anyone familiar with caching algorithms will groan when they read the description of the &quot;sampling&quot; LRU. First, LRU isn&#x27;t that great--it is a _lot_ better than nothing and having a suitably large cache tends to cover up cache eviction problems, but LRU is still susceptible to a number of problems. The pseudo-LRU redis used to have is appropriate for very high-speed caches (it&#x27;s essentially a 5-way associative cache), but is so very not appropriate when going out to disk, where the access latency is horrible.<p>ARC as mentioned below incorporates the LFU statistics, but it is patent encumbered. A number of other NoSQL systems implement either 2Queues (&quot;Segmented LRU&quot;) or LIRS. My team recently implemented both of these for a block-caching system and found LIRS to perform better for our purposes; essentially LIRS has a bit more information that it collects so it can evict low future-probability data faster and thus retain more data that is likely to be accessed again in the future. It only takes a few more hits to be worth it. The downside to LIRS is that it&#x27;s more complicated than 2Queues, and far less well-described in the literature.<p>See <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Cache_algorithms" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Cache_algorithms</a><p>The thing that&#x27;s really necessary, though, is to collect metrics and to have an instrumented version that will log all accesses. Given a log of all accesses, you can compare whatever implementation you use to Bélády&#x27;s algorithm (i.e., perfection). Without instrumentation and testing, it is very very difficult to know what the right strategy is.<p>Anyway, this helps confirm redis in my mind as a great amateur NoSQL system.