memcached源碼分析-----item過期失效處理以及LRU爬蟲
來源：程序員人生 發布時間：2015-02-27 08:11:37 閱讀次數：4588次
轉載請注明出處：http://blog.csdn.net/luotuo44/article/details/42963793
溫馨提示：本文用到了1些可以在啟動memcached設置的全局變量。關于這些全局變量的含義可以參考《memcached啟動參數詳解》。對這些全局變量，處理方式就像《如何瀏覽memcached源代碼》所說的那樣直接取其默許值。
過期失效處理：
1個item在兩種情況下會過期失效：1.item的exptime時間戳到了。2.用戶使用flush_all命令將全部item變成過期失效的。讀者可能會說touch命令也能夠使得1個item過期失效，其實這也屬于前面說的第1種情況。
超時失效：
對第1種過期失效，memcached的使用怠惰處理：不主動檢測1個item是不是過期失效。當worker線程訪問這個item時，才檢測這個item的exptime時間戳是不是到了。比較簡單，這里就先不貼代碼，后面會貼。
flush_all命令：
第2種過期失效是用戶flush_all命令設置的。flush_all會將所有item都變成過期失效。所有item是指哪些item？由于多個客戶端會不斷地往memcached插入item，所以必須要明白所有item是指哪些。是以worker線程接收到這個命令那1刻為界?還是以刪除那1刻為界？
當worker線程接收到flush_all命令后，會用全局變量settings的oldest_live成員存儲接收到這個命令那1刻的時間(準確地說，是worker線程解析得知這是1個flush_all命令那1刻再減1)，代碼為settings.oldest_live =current_time - 1;然后調用item_flush_expired函數鎖上cache_lock，然后調用do_item_flush_expired函數完成工作。
void do_item_flush_expired(void) {
int i;
item *iter, *next;
if (settings.oldest_live == 0)
return;
for (i = 0; i < LARGEST_ID; i++) {
for (iter = heads[i]; iter != NULL; iter = next) {
if (iter->time != 0 && iter->time >= settings.oldest_live) {
next = iter->next;
if ((iter->it_flags & ITEM_SLABBED) == 0) {
do_item_unlink_nolock(iter, hash(ITEM_key(iter), iter->nkey));
}
} else {
/* We've hit the first old item. Continue to the next queue. */
break;
}
}
}
}
do_item_flush_expired函數內部會變量所有LRU隊列，檢測每個item的time成員。檢測time成員是公道的。如果time成員小于settings.oldest_live就說明該item在worker線程接收到flush_all命令的時候就已存在了(time成員表示該item的最后1次訪問時間)。那末就該刪除這個item。
這樣看來memcached是以worker線程接收到flush_all命令那1刻為界的。等等等等，看清楚1點！！在do_item_flush_expired函數里面，不是當item的time成員小于settings.oldest_live時刪除這個item，而是大于的時候才刪除。從time成員變量的意義來講，大于代表甚么啊？有大于的嗎？奇怪！@#@&￥
實際上memcached是以刪除那1刻為界的。那settings.oldest_live為何要存儲worker線程接收到flush_all命令的時間戳？為何又要判斷iter->time是不是大于settings.oldest_live呢？
依照1般的做法，在do_item_flush_expired函數中直接把哈希表和LRU上的所有item統統刪除便可。這樣確切是可以到達目標。但在本worker線程處理期間，其他worker線程完全不能工作(由于do_item_flush_expired的調用者已鎖上了cache_lock)。而LRU隊列里面可能有大量的數據，這個過期處理進程可能會很長。其他worker線程完全不能工作是難于接受的。
memcached的作者肯定也意想到這個問題，所以他就寫了1個奇怪的do_item_flush_expired函數，用來加速。do_item_flush_expired只會刪除少許特殊的item。如何特殊法，在后面代碼注釋中會解釋。對其他大量的item，memcached采取怠惰方式處理。只有當worker線程試圖訪問該item，才檢測item是不是已被設置為過期的了。事實上，無需對item進行任何設置就可以檢測該item是不是為過期的，通過settings.oldest_live變量便可。這類怠惰和前面第1種item過期失效的處理是1樣的。
現在再看1下do_item_flush_expired函數，看1下特殊的item。
void do_item_flush_expired(void) {
int i;
item *iter, *next;
if (settings.oldest_live == 0)
return;
for (i = 0; i < LARGEST_ID; i++) {
for (iter = heads[i]; iter != NULL; iter = next) {
//iter->time == 0的是lru爬蟲item，直接疏忽
//1般情況下iter->time是小于settings.oldest_live的。但在這類情況下
//就有可能出現iter->time >= settings.oldest_live : worker1接收到
//flush_all命令，并給settings.oldest_live賦值為current_time⑴。
//worker1線程還沒來得及調用item_flush_expired函數，就被worker2
//搶占了cpu，然后worker2往lru隊列插入了1個item。這個item的time
//成員就會滿足iter->time >= settings.oldest_live
if (iter->time != 0 && iter->time >= settings.oldest_live) {
next = iter->next;
if ((iter->it_flags & ITEM_SLABBED) == 0) {
//雖然調用的是nolock,但本函數的調用者item_flush_expired
//已鎖上了cache_lock，才調用本函數的
do_item_unlink_nolock(iter, hash(ITEM_key(iter), iter->nkey));
}
} else {
//由于lru隊列里面的item是根據time降序排序的，所以當存在1個item的time成員
//小于settings.oldest_live,剩下的item都不需要再比較了
break;
}
}
}
}
怠惰刪除：
現在來看1下item的怠惰刪除。注意代碼中的注釋。
item *do_item_get(const char *key, const size_t nkey, const uint32_t hv) {
item *it = assoc_find(key, nkey, hv);
...
if (it != NULL) {
//settings.oldest_live初始化值為0
//檢測用戶是不是使用過flush_all命令，刪除所有item。
//it->time <= settings.oldest_live就說明用戶在使用flush_all命令的時候
//就已存在該item了。那末該item是要刪除的。
//flush_all命令可以有參數，用來設定在未來的某個時刻把所有的item都設置
//為過期失效，此時settings.oldest_live是1個比worker接收到flush_all
//命令的那1刻大的時間,所以要判斷settings.oldest_live <= current_time
if (settings.oldest_live != 0 && settings.oldest_live <= current_time &&
it->time <= settings.oldest_live) {
do_item_unlink(it, hv);
do_item_remove(it);
it = NULL;
} else if (it->exptime != 0 && it->exptime <= current_time) {//該item已過期失效了
do_item_unlink(it, hv);//援用數會減1
do_item_remove(it);//援用數減1,如果援用數等于0，就刪除
it = NULL;
} else {
it->it_flags |= ITEM_FETCHED;
}
}
return it;
}
可以看到，在查找到1個item后就要檢測它是不是過期失效了。失效了就要刪除之。
除do_item_get函數外，do_item_alloc函數也是會處理過期失效item的。do_item_alloc函數不是刪除這個過期失效item，而是占為己用。由于這個函數的功能是申請1個item，如果1個item過期了那末就直接霸占這個item的那塊內存。下面看1下代碼。
item *do_item_alloc(char *key, const size_t nkey, const int flags,
const rel_time_t exptime, const int nbytes,
const uint32_t cur_hv) {
uint8_t nsuffix;
item *it = NULL;
char suffix[40];
//要存儲這個item需要的總空間
size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
if (settings.use_cas) {
ntotal += sizeof(uint64_t);
}
//根據大小判斷從屬于哪一個slab
unsigned int id = slabs_clsid(ntotal);
/* do a quick check if we have any expired items in the tail.. */
int tries = 5;
item *search;
item *next_it;
rel_time_t oldest_live = settings.oldest_live;
search = tails[id];
for (; tries > 0 && search != NULL; tries--, search=next_it) {
next_it = search->prev;
...
if (refcount_incr(&search->refcount) != 2) {//援用數，還有其他線程在援用，不能霸占這個item
//刷新這個item的訪問時間和在LRU隊列中的位置
do_item_update_nolock(search);
tries++;
refcount_decr(&search->refcount);
//此時援用數>=2
continue;
}
//search指向的item的refcount等于2，這說明此時這個item除本worker
//線程外，沒有其他任何worker線程索引其。可以放心釋放并重用這個item
//由于這個循環是從lru鏈表的后面開始遍歷的。所以1開始search就指向
//了最不經常使用的item，如果這個item都沒有過期。那末其他的比其更經常使用
//的item就不要刪除(即便它們過期了)。此時只能向slabs申請內存
if ((search->exptime != 0 && search->exptime < current_time)
|| (search->time <= oldest_live && oldest_live <= current_time)) {
//search指向的item是1個過期失效的item，可使用之
it = search;
//重新計算1下這個slabclass_t分配出去的內存大小
//直接霸占舊的item就需要重新計算
slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);
do_item_unlink_nolock(it, hv);//從哈希表和lru鏈表中刪除
/* Initialize the item block: */
it->slabs_clsid = 0;
}
//援用計數減1。此時該item已沒有任何worker線程索引其，并且哈希表也
//不再索引其
refcount_decr(&search->refcount);
break;
}
...
return it;
}
//新的item直接霸占舊的item就會調用這個函數
void slabs_adjust_mem_requested(unsigned int id, size_t old, size_t ntotal)
{
pthread_mutex_lock(&slabs_lock);
slabclass_t *p;
if (id < POWER_SMALLEST || id > power_largest) {
fprintf(stderr, "Internal error! Invalid slab class
");
abort();
}
p = &slabclass[id];
//重新計算1下這個slabclass_t分配出去的內存大小
p->requested = p->requested - old + ntotal;
pthread_mutex_unlock(&slabs_lock);
}
flush_all命令是可以有時間參數的。這個時間和其他時間1樣取值范圍是 1到REALTIME_MAXDELTA(30天)。如果命令為flush_all 100，那末99秒后所有的item失效。此時settings.oldest_live的值為current_time+100⑴，do_item_flush_expired函數也沒有甚么用了(總不會被搶占CPU99秒吧)。也正是這個緣由，需要在do_item_get里面，加入settings.oldest_live<= current_time這個判斷，避免過早刪除item。
這里明顯有1個bug。假設客戶端A向服務器提交了flush_all10命令。過了5秒后，客戶端B向服務器提交命令flush_all100。那末客戶端A的命令將失效，沒有起到任何作用。
LRU爬蟲：
前面說到，memcached是怠惰刪除過期失效item的。所以即便用戶在客戶端使用了flush_all命令使得全部item都過期失效了，但這些item還是占據者哈希表和LRU隊列并沒有歸還給slab分配器。
LRU爬蟲線程：
有無辦法強迫清除這些過期失效的item，不再占據哈希表和LRU隊列的空間并歸還給slabs呢？固然是有的。memcached提供了LRU爬蟲可以實現這個功能。
要使用LRU爬蟲就必須在客戶端使用lru_crawler命令。memcached服務器根據具體的命令參數進行處理。
memcached是用1個專門的線程負責清除這些過期失效item的，本文將稱這個線程為LRU爬蟲線程。默許情況下memcached是不啟動這個線程的，但可以在啟動memcached的時候添加參數-o lru_crawler啟動這個線程。也能夠通過客戶端命令啟動。即便啟動了這個LRU爬蟲線程，該線程還是不會工作。需要另外發送命令，指明要對哪一個LRU隊列進行清除處理。現在看1下lru_crawler有哪些參數。
LRU爬蟲命令：
- lru_crawler <enable|disable> 啟動或停止1個LRU爬蟲線程。任什么時候刻，最多只有1個LRU爬蟲線程。該命令對settings.lru_crawler進行賦值為true或false
- lru_crawler crawl <classid,classid,classid|all> 可使用2,3,6這樣的列表指明要對哪一個LRU隊列進行清除處理。也能夠使用all對所有的LRU隊列進行處理
- lru_crawler sleep <microseconds> LRU爬蟲線程在清除item的時候會占用鎖，會妨礙worker線程的正常業務。所以LRU爬蟲在處理的時候需要時不時休眠1下。默許休眠時間為100微秒。該命令對settings.lru_crawler_sleep進行賦值
- lru_crawler tocrawl <32u> 1個LRU隊列可能會有很多過期失效的item。如果1直檢查和清除下去，必將會妨礙worker線程的正常業務。這個參數用來指明最多只檢查每條LRU隊列的多少個item。默許值為0，所以如果不指定那末就不會工作。該命令對settings.lru_crawler_tocrawl進行賦值
如果要啟動LRU爬蟲主動刪除過期的item，需要這樣做：首先使用lru_crawlerenable命令啟動1個LRU爬蟲線程。然后使用lru_crawlertocrawl num命令肯定每個LRU隊列最多檢查num⑴個item。最后使用命令lru_crawlercrawl <classid,classid,classid|all>
指定要處理的LRU隊列。lru_crawler sleep可以不設置，如果要設置那末可以在lru_crawler crawl命令之前設置便可。
啟動LRU爬蟲線程：
現在來看1下LRU爬蟲是怎樣工作的。先來看1下memcached為LRU爬蟲定義了哪些全局變量。
static volatile int do_run_lru_crawler_thread = 0;
static int lru_crawler_initialized = 0;
static pthread_mutex_t lru_crawler_lock = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t lru_crawler_cond = PTHREAD_COND_INITIALIZER;
int init_lru_crawler(void) {//main函數會調用該函數
if (lru_crawler_initialized == 0) {
if (pthread_cond_init(&lru_crawler_cond, NULL) != 0) {
fprintf(stderr, "Can't initialize lru crawler condition
");
return ⑴;
}
pthread_mutex_init(&lru_crawler_lock, NULL);
lru_crawler_initialized = 1;
}
return 0;
}
代碼比較簡單，這里就不說了。下面看1下lru_crawler enable和disable命令。enable命令會啟動1個LRU爬蟲線程，而disable會停止這個LRU爬蟲線程，固然不是直接調用pthread_exit停止線程。pthread_exit函數是1個危險函數，不應當在代碼出現。
static pthread_t item_crawler_tid;
//worker線程接收到"lru_crawler enable"命令后會調用本函數
//啟動memcached時如果有-o lru_crawler參數也是會調用本函數
int start_item_crawler_thread(void) {
int ret;
//在stop_item_crawler_thread函數可以看到pthread_join函數
//在pthread_join返回后，才會把settings.lru_crawler設置為false。
//所以不會出現同時出現兩個crawler線程
if (settings.lru_crawler)
return ⑴;
pthread_mutex_lock(&lru_crawler_lock);
do_run_lru_crawler_thread = 1;
settings.lru_crawler = true;
//創建1個LRU爬蟲線程，線程函數為item_crawler_thread。LRU爬蟲線程在進入
//item_crawler_thread函數后，會調用pthread_cond_wait，等待worker線程指定
//要處理的LRU隊列
if ((ret = pthread_create(&item_crawler_tid, NULL,
item_crawler_thread, NULL)) != 0) {
fprintf(stderr, "Can't create LRU crawler thread: %s
",
strerror(ret));
pthread_mutex_unlock(&lru_crawler_lock);
return ⑴;
}
pthread_mutex_unlock(&lru_crawler_lock);
return 0;
}
//worker線程在接收到"lru_crawler disable"命令會履行這個函數
int stop_item_crawler_thread(void) {
int ret;
pthread_mutex_lock(&lru_crawler_lock);
do_run_lru_crawler_thread = 0;//停止LRU線程
//LRU爬蟲線程可能休眠于等待條件變量，需要喚醒才能停止LRU爬蟲線程
pthread_cond_signal(&lru_crawler_cond);
pthread_mutex_unlock(&lru_crawler_lock);
if ((ret = pthread_join(item_crawler_tid, NULL)) != 0) {
fprintf(stderr, "Failed to stop LRU crawler thread: %s
", strerror(ret));
return ⑴;
}
settings.lru_crawler = false;
return 0;
}
可以看到worker線程在接收到” lru_crawler enable”命令后會啟動1個LRU爬蟲線程。這個LRU爬蟲線程還沒去履行任務，由于還沒有指定任務。命令"lru_crawlertocrawl num"其實不是啟動1個任務。對這個命令，worker線程只是簡單地把settings.lru_crawler_tocrawl賦值為num。
清除失效item：
命令”lru_crawler crawl<classid,classid,classid|all>”才是指定任務的。該命令指明了要對哪一個LRU隊列進行清算。如果使用all那末就是對所有的LRU隊列進行清算。
在看memcached的清算代碼之前，先斟酌1個問題：怎樣對1條LRU隊列進行清算？
最直觀的做法是先加鎖(鎖上cache_lock)，然后遍歷1整條LRU隊列。直接判斷LRU隊列里面的每個item便可。明顯這類方法有問題。如果memcached有大量的item，那末遍歷1個LRU隊列耗時將太久。這樣會妨礙worker線程的正常業務。固然我們可以斟酌使用分而治之的方法，每次只處理幾個item，屢次進行，終究到達處理全部LRU隊列的目標。但LRU隊列是1個鏈表，不支持隨機訪問。處理隊列中間的某個item，需要從鏈表頭或尾順次訪問，時間復雜度還是O(n)。
偽item：
memcached為了實現隨機訪問，使用了1個很奇妙的方法。它在LRU隊列尾部插入1個偽item，然后驅動這個偽item向隊列頭部前進，每次前進1位。
這個偽item是全局變量，LRU爬蟲線程不必從LRU隊列頭部或尾部遍歷就能夠直接訪問這個偽item。通過這個偽item的next和prev指針，就能夠訪問真實的item。因而，LRU爬蟲線程無需遍歷就能夠直接訪問LRU隊列中間的某1個item。
下面看1下lru_crawler_crawl函數，memcached會在這個函數會把偽item插入到LRU隊列尾部的。當worker線程接收到lru_crawler crawl<classid,classid,classid|all>命令時就會調用這個函數。由于用戶可能要求LRU爬蟲線程清算多個LRU隊列的過期失效item，所以需要1個偽item數組。偽item數組的大小等于LRU隊列的個數，它們是逐一對應的。
//這個結構體和item結構體長得很像,是偽item結構體，用于LRU爬蟲
typedef struct {
struct _stritem *next;
struct _stritem *prev;
struct _stritem *h_next; /* hash chain next */
rel_time_t time; /* least recent
access */
rel_time_t exptime; /* expire time */
int nbytes; /* size of data */
unsigned short refcount;
uint8_t nsuffix; /* length of flags-and-length string */
uint8_t it_flags; /* ITEM_* above */
uint8_t slabs_clsid;/* which slab class we're in */
uint8_t nkey; /* key length, w/terminating null and padding */
uint32_t remaining; /* Max keys to crawl per slab per invocation */
} crawler;
static crawler crawlers[LARGEST_ID];
static int crawler_count = 0;//本次任務要處理多少個LRU隊列
//當客戶端使用命令lru_crawler crawl <classid,classid,classid|all>時，
//worker線程就會調用本函數,并將命令的第2個參數作為本函數的參數
enum crawler_result_type lru_crawler_crawl(char *slabs) {
char *b = NULL;
uint32_t sid = 0;
uint8_t tocrawl[POWER_LARGEST];
//LRU爬蟲線程進行清算的時候，會鎖上lru_crawler_lock。直到完成所有
//的清算任務才會解鎖。所以客戶真個前1個清算任務還沒結束前，不能
//再提交另外1個清算任務
if (pthread_mutex_trylock(&lru_crawler_lock) != 0) {
return CRAWLER_RUNNING;
}
pthread_mutex_lock(&cache_lock);
//解析命令，如果命令要求對某1個LRU隊列進行清算，那末就在tocrawl數組
//對應元素賦值1作為標志
if (strcmp(slabs, "all") == 0) {//處理全部lru隊列
for (sid = 0; sid < LARGEST_ID; sid++) {
tocrawl[sid] = 1;
}
} else {
for (char *p = strtok_r(slabs, ",", &b);
p != NULL;
p = strtok_r(NULL, ",", &b)) {
//解析出1個個的sid
if (!safe_strtoul(p, &sid) || sid < POWER_SMALLEST
|| sid > POWER_LARGEST) {//sid越界
pthread_mutex_unlock(&cache_lock);
pthread_mutex_unlock(&lru_crawler_lock);
return CRAWLER_BADCLASS;
}
tocrawl[sid] = 1;
}
}
//crawlers是1個偽item類型數組。如果用戶要清算某1個LRU隊列，那末
//就在這個LRU隊列中插入1個偽item
for (sid = 0; sid < LARGEST_ID; sid++) {
if (tocrawl[sid] != 0 && tails[sid] != NULL) {
//對偽item和真實的item，可以用nkey、time這兩個成員的值區分
crawlers[sid].nbytes = 0;
crawlers[sid].nkey = 0;
crawlers[sid].it_flags = 1; /* For a crawler, this means enabled. */
crawlers[sid].next = 0;
crawlers[sid].prev = 0;
crawlers[sid].time = 0;
crawlers[sid].remaining = settings.lru_crawler_tocrawl;
crawlers[sid].slabs_clsid = sid;
//將這個偽item插入到對應的lru隊列的尾部
crawler_link_q((item *)&crawlers[sid]);
crawler_count++;//要處理的LRU隊列數加1
}
}
pthread_mutex_unlock(&cache_lock);
//有任務了，喚醒LRU爬蟲線程，讓其履行清算任務
pthread_cond_signal(&lru_crawler_cond);
STATS_LOCK();
stats.lru_crawler_running = true;
STATS_UNLOCK();
pthread_mutex_unlock(&lru_crawler_lock);
return CRAWLER_OK;
}
現在再來看1下偽item是怎樣在LRU隊列中前進的。先看1個偽item前進圖。
從上面的圖可以看到，偽item通過與先驅節點交換位置實現前進。如果偽item是LRU隊列的頭節點，那末就將這個偽item移出LRU隊列。函數crawler_crawl_q完成這個交換操作，并且返回交換前偽item的先驅節點(固然在交換后就變成偽item的后驅節點了)。如果偽item處于LRU隊列的頭部，那末就返回NULL(此時沒有先驅節點了)。crawler_crawl_q函數里面那些指針滿天飛，這里就不貼出代碼了。
上面的圖，雖然偽item遍歷了LRU隊列，但并沒有刪除某個item。這樣畫，1來是為了好看，2來遍歷LRU隊列不1定會刪除item的(item不過期失效就不會刪除)。
清算item：
前面說到，可以用命令lru_crawler tocrawl num指定每一個LRU隊列最多只檢查num⑴個item。看清楚點，是檢查數，不是刪除數，而且是num⑴個。首先要調用item_crawler_evaluate函數檢查1個item是不是過期，是的話就刪除。如果檢查完num⑴個，偽item都還沒有到達LRU隊列的頭部，那末就直接將這個偽item從LRU隊列中刪除。下面看1下item_crawler_thread函數吧。
static void *item_crawler_thread(void *arg) {
int i;
pthread_mutex_lock(&lru_crawler_lock);
while (do_run_lru_crawler_thread) {
//lru_crawler_crawl函數和stop_item_crawler_thread函數會signal這個條件變量
pthread_cond_wait(&lru_crawler_cond, &lru_crawler_lock);
while (crawler_count) {//crawler_count表明要處理多少個LRU隊列
item *search = NULL;
void *hold_lock = NULL;
for (i = 0; i < LARGEST_ID; i++) {
if (crawlers[i].it_flags != 1) {
continue;
}
pthread_mutex_lock(&cache_lock);
//返回crawlers[i]的先驅節點,并交換crawlers[i]和先驅節點的位置
search = crawler_crawl_q((item *)&crawlers[i]);
if (search == NULL || //crawlers[i]是頭節點，沒有先驅節點
//remaining的值為settings.lru_crawler_tocrawl。每次啟動lru
//爬蟲線程，檢查每個lru隊列的多少個item。
(crawlers[i].remaining && --crawlers[i].remaining < 1)) {
//檢查了足夠屢次，退出檢查這個lru隊列
crawlers[i].it_flags = 0;
crawler_count--;//清算完1個LRU隊列,任務數減1
crawler_unlink_q((item *)&crawlers[i]);//將這個偽item從LRU隊列中刪除
pthread_mutex_unlock(&cache_lock);
continue;
}
uint32_t hv = hash(ITEM_key(search), search->nkey);
//嘗試鎖住控制這個item的哈希表段級別鎖
if ((hold_lock = item_trylock(hv)) == NULL) {
pthread_mutex_unlock(&cache_lock);
continue;
}
//此時有其他worker線程在援用這個item
if (refcount_incr(&search->refcount) != 2) {
refcount_decr(&search->refcount);//lru爬蟲線程放棄援用該item
if (hold_lock)
item_trylock_unlock(hold_lock);
pthread_mutex_unlock(&cache_lock);
continue;
}
//如果這個item過期失效了，那末就刪除這個item
item_crawler_evaluate(search, hv, i);
if (hold_lock)
item_trylock_unlock(hold_lock);
pthread_mutex_unlock(&cache_lock);
//lru爬蟲不能不中斷地爬lru隊列，這樣會妨礙worker線程的正常業務
//所以需要掛起lru爬蟲線程1段時間。在默許設置中，會休眠100微秒
if (settings.lru_crawler_sleep)
usleep(settings.lru_crawler_sleep);//微秒級
}
}
STATS_LOCK();
stats.lru_crawler_running = false;
STATS_UNLOCK();
}
pthread_mutex_unlock(&lru_crawler_lock);
return NULL;
}
//如果這個item過期失效了，那末就刪除其
static void item_crawler_evaluate(item *search, uint32_t hv, int i) {
rel_time_t oldest_live = settings.oldest_live;
//這個item的exptime時間戳到了，已過期失效了
if ((search->exptime != 0 && search->exptime < current_time)
//由于客戶端發送flush_all命令，致使這個item失效了
|| (search->time <= oldest_live && oldest_live <= current_time)) {
itemstats[i].crawler_reclaimed++;
if ((search->it_flags & ITEM_FETCHED) == 0) {
itemstats[i].expired_unfetched++;
}
//將item從LRU隊列中刪除
do_item_unlink_nolock(search, hv);
do_item_remove(search);
assert(search->slabs_clsid == 0);
} else {
refcount_decr(&search->refcount);
}
}
真實的LRU淘汰：
雖然本文前面屢次使用LRU這個詞，并且memcached代碼里面的函數命名也用了lru前綴，特別是lru_crawler命令。但實際上這和LRU淘汰沒有半毛錢關系！！
上當受騙了吧，罵吧：￥&@#￥&*@%##……%#%……#￥%￥@#%……
讀者可以回想1下操作系統里面的LRU算法。本文里面刪除的那些item都是過期失效的，刪除活該。過期了還霸著位置，有點像霸著茅坑不拉屎。操作系統里面LRU算法是由于資源不夠，迫于無奈而被踢的，被踢者也是挺無奈的。不1樣吧，所以說本文前面說的不是LRU。
那memcached的LRU在哪里體現了呢？do_item_alloc函數！！前面的博文1直都有提到這個神1般的函數，但從沒有給出完全的版本。固然這里也不會給出完全的版本。由于這個函數里面還是有1些東西暫時沒法解釋給讀者們聽。現在估計讀者都能體會到《如何瀏覽memcached源碼》中寫到的：memcached模塊間的關聯性太多了。
item *do_item_alloc(char *key, const size_t nkey, const int flags,
const rel_time_t exptime, const int nbytes,
const uint32_t cur_hv) {
uint8_t nsuffix;
item *it = NULL;
char suffix[40];
//要存儲這個item需要的總空間
size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
if (settings.use_cas) {
ntotal += sizeof(uint64_t);
}
//根據大小判斷從屬于哪一個slab
unsigned int id = slabs_clsid(ntotal);
int tries = 5;
item *search;
item *next_it;
rel_time_t oldest_live = settings.oldest_live;
search = tails[id];
for (; tries > 0 && search != NULL; tries--, search=next_it) {
next_it = search->prev;
uint32_t hv = hash(ITEM_key(search), search->nkey);
/* Now see if the item is refcount locked */
if (refcount_incr(&search->refcount) != 2) {//援用數>=3
refcount_decr(&search->refcount);
continue;
}
//search指向的item的refcount等于2，這說明此時這個item除本worker
//線程外，沒有其他任何worker線程索引其。可以放心釋放并重用這個item
//由于這個循環是從lru鏈表的后面開始遍歷的。所以1開始search就指向
//了最不經常使用的item，如果這個item都沒有過期。那末其他的比其更經常使用
//的item就不要刪除(即便它們過期了)。此時只能向slabs申請內存
if ((search->exptime != 0 && search->exptime < current_time)
|| (search->time <= oldest_live && oldest_live <= current_time)) {
..
} else if ((it = slabs_alloc(ntotal, id)) == NULL) {//申請內存失敗
//此刻，過期失效的item沒有找到，申請內存又失敗了。看來只能使用
//LRU淘汰1個item(即便這個item并沒有過期失效)
if (settings.evict_to_free == 0) {//設置了不進行LRU淘汰item
//此時只能向客戶端回復毛病了
itemstats[id].outofmemory++;
} else {
//即便1個item的exptime成員設置為永不超時(0)，還是會被踢的
it = search;
//重新計算1下這個slabclass_t分配出去的內存大小
//直接霸占舊的item就需要重新計算
slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);
do_item_unlink_nolock(it, hv);//從哈希表和lru鏈表中刪除
/* Initialize the item block: */
it->slabs_clsid = 0;
}
}
//援用計數減1。此時該item已沒有任何worker線程索引其，并且哈希表也
//不再索引其
refcount_decr(&search->refcount);
break;
}
...
return it;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
