LRU

LRU和LRU-K

August 12, 2019
LRU, LRU-K, Caching, Algorithm

缓存淘汰机制 #

缓存淘汰机制在缓存需要被清理的时候使用。主要有以下几种算法：

  • 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次访问时间距当前时间最大的数据。

...

访问量 访客数