Redis LRU机制

发表于2022-03-21更新于2022-05-07阅读次数

LRU概述

LRU 是 Least Recently Used 的缩写，即最近最少使用，是内存管理的一种页面置换算法。算法的核心是：如果一个数据在最近一段时间内没有被访问到，那么它在将来被访问的可能性也很小。换言之，当内存达到极限时，应该把内存中最久没有被访问的数据淘汰掉。

Java LRU实现

实现 LRU 算法除了需要 key/value 字典外，还需要附加一个链表，链表中的元素按照一定的顺序进行排列。当空间满的时候，会踢掉链表尾部的元素。当字典的某个元素被访问
时，它在链表中的位置会被移动到表头。所以链表的元素排列顺序就是元素最近被访问的时间顺序。
这里可以使用 HashMap 存储 key，这样可以做到 set 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点。

其中 h 代表双向链表的表头，t 代表尾部。首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

具体操作步骤

  • set(key, value)，首先在HashMap找到Key对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过tail淘汰掉队尾的节点，同时在HashMap中移除 Key。

  • get(key)，通过HashMap找到LRU链表节点，把节点插入到队头，返回缓存的值

Redis 近似LRU算法

Redis 使用的是一种近似 LRU 算法，它跟 LRU 算法还不太一样。之所以不使用 LRU 算法，是因为需要消耗大量的额外的内存，需要对现有的数据结构进行较大的改造。近似LRU 算法则很简单，在现有数据结构的基础上使用随机采样法来淘汰元素，能达到和 LRU 算法非常近似的效果。

Redis 为实现近似 LRU 算法，它给每个 key 增加了一个额外的小字段，这个字段的长度是 24 个 bit。每个对象的每次被访问都会记录下当前服务器的LRU时钟，然后用服务器的LRU时钟减去对象本身的时钟，得到的就是这个对象没有被访问的时间间隔（也称空闲时间），空闲时间最大的就是需要淘汰的对象。

淘汰策略

当 Redis 执行写操作时，发现内存超出 maxmemory，就会执行一次LRU 淘汰算法。这个算法也很简单，就是随机采样出 5(可以配置) 个 key，然后淘汰掉最旧的 key，如果淘汰后内存还是超出 maxmemory，那就继续随机采样淘汰，直到内存低于maxmemory 为止。

如何采样就是看 maxmemory-policy 的配置，如果是 allkeys 就是从所有的 key 字典中随机，如果是volatile就从带过期时间的 key 字典中随机。每次采样多少个key看的是maxmemory_samples的配置，默认为 5。

Redis缓存淘汰策略与Redis键的过期删除策略并不完全相同，前者是在Redis内存使用超过maxmemory使用的淘汰策略；而后者是通过定期删除+惰性删除两者结合的方式淘汰内存过期键的。

Redis LRU行为配置参数

Redis系统中与LRU功能相关的配置参数有三个:

  • maxmemory: 该参数即为缓存数据占用的内存限制。当缓存的数据消耗的内存超过这个数值限制时，将触发数据淘汰。该数据配置为0时，表示缓存的数据量没有限制， 即LRU功能不生效
  • maxmemory_policy: 淘汰策略，定义参与淘汰的数据的类型和属性
  • maxmemory_samples: 随机采样的精度， 该数值配置越大， 越接近于真实的LRU算法，但是数值越大， 消耗的CPU计算时间越多，执行效率越低

Redis LRU执行过程

Redis数据库结构定义

Redis在每个数据库结构中使用了两个不同的哈希表来管理缓存数据。 Redis数据库结构的定义为(redis.h):

1
2
3
4
5
6
7
8
9
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;
    long long avg_ttl;          /* Average TTL, just for stats */
} redisDb;

哈希表expires存储具有超时属性的数据，哈希表dict既存储没有超时属性的数据, 也存储具有超时属性的数据,即哈希表dict中存储的是全量的缓存数据。

淘汰逻辑

在函数freeMemoryIfNeeded实现淘汰缓存的数据,其实现为(redis.c):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
int freeMemoryIfNeeded(void) {
    //省略部分代码
 
    /* Check if we are over the memory limit. */
    if (mem_used <= server.maxmemory) return REDIS_OK;
    //执行NO_EVICTION淘汰策略
    if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
        return REDIS_ERR; /* We need to free memory, but policy forbids. */

    /* Compute how much memory we need to free. */
    mem_tofree = mem_used - server.maxmemory;
    mem_freed = 0;
    latencyStartMonitor(latency);
    while (mem_freed < mem_tofree) {
        int j, k, keys_freed = 0;

        for (j = 0; j < server.dbnum; j++) {
            long bestval = 0; /* just to prevent warning */
            sds bestkey = NULL;
            struct dictEntry *de;
            redisDb *db = server.db+j;
            dict *dict;

           // ALLKEYS_LRU、ALLKEYS_RANDOM淘汰策略就从哈希表dict淘汰缓存、否则从哈希表expires淘汰缓存
            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
            {
                dict = server.db[j].dict;
            } else {
                dict = server.db[j].expires;
            }
            if (dictSize(dict) == 0) continue;

            /* volatile-random and allkeys-random policy */
            if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
            {
                de = dictGetRandomKey(dict);
                bestkey = dictGetKey(de);
            }

            /* 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;
                    }
                }
            }

            /* volatile-ttl */
            else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
                for (k = 0; k < server.maxmemory_samples; k++) {
                    sds thiskey;
                    long thisval;

                    de = dictGetRandomKey(dict);
                    thiskey = dictGetKey(de);
                    thisval = (long) dictGetVal(de);

                    /* Expire sooner (minor expire unix timestamp) is better
                     * candidate for deletion */
                    if (bestkey == NULL || thisval < bestval) {
                        bestkey = thiskey;
                        bestval = thisval;
                    }
                }
            }

            /* Finally remove the selected key. */
            if (bestkey) {
                long long delta;

                robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
                propagateExpire(db,keyobj);
                /* We compute the amount of memory freed by dbDelete() alone.
                 * It is possible that actually the memory needed to propagate
                 * the DEL in AOF and replication link is greater than the one
                 * we are freeing removing the key, but we can't account for
                 * that otherwise we would never exit the loop.
                 *
                 * AOF and Output buffer memory will be freed eventually so
                 * we only care about memory used by the key space. */
                delta = (long long) zmalloc_used_memory();
                dbDelete(db,keyobj);
                delta -= (long long) zmalloc_used_memory();
                mem_freed += delta;
                server.stat_evictedkeys++;
                notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
                    keyobj, db->id);
                decrRefCount(keyobj);
                keys_freed++;

                /* When the memory to free starts to be big enough, we may
                 * start spending so much time here that is impossible to
                 * deliver data to the slaves fast enough, so we force the
                 * transmission here inside the loop. */
                if (slaves) flushSlavesOutputBuffers();
            }
        }
        if (!keys_freed) {
            latencyEndMonitor(latency);
            latencyAddSampleIfNeeded("eviction-cycle",latency);
            return REDIS_ERR; /* nothing to free... */
        }
    }
    latencyEndMonitor(latency);
    latencyAddSampleIfNeeded("eviction-cycle",latency);
    return REDIS_OK;
}

局部变量mem_tofree表示需要淘汰的内存，局部变量mem_freed表示已经淘汰的内存。
循环执行while (mem_freed < mem_tofree)淘汰缓存数据，该循环中的逻辑可以概括为:

  • 从全局的0号数据库开始(Redis默认有16个全局的数据库)，根据淘汰策略,选择该数据库中的哈希表。如果该哈希表为空， 选择下一个全局数据库
  • 根据淘汰策略，在相应哈希表中找到一个待淘汰的key，从该数据库对象中删除该key所对应的缓存数据
  • 如果没有找到待淘汰的key，即无法淘汰所需的缓存数据大小函数直接返回错误
  • 如果当前访问的是最后一个全局数据库， 并且已经淘汰了所需的缓存数据,则该函数成功返回.如果没有淘汰所需的缓存数据,则返回步骤1,并且从0号数据库重新淘汰
  • 如果当前访问的不是最后一个全局数据库， 则返回步骤1， 从当前数据库的下一个数据库继续淘汰缓存数据

1、如果淘汰策略是allkeys-random或者volatile-random，则从相应数据库中随机选择一个key进行淘汰
2、如果淘汰策略是allkeys-lru或者volatile-lru，则根据配置的采样值maxmemory_samples，随机从数据库中选择maxmemory_samples个key， 淘汰其中热度最低的key对应的缓存数据
3、如果淘汰策略是volatile-ttl，则根据配置的采样值maxmemory_samples，随机从数据库中选择maxmemory_samples个key，淘汰其中最先要超时的key对应的缓存数据

从数据库的哈希表结构中随机返回一个key的执行函数为dictGetRandomKey，执行过程分为两步:

  • 在哈希表中随机选择一个非空的桶(bucket)
  • 在该桶的冲突链表中随机选择一个节点
更新缓存对象热度值

Redis中的对象结构定义为(redis.h):

1
2
3
4
5
6
7
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

即对象结构中存在一个lru字段， 且使用了unsigned的低24位(REDIS_LRU_BITS定义的值)
Redis命令访问缓存的数据时，均会调用函数lookupKey去更新对象lru值，其实现为(db.c):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
robj *lookupKey(redisDb *db, robj *key) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);

        /* Update the access time for the ageing algorithm.
         * Don't do it if we have a saving child, as this will trigger
         * a copy on write madness. */
        if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
            val->lru = server.lruclock;
        return val;
    } else {
        return NULL;
    }
}

对象的lru值会被设置为全局的server.lruclock值。当然，在对象创建的时候也会将该lru字段设置为全局的server.lruclock。
lookupKey()不会直接被 redis 命令调用，往往是通过lookupKeyRead()、lookupKeyWrite() 、lookupKeyReadWithFlags() 间接调用的。这个函数的作用是通过传入的 key 查找对应的 redis 对象，并且会在条件满足时设置上 LRU 时钟。

而全局的server.lruclock是在定时任务函数serverCron中调用函数updateLRUClock更新的(redis.c):

1
2
3
4
void updateLRUClock(void) {
    server.lruclock = (server.unixtime/REDIS_LRU_CLOCK_RESOLUTION) &
                                                REDIS_LRU_CLOCK_MAX;
}

而全局的server.unixtime是在函数serverCron中调用函数updateCachedTime更新的(redis.c):

1
2
3
4
5
6
7
8
/* We take a cached value of the unix time in the global state because with
 * virtual memory and aging there is to store the current time in objects at
 * every object access, and accuracy is not needed. To access a global var is
 * a lot faster than calling time(NULL) */
void updateCachedTime(void) {
    server.unixtime = time(NULL);
    server.mstime = mstime();
}

Redis系统中全局变量server.hz设置为10，则serverCron的调度周期为100毫秒。也就是说，全局变量server.lruclock会每隔100毫秒得到更新，该字段也和对象结构的lru字段一样，也是使用了unsigned的低24位。
所以函数lookupKey中更新缓存数据的lru热度值时，不是调用的系统函数获得的当前时间戳，而是该值的一个近似值server.lruclock， 这样不用每次调用系统函数，可以提高执行效率。

函数estimateObjectIdleTime评估指定对象的lru热度,其实现为(object.c):

1
2
3
4
5
6
7
8
9
10
/* 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;
    }
}

其思想就是对象的lru热度值和全局的server.lruclock的差值越大， 该对象热度越低。但是，因为全局时钟只有24位，按秒为单位来表示才能存储194天，server.lruclock数值有可能发生溢出(超过REDIS_LRU_CLOCK_MAX则溢出)， 所以对象的lru数值可能大于server.lruclock数值，所以可能会出现key的时钟大于全局时钟的情况，如果这种情况出现，那么就两个相加而不是相减来求最久的key。

Redis3.0新特性-淘汰池

在Redis 3.0以后增加了LRU淘汰池evictionPool，进一步提高了与LRU算法的近似效果。关于淘汰池：它是一个数组，数组大小等于MAXMEMORY_EVICTION_POOL_SIZE=16，在每一次淘汰循环中，新随机得到的key列表会和淘汰池中的key进行合并，淘汰掉最旧的key后保留剩余较旧的key列表放入淘汰池中待下一次循环使用。

淘汰池下LRU执行过程

  • 在每一次处理客户端命令（如set、add）时，当 maxmemory 的值非 0，则检测是否有需要回收的内存。如果有则执行下面步骤；
  • 随机从大字典中取出 maxmemory_samples 个键（实际取到的数量取决于大字典原本的大小），然后用一个长度为 16 （由宏 MAXMEMORY_EVICTION_POOL_SIZE 指定） 的 evictionPool （回收池）对这几个键进行筛选，筛选出 idletime （空闲时间）最长的键，并且按照 idletime 从小到大的顺序排列在 evictionPool中；
  • 从 evictionPool 池中取出 idletime 最大且在字典中存在的键作为 bestkey 执行删除，并且从 evictionPool 池中移除；

以上 evictionPool 扮演的是大顶堆的角色，并且在 Redis 服务器启动后一直存在。

freeMemoryIfNeeded函数优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define MAXMEMORY_EVICTION_POOL_SIZE 16
struct evictionPoolEntry {                                                /* a */
    unsigned long long idle;
    sds key;
};
int processCommand(client *c) {
    ...
    if (server.maxmemory) freeMemoryIfNeeded();                           /* b */
    ...
}
//用于收集 evictionPool 元素并且找出空闲时间最大的键并进行释放
int freeMemoryIfNeeded(void) {
    ...
    if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == MAXMEMORY_VOLATILE_LRU) {
        struct evictionPoolEntry *pool = db->eviction_pool;              /* c */
        while(bestkey == NULL) {
        	//用于随机采样数据库中的键，并且逐一和回收池中的键的空闲时间进行比较，筛选出空闲时间最大的键留在回收池中
            evictionPoolPopulate(dict, db->dict, db->eviction_pool);     /* d */
            for (k = MAXMEMORY_EVICTION_POOL_SIZE-1; k >= 0; k--) {
                if (pool[k].key == NULL) continue;
                de = dictFind(dict,pool[k].key);
                sdsfree(pool[k].key);
                memmove(pool+k,pool+k+1,
                  sizeof(pool[0])*(MAXMEMORY_EVICTION_POOL_SIZE-k-1));
                pool[MAXMEMORY_EVICTION_POOL_SIZE-1].key = NULL;
                pool[MAXMEMORY_EVICTION_POOL_SIZE-1].idle = 0;
                if (de) {
                	//找出空闲时间最大且存在的键，等待执行删除操作
                    bestkey = dictGetKey(de);                            /* e */
                    break;
                } else {
                    continue;
                }
            }
        }
    }
    ...
}
  • evictionPoolEntry 是回收池中的元素结构体，由一个空闲时间 idle 和 键名key 组成
  • eviction_pool 是数据库对象 db 的成员，代表回收池，为evictionPoolEntry 类型的数组，数组长度由宏 MAXMEMORY_EVICTION_POOL_SIZE 指定，默认值为 16

回收池eviction_pool更新

这是LRU 算法的核心，首先从目标字典中随机采样出server.maxmemory_samples个键，缓存在samples数组中，然后一个一个取出来，并且和回收池中的已有的键对比空闲时间，从而更新回收池。更新的过程首先，利用遍历找到每个键的实际插入位置 k ，然后，总共涉及四种情况如下：

  • 回收池已满，且当前插入的元素的空闲时间最小，则不作任何操作；
  • 回收池未满，且将要插入的位置 k 原本没有键，则可直接执行插入操作；
  • 回收池未满，且将要插入的位置 k 原本已经有键，则将当前第 k 个以后的元素往后挪一个位置，然后执行插入操作；
  • 回收池已满，则将当前第 k 个以前的元素往前挪一个位置，然后执行插入操作

big key删除

当你删除一个超级大的key时，那么这个删除命令是很具有杀伤性的，会导致Redis暂时卡顿。在4.0以后引入了unlink指令，它是一个后台异步线程，不会阻塞当前线程。当然在此大家不要担心多线程竞争写的问题，当unlink指令接收到后，其他线程将无法看到这部分key的。
当有大量缓存集中失效的话就会导致缓存服务持续卡顿，因为这时候Redis定时任务在删除一些过期的key，不能正常的对外提供服务，可能会造成缓存雪崩。

参考资料