轉(zhuǎn)載：http://blog.csdn.net/luotuo44/article/details/42963793

   溫馨提示：本文用到了一些可以在啟動(dòng)memcached設(shè)置的全局變量。關(guān)于這些全局變量的含義可以參考《memcached啟動(dòng)參數(shù)詳解》。對(duì)于這些全局變量，處理方式就像《如何閱讀memcached源代碼》所說的那樣直接取其默認(rèn)值。另外， 本文會(huì)提及LRU隊(duì)列，關(guān)于LRU隊(duì)列的介紹可以參考《LRU隊(duì)列與item結(jié)構(gòu)體》。

過期失效處理：

        一個(gè)item在兩種情況下會(huì)過期失效：1.item的exptime時(shí)間戳到了。2.用戶使用flush_all命令將全部item變成過期失效的。讀者可能會(huì)說touch命令也可以使得一個(gè)item過期失效，其實(shí)這也屬于前面說的第一種情況。

超時(shí)失效：

        對(duì)于第一種過期失效，memcached的使用懶惰處理：不主動(dòng)檢測(cè)一個(gè)item是否過期失效。當(dāng)worker線程訪問這個(gè)item時(shí)，才檢測(cè)這個(gè)item的exptime時(shí)間戳是否到了。比較簡(jiǎn)單，這里就先不貼代碼，后面會(huì)貼。

flush_all命令：

        第二種過期失效是用戶flush_all命令設(shè)置的。flush_all會(huì)將所有item都變成過期失效。所有item是指哪些item？因?yàn)槎鄠€(gè)客戶端會(huì)不斷地往memcached插入item，所以必須要明白所有item是指哪些。是以worker線程接收到這個(gè)命令那一刻為界?還是以刪除那一刻為界？

        當(dāng)worker線程接收到flush_all命令后，會(huì)用全局變量settings的oldest_live成員存儲(chǔ)接收到這個(gè)命令那一刻的時(shí)間(準(zhǔn)確地說，是worker線程解析得知這是一個(gè)flush_all命令那一刻再減一)，代碼為settings.oldest_live =current_time - 1;然后調(diào)用item_flush_expired函數(shù)鎖上cache_lock，然后調(diào)用do_item_flush_expired函數(shù)完成工作。

 %20 %20 %20  這樣看來memcached是以worker線程接收到flush_all命令那一刻為界的。等等等等，看清楚一點(diǎn)！！在do_item_flush_expired函數(shù)里面，不是當(dāng)item的time成員小于settings.oldest_live時(shí)刪除這個(gè)item，而是大于的時(shí)候才刪除。從time成員變量的意義來說，大于代表什么啊？有大于的嗎？奇怪！@#@&￥

 %20 %20 %20  實(shí)際上memcached是以刪除那一刻為界的。那settings.oldest_live為什么要存儲(chǔ)worker線程接收到flush_all命令的時(shí)間戳？為什么又要判斷iter->time是否大于settings.oldest_live呢？

 %20 %20 %20  按照一般的做法，在do_item_flush_expired函數(shù)中直接把哈希表和LRU上的所有item統(tǒng)統(tǒng)刪除即可。這樣確實(shí)是可以達(dá)到目標(biāo)。但在本worker線程處理期間，其他worker線程完全不能工作(因?yàn)閐o_item_flush_expired的調(diào)用者已經(jīng)鎖上了cache_lock)。而LRU隊(duì)列里面可能有大量的數(shù)據(jù)，這個(gè)過期處理過程可能會(huì)很長(zhǎng)。其他worker線程完全不能工作是難于接受的。

 %20 %20 %20  memcached的作者肯定也意識(shí)到這個(gè)問題，所以他就寫了一個(gè)奇怪的do_item_flush_expired函數(shù)，用來加速。do_item_flush_expired只會(huì)刪除少量特殊的item。如何特殊法，在后面代碼注釋中會(huì)解釋。對(duì)于其他大量的item，memcached采用懶惰方式處理。只有當(dāng)worker線程試圖訪問該item，才檢測(cè)item是否已經(jīng)被設(shè)置為過期的了。事實(shí)上，無需對(duì)item進(jìn)行任何設(shè)置就能檢測(cè)該item是否為過期的，通過settings.oldest_live變量即可。這種懶惰和前面第一種item過期失效的處理是一樣的。

 %20 %20 %20  現(xiàn)在再看一下do_item_flush_expired函數(shù)，看一下特殊的item。

[cpp] view%20plain copy 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，直接忽略              //一般情況下iter->time是小于settings.oldest_live的。但在這種情況下              //就有可能出現(xiàn)iter->time >= settings.oldest_live :  worker1接收到              //flush_all命令，并給settings.oldest_live賦值為current_time-1。              //worker1線程還沒來得及調(diào)用item_flush_expired函數(shù)，就被worker2              //搶占了cpu，然后worker2往lru隊(duì)列插入了一個(gè)item。這個(gè)item的time              //成員就會(huì)滿足iter->time >= settings.oldest_live              if (iter->time != 0 && iter->time >= settings.oldest_live) {                  next = iter->next;                  if ((iter->it_flags & ITEM_SLABBED) == 0) {                      //雖然調(diào)用的是nolock,但本函數(shù)的調(diào)用者item_flush_expired                      //已經(jīng)鎖上了cache_lock，才調(diào)用本函數(shù)的                      do_item_unlink_nolock(iter, hash(ITEM_key(iter), iter->nkey));                  }              } else {                  //因?yàn)閘ru隊(duì)列里面的item是根據(jù)time降序排序的，所以當(dāng)存在一個(gè)item的time成員                  //小于settings.oldest_live,剩下的item都不需要再比較了                  break;              }          }      }  }  懶惰刪除： %20 %20 %20  現(xiàn)在閱讀item的懶惰刪除。注意代碼中的注釋。

[cpp] view%20plain copy 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          //檢測(cè)用戶是否使用過flush_all命令，刪除所有item。          //it->time <= settings.oldest_live就說明用戶在使用flush_all命令的時(shí)候          //就已經(jīng)存在該item了。那么該item是要?jiǎng)h除的。          //flush_all命令可以有參數(shù)，用來設(shè)定在未來的某個(gè)時(shí)刻把所有的item都設(shè)置          //為過期失效，此時(shí)settings.oldest_live是一個(gè)比worker接收到flush_all          //命令的那一刻大的時(shí)間,所以要判斷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已經(jīng)過期失效了              do_item_unlink(it, hv);//引用數(shù)會(huì)減一              do_item_remove(it);//引用數(shù)減一,如果引用數(shù)等于0，就刪除              it = NULL;            } else {              it->it_flags |= ITEM_FETCHED;          }      }          return it;  }  

 %20 %20 %20  可以看到，在查找到一個(gè)item后就要檢測(cè)它是否過期失效了。失效了就要?jiǎng)h除之。

 %20 %20 %20  除了do_item_get函數(shù)外，do_item_alloc函數(shù)也是會(huì)處理過期失效item的。do_item_alloc函數(shù)不是刪除這個(gè)過期失效item，而是占為己用。因?yàn)檫@個(gè)函數(shù)的功能是申請(qǐng)一個(gè)item，如果一個(gè)item過期了那么就直接霸占這個(gè)item的那塊內(nèi)存。下面看一下代碼。

[cpp] view%20plain copy 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];      //要存儲(chǔ)這個(gè)item需要的總空間      size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);      if (settings.use_cas) {          ntotal += sizeof(uint64_t);      }        //根據(jù)大小判斷從屬于哪個(gè)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->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函數(shù)會(huì)調(diào)用該函數(shù)      if (lru_crawler_initialized == 0) {          if (pthread_cond_init(&lru_crawler_cond, NULL) != 0) {              fprintf(stderr, "Can't initialize lru crawler condition/n");              return -1;          }          pthread_mutex_init(&lru_crawler_lock, NULL);          lru_crawler_initialized = 1;      }      return 0;  }   %20 %20 %20  代碼比較簡(jiǎn)單，這里就不說了。下面看一下lru_crawler%20enable和disable命令。enable命令會(huì)啟動(dòng)一個(gè)LRU爬蟲線程，而disable會(huì)停止這個(gè)LRU爬蟲線程，當(dāng)然不是直接調(diào)用pthread_exit停止線程。pthread_exit函數(shù)是一個(gè)危險(xiǎn)函數(shù)，不應(yīng)該在代碼出現(xiàn)。

[cpp] view%20plain copy static pthread_t item_crawler_tid;    //worker線程接收到"lru_crawler enable"命令后會(huì)調(diào)用本函數(shù)  //啟動(dòng)memcached時(shí)如果有-o lru_crawler參數(shù)也是會(huì)調(diào)用本函數(shù)  int start_item_crawler_thread(void) {      int ret;        //在stop_item_crawler_thread函數(shù)可以看到pthread_join函數(shù)      //在pthread_join返回后，才會(huì)把settings.lru_crawler設(shè)置為false。      //所以不會(huì)出現(xiàn)同時(shí)出現(xiàn)兩個(gè)crawler線程      if (settings.lru_crawler)          return -1;            pthread_mutex_lock(&lru_crawler_lock);      do_run_lru_crawler_thread = 1;      settings.lru_crawler = true;      //創(chuàng)建一個(gè)LRU爬蟲線程，線程函數(shù)為item_crawler_thread。LRU爬蟲線程在進(jìn)入      //item_crawler_thread函數(shù)后，會(huì)調(diào)用pthread_cond_wait，等待worker線程指定      //要處理的LRU隊(duì)列      if ((ret = pthread_create(&item_crawler_tid, NULL,          item_crawler_thread, NULL)) != 0) {          fprintf(stderr, "Can't create LRU crawler thread: %s/n",              strerror(ret));          pthread_mutex_unlock(&lru_crawler_lock);          return -1;      }      pthread_mutex_unlock(&lru_crawler_lock);        return 0;  }      //worker線程在接收到"lru_crawler disable"命令會(huì)執(zhí)行這個(gè)函數(shù)  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/n", strerror(ret));          return -1;      }      settings.lru_crawler = false;      return 0;  }  

 %20 %20 %20  可以看到worker線程在接收到”%20lru_crawler%20enable”命令后會(huì)啟動(dòng)一個(gè)LRU爬蟲線程。這個(gè)LRU爬蟲線程還沒去執(zhí)行任務(wù)，因?yàn)檫€沒有指定任務(wù)。命令"lru_crawler%20tocrawl%20num"并不是啟動(dòng)一個(gè)任務(wù)。對(duì)于這個(gè)命令，worker線程只是簡(jiǎn)單地把settings.lru_crawler_tocrawl賦值為num。

清除失效item：

 %20 %20 %20  命令”lru_crawler%20crawl<classid,classid,classid|all>”才是指定任務(wù)的。該命令指明了要對(duì)哪個(gè)LRU隊(duì)列進(jìn)行清理。如果使用all那么就是對(duì)所有的LRU隊(duì)列進(jìn)行清理。

 %20 %20 %20  在看memcached的清理代碼之前，先考慮一個(gè)問題：怎么對(duì)一條LRU隊(duì)列進(jìn)行清理？

 %20 %20 %20  最直觀的做法是先加鎖(鎖上cache_lock)，然后遍歷一整條LRU隊(duì)列。直接判斷LRU隊(duì)列里面的每一個(gè)item即可。明顯這種方法有問題。如果memcached有大量的item，那么遍歷一個(gè)LRU隊(duì)列耗時(shí)將太久。這樣會(huì)妨礙worker線程的正常業(yè)務(wù)。當(dāng)然我們可以考慮使用分而治之的方法，每次只處理幾個(gè)item，多次進(jìn)行，最終達(dá)到處理整個(gè)LRU隊(duì)列的目標(biāo)。但LRU隊(duì)列是一個(gè)鏈表，不支持隨機(jī)訪問。處理隊(duì)列中間的某個(gè)item，需要從鏈表頭或者尾依次訪問，時(shí)間復(fù)雜度還是O(n)。

偽item：

 %20 %20 %20  memcached為了實(shí)現(xiàn)隨機(jī)訪問，使用了一個(gè)很巧妙的方法。它在LRU隊(duì)列尾部插入一個(gè)偽item，然后驅(qū)動(dòng)這個(gè)偽item向隊(duì)列頭部前進(jìn)，每次前進(jìn)一位。

 %20 %20 %20  這個(gè)偽item是全局變量，LRU爬蟲線程無須從LRU隊(duì)列頭部或者尾部遍歷就可以直接訪問這個(gè)偽item。通過這個(gè)偽item的next和prev指針，就可以訪問真正的item。于是，LRU爬蟲線程無需遍歷就可以直接訪問LRU隊(duì)列中間的某一個(gè)item。

 %20 %20 %20  下面看一下lru_crawler_crawl函數(shù)，memcached會(huì)在這個(gè)函數(shù)會(huì)把偽item插入到LRU隊(duì)列尾部的。當(dāng)worker線程接收到lru_crawler%20crawl<classid,classid,classid|all>命令時(shí)就會(huì)調(diào)用這個(gè)函數(shù)。因?yàn)橛脩艨赡芤驦RU爬蟲線程清理多個(gè)LRU隊(duì)列的過期失效item，所以需要一個(gè)偽item數(shù)組。偽item數(shù)組的大小等于LRU隊(duì)列的個(gè)數(shù)，它們是一一對(duì)應(yīng)的。

[cpp] view%20plain copy //這個(gè)結(jié)構(gòu)體和item結(jié)構(gòu)體長(zhǎng)得很像,是偽item結(jié)構(gòu)體，用于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;//本次任務(wù)要處理多少個(gè)LRU隊(duì)列      //當(dāng)客戶端使用命令lru_crawler crawl <classid,classid,classid|all>時(shí)，  //worker線程就會(huì)調(diào)用本函數(shù),并將命令的第二個(gè)參數(shù)作為本函數(shù)的參數(shù)  enum crawler_result_type lru_crawler_crawl(char *slabs) {      char *b = NULL;      uint32_t sid = 0;      uint8_t tocrawl[POWER_LARGEST];        //LRU爬蟲線程進(jìn)行清理的時(shí)候，會(huì)鎖上lru_crawler_lock。直到完成所有      //的清理任務(wù)才會(huì)解鎖。所以客戶端的前一個(gè)清理任務(wù)還沒結(jié)束前，不能      //再提交另外一個(gè)清理任務(wù)         if (pthread_mutex_trylock(&lru_crawler_lock) != 0) {          return CRAWLER_RUNNING;      }      pthread_mutex_lock(&cache_lock);        //解析命令，如果命令要求對(duì)某一個(gè)LRU隊(duì)列進(jìn)行清理，那么就在tocrawl數(shù)組      //對(duì)應(yīng)元素賦值1作為標(biāo)志      if (strcmp(slabs, "all") == 0) {//處理全部lru隊(duì)列          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)) {                //解析出一個(gè)個(gè)的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是一個(gè)偽item類型數(shù)組。如果用戶要清理某一個(gè)LRU隊(duì)列，那么      //就在這個(gè)LRU隊(duì)列中插入一個(gè)偽item      for (sid = 0; sid < LARGEST_ID; sid++) {          if (tocrawl[sid] != 0 && tails[sid] != NULL) {                //對(duì)于偽item和真正的item，可以用nkey、time這兩個(gè)成員的值區(qū)別              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;              //將這個(gè)偽item插入到對(duì)應(yīng)的lru隊(duì)列的尾部              crawler_link_q((item *)&crawlers[sid]);              crawler_count++;//要處理的LRU隊(duì)列數(shù)加一          }      }      pthread_mutex_unlock(&cache_lock);      //有任務(wù)了，喚醒LRU爬蟲線程，讓其執(zhí)行清理任務(wù)      pthread_cond_signal(&lru_crawler_cond);      STATS_LOCK();      stats.lru_crawler_running = true;      STATS_UNLOCK();      pthread_mutex_unlock(&lru_crawler_lock);      return CRAWLER_OK;  }  

 %20 %20 %20  現(xiàn)在再來看一下偽item是怎么在LRU隊(duì)列中前進(jìn)的。先看一個(gè)偽item前進(jìn)圖。

 %20 %20 %20  

        從上面的圖可以看到，偽item通過與前驅(qū)節(jié)點(diǎn)交換位置實(shí)現(xiàn)前進(jìn)。如果偽item是LRU隊(duì)列的頭節(jié)點(diǎn)，那么就將這個(gè)偽item移出LRU隊(duì)列。函數(shù)crawler_crawl_q完成這個(gè)交換操作，并且返回交換前偽item的前驅(qū)節(jié)點(diǎn)(當(dāng)然在交換后就變成偽item的后驅(qū)節(jié)點(diǎn)了)。如果偽item處于LRU隊(duì)列的頭部，那么就返回NULL(此時(shí)沒有前驅(qū)節(jié)點(diǎn)了)。crawler_crawl_q函數(shù)里面那些指針滿天飛，這里就不貼出代碼了。

        上面的圖，雖然偽item遍歷了LRU隊(duì)列，但并沒有刪除某個(gè)item。這樣畫，一來是為了好看，二來遍歷LRU隊(duì)列不一定會(huì)刪除item的(item不過期失效就不會(huì)刪除)。

清理item：

        前面說到，可以用命令lru_crawler tocrawl num指定每個(gè)LRU隊(duì)列最多只檢查num-1個(gè)item。看清楚點(diǎn)，是檢查數(shù)，不是刪除數(shù)，而且是num-1個(gè)。首先要調(diào)用item_crawler_evaluate函數(shù)檢查一個(gè)item是否過期，是的話就刪除。如果檢查完num-1個(gè)，偽item都還沒有到達(dá)LRU隊(duì)列的頭部，那么就直接將這個(gè)偽item從LRU隊(duì)列中刪除。下面看一下item_crawler_thread函數(shù)吧。

[cpp] view plain copy static void *item_crawler_thread(void *arg) {      int i;        pthread_mutex_lock(&lru_crawler_lock);      while (do_run_lru_crawler_thread) {      //lru_crawler_crawl函數(shù)和stop_item_crawler_thread函數(shù)會(huì)signal這個(gè)條件變量      pthread_cond_wait(&lru_crawler_cond, &lru_crawler_lock);        while (crawler_count) {//crawler_count表明要處理多少個(gè)LRU隊(duì)列          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]的前驅(qū)節(jié)點(diǎn),并交換crawlers[i]和前驅(qū)節(jié)點(diǎn)的位置              search = crawler_crawl_q((item *)&crawlers[i]);              if (search == NULL || //crawlers[i]是頭節(jié)點(diǎn)，沒有前驅(qū)節(jié)點(diǎn)                  //remaining的值為settings.lru_crawler_tocrawl。每次啟動(dòng)lru                  //爬蟲線程，檢查每一個(gè)lru隊(duì)列的多少個(gè)item。                  (crawlers[i].remaining && --crawlers[i].remaining < 1)) {                    //檢查了足夠多次，退出檢查這個(gè)lru隊(duì)列                  crawlers[i].it_flags = 0;                  crawler_count--;//清理完一個(gè)LRU隊(duì)列,任務(wù)數(shù)減一                  crawler_unlink_q((item *)&crawlers[i]);//將這個(gè)偽item從LRU隊(duì)列中刪除                  pthread_mutex_unlock(&cache_lock);                  continue;              }              uint32_t hv = hash(ITEM_key(search), search->nkey);              //嘗試鎖住控制這個(gè)item的哈希表段級(jí)別鎖              if ((hold_lock = item_trylock(hv)) == NULL) {                  pthread_mutex_unlock(&cache_lock);                  continue;              }                  //此時(shí)有其他worker線程在引用這個(gè)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;              }                //如果這個(gè)item過期失效了，那么就刪除這個(gè)item              item_crawler_evaluate(search, hv, i);                if (hold_lock)                  item_trylock_unlock(hold_lock);              pthread_mutex_unlock(&cache_lock);                //lru爬蟲不能不間斷地爬lru隊(duì)列，這樣會(huì)妨礙worker線程的正常業(yè)務(wù)              //所以需要掛起lru爬蟲線程一段時(shí)間。在默認(rèn)設(shè)置中，會(huì)休眠100微秒              if (settings.lru_crawler_sleep)                  usleep(settings.lru_crawler_sleep);//微秒級(jí)          }      }      STATS_LOCK();      stats.lru_crawler_running = false;      STATS_UNLOCK();      }      pthread_mutex_unlock(&lru_crawler_lock);        return NULL;  }       //如果這個(gè)item過期失效了，那么就刪除其  static void item_crawler_evaluate(item *search, uint32_t hv, int i) {      rel_time_t oldest_live = settings.oldest_live;        //這個(gè)item的exptime時(shí)間戳到了，已經(jīng)過期失效了      if ((search->exptime != 0 && search->exptime < current_time)          //因?yàn)榭蛻舳税l(fā)送flush_all命令，導(dǎo)致這個(gè)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隊(duì)列中刪除          do_item_unlink_nolock(search, hv);          do_item_remove(search);          assert(search->slabs_clsid == 0);      } else {          refcount_decr(&search->refcount);      }  }  真正的LRU淘汰：

 %20 %20 %20 %20雖然本文前面多次使用LRU這個(gè)詞，并且memcached代碼里面的函數(shù)命名也用了lru前綴，特別是lru_crawler命令。但實(shí)際上這和LRU淘汰沒有半毛錢關(guān)系！！

 %20 %20 %20  上當(dāng)受騙了吧，罵吧：￥&@#￥&*@%##……%#%……#￥%￥@#%……

 %20 %20 %20  讀者可以回憶一下操作系統(tǒng)里面的LRU算法。本文里面刪除的那些item都是過期失效的，刪除了活該。過期了還霸著位置，有點(diǎn)像霸著茅坑不拉屎。操作系統(tǒng)里面LRU算法是因?yàn)橘Y源不夠，迫于無奈而被踢的，被踢者也是挺無奈的。不一樣吧，所以說本文前面說的不是LRU。

 %20 %20 %20  那memcached的LRU在哪里體現(xiàn)了呢？do_item_alloc函數(shù)！！前面的博文一直都有提到這個(gè)神一般的函數(shù)，但從沒有給出完整的版本。當(dāng)然這里也不會(huì)給出完整的版本。因?yàn)檫@個(gè)函數(shù)里面還是有一些東西暫時(shí)無法解釋給讀者們聽。現(xiàn)在估計(jì)讀者都能體會(huì)到《如何閱讀memcacheditem *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];      //要存儲(chǔ)這個(gè)item需要的總空間      size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);      if (settings.use_cas) {          ntotal += sizeof(uint64_t);      }        //根據(jù)大小判斷從屬于哪個(gè)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) {//引用數(shù)>=3              refcount_decr(&search->refcount);              continue;          }            //search指向的item的refcount等于2，這說明此時(shí)這個(gè)item除了本worker          //線程外，沒有其他任何worker線程索引其。可以放心釋放并重用這個(gè)item                     //因?yàn)檫@個(gè)循環(huán)是從lru鏈表的后面開始遍歷的。所以一開始search就指向           //了最不常用的item，如果這個(gè)item都沒有過期。那么其他的比其更常用          //的item就不要?jiǎng)h除了(即使它們過期了)。此時(shí)只能向slabs申請(qǐng)內(nèi)存          if ((search->exptime != 0 && search->exptime < current_time)              || (search->time <= oldest_live && oldest_live <= current_time)) {                ..          } else if ((it = slabs_alloc(ntotal, id)) == NULL) {//申請(qǐng)內(nèi)存失敗              //此刻，過期失效的item沒有找到，申請(qǐng)內(nèi)存又失敗了。看來只能使用              //LRU淘汰一個(gè)item(即使這個(gè)item并沒有過期失效)                            if (settings.evict_to_free == 0) {//設(shè)置了不進(jìn)行LRU淘汰item                  //此時(shí)只能向客戶端回復(fù)錯(cuò)誤了                  itemstats[id].outofmemory++;              } else {                  //即使一個(gè)item的exptime成員設(shè)置為永不超時(shí)(0)，還是會(huì)被踢的                        it = search;                  //重新計(jì)算一下這個(gè)slabclass_t分配出去的內(nèi)存大小                  //直接霸占舊的item就需要重新計(jì)算                  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;                }          }            //引用計(jì)數(shù)減一。此時(shí)該item已經(jīng)沒有任何worker線程索引其，并且哈希表也          //不再索引其          refcount_decr(&search->refcount);          break;      }        ...        return it;  }