面试题：缓存设计：LRU - K缓存替换策略的基本原理

Question

请简要阐述LRU - K缓存替换策略的基本工作原理，与传统LRU策略相比，它有哪些改进？

Answer 1

LRU - K缓存替换策略基本工作原理

1. 记录访问历史：LRU - K为每个缓存数据项维护一个访问历史列表，记录该数据项的最近K次访问时间戳。
2. 缓存淘汰决策：当缓存空间不足需要淘汰数据时，优先淘汰那些距离当前时间，第K次访问时间最久远的数据。也就是说，不是只看最近一次访问（如传统LRU ），而是综合考虑最近K次访问情况。

与传统LRU策略相比的改进

1. 抗“偶尔访问”数据干扰能力强：传统LRU可能因为某个数据偶尔被访问一次就将其留在缓存中，而LRU - K可以根据K次访问情况，不会轻易因为偶尔的一次访问就保留该数据。例如，某个数据长时间未被访问，突然被访问一次，传统LRU会将其置于缓存头部，但LRU - K会综合多次访问情况，若其他数据的K次访问情况更好，该偶尔访问的数据仍可能被淘汰。
2. 更适应复杂访问模式：在实际应用中，数据访问模式往往较为复杂，LRU - K能通过考虑K次访问来更精准地反映数据的真实访问热度，从而做出更合理的缓存替换决策，相比传统LRU单一依赖最近一次访问的方式，能在复杂场景下提供更好的缓存命中率。