首页 > Memcached > Memcached 缓存过期机制源码分析

Memcached 缓存过期机制源码分析

2015年10月7日 发表评论 阅读评论 3257次阅读    

之前的文章说了 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是怎么管理的,如何回收和整理内存的。

Share
分类: Memcached 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

注意: 评论者允许使用'@user空格'的方式将自己的评论通知另外评论者。例如, ABC是本文的评论者之一,则使用'@ABC '(不包括单引号)将会自动将您的评论发送给ABC。使用'@all ',将会将评论发送给之前所有其它评论者。请务必注意user必须和评论者名相匹配(大小写一致)。