由一道leetcode题引起的LRU算法思考

2019-08-08 本文已影响0人 one_zheng

leetcode题目:

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

LRU原理
LRU(Least recently used,最近最少使用)算法根据数据的访问记录来进行淘汰数据，其核心思想是"如果数据最近被访问过,那么未来被访问的几率也更高"
针对这道题目，需要在 O(1) 时间复杂度内完成获取数据 get 和写入数据 put,我们可以考虑用数据结构Map和双向链表List来实现LRU。

基于HashMap 和双向链表实现LRU
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。

image.png

Go代码实现


// LRUCache Least Reacently Used Cache
type LRUCache struct {
    capacity   int
    hashMap    map[int]*list.Element
    linkedList *list.List
}

// Constructorretruen a LRUCache
func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity:   capacity,
        hashMap:    make(map[int]*list.Element, capacity),
        linkedList: list.New(),
    }
}

// Get return value of the key
func (this *LRUCache) Get(key int) int {

    node, exist := this.hashMap[key]
    if !exist || node == nil {
        return -1
    }

    this.linkedList.MoveToFront(node)

    return spiltValue(node.Value.(string))
}

// Put store key,value
func (this *LRUCache) Put(key int, value int) {

    if this.hashMap[key] != nil {
        node := this.hashMap[key]
        node.Value = join(key, value)
        this.linkedList.MoveToFront(node)
        return
    }

    if this.linkedList.Len() >= this.capacity {
        back := this.linkedList.Back()
        if back == nil {
            return
        }
        this.linkedList.Remove(back)
        this.hashMap[spiltKey(back.Value.(string))] = nil
    }
    this.linkedList.PushFront(join(key, value))
    this.hashMap[key] = this.linkedList.Front()
    return
}

func join(k, v int) string {
    return fmt.Sprintf("%d;%d", k, v)
}

func spiltValue(value string) int {
    str := strings.Split(value, ";")
    if len(str) != 2 {
        return -1
    }
    v, _ := strconv.Atoi(str[1])
    return v
}

func spiltKey(value string) int {
    str := strings.Split(value, ";")
    if len(str) != 2 {
        return -1
    }
    k, _ := strconv.Atoi(str[0])
    return k
}

进阶,Redis中的LRU算法改进

Redis 3.0的淘汰策略
Redis 3.0中LRU是近似LRU的实现。
redis为了减少内存使用，不使用双链表或其他结构管理对象,才用随机算法每次从hash表中随机选择maxmemory-samples配置数量的key(一般5策略最佳),将这些key存入淘汰缓存池(池大小一般是16)，池中entry按照上次访问时间降序排序。每次从池中选择尾部的entery，也就是最差对象淘汰。

源码：

int freeMemoryIfNeeded(void){
    while (mem_freed < mem_tofree) {
        if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
        return REDIS_ERR; /* We need to free memory, but policy forbids. */

        if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
            {......}
        /* volatile-random and allkeys-random policy */
        if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
            {......}
        /* volatile-lru and allkeys-lru policy */
        else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
            server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
        {
            // 淘汰池函数
            evictionPoolPopulate(dict, db->dict, db->eviction_pool);
            while(bestkey == NULL) {
                evictionPoolPopulate(dict, db->dict, db->eviction_pool);
                // 从后向前逐一淘汰
                for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
                    if (pool[k].key == NULL) continue;
                    de = dictFind(dict,pool[k].key); // 定位目标

                    /* Remove the entry from the pool. */
                    sdsfree(pool[k].key);
                    /* Shift all elements on its right to left. */
                    memmove(pool+k,pool+k+1,
                        sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
                    /* Clear the element on the right which is empty
                     * since we shifted one position to the left.  */
                    pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
                    pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;

                    /* If the key exists, is our pick. Otherwise it is
                     * a ghost and we need to try the next element. */
                    if (de) {
                        bestkey = dictGetKey(de); // 确定删除键
                        break;
                    } else {
                        /* Ghost... */
                        continue;
                    }
                }
            }
        }
        /* volatile-ttl */
        else if (server.maxmemory_policy == EDIS_MAXMEMORY_VOLATILE_TTL) {......}

        // 最终选定待删除键bestkey
        if (bestkey) {
            long long delta;
            robj *keyobj = createStringObject(bestkey,sdslenbestkey)); // 目标对象
            propagateExpire(db,keyobj);
            latencyStartMonitor(eviction_latency); // 延迟监控开始
            dbDelete(db,keyobj); // 从db删除对象
            latencyEndMonitor(eviction_latency);// 延迟监控结束
            latencyAddSampleIfNeeded("eviction-del",iction_latency); // 延迟采样
            latencyRemoveNestedEvent(latency,eviction_latency);
            delta -= (long long) zmalloc_used_memory();
            mem_freed += delta; // 释放内存计数
            server.stat_evictedkeys++; // 淘汰key计数，info中可见
            notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted", keyobj, db->id); // 事件通知
            decrRefCount(keyobj); // 引用计数更新
            keys_freed++;
            // 避免删除较多键导致的主从延迟，在循环内同步
            if (slaves) flushSlavesOutputBuffers();
        }
    }
}

该近似LRU算法与理论LRU的效果对比如下：

image.png

按时间顺序接入不同键，此时最早写入也就是最佳淘汰键
浅灰色区域：被淘汰的键
灰色区域：未被淘汰的键
绿色区域：新增写入的键

总结图中展示规律，

图1Theoretical LRU符合预期：最早写入键逐步被淘汰
图2Approx LRU Redis 3.0 10 samples：Redis 3.0中近似LRU算法(采样值为10)
图3Approx LRU Redis 2.8 5 samples：Redis 2.8中近似LRU算法(采样值为5)
图4Approx LRU Redis 3.0 5 samples：Redis 3.0中近似LRU算法(采样值为5)

结论：

通过图4和图3对比：得出相同采样值下，3.0比2.8的LRU淘汰机制更接近理论LRU
通过图4和图2对比：得出增加采样值，在3.0中将进一步改善LRU淘汰效果逼近理论LRU
对比图2和图1：在3.0中采样值为10时，效果非常接近理论LRU

采样值设置通过maxmemory-samples指定，可通过CONFIG SET maxmemory-samples <count>动态设置，也可启动配置中指定maxmemory-samples <count>

Redis 4.0中的新的LRU算法
当我们重新回到问题的原点，哪些key需要我们真正想要保留：将来有最大可能被访问，最频繁被访问，而不是最近被访问的key。
淘汰最少被访问的key算法成为:LFU(Least Frequently Used),将来要被淘汰腾出新空间给新key。
理论上LFU的思想相当简单，只需要给每个key加一个访问计数器。每次访问就自增1，所以也就很容易知道哪些key被访问更频繁。
当然，LFU也会带起其他问题，不单单是针对redis，对于LFU实现：

1、不能使用“移除顶部元素”的方式，keys必须要根据访问计数器进行排序。每访问一次就得遍历所有key找出访问次数最少的key。
2、LFU不能仅仅是只增加每一访问的计数器。正如我们所讲的，访问模式改变随时变化，因此一个有高访问次数的key，后面很可能没有人继续访问它，因此我们的算法必须要适应超时的情况。
在redis中，第一个问题很好解决：我们可以在LRU的方式一样：随机在缓存池中选举，淘汰其中某项。第二个问题redis还是存在，因此一般对于LFU的思想必须使用一些方式进行减少，或者定期把访问计数器减半。
具体细节参考：https://blog.csdn.net/qq_35440678/article/details/53453107

[参考文档]
redis之父的博客翻译-Redis中的LRU算法改进：http://antirez.com/news/109
Redis中内存淘汰算法实现：http://fivezh.github.io/2019/01/10/Redis-LRU-algorithm/
redis缓存机制：https://www.xuejiayuan.net/blog/1a9bb4d25fa8444fa247acd03a3562c8
将redis当做使用LRU算法的缓存来使用：http://www.redis.cn/topics/lru-cache.html
Random notes on improving the Redis LRU algorithm：https://blog.csdn.net/qq_35440678/article/details/53453107

由一道leetcode题引起的LRU算法思考

猜你喜欢

热点阅读