5 ms·

This is probably over-complicated and would cause hard-to-diagnose behaviour, but here's a random idea: use a multi-armed bandit algorithm to pick which evictio

This is probably over-complicated and would cause hard-to-diagnose behaviour, but here's a random idea: use a multi-armed bandit algorithm to pick which eviction policy to use. You'll want to keep a queue of recent evictions. When you get a cache miss, check if the key was recently evicted, and if so, penalize the algorithm that evicted it. Otherwise, if after a period of time you don't get a cache miss, credit the algorithm that evicted it so it's used more often. This way Redis would self-tune its overall eviction policy to the workloads it's presented with. The idea is that, hopefully, you wouldn't have to do as many upfront trade-offs between conflicting use cases.

jonstewart 10y ago
The problem is that then you have K caching algorithms in use, and the memory used by K-1 of them would be better used if given to the winner. The more sophisticated algorithms that use a combination of recency and frequency, like LIRS and ARC, will adapt to most workloads. 2Queues does better than LRU at not letting sequential reads evict frequently accessed data and it's pretty simple to implement, but, in my experience, LIRS seems to evict low probability data faster, letting you use more memory for higher probability data. Regardless, if you have instrumentation, you can do a lot of testing and offline analysis.