Redis源码——内存淘汰机制

发表于

Redis缓存淘汰策略

noeviction：内存达到了上限，不淘汰内存数据，遇到大部分写命令返回Out Of Memory错误。

allkeys-lru：在所有的key的哈希表中随机选择多个key，在选择到的key中使用lru算法淘汰最近最少使用的缓存。

volatile-lru：在设置了过期时间的哈希表里面随机选择多个key，在选择到的key中使用lru算法淘汰最近最少使用的缓存。

allkeys-random：在所有的key的哈希表中随机选择一个key淘汰掉。

volatile-random：在设置了过期时间的哈希表里面随机选择一个key淘汰掉。

volatile-ttl：在设置了过期时间的哈希表里面随机选择多个key，在挑选到的key中选择过期时间最小的一个淘汰掉。

LRU算法

lru算法原理，根据数据的访问时间，选择淘汰最长时间未被使用的数据。可以使用链表来实现，新增数据（访问数据），把这数据插入（移动）到链表头部，淘汰数据就选择链表末尾的数据淘汰掉。

Redis采样淘汰

Redis实现的lru淘汰算法，选择被淘汰的key不一定是所有key中最近最少使用的，只是选取的样本中访问时间距离当前时间最远的。Redis有个maxmemory-samples配置项，当Redis内存使用达到上限后，从对应哈希表中挑选设置样本数量的key，插入或者替换到样本集中，最后对样本集使用lru算法，淘汰最长时间未被使用的数据。

Redis在随机采样集中应用lru淘汰数据，而不是类似memcached那样严格地挑选所有key中最近最少访问的数据。第一是考虑到Redis内部db的实现方式，Redis是使用hash表结构实现key的存储，要实现严格的lru，那么Redis就要额外的实现一个访问时间链表，增加内存开销（Redis对内存使用还是很抠门的，很多地方都牺牲时间来换取更少的空间开销），这说法是来自官网的，并且每次读写操作都需要维护更新访问时间链表；第二考虑操作的时间开销，实现严格的lru算法，那样淘汰数据的时候都需要扫描整个哈希表（前提是基于当前的数据结构来说），扫描所有key，这样付出的时间开销不言而喻。

Redis缓存淘汰源码分析

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
int freeMemoryIfNeeded(void) {
    /**
     * noeviction 不淘汰数据，什么都不做
     */
    if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION)
        return C_ERR;
    while (mem_freed < mem_tofree) {
        int j, k, keys_freed = 0;
        for (j = 0; j < server.dbnum; j++) {
            /**
             * 选择操作的哈希表，Redis另外维护着一个保存过期时间的key=>expire关联的哈希表
             */
            if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM)
            {
                dict = server.db[j].dict;
            } else {
                dict = server.db[j].expires;
            }
            /**
             * 分支一：全局哈希表随机或者过期时间哈希表中，随机淘汰一个key
             */
            if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM ||
                server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM)
            {
                de = dictGetRandomKey(dict);
                bestkey = dictGetKey(de);
            }
            /**
             * 分支二：全局哈希表随机或者过期时间哈希表中，随机采样多个数据，再运用lru算法挑选一个淘汰
             */
            else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_LRU ||
                server.maxmemory_policy == MAXMEMORY_VOLATILE_LRU)
            {
                /* 样本集 */
                struct evictionPoolEntry *pool = db->eviction_pool;
                while(bestkey == NULL) {
                    /* 
                     * 采样，更新和维护样本集；
                     * 样本集开始是空的，每次操作完并不会清空样本集；
                     * 而且每次采样，都会采集多个数据，同时和样本集中已有的数据进行比较，新增或者更新样本集；
                     */ 
                    evictionPoolPopulate(dict, db->dict, db->eviction_pool);
                    /**
                     * 开始对样本集使用lru算法，淘汰样本集中访问时间最晚的key
                     */
                    for (k = MAXMEMORY_EVICTION_POOL_SIZE-1; k >= 0; k--) {
                        if (pool[k].key == NULL) continue;
                        de = dictFind(dict,pool[k].key);
                        /* 把选取到的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;
                        /* pool样本集内的key，只是样本，不一定和db内保持一致，也不必，可能在db中已经被删除的，所以要作判断 */
                        if (de) {
                            bestkey = dictGetKey(de);
                            break;
                        } else {
                            /* Ghost... */
                            continue;
                        }
                    }
                }
            }
            /**
             * 分支三：在设置了过期时间的哈希表里面随机选择多个key，在挑选到的key中选择过期时间最小的一个淘汰掉
             */
            else if (server.maxmemory_policy == 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);
                    if (bestkey == NULL || thisval < bestval) {
                        bestkey = thiskey;
                        bestval = thisval;
                    }
                }
            }
            if (bestkey) {
                long long delta;
                robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
                // 命令扩散，把删除key的命令同步到所有从库slave
                propagateExpire(db,keyobj);
                // 删除key
                dbDelete(db,keyobj);
            }
        }
    }
    return C_OK;
}