1 配置文件中的最大內存刪除策略
在redis的配置文件中，可以設置redis內存使用的最大值，當redis使用內存達到最大值時(如何知道已達到最大值？)，redis會根據配置文件中的策略選取要刪除的key，并刪除這些key-value的值。若根據配置的策略，沒有符合策略的key，也就是說內存已經容不下新的key-value了，但此時有不能刪除key，那么這時候寫的話，將會出現寫錯誤。
1.1 最大內存參數設置
若maxmemory參數設置為0，則分兩種情況：
*在64位系統上，表示沒有限制。
*在32為系統上，是3G，redis官方文檔的說法是，32位系統最大內存是4G，預留1G給系統。而且策略會自動設置為noeviction。
也就是說在32位系統上，若maxmemory設置為0，則默認是3G，當到達3G，再往reidis中寫入時，則會報錯。
1.2 到達最大內存時的幾種刪除key的策略
* volatile-lru -> remove the key with an expire set using an LRU algorithm
按照LRU算法（最少最近沒使用）來選取，并刪除已經設置了expire時間的key。
* allkeys-lru -> remove any key accordingly to the LRU algorithm
根據LRU算法，刪除任意的key。不論這個key是否設置了expire時間。
* volatile-random -> remove a random key with an expire set
隨機刪除一個設置了expire時間的key。
* allkeys-random -> remove a random key, any key
隨機刪除任意一個key，不論這個key是否設置了expire時間。
* volatile-ttl -> remove the key with the nearest expire time (minor TTL)
刪除具有最近終止時間值(TTL)的key。
* noeviction -> don't expire at all, just return an error on write operations
若沒有設置終止時間，返回一個錯誤。
1.3 配置內存最大值策略
以下這些命令的默認策略是：volatile-lru
# At the date of writing this commands are: set setnx setex append
# incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
# sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
# zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
# getset mset msetnx exec sort
#
# The default is:
# maxmemory-policy volatile-lru
1.4 配置要刪除key的檢測樣本個數
maxmemory-samples
由于LRU和最小TTL算法都是不是精確的算法。因此你可以選擇要檢測樣本的個數。例如，默認情況下redis將會檢查3個key，并從這3個key中選取一個最近沒有使用的key。當然你可以修改檢查樣本的個數的值。
要修改這個值，可以通過在配置文件中設置參數：
maxmemory-samples 3
2 實現
這幾種刪除策略的實現都是在函數 freeMemoryIfNeeded(void) 中完成的。下面具體講解每種策略是如何實現的。
2.1 什么時候去刪除key-value
當設置了maxmemory-policy策略后，什么時候會去刪除key呢？
實際上，當設置了maxmemory參數后，在處理每個命令的時候都會根據maxmemory-policy去刪除對應的key值。
代碼如下：
// 處理客戶端的每個命令，都會調用這個函數
int processCommand(redisClient *c) {
... ...
/* Handle the maxmemory directive.
*
* First we try to free some memory if possible (if there are volatile
* keys in the dataset). If there are not the only thing we can do
* is returning an error. */
// 以上意思是：若存在可以刪除的key，就釋放一些內存，若不存在，給客戶端返回一個錯誤。
if (server.maxmemory) { // 若maxmemory不為0，則調用以下函數，釋放其中一些key
int retval = freeMemoryIfNeeded(); // 根據配置策略刪除key
if ((c->cmd->flags REDIS_CMD_DENYOOM) retval == REDIS_ERR) { // 若出錯，就終止處理命令，把錯誤返回給客戶端
flagTransaction(c);
addReply(c, shared.oomerr);
return REDIS_OK;
}
}
... ...
}
實戰1：若沒有設置maxmemory變量，即使設置了maxmemory-policy，也不會起作用。
實戰2：若沒有設置maxmemory變量，在處理命令時將不會調用釋放策略，會加速命令的處理過程。
2.2 刪除key的總體流程
當內存達到最大值時需要按策略刪除老的key，所有的刪除操作和刪除策略的實現都是在函數freeMemoryIfNeeded()中實現的。
在執行刪除策略之前，先要選取db和查找key。
總體步驟如下：
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
mstime_t latency;
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = zmalloc_used_memory();
if (slaves) {
listIter li;
listNode *ln;
listRewind(server.slaves,li);
while((ln = listNext(li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.aof_state != REDIS_AOF_OFF) {
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
/* Check if we are over the memory limit. */
// 檢查目前系統是否超過內存的限制
if (mem_used = server.maxmemory) return REDIS_OK;
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;
// 遍歷16個數據庫
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_xx策略，則直接在對應庫結構的dict中查找key。
// 若是非ALLKEYS_xx策略，也就是可能是 volatile-xxx等策略，操作的庫結構將設置成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;
}
// 若數據庫的大小為0，說明沒有key存在，繼續在下一個數據庫中查找
if (dictSize(dict) == 0) continue;
... ...
}
2.2 volatile-lru機制和allkeys-lru的實現
2.2.1 redis中的LRU機制
對于LRU機制，redis的官方文檔有這樣的解釋：
Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.
However since Redis 3.0 (that is currently in beta) the algorithm was improved to also take a pool of good candidates for eviction. This improved the performance of the algorithm, making it able to approximate more closely the behavior of a real LRU algorithm.
What is important about the Redis LRU algorithm is that you are able to tune the precision of the algorithm by changing the number of samples to check for every eviction. This parameter is controlled by the following configuration directive:
maxmemory-samples 5
The reason why Redis does not use a true LRU implementation is because it costs more memory. However the approximation is virtually equivalent for the application using Redis. The following is a graphical comparison of how the LRU approximation used by Redis compares with true LRU.
大意是說，redis的LRU算法不是正真意思上的LRU。而是使用另外一種方式實現的。也就意味著，redis并不能每次都選擇一個最好的key來刪除。沒有使用正真的LRU算法的原因是，它可能會消耗更多的內存。該算法和正真的LRU算法效果大概相同。
redis是在一小部分key中選擇最優的要刪除的key。這一小部分key的個數可以指定，可以在配置文件中設置參數maxmemory-samples 。
2.2.2 LRU機制的實現
freeMemoryIfNeeded()函數，首先要計算最大空余內存和目前已經使用的內存大差值，若不夠了，就要釋放老的key-value。
若使用的是LRU策略，就會走以下代碼，先進行最優刪除key的選擇，然后進行刪除操作：
int freeMemoryIfNeeded(void) {
size_t mem_used, mem_tofree, mem_freed;
int slaves = listLength(server.slaves);
mstime_t latency;
/* Remove the size of slaves output buffers and AOF buffer from the
* count of used memory. */
mem_used = zmalloc_used_memory(); // 計算目前使用的內存大小，要排除slave和AOF使用的buffer大小
if (slaves) { //遍歷slaves鏈表，減去slave使用的內存數量
listIter li;
listNode *ln;
listRewind(server.slaves,li);
while((ln = listNext(li))) {
redisClient *slave = listNodeValue(ln);
unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
if (obuf_bytes > mem_used)
mem_used = 0;
else
mem_used -= obuf_bytes;
}
}
if (server.aof_state != REDIS_AOF_OFF) { //減去AOF使用的內存大小
mem_used -= sdslen(server.aof_buf);
mem_used -= aofRewriteBufferSize();
}
/* Check if we are over the memory limit. */ //檢查是否達到設置的內存上限
if (mem_used = server.maxmemory) return REDIS_OK;
// 不釋放內存
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;
// 這一步要先選擇淘汰取值的數據庫的dict
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{ //若maxmemory-policy的值是LRU或RANDOM時，直接在主數據庫中進行淘汰
dict = server.db[j].dict;
} else { // 其他策略，在已經設置了終止時間的key中間進行淘汰。
dict = server.db[j].expires;
}
if (dictSize(dict) == 0) continue; //當前數據庫沒有數據跳過
/* volatile-random and allkeys-random policy */ //若是RANDOM策略中的一個
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 */// 若刪除策略是LRU策略中的一個
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
// 根據配置文件中maxmemory_samples的值，決定做幾次選擇，刪除的key要從這些key中選出來。
for (k = 0; k server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
// 從庫中隨機選取一個key-value結構(dictEntry類型)的節點
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de); // // 從該節點中獲取key的字符串地址
/* When policy is volatile-lru we need an additional lookup
* to locate the real key, as dict is set to db->expires. */
// 若最大內存刪除策略是volatile-lru，則需要從db中查找thiskey。
// 若是VOLATILE-xx策略，則目前操作的庫的存儲結構是expires，此時需要從dict中找到該key
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey);
// 獲取key de的value值
o = dictGetVal(de);
// 查看該key的剩下的生存時間
thisval = estimateObjectIdleTime(o);
/* Higher idle time is better candidate for deletion */
// 每次都從遍歷的幾個Key中選出lru最長的key。
// 那么如何更新key的lru值呢？每次查找該key的時候就會更新該key的lru值，該值是系統的時間戳。
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;
}
}
}
... ...
// 到這里，要刪除的最優key已經選出來了。現在進入刪除階段。
// 不論哪種策略，只要選出了最優key，就會執行以下刪除流程。
/* 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. */
// 刪除該bestkey對應的key-value值。注意這里既要從dict中刪除，還要從expires中刪除。
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;
}
以上這篇關于redis Key淘汰策略的實現方法就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持腳本之家。
您可能感興趣的文章:- Redis中LRU淘汰策略的深入分析
- 淺談redis的maxmemory設置以及淘汰策略
- 淺談Redis緩存有哪些淘汰策略
