【数据结构与算法】Redis中LRU算法的基本思想

前言

LRU(least recently used)是一种缓存置换算法。即在缓存有限的情况下，如果有新的数据需要加载进缓存，则需要将最不可能被继续访问的缓存剔除掉。

基于 HashMap 和 双向链表实现 LRU

• 整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 记录需要缓存数据在 LRU 存储中的槽。

image

• 而 LRU 存储是基于双向链表实现的，下面的图演示了它的原理。其中 h 代表双向链表的表头，t 代表尾部。如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，并更新队头。

image

下面总结一下核心操作的步骤:

• 1. save(key)，首先通过 hash 算法，在key space 找到 key，并且尝试把数据存储到LRU空间，如果LRU空间足够，则不需要淘汰旧的内容；如果缓存空间不足，会淘汰掉 tail 指向的内容，并更新队头，存储后返回使用槽下标，更新key space 的value。
• 2. get(key)，通过 hash 找到 key，然后通过 value 找到 LRU空间对应的槽，更新LRU指向关系。
• 完整基于 Java 的代码参考如下

class DLinkedNode {
    int key;
    int value;
    DLinkedNode pre;
    DLinkedNode post;
}

LRU Cache

public class LRUCache {

    private Hashtable<Integer, DLinkedNode>
            cache = new Hashtable<Integer, DLinkedNode>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.post = null;

        head.post = tail;
        tail.pre = head;
    }

    public int get(int key) {

        DLinkedNode node = cache.get(key);
        if(node == null){
            return -1; // should raise exception here.
        }

        // move the accessed node to the head;
        this.moveToHead(node);

        return node.value;
    }

    public void set(int key, int value) {
        DLinkedNode node = cache.get(key);

        if(node == null){

            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            if(count > capacity){
                // pop the tail
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        }else{
            // update the value.
            node.value = value;
            this.moveToHead(node);
        }
    }
    /**
     * Always add the new node right after head;
     */
    private void addNode(DLinkedNode node){
        node.pre = head;
        node.post = head.post;

        head.post.pre = node;
        head.post = node;
    }

    /**
     * Remove an existing node from the linked list.
     */
    private void removeNode(DLinkedNode node){
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }

    /**
     * Move certain node in between to the head.
     */
    private void moveToHead(DLinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }

    // pop the current tail.
    private DLinkedNode popTail(){
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }
}

Redis中的LRU算法

首先Redis并没有使用双向链表实现一个LRU算法。
Redis整体上是一个大的dict,key是一个string,而value都会保存为一个robj（redisObject）。
在Redis的dict中每次按key获取一个值的时候，都会调用lookupKey函数,如果配置使用了LRU模式,该函数会更新value中的lru字段为当前秒级别的时间戳。

Redis3.0的LRU实现算法：

1.第一次随机选取的key都会放入一个pool中(pool的大小为16),pool中的key是按lru时间戳大小顺序排列的。

2.接下来每次随机选取的key的lru值必须小于pool中最小的lru才会继续放入，直到将pool放满。

3.放满之后，每次如果有新的key需要放入，需要将pool中lru最大的一个key取出。

4.需要淘汰的时候，直接从pool中选取一个lru最小的值然后将其淘汰。

参考文章

Redis中的LRU算法实现