欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【Redis】LRU算法和Redis的LRU实现

程序员文章站 2022-04-19 23:16:04
LRU原理 在一般标准的操作系统教材里,会用下面的方式来演示 LRU 原理,假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,LRU就是这样工作的。 但是如果让我们自己设计一个基于 ......

lru原理

在一般标准的操作系统教材里,会用下面的方式来演示 lru 原理,假设内存只能容纳3个页大小,按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间,在上面的,是最近访问的,在下面的是,最远时间访问的,lru就是这样工作的。

【Redis】LRU算法和Redis的LRU实现

但是如果让我们自己设计一个基于 lru 的缓存,这样设计可能问题很多,这段内存按照访问时间进行了排序,会有大量的内存拷贝操作,所以性能肯定是不能接受的。

那么如何设计一个lru缓存,使得放入和移除都是 o(1) 的,我们需要把访问次序维护起来,但是不能通过内存中的真实排序来反应,有一种方案就是使用双向链表。

 

实现lru

1.用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。

2.利用一个链表来实现,每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据丢弃。

3.利用链表和hashmap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

对于第一种方法,需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是o(n)。对于第二种方法,链表在定位数据的时候时间复杂度为o(n)。所以在一般使用第三种方式来是实现lru算法。

 

基于 hashmap 和 双向链表实现 lru 的

整体的设计思路是,可以使用 hashmap 存储 key,这样可以做到 save 和 get key的时间都是 o(1),而 hashmap 的 value 指向双向链表实现的 lru 的 node 节点,如图所示。

【Redis】LRU算法和Redis的LRU实现

lru 存储是基于双向链表实现的,下面的图演示了它的原理。其中 head 代表双向链表的表头,tail 代表尾部。首先预先设置 lru 的容量,如果存储满了,可以通过 o(1) 的时间淘汰掉双向链表的尾部,每次新增和访问数据,都可以通过 o(1)的效率把新的节点增加到对头,或者把已经存在的节点移动到队头。

下面展示了,预设大小是 3 的,lru存储的在存储和访问过程中的变化。为了简化图复杂度,图中没有展示 hashmap部分的变化,仅仅演示了上图 lru 双向链表的变化。我们对这个lru缓存的操作序列如下:

save("key1", 7)

save("key2", 0)

save("key3", 1)

save("key4", 2)

get("key2")

save("key5", 3)

get("key2")

save("key6", 4)

相应的 lru 双向链表部分变化如下:

【Redis】LRU算法和Redis的LRU实现

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

  1. save(key, value),首先在 hashmap 找到 key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果lru空间不足,则通过 tail 淘汰掉队尾的节点,同时在 hashmap 中移除 key。
  2. get(key),通过 hashmap 找到 lru 链表节点,因为根据lru 原理,这个节点是最新访问的,所以要把节点插入到队头,然后返回缓存的值。

 完整基于 java 的代码参考如下

class dlinkednode {
    string 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(string 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(string 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;
    }
}

 

继承linkedhashmap的简单实现:

linkedhashmap底层就是用的hashmap加双链表实现的,而且本身已经实现了按照访问顺序的存储。此外,linkedhashmap中本身就实现了一个方法removeeldestentry用于判断是否需要移除最不常读取的数,方法默认是直接返回false,不会移除元素,所以需要重写该方法。即当缓存满后就移除最不常用的数。

public class lrucache<k, v> extends linkedhashmap<k, v> {

    private final int cache_size;

    // 这里就是传递进来最多能缓存多少数据
    public lrucache(int cachesize) {
        // 设置一个hashmap的初始大小,最后一个true指的是让linkedhashmap按照访问顺序来进行排序,最近访问的放在头,最老访问的就在尾
        super((int) math.ceil(cachesize / 0.75) + 1, 0.75f, true);
        cache_size = cachesize;
    }

    @override
    protected boolean removeeldestentry(map.entry eldest) {
        // 当map中的数据量大于指定的缓存个数的时候,就自动删除最老的数据
        return size() > cache_size;
    }
}

那么问题的后半部分,是 redis 如何实现,这个问题这么问肯定是有坑的,那就是redis肯定不是这样实现的。

redis的lru实现

如果按照hashmap和双向链表实现,需要额外的存储存放 next 和 prev 指针,牺牲比较大的存储空间,显然是不划算的。所以redis采用了一个近似的做法,就是随机取出若干个key,然后按照访问时间排序后,淘汰掉最不经常使用的,具体分析如下:

为了支持lru,redis 2.8.19中使用了一个全局的lru时钟,server.lruclock,定义如下,

#define redis_lru_bits 24
unsigned lruclock:redis_lru_bits; /* clock for lru eviction */

默认的lru时钟的分辨率是1秒,可以通过改变redis_lru_clock_resolution宏的值来改变,redis会在servercron()中调用updatelruclock定期的更新lru时钟,更新的频率和hz参数有关,默认为100ms一次,如下,

#define redis_lru_clock_max ((1<<redis_lru_bits)-1) /* max value of obj->lru */
#define redis_lru_clock_resolution 1 /* lru clock resolution in seconds */

void updatelruclock(void) {
    server.lruclock = (server.unixtime / redis_lru_clock_resolution) &
                                                redis_lru_clock_max;
}

server.unixtime是系统当前的unix时间戳,当 lruclock 的值超出redis_lru_clock_max时,会从头开始计算,所以在计算一个key的最长没有访问时间时,可能key本身保存的lru访问时间会比当前的lrulock还要大,这个时候需要计算额外时间,如下,

/* given an object returns the min number of seconds the object was never
 * requested, using an approximated lru algorithm. */
unsigned long estimateobjectidletime(robj *o) {
    if (server.lruclock >= o->lru) {
        return (server.lruclock - o->lru) * redis_lru_clock_resolution;
    } else {
        return ((redis_lru_clock_max - o->lru) + server.lruclock) *
                    redis_lru_clock_resolution;
    }
}

redis支持和lru相关淘汰策略包括,

  • volatile-lru 设置了过期时间的key参与近似的lru淘汰策略
  • allkeys-lru 所有的key均参与近似的lru淘汰策略

当进行lru淘汰时,redis按如下方式进行的,

......
            /* volatile-lru and allkeys-lru policy */
            else if (server.maxmemory_policy == redis_maxmemory_allkeys_lru ||
                server.maxmemory_policy == redis_maxmemory_volatile_lru)
            {
                for (k = 0; k < server.maxmemory_samples; k++) {
                    sds thiskey;
                    long thisval;
                    robj *o;

                    de = dictgetrandomkey(dict);
                    thiskey = dictgetkey(de);
                    /* when policy is volatile-lru we need an additional lookup
                     * to locate the real key, as dict is set to db->expires. */
                    if (server.maxmemory_policy == redis_maxmemory_volatile_lru)
                        de = dictfind(db->dict, thiskey);
                    o = dictgetval(de);
                    thisval = estimateobjectidletime(o);

                    /* higher idle time is better candidate for deletion */
                    if (bestkey == null || thisval > bestval) {
                        bestkey = thiskey;
                        bestval = thisval;
                    }
                }
            }
            ......

redis会基于server.maxmemory_samples配置选取固定数目的key,然后比较它们的lru访问时间,然后淘汰最近最久没有访问的key,maxmemory_samples的值越大,redis的近似lru算法就越接近于严格lru算法,但是相应消耗也变高,对性能有一定影响,样本值默认为5。