LRU：（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

在k8s.io/apimachinery/pkg/util/cache这个代码库中，实现了LRUExpireCache数据结构，他的功能类似于LRU但不完全是。LRUExpireCache可以设定数据结构的大小，当输出超过指定的大小的时候，会自动删除最不常用的数据，这里可能是根据时间点来判断的，我还没怎么细看源码。然后可以对每一个key值设定过期时间，类似于redis，超过该key值的过期时间，该key值会自动删除。

type ipAddrInfo struct {
    province string
    city     string
    isp      string
    desc     string
}
func Lrue() {
    cacheInstence := cache.NewLRUExpireCache(2)
    cacheInstence.Add("2", ipAddrInfo{province: "2"}, 11*time.Second)
    cacheInstence.Add("1", ipAddrInfo{province: "1"}, 10*time.Second)
    cacheInstence.Add("3", ipAddrInfo{province: "3"}, 2*time.Second)

    time.Sleep(time.Second * 1)
    value, is := cacheInstence.Get("1")
    if is {
        fmt.Println(value.(ipAddrInfo).province)
    } else {
        fmt.Println(3, "取不到数据")
    }

    value, is = cacheInstence.Get("2")
    if is {
        fmt.Println(2, value.(ipAddrInfo).province)
    } else {
        fmt.Println("取不到数据")
    }

    value, is = cacheInstence.Get("3")
    if is {
        fmt.Println(3, value.(ipAddrInfo).province)
    } else {
        fmt.Println("取不到数据")
    }
    time.Sleep(time.Second * 2)
    value, is = cacheInstence.Get("3")
    if is {
        fmt.Println(3, value.(ipAddrInfo).province)
    } else {
        fmt.Println("取不到数据")
    }
}

由上述运行结果可见，先添加的元素，不管他的过期时间是多少，当需要剔除元素时，都是剔除最先添加的元素。根据元素3可知，当某个元素到期时，也会自动删除。

修改

由与在剔除key值，不能根据最近原则进行删除，我们可以在get的时候将取出的元素重新添加到该数据结构中，将原来的删除（内部已经实现），这样，就变相的实现了，最近最新原则（刚刚查过的和最新添加的最后删除）。我们在cache中添加一个函数

func (c *LRUExpireCache) GetAndSetTimeOut(key interface{}, ttl time.Duration) (interface{}, bool) {
    c.lock.Lock()
    defer c.lock.Unlock()
    e, ok := c.cache.Get(key)
    if !ok {
        return nil, false
    }
    // 这是新增加的一步 cache会将已存在的key删掉，并存储新的
    c.cache.Add(key, &cacheEntry{e.(*cacheEntry).value, c.clock.Now().Add(ttl)})

    if c.clock.Now().After(e.(*cacheEntry).expireTime) {
        c.cache.Remove(key)
        return nil, false
    }
    return e.(*cacheEntry).value, true
}

我们使用经过修改后的函数

func LrueSetTimeOut() {
    cacheInstence := cache.NewLRUExpireCache(2)
    cacheInstence.Add("1", ipAddrInfo{province: "1"}, 2*time.Second)
    cacheInstence.Add("2", ipAddrInfo{province: "2"}, 10*time.Second)

    time.Sleep(time.Second * 1)
    value, is := cacheInstence.GetAndSetTimeOut("1", 2*time.Second)
    if is {
        fmt.Println(value.(ipAddrInfo).province)
    } else {
        fmt.Println("取不到数据")
    }
    time.Sleep(time.Second * 1)

    value, is = cacheInstence.GetAndSetTimeOut("1", 2*time.Second)
    if is {
        fmt.Println(value.(ipAddrInfo).province)
    } else {
        fmt.Println(1, "取不到数据")
    }
    cacheInstence.Add("3", ipAddrInfo{province: "2"}, 10*time.Second)

    value, is = cacheInstence.GetAndSetTimeOut("2", 2*time.Second)
    if is {
        fmt.Println(2, value.(ipAddrInfo).province)
    } else {
        fmt.Println("取不到数据")
    }
    value, is = cacheInstence.GetAndSetTimeOut("1", 2*time.Second)
    if is {
        fmt.Println(1, value.(ipAddrInfo).province)
    } else {
        fmt.Println("取不到数据")
    }
}

执行结果：

由执行结果可见，虽然我们设定1的过期时间为2s但是我们每次get的时候，重新设定了他的过期时间，这样它只有在最后一次get设定的过期时间到了的时候才会删除。。另外，我们先添加了key=1再添加了key=2，然后get（1）再添加一个3，此时根据最近最新的原则，应该2被删除1和3保留。根据运行结果显示，的确如此。

好了，我要去好好看源码了。希望不要误导大家，另外这样实现，不知道并发性能怎么样。