Redis LRU算法

LRU概念

LRU的全称是Least Recently Used即最近最少使用，它是操作系统中一种常见的页面置换算法，其思想是当内存不够用的时候，淘汰那些最近最长未使用的页面。

可以通过命令获取Redis的最大内存和使用的内存淘汰算法：

获取最大内存大小

CONFIG GET maxmemory

CONFIG GET maxmemory-policy

下面解释一般操作系统教材中的LRU算法，假如内存中只能容纳3个页面的大小按照0,2,3,1,2,4,顺序访问，如图所示：

上面的例子中是基于栈的方式设计的LRU算法，那么会涉及到大量的排序工作，增加时间复杂度，可以通过HashMap+双向链表的方式设计一个LRU算法。

LRU算法

使用双向链表可以对数据插入、删除、移动的时间复杂度可以做到O(1)，即只需要一步即可，HashMap使用用来存储链表的Node节点，用来判断是否存在节点，它的时间复杂度也是O(1)。其思想是：对于新增或者最近访问的节点我们将它放到链表的头部，当链表中的长度不够的时候，我们将链表的尾部节点删除即可。参考之前使用Java实现的双向链表代码来实现我们的LRU算法如下：

 import java.util.HashMap;

public class Lru {
    private Node head ; //头部节点
    private Node tail;//尾部节点
    private HashMap<String, Node> hashMap = new HashMap();//所有的node节点
    private Integer size = 3;//最大容量
    //定义内部类节点Node
    private static class Node{
        String key;//key
        Node prev ;//前驱
        Node next;//后置

        public Node(String key) {
            this.key = key;
        }
    }

    /**
     * show
     */
    public void show(){
        Node temp = head;
        while (true) {
            System.out.println(temp.key);
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 移动到首部
     * @param node
     */
    private void moveToHead(Node node) {
        if (head == node) {
            return;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node == tail) {
            tail = tail.prev;
        }
        if (head == null || tail == null) {
            head = tail = node;
            return;
        }
        node.next = head;
        head.prev = node;
        head = node;
        head.prev = null;
    }


    /**
     * 添加元素
     * @param key
     */
    public void add(String key){
        Node node = hashMap.get(key);
        if (null == node) {
            //不存在
            // 如果超过最大容量，移除最后一个节点
            if (hashMap.size()>=this.size) {
                hashMap.remove(key);
                removeTail();
            }
            // 没有超过最大节点，创建一个节点
            node = new Node(key);
        }
        //将该节点添加到链表首部，并放入hashmap
        moveToHead(node);
        hashMap.put(key, node);

    }

    /**
     * 移除尾部节点
     */
    private void removeTail(){
        if (tail != null) {
            tail = tail.prev;
            if (tail == null) {
                head = null;
            } else {
                tail.next = null;
            }
        }
    }

    /**
     * 删除元素
     * @param key
     */
    public void del(String key){
        Node node = hashMap.get(key);
        if (node != null) {
            if (node.prev != null) {
                node.prev.next = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            }
            if (node == head) {
                head = node.next;
            }
            if (node == tail) {
                tail = node.prev;
            }
        }
        hashMap.remove(key);
    }


    public static void main(String args[]){
        //0,2,3,1,2,4
        Lru lru = new Lru();
        lru.add("0");
        lru.add("2");
        lru.add("3");
        lru.add("1");
        lru.add("2");
        lru.add("4");
        lru.show();
    }
}

测试一下

Redis LRU算法

在上面使用hashmap和双向链表的方式，因为有前驱和后置节点需要额外的空间，Redis采用的是一种随机选取key的方式。

它有3次变化

1. 最开始，随机选取3个key，将空闲时间最长的key移除。
2. 然后，将3改为可以配置的参数，默认为N=5，maxmemory-samples 5
3. 最后，因为每次随机选取会选取重复的key，所以为了优化，Redis使用了缓冲池采样的方式，每次采样随机选取的key中，如果它的空间时间大于缓冲池里面的，就将它放到缓冲池中，在需要移除的时候直接从缓冲池中选取最大的空闲时间的key即可。