LRU和LRU-K
LRU(Least Recently Used) 是一种根据数据的历史访问频率来淘汰数据的算法，而LRU-K是这种算法的变种之一，其他变种还包括：MQ，2Q
缓存淘汰机制
缓存淘汰机制在缓存需要被清理的时候使用。主要有以下几种算法：
- FIFO：先入先出，优先清理最先被缓存的数据对象。实现简单，直接使用队列就可以实现。
- LRU：最近最久未被使用，优先清理最近没有被使用的对象。使用一个最近使用时间降序的有序队列，优先清理队列对后的数据。与LFU的区别在于：LRU是按照最近使用使用的时间排序，LFU需要维护一个使用频次并用于排序。
- LFU：最近最少使用，优先清理最近最少使用的数据对象。使用一个使用次数降序的有序队列，优先清理队列最后的数据。
// 其中LRU和LFU可以通过维护一个Hashmap来提高访问效率。
LRU / LRU-1
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。实现思路也很简单，就不过多赘述了：
// data to cache
type data struct {
key int
value int
}
// LRUCache structture to support LRU alg.
type LRUCache struct {
recoder map[int]*list.Element // key hit for get op O(1)
linked *list.List // linked-list
rest int // rest capacity
}
// Constructor ... to generate a LRUCache
func Constructor(capacity int) LRUCache {
c := LRUCache{
rest: capacity,
linked: list.New(),
recoder: make(map[int]*list.Element),
}
return c
}
// Get ... O(1) wanted
func (c *LRUCache) Get(key int) int {
v, ok := c.recoder[key]
if !ok {
return -1
}
// hit the key
_ = c.linked.Remove(v)
c.recoder[key] = c.linked.PushFront(v.Value)
fmt.Println("get", key, c.linked.Len(), c.recoder)
return v.Value.(*data).value
}
// Put ... O(1) wanted
func (c *LRUCache) Put(key int, value int) {
if v, ok := c.recoder[key]; ok {
c.linked.Remove(v)
goto h
}
if c.rest == 0 {
tail := c.linked.Back()
c.linked.Remove(tail)
delete(c.recoder, tail.Value.(*data).key)
} else {
c.rest--
}
h:
head := c.linked.PushFront(&data{key, value})
c.recoder[key] = head
}
LRU-K
LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。也就是说没有到达K次访问的数据并不会被缓存，这也意味着需要对于缓存数据的访问次数进行计数，并且访问记录不能无限记录，也需要使用替换算法进行替换。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
简单的描述就是：当访问次数达到K次后，将数据索引从历史队列移到缓存队列中（缓存队列时间降序）；缓存数据队列中被访问后重新排序；需要淘汰数据时，淘汰缓存队列中排在末尾的数据。
相比于LRU-1，缓存数据更不容易被替换，而且偶发性的数据不易被缓存。在保证了缓存数据纯净的同时还提高了热点数据命中率。
code 有点略长
下面的代码只能帮助理解LRU-K的算法思想，并不适用于生产。
// LRUKCache history count struct
type historyCounter struct {
key int
visited uint
}
// LRUKCache .
type LRUKCache struct {
K uint // the K setting
rest uint // max - used = rest
historyRest uint // historyMax - used = historyRest
history *list.List // history doubly linked list
historyHash map[int]*list.Element // history get op O(1)
cache *list.List // cache doubly linked list, save
cacheHash map[int]*list.Element // cache get op O(1)
}
// NewLRUKCache .
func NewLRUKCache(k uint, capacity uint) *LRUKCache {
// ignored
}
// reorderCache cache linked-list to sort (Least Recently Used)
func (c *LRUKCache) reorderCache(ele *list.Element) {
// 默认最近访问的元素排在队首
}
func (c *LRUKCache) cacheReplacingCheck() {
if c.rest == 0 {
// 如果超出容量则删除队尾元素
}
}
func (c *LRUKCache) historyReplacingCheck() {
if c.historyRest == 0 {
// 如果超出容量则删除队尾元素
}
}
func (c *LRUKCache) delfromHistory(key int) {
// 从历史中删除一个元素
}
func (c *LRUKCache) addtoCache(d data) {
// 增加一条缓存记录
}
func (c *LRUKCache) addtoHistory(key, value int) historyCounter {
var (
hc historyCounter
)
hEle, ok := c.historyHash[key]
if ok {
// 如果已经存在于历史队列中，则自增访问次数
hc = hEle.Value.(historyCounter)
hc.visited++
// 如果访问次数达到标准，则从历史中演移除，增加在缓存队列中去
if hc.visited >= c.K {
// true: removed from history, and add into cache
c.delfromHistory(key)
c.addtoCache(data{key: key, value: value})
return hc
}
// 否则写回历史队列
hEle.Value = hc
} else {
// 如果不存在于历史队列中
c.historyReplacingCheck()
hc = historyCounter{key: key, visited: 1}
hEle = c.history.PushFront(hc)
c.historyRest--
}
// 更新历史访问数据
c.historyHash[key] = hEle
return hc
}
// Get key of cache in LRUKCache .
func (c *LRUKCache) Get(key int) (value int, ok bool) {
ele, ok := c.cacheHash[key]
if ok {
c.reorderCache(ele)
return ele.Value.(data).value, true
}
// false: missed
return 0, false
}
// Put of LRUKCache
func (c *LRUKCache) Put(key, value int) {
ele, ok := c.cacheHash[key]
if ok {
// true: hit the key
c.reorderCache(ele)
return
}
_ = c.addtoHistory(key, value)
fmt.Printf("cacheRest: %d / cacheMap: %v \nhistoryRest: %d / historyMap: %v\n\n",
c.rest, c.cacheHash, c.historyRest, c.historyHash)
return
}
testcase
func TestLRUKCache(t *testing.T) {
cache := cp.NewLRUKCache(2, 2)
cache.Put(2, 1)
if _, hit := cache.Get(2); hit {
t.Error("could not get 2 hit")
}
cache.Put(3, 1)
if _, hit := cache.Get(3); hit {
t.Error("could not get 3 hit")
}
cache.Put(3, 1)
if _, hit := cache.Get(3); !hit {
t.Error("should get 3 hit")
}
cache.Put(4, 1)
cache.Put(4, 1)
if _, hit := cache.Get(2); hit {
t.Error("could not get 2 hit")
}
if _, hit := cache.Get(4); !hit {
t.Error("should get 2 hit")
}
if _, hit := cache.Get(3); !hit {
t.Error("should get 3 hit")
}
}
output
# cacheRest: 2, historyRest: 6, k: 2
# cache.Put(2, 1)
cacheRest: 2 / cacheMap: map[]
historyRest: 5 / historyMap: map[2:0xc00006e420]
# cache.Put(3, 1)
cacheRest: 2 / cacheMap: map[]
historyRest: 4 / historyMap: map[2:0xc00006e420 3:0xc0000e0000]
# cache.Put(3, 1)
cacheRest: 1 / cacheMap: map[3:0xc00006e4b0]
historyRest: 5 / historyMap: map[2:0xc00006e420]
# cache.Put(4, 1)
cacheRest: 1 / cacheMap: map[3:0xc00006e4b0]
historyRest: 4 / historyMap: map[2:0xc00006e420 4:0xc00006e570]
# cache.Put(4, 1)
cacheRest: 0 / cacheMap: map[3:0xc00006e4b0 4:0xc0000e00f0]
historyRest: 5 / historyMap: map[2:0xc00006e420]
FAQ
Q1. LRU缓存污染指的是什么情况？
偶发性的、周期性的批量操作会导致LRU命中率急剧下降，这时候缓存中的数据大部分都不是热点数据。
Q2. LRU-K的K值怎么确定？
K值增大，命中率会更高，但是适应性差（清除一个缓存需要大量的数据访问，一般选择LRU-2）。