3 ms·
Cache replacement algorithms are fascinating and have always been one of my favorite research and development hobbies. I really like the LHD concept but the com
by jandrewrogers 9y ago
Cache replacement algorithms are fascinating and have always been one of my favorite research and development hobbies. I really like the LHD concept but the comparison to other algorithms makes it less informative for practical use cases than it could be. Specifically:
- It primarily compares against relatively weak, naive algorithms like LRU because (inexplicably) that is what many open source systems use. All of the high-performance closed source systems I've seen use better algorithms that are not represented here. Maybe an availability bias? Also, some great algorithms don't even have names AFAIK, just implementations, which doesn't lend them to easy reference.
- CPU cache efficiency of algorithm implementations is often highly relevant to real-world performance of cache replacement algorithms. This is frequently overlooked in the academic literature, which focuses on hit rate under various workloads. Many algorithms that produce good hit rates have poor throughput in practice due to CPU cache behavior; quite a bit of R&D at database companies focuses on minimizing CPU cache thrashing from these algorithms. A slight reduction in hit rate that substantially reduces CPU cache thrashing can be a big win. Cache throughput often comes from surprising places.
- Schedule-based replacement mechanics are ignored. Given some large number of concurrent in-flight operations against the cache, you can adaptively reschedule the order of operations to approximate Bélády's optimal algorithm. For many workloads you can get a step function improvement in cache throughput from this, and it applies to the aforementioned CPU cache efficiency as well. Design of schedule-optimized cache replacement algorithms is not trivial; the obvious way is NP-Hard, so the challenge is in finding efficient approximations.
Generally though, I like the formulation of LHD. It would be interesting to see how it sits in the broader scope of real-world cache replacement algorithm implementations. This is one of those areas in database computer science where the closed source design theory is richer than what makes it into the academic literature, so it is more difficult to figure out what the state-of-the-art even looks like.
- NovaX 9y agoCan you provide examples of closed-source / unnamed algorithms? Most of the advanced algorithms, like ARC, can only provide a modest improvement to LRU. LIRS does quite well, but is complex and usually poorly implemented. The newest generation of systems have begun adopting TinyLFU, with research focusing on making it adaptive. I would be interested in understanding the unpublished work (you can reach out privately if desired: ben.manes @ gmail).