趁着年轻

之前的文章说了 memcached源码学习-线程框架 和 get操作处理代码， 其实最重要的是他的缓存过期策略，以及内存管理机制， 篇幅过长分几篇文章写，这里写一下memcached的缓存过期策略。

说到缓存过期策略，网上有一大堆帖子会介绍说“LRU, 最近最少使用 ” 算法，而且源码中间也是大量的含lru字样的函数，变量，比如lru_crawler_crawl 等，很多人也就信了，可事实却不是这样的。

零、前言

实际上memcached的缓存策略是LU, 没有R， 也就是没有最少使用这回事，能想到，也就是说memcached没有记录一个key最近被访问过几次这回事，他只是记录了最近访问时间，以及过期时间（如果设置了的话）。来看一下一个key-value的内存表示形式：

typedef struct _stritem {
    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 */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;
        char end;
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

上面time是最近访问时间，exptime是主动设置的过期时间， refcount是内部使用的引用计数，data为一个联合体，为了节省内存。 time的更新时机为 do_item_update 函数调用的时候。一共有如下几个：

1. 存储的时候设置为current_time；
2. 每次get访问的时候，调用item_update 更新时间（process_get_command)；
3. do_store_item 去存储一个item的时候，发现已经有了，那就更新时间；
4. 执行touch命令的时候，更新time时间（process_touch_command）；

关于过期时间exptime字段，只会在主动设置的时候才会有效，否则无效，另外有个小坑是如果设置了过期时间超过30天，那么实际上的效果是：这个key是1秒后过期的，用的时候注意，否则就玩死人了。可以看下如下代码：

static rel_time_t realtime(const time_t exptime) {
    /*expiretime参数要么是个大于28天的秒数的时间戳，并且大于服务器启动的时间戳，也就是说，确保这个是个时间戳，
     * 或者为最大30天的秒数，代表从现在起，多少秒过期
        *
     * */
    /* no. of seconds in 30 days - largest possible delta exptime */

    if (exptime == 0) return 0; /* 0 means never expire */

    if (exptime > REALTIME_MAXDELTA) {
        /* if item expiration is at/before the server started, give it an
           expiration time of 1 second after the server started.
           (because 0 means don't expire).  without this, we'd
           underflow and wrap around to some large value way in the
           future, effectively making items expiring in the past
           really expiring never */
        if (exptime <= process_started)
            return (rel_time_t)1;//1秒后过期
        return (rel_time_t)(exptime - process_started);//返回的是服务器启动后多少秒过期
    } else {
        return (rel_time_t)(exptime + current_time);//在这个时间戳之后过期
    }
}

下面说下其缓存的过期机制，和redis不同，memcached不会记录一个即将过期的key列表，并且其过期机制属于“懒惰过期” ， key过期后不会立即删除，而是会在下次访问，或者下次有内存需要分配的时候，等一堆时机上会有过期回收的机会。整体可以分为如下几部分：

1. do_item_get 查询的时候，如果过期了，删除，返回空。
2. do_item_alloc 分配一个新的大小类似的数据的时候，看setting.oldest_live 和exptime 两部分来过期一部分item；
3. 执行flush_all 命令的时候，do_item_flush_expired 清空所有数据的时候；
4. lru_crawler enable 进行后台爬虫扫描过期。

下面一个个介绍其实现原理。

一、 查询时检查过期

这个最简单了，因为设置的时候记录了访问时间，所以查询的时候，只要判断一下时间就行了。如下代码：

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) {
        if (settings.oldest_live != 0 && settings.oldest_live <= current_time &&
            it->time <= settings.oldest_live) {
            //flush_all指令可以控制要不要刷掉所有时间在这之前的数据, 这算懒惰过期机制的一个
            do_item_unlink(it, hv);
            do_item_remove(it);
            it = NULL;
            if (was_found) {
                fprintf(stderr, " -nuked by flush");
            }
        } else if (it->exptime != 0 && it->exptime <= current_time) {
            do_item_unlink(it, hv);//进行懒惰过期清空
            do_item_remove(it);
            it = NULL;
            if (was_found) {
                fprintf(stderr, " -nuked by expire");
            }
        } else {
            it->it_flags |= ITEM_FETCHED;//搞定，找到了
            DEBUG_REFCNT(it, '+');
        }
    }
//----------
}

注意上面的代码中oldest_live相关的逻辑是跟flush_all指令有关系的，这个后面介绍。

二、申请新item的时候，顺便检查过期

也就是说，当memcached接到新的set类似命令的时候，需要申请一个新的item用来存储新数据，此时他会检查跟这个item大小类似的这个slabs组里面的过期数据。

我们知道memcached对于内存池的管理，是使用注明的slab内存池管理机制。所有的slab大小快都存放在static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES]; 的数组里面，具体的实现机制后面的文章再写。

当接到update命令时，process_update_command 函数被调用，进而调用item_alloc 申请一个新的item，

static void process_update_command(conn *c, token_t *tokens, const size_t ntokens, int comm, bool handle_cas) {
    //解析 "set aaa 0 0 5" 指令，申请内存用来后续存放数据部分的内容， 注意这里只是申请没存，没做其他操作
    //处理完后悔设置连接的状态为conn_nread， 因此继续读取数据到指定地方, 这样节省了内存的拷贝
//----
    it = item_alloc(key, nkey, flags, realtime(exptime), vlen);
//-----
}
item *item_alloc(char *key, size_t nkey, int flags, rel_time_t exptime, int nbytes) {
    item *it;
    /* do_item_alloc handles its own locks */
    it = do_item_alloc(key, nkey, flags, exptime, nbytes, 0);
    return it;
}

而do_item_alloc去分配新item的时候，为了效率，这里会有一些优化措施。它首先计算存进来的数据需要多大的内存空间，从而用slabs_clsid(ntotal) 函数计算应该放到哪个slab类里面；

然后顺便进行了最多5次扫描，从该类slab的尾部倒序扫描，看有没有要过期的数据，如果有，那就果断复用这个过期的item，从而既达到了懒惰清除过期key的效果，又搞笑的使用了已经申请的内存。看如下代码：

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) {
    //申请一个item，方法有：
    //1. 从当前这个slabs_clsid里面扫描最旧的item，看有没有过期的；
    //2. 用slabs_alloc 申请一个新的；
    //3. 如果slabs_alloc 申请失败，且evict_to_free开关打开了(默认打开)，就强制删掉一个最旧的
    uint8_t nsuffix;
    item *it = NULL;
    char suffix[40];
    //算一下需要多长的内存，用来决定slab的桶. 大小为： sizeof(item) + nkey+1 + " %flags %nbytes-2\r\n" + nbytes
    //其实就是把命令转为字符串
    size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
    if (settings.use_cas) {
        ntotal += sizeof(uint64_t);
    }

    unsigned int id = slabs_clsid(ntotal);//根据数据大小，找一个合适的slab槽
    int tries = 5;
    search = tails[id];
    /* We walk up *only* for locked items. Never searching for expired.
     * Waste of CPU for almost all deployments */
    for (; tries > 0 && search != NULL; tries--, search=search->prev) {//从这个slab链表的尾部扫描，看有没有要过期的，正好用它
//-----------
        /* Expired or flushed */
        if ((search->exptime != 0 && search->exptime < current_time)
            || (search->time <= oldest_live && oldest_live <= current_time)) {//找到了一个已经过期的it了，准备用它
            itemstats[id].reclaimed++;
            if ((search->it_flags & ITEM_FETCHED) == 0) {
                itemstats[id].expired_unfetched++;
            }
            it = search;
            slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);//更新统计数据
            do_item_unlink_nolock(it, hv);//从hash和slab链表里面都删除这个it
            /* Initialize the item block: */
            it->slabs_clsid = 0;//临时清空一下，下面还是会设置为id的
        } else if ((it = slabs_alloc(ntotal, id)) == NULL) {
            //这里很巧妙，如果申请成功了，自然不会进去，如果失败了，就进去用当前这个item，清空他，然后使用
            tried_alloc = 1;
            if (settings.evict_to_free == 0) {
                itemstats[id].outofmemory++;
            } else {//干掉一个本slabs_clsid里面最旧的item
                itemstats[id].evicted++;
                itemstats[id].evicted_time = current_time - search->time;//记录我回收到了几秒之前访问的数据了，用来评估回收的程度
//------------------
}

三、执行flush_all 命令的时候，do_item_flush_expired 懒惰清空所有数据

flush_all 指令专门用来清空所有的数据，最开始这个指令没有参数，由于这个操作比较重，后来就增加了一个时间戳的整数参数，用来控制清空的即时性，或者说提高flush_all的响应时间。这个时间默认是current_time-1秒， 会设置到settings.oldest_live 上面。处理函数是item_flush_expired 。

void item_flush_expired() {
    //处理flush_all指令，用懒惰机制清空所有数据
    mutex_lock(&cache_lock);
    do_item_flush_expired();
    mutex_unlock(&cache_lock);
}
/* expires items that are more recent than the oldest_live setting. */
void do_item_flush_expired(void) {
    //处理fflush_all 指令，功能是把oldest_live之后访问的数据立即删掉，
    //再老的数据不管，因为等到do_item_alloc需要分配新item时，会复用那些老于oldest_live 的数据的
    //这样就保证了速度了，所以如果想立即'清空'所有数据, 那就不要带个1或者很小的参数，这样都会调用到do_item_unlink_nolock
    //否则设置一个很大的时间戳或者不设置，这样就不会真正去do_item_unlink_nolock所有数据了，而是采用懒惰做法。
    //注意就算设置了1的参数，unlink了所有数据，实际上memcache不会真正清空内存给操作系统，知识放到自己的空闲item列表里面
    int i;
    item *iter, *next;
    if (settings.oldest_live == 0)
        return;
    for (i = 0; i < LARGEST_ID; i++) {
        /* The LRU is sorted in decreasing time order, and an item's timestamp
         * is never newer than its last access time, so we only need to walk
         * back until we hit an item older than the oldest_live time.
         * The oldest_live checking will auto-expire the remaining items.
         */
        for (iter = heads[i]; iter != NULL; iter = next) {
            /* iter->time of 0 are magic objects. */
            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 并没有真的清空所有数据，相反，他只是清空过来最近的一部分数据，然后依靠其他时机去用标记的时间oldest_live清理数据。

上的代码是什么意思呢？实际上只清空了访问时间在settings.oldest_live 以后的数据，再老的数据依靠访问时，或者申请内存时进行清理，具体看注释。由此联想到上面第一，二点中，关于 settings.oldest_live 的检查逻辑了。

四、lru_crawler enable 进行后台爬虫扫描过期

有了上面的机制，基本能保证需要申请内存的时候，只要有过期的内存，我能申请到，那么，如果非要立即能清理过期的数据怎么办呢？答案是：lru_crawler指令。

lru_crawler enable 命令或者启动时指定参数，可以让memcached 启动后台crawler线程，也就是所谓的爬虫线程，运行函数是item_crawler_thread，但不会进行爬虫清理；lru_crawler crawl 命令可以让memcached 立即进行爬虫清理，这个命令可以设置我要清理的是哪个slab class；

来看一下crawl 参数触发的lru_crawler_crawl 函数：

enum crawler_result_type lru_crawler_crawl(char *slabs) {
    //对参数指定的slabs的类进行爬虫扫描，告诉后台线程item_crawler_thread 去清理过期数据
    char *b = NULL;
    uint32_t sid = 0;
    uint8_t tocrawl[POWER_LARGEST];//需要清理扫描的大小类
    //注意上面变了数组没有初始化，下面肯定有问题的。不过1.4.24版本已经修复这问题了.  memset(tocrawl, 0, sizeof(uint8_t) * MAX_NUMBER_OF_SLAB_CLASSES);
    if (pthread_mutex_trylock(&lru_crawler_lock) != 0) {
        return CRAWLER_RUNNING;
    }
    pthread_mutex_lock(&cache_lock);

    if (strcmp(slabs, "all") == 0) {
        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)) {

            if (!safe_strtoul(p, &sid) || sid < POWER_SMALLEST
                    || sid > POWER_LARGEST) {
                pthread_mutex_unlock(&cache_lock);
                pthread_mutex_unlock(&lru_crawler_lock);
                return CRAWLER_BADCLASS;
            }
            tocrawl[sid] = 1;//为什么不初始化？如果不是0怎么办
        }
    }

    for (sid = 0; sid < LARGEST_ID; sid++) {
        if (tocrawl[sid] != 0 && tails[sid] != NULL) {
            if (settings.verbose > 2)
                fprintf(stderr, "Kicking LRU crawler off for slab %d\n", sid);
            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;
            crawler_link_q((item *)&crawlers[sid]);
            crawler_count++;
        }
    }
    pthread_mutex_unlock(&cache_lock);
    pthread_cond_signal(&lru_crawler_cond);//唤起item_crawler_thread
    STATS_LOCK();
    stats.lru_crawler_running = true;
    STATS_UNLOCK();
    pthread_mutex_unlock(&lru_crawler_lock);
    return CRAWLER_OK;
}

这里实际上使用信号量进行线程间通信的，用来告诉爬虫线程，你要爬去的数据在crawlers[sid]结构里面，因此爬虫线程便会按照参数去扫描是否有过期的item。执行函数是item_crawler_thread 。

static void *item_crawler_thread(void *arg) {
    //lru_crawler enable 命令，或者启动时指定crawler
    //start_item_crawler_thread创建线程，执行这里，进行后台定期清理过期key
    int i;

    pthread_mutex_lock(&lru_crawler_lock);
    if (settings.verbose > 2)
        fprintf(stderr, "Starting LRU crawler background thread\n");
    while (do_run_lru_crawler_thread) {
        pthread_cond_wait(&lru_crawler_cond, &lru_crawler_lock);//等待lru_crawler_crawl，stop_item_crawler_thread的指令，这里不会自动运行下去，得手动触发

        while (crawler_count) {//是tocrawl里面有效的slabs组个数，也就是crawler_link_q 的长度
            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);
                search = crawler_crawl_q((item *)&crawlers[i]);//存进去的是一个跟item类似的crawler 结构体
                if (search == NULL ||
                        (crawlers[i].remaining && --crawlers[i].remaining < 1)) {
                    if (settings.verbose > 2)
                        fprintf(stderr, "Nothing left to crawl for %d\n", i);
                    crawlers[i].it_flags = 0;
                    crawler_count--;//终于轮完一个了
                    crawler_unlink_q((item *)&crawlers[i]);
                    pthread_mutex_unlock(&cache_lock);
                    continue;
                }
                uint32_t hv = hash(ITEM_key(search), search->nkey);
//----
                item_crawler_evaluate(search, hv, i);
//----
}

item_crawler_thread 函数用类似堆排序的轮流扫描的机制来均匀的清理不同class的数据，将其返回到可用的slabs item列表中以备复用内存。

真正的清理函数是item_crawler_evaluate， 函数很简单，判断 oldest_live 和exptime 是否能匹配，如果能，那就调用do_item_unlink_nolock 解除item的关联关系，并且do_item_remove 返回内存给slab管理器。

static void item_crawler_evaluate(item *search, uint32_t hv, int i) {
    //item_crawler_thread定期清理过期的key
    rel_time_t oldest_live = settings.oldest_live;
    if ((search->exptime != 0 && search->exptime < current_time)
        || (search->time <= oldest_live && oldest_live <= current_time)) {
        itemstats[i].crawler_reclaimed++;

        if (settings.verbose > 1) {
            int ii;
            char *key = ITEM_key(search);
            fprintf(stderr, "LRU crawler found an expired item (flags: %d, slab: %d): ",
                search->it_flags, search->slabs_clsid);
            for (ii = 0; ii < search->nkey; ++ii) {
                fprintf(stderr, "%c", key[ii]);
            }
            fprintf(stderr, "\n");
        }
        if ((search->it_flags & ITEM_FETCHED) == 0) {
            itemstats[i].expired_unfetched++;
        }
        do_item_unlink_nolock(search, hv);//减除关联关系
        do_item_remove(search);//返回内存给slab管理器
        assert(search->slabs_clsid == 0);
    } else {
        refcount_decr(&search->refcount);
    }
}

---

由上可知，memcached的key过期机制不是LRU，而是LU而已， 并且其懒惰过期机制性能高效，基本能做到按需过期，懒惰过期，并且提供flush_all和crawl 爬虫的指令让管理员可以手动强制的进行过期清理。

不过需要注意的是，memcached到此为止实际上清理的内存并没有返回给操作系统，而是由slabs_free 函数返回给了slab管理器的可用item列表中了，以备后续使用。后面再介绍下返回过去的内存，memcached是怎么管理的，如何回收和整理内存的。