go 实现LRU算法

本文转载自：动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略

缓存算法简介

内存是有限的，因此不可能无限制地添加数据。假定我们设置缓存能够使用的内存大小为 N，那么在某一个时间点，添加了某一条缓存记录之后，占用内存超过了 N，这个时候就需要从缓存中移除一条或多条数据了。那移除谁呢？我们肯定希望尽可能移除“没用”的数据，那如何判定数据“有用”还是“没用”呢？

• FIFO（First In First Out）
  先进先出，也就是淘汰缓存中最老(最早添加)的记录。FIFO 认为，最早添加的记录，其不再被使用的可能性比刚添加的可能性大。

  这种算法的实现也非常简单，创建一个队列，新增记录添加到队尾，每次内存不够时，淘汰队首。

  但是很多场景下，部分记录虽然是最早添加但也最常被访问，而不得不因为呆的时间太长而被淘汰。这类数据会被频繁地添加进缓存，又被淘汰出去，导致缓存命中率降低。

• LFU（Least Frequently Used）
  最少使用，也就是淘汰缓存中访问频率最低的记录。LFU 认为，如果数据过去被访问多次，那么将来被访问的频率也更高。

  LFU 的实现需要维护一个按照访问次数排序的队列，每次访问，访问次数加1，队列重新排序，淘汰时选择访问次数最少的即可。

  LFU 算法的命中率是比较高的，但缺点也非常明显，维护每个记录的访问次数，对内存的消耗是很高的；另外，如果数据的访问模式发生变化，LFU 需要较长的时间去适应，也就是说 LFU 算法受历史数据的影响比较大。例如某个数据历史上访问次数奇高，但在某个时间点之后几乎不再被访问，但因为历史访问次数过高，而迟迟不能被淘汰。

• LRU（Least Recently Used）
  最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU，LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，如果数据最近被访问过，那么将来被访问的概率也会更高。

  LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了，则移动到队尾，那么队首则是最近最少访问的数据，需要淘汰时直接淘汰该条记录即可。

LRU 算法实现

核心数据结构：

这张图很好地表示了 LRU 算法最核心的 2 个数据结构

• 绿色的是字典(map)，存储键和值的映射关系。这样根据某个键(key)查找对应的值(value)的复杂是O(1)，在字典中插入一条记录的复杂度也是O(1)。
• 红色的是双向链表(double linked list)实现的队列。将所有的值放到双向链表中，这样，当访问到某个值时，将其移动到队尾的复杂度是O(1)，在队尾新增一条记录以及删除一条记录的复杂度均为O(1)。

package lru

import "container/list"

type Value interface {
    Len() int
}

type entry struct {
    key   string
    value Value
}

type Cache struct {
    maxBytes  int64 // 缓存最大占用内存, 当为0时表示不作限制
    nBytes    int64 // 当前缓存已经占用的内存
    ll        *list.List
    cache     map[string]*list.Element
    OnEvicted func(key string, value Value) // 被淘汰时的回调函数
}

func NewCache(maxBytes int64, onEvicted func(string, Value)) *Cache {
    return &Cache{
        maxBytes:  maxBytes,
        ll:        list.New(),
        cache:     make(map[string]*list.Element),
        OnEvicted: onEvicted,
    }
}

func (c *Cache) Len() int {
    return c.ll.Len()
}

func (c *Cache) Get(key string) (value Value, exist bool) {
    elem, exist := c.cache[key]
    if exist {
        c.ll.MoveToFront(elem)
        kv := elem.Value.(*entry)
        return kv.value, true
    }

    return
}

func (c *Cache) Add(key string, value Value) {
    elem, exist := c.cache[key]
    if exist {
        c.ll.MoveToFront(elem)
        kv := elem.Value.(*entry)
        c.nBytes += int64(value.Len()) - int64(kv.value.Len())
        kv.value = value
    } else {
        elem := c.ll.PushFront(&entry{key, value})
        c.cache[key] = elem
        c.nBytes += int64(len(key)) + int64(value.Len())
    }

    for c.maxBytes != 0 && c.maxBytes < c.nBytes {
        c.removeOldest()
    }
}

func (c *Cache) removeOldest() {
    elem := c.ll.Back()
    if elem != nil {
        c.ll.Remove(elem)
        kv := elem.Value.(*entry)
        delete(c.cache, kv.key)
        c.nBytes = int64(len(kv.key)) + int64(kv.value.Len())
        if c.OnEvicted != nil {
            c.OnEvicted(kv.key, kv.value)
        }
    }
}

测试代码：

package lru

import (
    "reflect"
    "testing"
)

type String string

func (d String) Len() int {
    return len(d)
}

func TestGet(t *testing.T) {
    lru := NewCache(int64(0), nil)
    lru.Add("key1", String("1234"))
    if v, ok := lru.Get("key1"); !ok || string(v.(String)) != "1234" {
        t.Fatalf("cache hit key1=1234 failed")
    }
    if _, ok := lru.Get("key2"); ok {
        t.Fatalf("cache miss key2 failed")
    }
}

func TestRemoveoldest(t *testing.T) {
    k1, k2, k3 := "key1", "key2", "k3"
    v1, v2, v3 := "value1", "value2", "v3"
    cap := len(k1 + k2 + v1 + v2)
    lru := NewCache(int64(cap), nil)
    lru.Add(k1, String(v1))
    lru.Add(k2, String(v2))
    lru.Add(k3, String(v3))

    if _, ok := lru.Get("key1"); ok || lru.Len() != 2 {
        t.Fatalf("Removeoldest key1 failed")
    }
}

func TestOnEvicted(t *testing.T) {
    keys := make([]string, 0)
    callback := func(key string, value Value) {
        keys = append(keys, key)
    }
    lru := NewCache(int64(10), callback)
    lru.Add("key1", String("123456"))
    lru.Add("k2", String("k2"))
    lru.Add("k3", String("k3"))
    lru.Add("k4", String("k4"))

    expect := []string{"key1", "k2"}

    if !reflect.DeepEqual(expect, keys) {
        t.Fatalf("Call OnEvicted failed, expect keys equals to %s", expect)
    }
}

func TestAdd(t *testing.T) {
    lru := NewCache(int64(0), nil)
    lru.Add("key", String("1"))
    lru.Add("key", String("111"))

    if lru.nBytes != int64(len("key")+len("111")) {
        t.Fatal("expected 6 but got", lru.nBytes)
    }
}