Redis使用场景
Redis内存淘汰指的是用户存储的一些键被可以被Redis主动地从实例中删除，从而产生读miss的情况，那么Redis为什么要有这种功能？这就是我们需要探究的设计初衷。Redis最常见的两种应用场景为缓存和持久存储，首先要明确的一个问题是内存淘汰策略更适合于那种场景？是持久存储还是缓存？这个问题很显然的我就不回答了。
当Redis被当做缓存来使用，当你新增数据时，让它自动地回收旧数据是件很方便的事情。这个行为在开发者社区非常有名，因为它是流行的memcached系统的默认行为。而LRU是Redis唯一支持的回收方法。本页面包括一些常规话题，Redis的maxmemory指令用于将可用内存限制成一个固定大小，还包括了Redis使用的LRU算法，这个实际上只是近似的LRU。
如何开启淘汰策略？
maxmemory配置指令用于配置Redis存储数据时指定限制的内存大小。通过redis.conf可以设置该指令，或者之后使用CONFIG SET命令来进行运行时配置。
例如为了配置内存限制为100mb，以下的指令可以放在redis.conf文件中。
|
1 |
maxmemory 100mb |
当指定的内存限制大小达到时，需要选择不同的行为，也就是策略。 Redis可以仅仅对命令返回错误，这将使得内存被使用得更多，或者回收一些旧的数据来使得添加数据时可以避免内存限制。
至于这个值到底有什么意义，我们可以通过了解内存淘汰的过程来理解它的意义：
- 客户端发起了需要申请更多内存的命令（如set）。
- Redis检查内存使用情况，如果已使用的内存大于maxmemory则开始根据用户配置的不同淘汰策略来淘汰内存（key），从而换取一定的内存。
- 如果上面都没问题，则这个命令执行成功。
maxmemory为0的时候表示我们对Redis的内存使用没有限制。对于64位的系统这是个默认值，对于32位的系统默认内存限制为3GB。
内存淘汰策略
内存淘汰只是Redis提供的一个功能，为了更好地实现这个功能，必须为不同的应用场景提供不同的策略，内存淘汰策略讲的是为实现内存淘汰我们具体怎么做，要解决的问题包括淘汰键空间如何选择？在键空间中淘汰键如何选择？
当maxmemory限制达到的时候，Redis淘汰key的策略由Redis的maxmemory-policy配置指令来进行配置。Redis提供了下面几种淘汰策略供用户选择，其中默认的策略为noeviction策略：
- noeviction：当内存不足以容纳新写入数据时，新写入操作会报错。
- allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的key。
- volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的key。
- allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个key。
- volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个key。
- volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的key优先移除。
-
volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键。
-
allkeys-lfu：从所有键中驱逐使用频率最少的键。
这里补充一下主键空间和设置了过期时间的键空间，举个例子，假设我们有一批键存储在Redis中，则有那么一个哈希表用于存储这批键及其值，如果这批键中有一部分设置了过期时间，那么这批键还会被存储到另外一个哈希表中，这个哈希表中的值对应的是键被设置的过期时间。设置了过期时间的键空间为主键空间的子集。
如何选择淘汰策略？
我们了解了Redis大概提供了这么几种淘汰策略，那么如何选择呢？
为解决这个问题，我们需要了解我们的应用请求对于Redis中存储的数据集的访问方式以及我们的诉求是什么。同时Redis也支持Runtime修改淘汰策略，这使得我们不需要重启Redis实例而实时的调整内存淘汰策略。
下面看看几种策略的适用场景：
- allkeys-lru：如果我们的应用对缓存的访问符合幂律分布（也就是存在相对热点数据），或者我们不太清楚我们应用的缓存访问分布状况，我们可以选择allkeys-lru策略。
- allkeys-random：如果我们的应用对于缓存key的访问概率相等，则可以使用这个策略。
- volatile-ttl：这种策略使得我们可以向Redis提示哪些key更适合被eviction。
另外，volatile-lru策略和volatile-random策略适合我们将一个Redis实例既应用于缓存和又应用于持久化存储的时候，然而我们也可以通过使用两个Redis实例来达到相同的效果，值得一提的是将key设置过期时间实际上会消耗更多的内存，因此我们建议使用allkeys-lru策略从而更有效率的使用内存。
近似LRU算法
Redis 中的LRU 与常规的 LRU 实现并不相同，一般 LRU 算法的实现基于链表结构，链表中的元素按照操作顺序从前往后排列，最新操作的键会被移动到表头，当需要内存淘汰时，只需要删除链表尾部的元素即可。但是 Redis 的 LRU 并不维护队列，只是根据配置的策略要么从所有的 key 中随机选择 N 个（可配置），要么从所有的设置了过期时间的 key 中选出 N 个键，然后再从这 N 个键中选出最久没有使用的一个 key 进行淘汰。所以 Redis LRU 只是名义上的 LRU 算法，一种近似 LRU 算法，但是实际上被淘汰的键并不一定是真正的最久没用的，这里涉及到一个权衡的问题，如果需要在全部键空间内搜索最优解，则必然会增加系统的开销，Redis 是单线程的，也就是同一个实例在每一个时刻只能服务于一个客户端，所以耗时的操作一定要谨慎。
为了在一定成本内实现相对的 LRU，早期的 Redis 版本是基于采样的 LRU，也就是放弃全部键空间内搜索解改为采样空间搜索最优解。从 Redis 3.0 版本之后，对于基于采样的 LRU 进行了一些优化，目的是在一定的成本内让结果更靠近真实的 LRU。
Redis维护了一个24位时钟，可以简单理解为当前系统的时间戳，每隔一定时间会更新这个时钟。每个key对象内部同样维护了一个24位的时钟，当新增key对象的时候会把系统的时钟赋值到这个内部对象时钟。比如我现在要进行LRU，那么首先拿到当前的全局时钟，然后再找到内部时钟与全局时钟距离时间最久的（差最大）进行淘汰，这里值得注意的是全局时钟只有24位，按秒为单位来表示才能存储194天，所以可能会出现key的时钟大于全局时钟的情况，如果这种情况出现那么就两个相加而不是相减来求最久的key。
Redis 在源码中对于每个键值对中的值，会使用一个 redisObject 结构体来保存指向值的指针，这里先来看下 redisObject 的结构。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
struct redisServer { pid_t pid; char *configfile; /* 全局时钟 */ unsigned lruclock:LRU_BITS; ... }; typedef struct redisObject { unsigned type:4; unsigned encoding:4; // 这里保存 // LRU时间(相对于全局LRU时钟) // LFU数据 (低 8 bits 作为计数器,用 24 bits 中的高 16 bits，记录访问的时间戳) unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */ int refcount; void *ptr; } robj; |
当一个键值对被创建的时候，就会记录下更新的时间。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
robj *createObject(int type, void *ptr) { robj *o = zmalloc(sizeof(*o)); o->type = type; o->encoding = OBJ_ENCODING_RAW; o->ptr = ptr; o->refcount = 1; // 如果缓存替换策略是LFU，那么将lru变量设置为LFU的计数值 // 如果是LRU，调用LRU_CLOCK函数获取LRU时钟值 if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL; } else { o->lru = LRU_CLOCK(); } return o; } |
同时一个键值对被访问的时候记录的时间也会被更新，当一个键值对被访问时，访问操作最终都会调用 lookupKey 函数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
robj *lookupKey(redisDb *db, robj *key, int flags) { dictEntry *de = dictFind(db->dict,key->ptr); if (de) { robj *val = dictGetVal(de); // 使用LRU则更新lru的时间 // 如果当前有子进程在活动则不更新，否则会触发写实复制（copy on write） if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){ if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { updateLFU(val); } else { val->lru = LRU_CLOCK(); } } return val; } else { return NULL; } } |
上面我们分别看了，创建和访问一个键值对的代码，每次操作，redisObject 中记录的 lru 时间就会被同步的更新。
Redis LRU 有个很重要的点，你通过调整每次回收时检查的采样数量，以实现调整算法的精度。这个参数可以通过以下的配置指令调整:
|
1 |
maxmemory-samples 5 |
取样数越高越精准，如果你的 CPU 和内存有足够，可以提高取样数看命中率来探测最佳的采样比例。
Redis 会判断当前内存的使用情况，如果超过了 maxmemory 配置的值，就会触发新的内存淘汰了。
如果内存超过了 maxmemory 的值，这时候还需要去计算需要释放的内存量，这个释放的内存大小等于已使用的内存量减去 maxmemory。不过，已使用的内存量并不包括用于主从复制的复制缓冲区大小。
|
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 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 |
/* This function is periodically called to see if there is memory to free * according to the current "maxmemory" settings. In case we are over the * memory limit, the function will try to free some memory to return back * under the limit. * * The function returns C_OK if we are under the memory limit or if we * were over the limit, but the attempt to free memory was successful. * Otherwise if we are over the memory limit, but not enough memory * was freed to return back under the limit, the function returns C_ERR. */ int freeMemoryIfNeeded(void) { int keys_freed = 0; /* By default replicas should ignore maxmemory * and just be masters exact copies. */ if (server.masterhost && server.repl_slave_ignore_maxmemory) return C_OK; size_t mem_reported, mem_tofree, mem_freed; mstime_t latency, eviction_latency, lazyfree_latency; long long delta; int slaves = listLength(server.slaves); int result = C_ERR; /* When clients are paused the dataset should be static not just from the * POV of clients not being able to write, but also from the POV of * expires and evictions of keys not being performed. */ if (clientsArePaused()) return C_OK; if (getMaxmemoryState(&mem_reported,NULL,&mem_tofree,NULL) == C_OK) return C_OK; mem_freed = 0; latencyStartMonitor(latency); if (server.maxmemory_policy == MAXMEMORY_NO_EVICTION) goto cant_free; /* We need to free memory, but policy forbids. */ while (mem_freed < mem_tofree) { int j, k, i; static unsigned int next_db = 0; sds bestkey = NULL; int bestdbid; redisDb *db; dict *dict; dictEntry *de; if (server.maxmemory_policy & (MAXMEMORY_FLAG_LRU|MAXMEMORY_FLAG_LFU) || server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) { struct evictionPoolEntry *pool = EvictionPoolLRU; while(bestkey == NULL) { unsigned long total_keys = 0, keys; /* We don't want to make local-db choices when expiring keys, * so to start populate the eviction pool sampling keys from * every DB. */ for (i = 0; i < server.dbnum; i++) { db = server.db+i; dict = (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) ? db->dict : db->expires; if ((keys = dictSize(dict)) != 0) { evictionPoolPopulate(i, dict, db->dict, pool); total_keys += keys; } } if (!total_keys) break; /* No keys to evict. */ /* 从数组最后一个key开始查找 */ for (k = EVPOOL_SIZE-1; k >= 0; k--) { // 当前key为空值，则查找下一个key if (pool[k].key == NULL) continue; bestdbid = pool[k].dbid; // 从全局哈希表或是expire哈希表中，获取当前key对应的键值对 if (server.maxmemory_policy & MAXMEMORY_FLAG_ALLKEYS) { de = dictFind(server.db[pool[k].dbid].dict, pool[k].key); } else { de = dictFind(server.db[pool[k].dbid].expires, pool[k].key); } /* 将当前key从EvictionPoolLRU数组删除 */ if (pool[k].key != pool[k].cached) sdsfree(pool[k].key); pool[k].key = NULL; pool[k].idle = 0; /* 如果当前key存在，选择当前key为被淘汰的key。否则它就是一个幽灵，我们需要尝试下一个元素 */ if (de) { bestkey = dictGetKey(de); break; } else { /* Ghost... Iterate again. */ } } } } /* volatile-random and allkeys-random policy */ else if (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM || server.maxmemory_policy == MAXMEMORY_VOLATILE_RANDOM) { /* When evicting a random key, we try to evict a key for * each DB, so we use the static 'next_db' variable to * incrementally visit all DBs. */ for (i = 0; i < server.dbnum; i++) { j = (++next_db) % server.dbnum; db = server.db+j; dict = (server.maxmemory_policy == MAXMEMORY_ALLKEYS_RANDOM) ? db->dict : db->expires; if (dictSize(dict) != 0) { de = dictGetRandomKey(dict); bestkey = dictGetKey(de); bestdbid = j; break; } } } /* Finally remove the selected key. */ if (bestkey) { db = server.db+bestdbid; robj *keyobj = createStringObject(bestkey,sdslen(bestkey)); propagateExpire(db,keyobj,server.lazyfree_lazy_eviction); /* We compute the amount of memory freed by db*Delete() 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. * * Same for CSC invalidation messages generated by signalModifiedKey. * * 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(); latencyStartMonitor(eviction_latency); if (server.lazyfree_lazy_eviction) dbAsyncDelete(db,keyobj); else dbSyncDelete(db,keyobj); latencyEndMonitor(eviction_latency); latencyAddSampleIfNeeded("eviction-del",eviction_latency); delta -= (long long) zmalloc_used_memory(); mem_freed += delta; server.stat_evictedkeys++; signalModifiedKey(NULL,db,keyobj); notifyKeyspaceEvent(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(); /* Normally our stop condition is the ability to release * a fixed, pre-computed amount of memory. However when we * are deleting objects in another thread, it's better to * check, from time to time, if we already reached our target * memory, since the "mem_freed" amount is computed only * across the dbAsyncDelete() call, while the thread can * release the memory all the time. */ if (server.lazyfree_lazy_eviction && !(keys_freed % 16)) { if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) { /* Let's satisfy our stop condition. */ mem_freed = mem_tofree; } } } else { goto cant_free; /* nothing to free... */ } } result = C_OK; cant_free: /* We are here if we are not able to reclaim memory. There is only one * last thing we can try: check if the lazyfree thread has jobs in queue * and wait... */ if (result != C_OK) { latencyStartMonitor(lazyfree_latency); while(bioPendingJobsOfType(BIO_LAZY_FREE)) { if (getMaxmemoryState(NULL,NULL,NULL,NULL) == C_OK) { result = C_OK; break; } usleep(1000); } latencyEndMonitor(lazyfree_latency); latencyAddSampleIfNeeded("eviction-lazyfree",lazyfree_latency); } latencyEndMonitor(latency); latencyAddSampleIfNeeded("eviction-cycle",latency); return result; } |
用来填充evictionPool
|
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 |
// 用来填充evictionPool // 按升序插入键，所以空闲时间小的键在左边，空闲时间高的键在右边。 // https://github.com/redis/redis/blob/6.2/src/evict.c#L145 void evictionPoolPopulate(int dbid, dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) { int j, k, count; dictEntry *samples[server.maxmemory_samples]; count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples); for (j = 0; j < count; j++) { ... // 将元素插入池中。 首先，找到第一个空闲时间小于我们空闲时间的空桶或第一个填充的桶。 k = 0; while (k < EVPOOL_SIZE && pool[k].key && pool[k].idle < idle) k++; if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) { /* Can't insert if the element is < the worst element we have * and there are no empty buckets. */ continue; } else if (k < EVPOOL_SIZE && pool[k].key == NULL) { /* Inserting into empty position. No setup needed before insert. */ } else { /* Inserting in the middle. Now k points to the first element * greater than the element to insert. */ if (pool[EVPOOL_SIZE-1].key == NULL) { /* Free space on the right? Insert at k shifting * all the elements from k to end to the right. */ /* Save SDS before overwriting. */ sds cached = pool[EVPOOL_SIZE-1].cached; memmove(pool+k+1,pool+k, sizeof(pool[0])*(EVPOOL_SIZE-k-1)); pool[k].cached = cached; } else { /* No free space on right? Insert at k-1 */ k--; /* Shift all elements on the left of k (included) to the * left, so we discard the element with smaller idle time. */ sds cached = pool[0].cached; /* Save SDS before overwriting. */ if (pool[0].key != pool[0].cached) sdsfree(pool[0].key); memmove(pool,pool+1,sizeof(pool[0])*k); pool[k].cached = cached; } } ... } } |
处理淘汰的数据，Redis 中提供了一个数组 EvictionPoolLRU，用来保存待淘汰的候选键值对。这个数组的元素类型是 evictionPoolEntry 结构体，该结构体保存了待淘汰键值对的空闲时间 idle、对应的 key 等信息。
可以看到上面会选取一定的过期键，然后插入到 EvictionPoolLRU 中。
dictGetSomeKeys 函数采样的 key 的数量，是由配置项 maxmemory-samples 决定的，该配置项的默认值是 5。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
struct evictionPoolEntry { // 待淘汰的键值对的空闲时间 unsigned long long idle; /* Object idle time (inverse frequency for LFU) */ // 待淘汰的键值对的key sds key; /* Key name. */ // 缓存的SDS对象 sds cached; /* Cached SDS object for key name. */ // 待淘汰键值对的key所在的数据库ID int dbid; /* Key DB number. */ }; static struct evictionPoolEntry *EvictionPoolLRU; |
然后通过 evictionPoolPopulate 函数，进行采样，然后将采样数据写入到 EvictionPoolLRU 中，插入到 EvictionPoolLRU 中的数据是按照空闲时间从小到大进行排好序的。
freeMemoryIfNeeded 函数会遍历一次 EvictionPoolLRU 数组，从数组的最后一个 key 开始选择，如果选到的 key 不是空值，那么就把它作为最终淘汰的 key。
每次选中一部分过期的键值对，每次淘汰最久没有使用的那个，如果释放的内存空间还不够，就会重复的进行采样，删除的过程。
为什么要使用近似LRU？
1、性能问题，由于近似LRU算法只是最多随机采样N个key并对其进行排序，如果精准需要对所有key进行排序，这样近似LRU性能更高
2、内存占用问题，Redis对内存要求很高，会尽量降低内存使用率，如果是抽样排序可以有效降低内存的占用
3、实际效果基本相等，如果请求符合长尾法则，那么真实LRU与Redis LRU之间表现基本无差异
LFU
LFU是在Redis4.0后出现的，LRU的最近最少使用实际上并不精确，考虑下面的情况，如果在|处删除，那么A距离的时间最久，但实际上A的使用频率要比B频繁，所以合理的淘汰策略应该是淘汰B。LFU就是为应对这种情况而生的。
A~~A~~A~~A~~A~~A~~A~~A~~A~~A~~~|
B~~~~~B~~~~~B~~~~~B~~~~~~~~~~~~B|
LFU把原来的key对象的内部时钟的24位分成两部分，前16位还代表时钟，后8位代表一个计数器。16位的情况下如果还按照秒为单位就会导致不够用，所以一般这里以时钟为单位。而后8位表示当前key对象的访问频率，8位只能代表255，但是redis并没有采用线性上升的方式，而是通过一个复杂的公式，通过配置如下两个参数来调整数据的递增速度。
lfu-log-factor 可以调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。
lfu-decay-time 是一个以分钟为单位的数值，可以调整counter的减少速度。
所以这两个因素就对应到了LFU的Counter减少策略和增长策略，它们实现逻辑分别如下。
降低LFUDecrAndReturn
1、先从高16位获取最近的降低时间ldt以及低8位的计数器counter值
2、计算当前时间now与ldt的差值（now-ldt），当ldt大于now时，那说明是过了一个周期，按照65535-ldt+now计算（16位一个周期最大65535）
3、使用第2步计算的差值除以lfu_decay_time，即LFUTimeElapsed(ldt) / server.lfu_decay_time，已过去n个lfu_decay_time，则将counter减少n。
增长LFULogIncr
1、获取0-1的随机数r
2、计算0-1之间的控制因子p，它的计算逻辑如下
|
1 2 3 4 |
// LFU_INIT_VAL默认为5 baseval = counter - LFU_INIT_VAL; // 计算控制因子 p = 1.0/(baseval*lfu_log_factor+1); |
3、如果r小于p，counter增长1
p取决于当前counter值与lfu_log_factor因子，counter值与lfu_log_factor因子越大，p越小，r小于p的概率也越小，counter增长的概率也就越小。增长情况如下图：
|
1 2 3 4 5 6 7 8 9 10 11 |
+--------+----------+-----------+------------+---------+-----------+ | factor | 100 hits | 1000 hits | 100K hists | 1M hits | 10M hists | +--------+----------+-----------+------------+---------+-----------+ | 0 | 104 | 255 | 255 | 255 | 255 | +--------+----------+-----------+------------+---------+-----------+ | 1 | 18 | 49 | 255 | 255 | 255 | +--------+----------+-----------+------------+---------+-----------+ | 10 | 10 | 18 | 142 | 255 | 255 | +--------+----------+-----------+------------+---------+-----------+ | 100 | 8 | 11 | 49 | 143 | 255 | +--------+----------+-----------+------------+---------+-----------+ |
从左到右表示key的命中次数，从上到下表示影响因子，在影响因子为100的条件下，经过10M次命中才能把后8位值加满到255.
新生KEY策略
另外一个问题是，当创建新对象的时候，对象的counter如果为0，很容易就会被淘汰掉，还需要为新生key设置一个初始counter。counter会被初始化为LFU_INIT_VAL，默认5。
<参考>
https://zhuanlan.zhihu.com/p/105587132
