`
August 12, 2019 本文阅读量

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)。