系列
redis數(shù)據(jù)淘汰原理
redis過期數(shù)據(jù)刪除策略
redis server事件模型
redis cluster mget 引發(fā)的討論
redis 3.x windows 集群搭建
redis 命令執(zhí)行過程
redis string底層數(shù)據(jù)結(jié)構(gòu)
redis list底層數(shù)據(jù)結(jié)構(gòu)
redis hash底層數(shù)據(jù)結(jié)構(gòu)
redis set底層數(shù)據(jù)結(jié)構(gòu)
redis zset底層數(shù)據(jù)結(jié)構(gòu)
redis 客戶端管理
redis 主從同步-slave端
redis 主從同步-master端
redis 主從超時(shí)檢測(cè)
redis aof持久化
redis rdb持久化
redis 數(shù)據(jù)恢復(fù)過程
redis TTL實(shí)現(xiàn)原理
redis cluster集群建立
redis cluster集群選主
redis 存儲(chǔ)結(jié)構(gòu)
- redis的存儲(chǔ)結(jié)構(gòu)從外層往內(nèi)層依次是redisDb艺演、dict伟墙、dictht、dictEntry蕴坪。
- redis的Db默認(rèn)情況下有16個(gè)，每個(gè)redisDb內(nèi)部包含一個(gè)dict的數(shù)據(jù)結(jié)構(gòu)。
- redis的dict內(nèi)部包含dictht的數(shù)組敲霍，數(shù)組個(gè)數(shù)為2，主要用于hash擴(kuò)容使用丁存。
- dictht內(nèi)部包含dictEntry的數(shù)組肩杈，可以理解就是hash的桶，然后如果沖突通過掛鏈法解決解寝。
redis存儲(chǔ)結(jié)構(gòu)
?redisServer內(nèi)部包含著 redisDb *db的數(shù)組元素扩然，只是用指針體現(xiàn)而已。
struct redisServer {
/* General */
// 配置文件的絕對(duì)路徑
char *configfile; /* Absolute config file path, or NULL */
// serverCron() 每秒調(diào)用的次數(shù)
int hz; /* serverCron() calls frequency in hertz */
// 數(shù)據(jù)庫
redisDb *db;
// 省略很多其他屬性
}
?redisDb內(nèi)部包含著dict *dict和dict *expires聋伦，用于存儲(chǔ)數(shù)據(jù)和過期事件
typedef struct redisDb {
// 數(shù)據(jù)庫鍵空間夫偶，保存著數(shù)據(jù)庫中的所有鍵值對(duì)
dict *dict; /* The keyspace for this DB */
// 鍵的過期時(shí)間界睁，字典的鍵為鍵，字典的值為過期事件 UNIX 時(shí)間戳
dict *expires; /* Timeout of keys with a timeout set */
// 正處于阻塞狀態(tài)的鍵
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */
// 可以解除阻塞的鍵
dict *ready_keys; /* Blocked keys that received a PUSH */
// 正在被 WATCH 命令監(jiān)視的鍵
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */
// 數(shù)據(jù)庫號(hào)碼
int id; /* Database ID */
// 數(shù)據(jù)庫的鍵的平均 TTL 兵拢，統(tǒng)計(jì)信息
long long avg_ttl; /* Average TTL, just for stats */
} redisDb;
?dict內(nèi)部包含 dictht ht[2]翻斟，是存儲(chǔ)數(shù)據(jù)的對(duì)象，之所以有兩個(gè)元素是為了擴(kuò)容方便说铃。
/*
* 字典
*/
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 當(dāng) rehash 不在進(jìn)行時(shí)访惜，值為 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在運(yùn)行的安全迭代器的數(shù)量
int iterators; /* number of iterators currently running */
} dict;
?真正保存數(shù)據(jù)的核心數(shù)據(jù)結(jié)構(gòu)， dictEntry **table可以理解為hash的桶腻扇，通過掛鏈法解決沖突债热。
/*
* 哈希表
*
* 每個(gè)字典都使用兩個(gè)哈希表，從而實(shí)現(xiàn)漸進(jìn)式 rehash 幼苛。
*/
typedef struct dictht {
// 哈希表數(shù)組
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩碼窒篱，用于計(jì)算索引值
// 總是等于 size - 1
unsigned long sizemask;
// 該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
} dictht;
?存儲(chǔ)數(shù)據(jù)的單個(gè)節(jié)點(diǎn)，包含key和value蚓峦。保存我們存儲(chǔ)在redis的數(shù)據(jù)舌剂。
/*
* 哈希表節(jié)點(diǎn)
*/
typedef struct set {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
} dictEntry;
redis 數(shù)據(jù)存儲(chǔ)過程
?數(shù)據(jù)存儲(chǔ)過程以set為例作為說明暑椰，過程如下：
- 從redisDb當(dāng)中找到dict霍转，每個(gè)db就一個(gè)dict而已。
- 從dict當(dāng)中選擇具體的dictht對(duì)象一汽。
- 首先根據(jù)key計(jì)算hash桶的位置避消，也就是index。
- 新建一個(gè)DictEntry對(duì)象用于保存key/value召夹，將新增的entry掛到dictht的table對(duì)應(yīng)的hash桶當(dāng)中岩喷，每次保存到掛鏈的頭部。
- dictSetKey的宏保存key
- dictSetVal的宏保存value
/* High level Set operation. This function can be used in order to set
* a key, whatever it was existing or not, to a new object.
*
* 高層次的 SET 操作函數(shù)监憎。
*
* 這個(gè)函數(shù)可以在不管鍵 key 是否存在的情況下纱意，將它和 val 關(guān)聯(lián)起來。
*
* 1) The ref count of the value object is incremented.
* 值對(duì)象的引用計(jì)數(shù)會(huì)被增加
*
* 2) clients WATCHing for the destination key notified.
* 監(jiān)視鍵 key 的客戶端會(huì)收到鍵已經(jīng)被修改的通知
*
* 3) The expire time of the key is reset (the key is made persistent).
* 鍵的過期時(shí)間會(huì)被移除（鍵變?yōu)槌志玫模? */
void setKey(redisDb *db, robj *key, robj *val) {
// 添加或覆寫數(shù)據(jù)庫中的鍵值對(duì)
if (lookupKeyWrite(db,key) == NULL) {
dbAdd(db,key,val);
} else {
dbOverwrite(db,key,val);
}
incrRefCount(val);
// 移除鍵的過期時(shí)間
removeExpire(db,key);
// 發(fā)送鍵修改通知
signalModifiedKey(db,key);
}
/* Add the key to the DB. It's up to the caller to increment the reference
* counter of the value if needed.
*
* 嘗試將鍵值對(duì) key 和 val 添加到數(shù)據(jù)庫中鲸阔。
*
* 調(diào)用者負(fù)責(zé)對(duì) key 和 val 的引用計(jì)數(shù)進(jìn)行增加偷霉。
*
* The program is aborted if the key already exists.
*
* 程序在鍵已經(jīng)存在時(shí)會(huì)停止。
*/
void dbAdd(redisDb *db, robj *key, robj *val) {
// 復(fù)制鍵名
sds copy = sdsdup(key->ptr);
// 嘗試添加鍵值對(duì)
int retval = dictAdd(db->dict, copy, val);
// 如果鍵已經(jīng)存在褐筛，那么停止
redisAssertWithInfo(NULL,key,retval == REDIS_OK);
// 如果開啟了集群模式类少，那么將鍵保存到槽里面
if (server.cluster_enabled) slotToKeyAdd(key);
}
/* Add an element to the target hash table */
/*
* 嘗試將給定鍵值對(duì)添加到字典中
*
* 只有給定鍵 key 不存在于字典時(shí)，添加操作才會(huì)成功
*
* 添加成功返回 DICT_OK 渔扎，失敗返回 DICT_ERR
*
* 最壞 T = O(N) 硫狞，平灘 O(1)
*/
int dictAdd(dict *d, void *key, void *val)
{
// 嘗試添加鍵到字典，并返回包含了這個(gè)鍵的新哈希節(jié)點(diǎn)
// T = O(N)
dictEntry *entry = dictAddRaw(d,key);
// 鍵已存在，添加失敗
if (!entry) return DICT_ERR;
// 鍵不存在残吩，設(shè)置節(jié)點(diǎn)的值
// T = O(1)
dictSetVal(d, entry, val);
// 添加成功
return DICT_OK;
}
/*
* 嘗試將鍵插入到字典中
*
* 如果鍵已經(jīng)在字典存在财忽，那么返回 NULL
*
* 如果鍵不存在，那么程序創(chuàng)建新的哈希節(jié)點(diǎn)世剖，
* 將節(jié)點(diǎn)和鍵關(guān)聯(lián)定罢，并插入到字典，然后返回節(jié)點(diǎn)本身旁瘫。
*
* T = O(N)
*/
dictEntry *dictAddRaw(dict *d, void *key)
{
int index;
dictEntry *entry;
dictht *ht;
// 如果條件允許的話祖凫，進(jìn)行單步 rehash
// T = O(1)
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. */
// 計(jì)算鍵在哈希表中的索引值
// 如果值為 -1 ，那么表示鍵已經(jīng)存在
// T = O(N)
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
// T = O(1)
/* Allocate the memory and store the new entry */
// 如果字典正在 rehash 酬凳，那么將新鍵添加到 1 號(hào)哈希表
// 否則惠况，將新鍵添加到 0 號(hào)哈希表
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 為新節(jié)點(diǎn)分配空間
entry = zmalloc(sizeof(*entry));
// 將新節(jié)點(diǎn)插入到鏈表表頭
entry->next = ht->table[index];
ht->table[index] = entry;
// 更新哈希表已使用節(jié)點(diǎn)數(shù)量
ht->used++;
/* Set the hash entry fields. */
// 設(shè)置新節(jié)點(diǎn)的鍵
// T = O(1)
dictSetKey(d, entry, key);
return entry;
}
// 設(shè)置給定字典節(jié)點(diǎn)的鍵
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
entry->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
entry->key = (_key_); \
} while(0)
// 設(shè)置給定字典節(jié)點(diǎn)的值
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
entry->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
entry->v.val = (_val_); \
} while(0)
redis 過期時(shí)間存儲(chǔ)過程
?redis的過期時(shí)間存儲(chǔ)在db->expires的對(duì)象當(dāng)中，整個(gè)設(shè)置過期時(shí)間的過程如下：
- 從db-dict獲取原來存儲(chǔ)數(shù)據(jù)宁仔，之所以去取數(shù)是為了保證key的存在性
- 從db->expires獲取舊的過期事件并重新計(jì)算過期時(shí)間dictReplaceRaw
- 將過期時(shí)間重新保存到DictEntry當(dāng)中稠屠，也就是db->expires中的某個(gè)對(duì)象。
/*
* 將鍵 key 的過期時(shí)間設(shè)為 when
*/
void setExpire(redisDb *db, robj *key, long long when) {
dictEntry *kde, *de;
/* Reuse the sds from the main dict in the expire dict */
// 取出鍵
kde = dictFind(db->dict,key->ptr);
redisAssertWithInfo(NULL,key,kde != NULL);
// 根據(jù)鍵取出鍵的過期時(shí)間
de = dictReplaceRaw(db->expires,dictGetKey(kde));
// 設(shè)置鍵的過期時(shí)間
// 這里是直接使用整數(shù)值來保存過期時(shí)間翎苫，不是用 INT 編碼的 String 對(duì)象
dictSetSignedIntegerVal(de,when);
}
redis數(shù)據(jù)淘汰過程
?淘汰數(shù)據(jù)的過程是在processCommand當(dāng)中實(shí)現(xiàn)的权埠，這里我們需要關(guān)注freeMemoryIfNeeded的方法。
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. */
// 如果設(shè)置了最大內(nèi)存煎谍，那么檢查內(nèi)存是否超過限制攘蔽，并做相應(yīng)的操作
if (server.maxmemory) {
// 如果內(nèi)存已超過限制，那么嘗試通過刪除過期鍵來釋放內(nèi)存
int retval = freeMemoryIfNeeded();
// 如果即將要執(zhí)行的命令可能占用大量內(nèi)存（REDIS_CMD_DENYOOM）
// 并且前面的內(nèi)存釋放失敗的話
// 那么向客戶端返回內(nèi)存錯(cuò)誤
if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
flagTransaction(c);
addReply(c, shared.oomerr);
return REDIS_OK;
}
}
?整個(gè)數(shù)據(jù)淘汰過程如下：
- 遍歷所有的db進(jìn)行數(shù)據(jù)的釋放
- 根據(jù)不同的策略選擇從db.dict還是從db.expires選擇待過期數(shù)據(jù)
- 區(qū)分不同的淘汰策略選擇不同的key呐粘，主要分為隨機(jī)淘汰满俗、LRU淘汰、TTL時(shí)間淘汰作岖。
int freeMemoryIfNeeded(void) {
/* Compute how much memory we need to free. */
// 計(jì)算需要釋放多少字節(jié)的內(nèi)存
mem_tofree = mem_used - server.maxmemory;
// 初始化已釋放內(nèi)存的字節(jié)數(shù)為 0
mem_freed = 0;
// 根據(jù) maxmemory 策略唆垃，
// 遍歷字典，釋放內(nèi)存并記錄被釋放內(nèi)存的字節(jié)數(shù)
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;
dictEntry *de;
redisDb *db = server.db+j;
dict *dict;
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
// 如果策略是 allkeys-lru 或者 allkeys-random
// 那么淘汰的目標(biāo)為所有數(shù)據(jù)庫鍵
dict = server.db[j].dict;
} else {
// 如果策略是 volatile-lru 痘儡、 volatile-random 或者 volatile-ttl
// 那么淘汰的目標(biāo)為帶過期時(shí)間的數(shù)據(jù)庫鍵
dict = server.db[j].expires;
}
// 跳過空字典
if (dictSize(dict) == 0) continue;
/* volatile-random and allkeys-random policy */
// 如果使用的是隨機(jī)策略辕万，那么從目標(biāo)字典中隨機(jī)選出鍵
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 策略，
// 那么從一集 sample 鍵中選出 IDLE 時(shí)間最長的那個(gè)鍵
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
struct evictionPoolEntry *pool = db->eviction_pool;
while(bestkey == NULL) {
evictionPoolPopulate(dict, db->dict, db->eviction_pool);
/* Go backward from best to worst element to evict. */
for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
if (pool[k].key == NULL) continue;
de = dictFind(dict,pool[k].key);
/* Remove the entry from the pool. */
sdsfree(pool[k].key);
/* Shift all elements on its right to left. */
memmove(pool+k,pool+k+1,
sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
/* Clear the element on the right which is empty
* since we shifted one position to the left. */
pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;
/* If the key exists, is our pick. Otherwise it is
* a ghost and we need to try the next element. */
if (de) {
bestkey = dictGetKey(de);
break;
} else {
/* Ghost... */
continue;
}
}
}
}
/* volatile-ttl */
// 策略為 volatile-ttl 沉删，從一集 sample 鍵中選出過期時(shí)間距離當(dāng)前時(shí)間最接近的鍵
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. */
// 計(jì)算刪除鍵所釋放的內(nèi)存數(shù)量
delta = (long long) zmalloc_used_memory();
dbDelete(db,keyobj);
delta -= (long long) zmalloc_used_memory();
mem_freed += delta;
// 對(duì)淘汰鍵的計(jì)數(shù)器增一
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) return REDIS_ERR; /* nothing to free... */
}
return REDIS_OK;
}
隨機(jī)淘汰
?隨機(jī)淘汰的場(chǎng)景下獲取待刪除key的策略蓄坏，隨機(jī)找hash桶再次hash指定位置的dictEntry即可。
就是在場(chǎng)景REDIS_MAXMEMORY_VOLATILE_RANDOM和REDIS_MAXMEMORY_ALLKEYS_LRU情況下的待淘汰的key丑念。
/*
* 隨機(jī)返回字典中任意一個(gè)節(jié)點(diǎn)。
*
* 可用于實(shí)現(xiàn)隨機(jī)化算法结蟋。
*
* 如果字典為空脯倚，返回 NULL 。
*
* T = O(N)
*/
dictEntry *dictGetRandomKey(dict *d)
{
dictEntry *he, *orighe;
unsigned int h;
int listlen, listele;
// 字典為空
if (dictSize(d) == 0) return NULL;
// 進(jìn)行單步 rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 如果正在 rehash ，那么將 1 號(hào)哈希表也作為隨機(jī)查找的目標(biāo)
if (dictIsRehashing(d)) {
// T = O(N)
do {
h = random() % (d->ht[0].size+d->ht[1].size);
he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
d->ht[0].table[h];
} while(he == NULL);
// 否則推正，只從 0 號(hào)哈希表中查找節(jié)點(diǎn)
} else {
// T = O(N)
do {
h = random() & d->ht[0].sizemask;
he = d->ht[0].table[h];
} while(he == NULL);
}
/* Now we found a non empty bucket, but it is a linked
* list and we need to get a random element from the list.
* The only sane way to do so is counting the elements and
* select a random index. */
// 目前 he 已經(jīng)指向一個(gè)非空的節(jié)點(diǎn)鏈表
// 程序?qū)倪@個(gè)鏈表隨機(jī)返回一個(gè)節(jié)點(diǎn)
listlen = 0;
orighe = he;
// 計(jì)算節(jié)點(diǎn)數(shù)量, T = O(1)
while(he) {
he = he->next;
listlen++;
}
// 取模恍涂，得出隨機(jī)節(jié)點(diǎn)的索引
listele = random() % listlen;
he = orighe;
// 按索引查找節(jié)點(diǎn)
// T = O(1)
while(listele--) he = he->next;
// 返回隨機(jī)節(jié)點(diǎn)
return he;
}
LRU 策略
?LRU 策略淘汰思路如下：
- dictGetRandomKeys隨機(jī)獲取指定數(shù)目的dictEntry。
- 將獲取的的dictEntry進(jìn)行下sort按照最近時(shí)間進(jìn)行排序植榕。
- 選擇最近使用時(shí)間最久遠(yuǎn)的數(shù)據(jù)進(jìn)行過期
- 每次過期的數(shù)據(jù)其實(shí)是采樣的結(jié)果數(shù)據(jù)中的最近未被訪問數(shù)據(jù)而非全局的再沧。
void evictionPoolPopulate(dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
int j, k, count;
dictEntry *_samples[EVICTION_SAMPLES_ARRAY_SIZE];
dictEntry **samples;
/* Try to use a static buffer: this function is a big hit...
* Note: it was actually measured that this helps. */
if (server.maxmemory_samples <= EVICTION_SAMPLES_ARRAY_SIZE) {
samples = _samples;
} else {
samples = zmalloc(sizeof(samples[0])*server.maxmemory_samples);
}
#if 1 /* Use bulk get by default. */
count = dictGetRandomKeys(sampledict,samples,server.maxmemory_samples);
#else
count = server.maxmemory_samples;
for (j = 0; j < count; j++) samples[j] = dictGetRandomKey(sampledict);
#endif
for (j = 0; j < count; j++) {
unsigned long long idle;
sds key;
robj *o;
dictEntry *de;
de = samples[j];
key = dictGetKey(de);
/* If the dictionary we are sampling from is not the main
* dictionary (but the expires one) we need to lookup the key
* again in the key dictionary to obtain the value object. */
if (sampledict != keydict) de = dictFind(keydict, key);
o = dictGetVal(de);
idle = estimateObjectIdleTime(o);
/* Insert the element inside the pool.
* First, find the first empty bucket or the first populated
* bucket that has an idle time smaller than our idle time. */
k = 0;
while (k < REDIS_EVICTION_POOL_SIZE &&
pool[k].key &&
pool[k].idle < idle) k++;
if (k == 0 && pool[REDIS_EVICTION_POOL_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 < REDIS_EVICTION_POOL_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[REDIS_EVICTION_POOL_SIZE-1].key == NULL) {
/* Free space on the right? Insert at k shifting
* all the elements from k to end to the right. */
memmove(pool+k+1,pool+k,
sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
} 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. */
sdsfree(pool[0].key);
memmove(pool,pool+1,sizeof(pool[0])*k);
}
}
pool[k].key = sdsdup(key);
pool[k].idle = idle;
}
if (samples != _samples) zfree(samples);
}
?通過random() & d->ht[j].sizemask方法隨機(jī)獲取從某個(gè)hash桶開始隨機(jī)獲取dictEntry。獲取的待淘汰的數(shù)據(jù)通過count進(jìn)行指定尊残。
int dictGetRandomKeys(dict *d, dictEntry **des, int count) {
int j; /* internal hash table id, 0 or 1. */
int stored = 0;
if (dictSize(d) < count) count = dictSize(d);
while(stored < count) {
for (j = 0; j < 2; j++) {
/* Pick a random point inside the hash table 0 or 1. */
unsigned int i = random() & d->ht[j].sizemask;
int size = d->ht[j].size;
/* Make sure to visit every bucket by iterating 'size' times. */
while(size--) {
dictEntry *he = d->ht[j].table[i];
while (he) {
/* Collect all the elements of the buckets found non
* empty while iterating. */
*des = he;
des++;
he = he->next;
stored++;
if (stored == count) return stored;
}
i = (i+1) & d->ht[j].sizemask;
}
/* If there is only one table and we iterated it all, we should
* already have 'count' elements. Assert this condition. */
assert(dictIsRehashing(d) != 0);
}
}
return stored; /* Never reached. */
}
TTL時(shí)間淘汰
?TTL時(shí)間淘汰策略跟隨機(jī)策略很像炒瘸，唯一的區(qū)別就是TTL時(shí)間淘汰基于采樣結(jié)果進(jìn)行選擇然后選擇距離過期時(shí)間最近的數(shù)據(jù)進(jìn)行過期，所以他理論上結(jié)合了采樣+TTL時(shí)間計(jì)算進(jìn)行數(shù)據(jù)淘汰的寝衫。
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;
}
}
