猪小花1号

个人签名

283篇博客

Memcached LRU策略(上篇)

猪小花1号2018-09-11 09:01

作者:吕宗胜


Memcached LRU介绍

Memcached作为内存缓存,不可避免的问题之一就是内存的置换问题。我们比较常用的内存置换策略有FIFO(先进先出),LRU(最近最少使用)等。Memcached采用了LRU的策略。

LRU策略是指把当内存发生置换的时候,把最近使用次数最少的内存置换掉,虽然这种置换方式不是最优的,确是性价比很高的实现方式。这篇文章将对Memcached LRU策略进行分析,进一步总结Memcached内存的管理方式。

Memcached LRU总览

Memcached的内存管理方式如下所示:

从上图,我们可以看到两个非常重要的链表:slots空闲列表和LRU链表。而Memcached1.4.24版本中,对LRU进行了进一步的划分,存在四级LRU:HOT_LRU、WARM_LRU、COLD_LRU、NOEXP_LRU。我们可以通过配置项来控制Memcached具体的LRU策略。

1. LRU分配

通过Memcached内存管理的学习,我们知道Memcached会初始化固定数量的slabclass(64个),每一个slabclass对应有4个LRU的链表。每一个LRU链表使用head和tail来标记,在Memcached中维护了大小为256的head和tail数组,其中不同数组段的具体含义如下所示。正是由于Memcached采用了以64作为LRU的分级策略,所以它可以通过位运算快速的定位各个LRU链表。

#define HOT_LRU 0
#define WARM_LRU 64
#define COLD_LRU 128
#define NOEXP_LRU 192
static unsigned int lru_type_map[4] = {HOT_LRU, WARM_LRU, COLD_LRU, NOEXP_LRU};
#define CLEAR_LRU(id) (id & ~(3<<6)) //这个方法会把所有的LRU都定位到0~63之间

2. LRU策略

通过对配置项lru_maintainer_thread,设置为0,我们可以使用基本的LRU策略,该策略下,Memcached只使用COLD_LRU链表来记录。而通过对lru_maintainer_thread设为1,我们可以使用4个LRU链表。使用多个LRU链表的最大好处是不同的LRU链表可以使用不同的置换策略,提供Memcached的性能。这里我们将具体介绍Memcached的分级LRU。

在Memcached分级LRU策略中,严格定义了四级LRU数据的流向。HOT_LRU和WARM_LRU数据可以流向COLD_LRU中,COLD_LRU数据可以流向WARM_LRU。而NOEXP_LRU比较特殊,它只存放那些不设置超时时间且不被强制换出的数据。

在具体介绍lru检查算法之前,我们先回顾一下Memcached中Item的结构:

#define ITEM_LINKED 1 //是否在链表中
#define ITEM_CAS 2 //是否CAS

/* temp */
#define ITEM_SLABBED 4 //是否在SLAB中未分配

/* Item was fetched at least once in its lifetime */
#define ITEM_FETCHED 8 //是否被fetched
/* Appended on fetch, removed on LRU shuffling */
#define ITEM_ACTIVE 16 //是否Active,在LRU检查时被置为0,在fetch时被置为1

typedef struct _stritem {
    /* Item被LRU锁保护,而LRU锁是通过hv来实现的 */
    struct _stritem *next; //next和prev这里可以有两种含义,可以是空闲链表和LRU链表
    struct _stritem *prev;
    /* Rest are protected by an item lock */
    struct _stritem *h_next;    /* 数据的查找是通过hash算法实现的,这里值hash值相同的链表 */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;   /* 引用计数,这个非常重要,refcount为0的Item回收才会放回slots空闲链表 */
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* 标记了该ITEM的状态,非常重要 */
    uint8_t         slabs_clsid;/* slab id,是LRU的标记 */
    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;

在Item中,time,exptime,refcount和it_flags对于LRU策略来说是非常重要的,理解了这些变量的含义非常有助于我们对LRU检查算法的理解。

static int lru_pull_tail(const int orig_id, const int cur_lru,
const unsigned int total_chunks, const bool do_evict, const uint32_t cur_hv) {
item *it = NULL;
int id = orig_id;
int removed = 0;
if (id == 0)
return 0;

int tries = 5;
item *search;
item *next_it;
void *hold_lock = NULL;
unsigned int move_to_lru = 0; //表示要移动的LRU类型
uint64_t limit;

id |= cur_lru; //根据当前的LRU类型获取LRU的id
pthread_mutex_lock(&lru_locks[id]);
search = tails[id];

/* 从尾部开始搜索,尝试5次,只走查可以被locked的item,一旦尾部的Item满足条件,跳出循环 */
for (; tries > 0 && search != NULL; tries--, search=next_it) {
/* we might relink search mid-loop, so search->prev isn't reliable */
next_it = search->prev;
if (search->nbytes == 0 && search->nkey == 0 && search->it_flags == 1)
{
/* 满足该条件的属于爬虫数据,忽略 */
tries++;
continue;
}
uint32_t hv = hash(ITEM_key(search), search->nkey);
/* Attempt to hash item lock the "search" item. If locked, no
* other callers can incr the refcount. Also skip ourselves. */
/* 尝试对Item进行加锁,如果lock失败,则跳过*/
if (hv == cur_hv || (hold_lock = item_trylock(hv)) == NULL)
continue;

/* item的refcount是引用计数,记录了该item被引用的次数,正常情况下,refcount>1说明该Item还是使用中 */
if (refcount_incr(&search->refcount) != 2) {
/* Note pathological case with ref'ed items in tail.
* Can still unlink the item, but it won't be reusable yet */
itemstats[id].lrutail_reflocked++;
/* In case of refcount leaks, enable for quick workaround. */
/* WARNING: This can cause terrible corruption */
/*对于refcount为1的item,要进行额外的判断,默认不执行这段代码*/
if (settings.tail_repair_time &&
search->time + settings.tail_repair_time < current_time) {
itemstats[id].tailrepairs++;
search->refcount = 1;
/* This will call item_remove -> item_free since refcnt is 1 */
do_item_unlink_nolock(search, hv);
item_trylock_unlock(hold_lock);
continue;
}
}

/* Expired or flushed */
if ((search->exptime != 0 && search->exptime < current_time)
|| is_flushed(search)) {
itemstats[id].reclaimed++;
if ((search->it_flags & ITEM_FETCHED) == 0) {
itemstats[id].expired_unfetched++;
}
/* refcnt 2 -> 1 */
/* 该方法删除Item的Hash值,同时从LRU中移除该Item,并尝试回收该ITEM,由于refcount从2->1,refcount>0,回收会失败*/
do_item_unlink_nolock(search, hv);
/* refcount从1->0,回收成功,回收的ITEM会被放入slots的空闲链表头 */
do_item_remove(search);
item_trylock_unlock(hold_lock);
removed++;

/* If all we're finding are expired, can keep going */
continue;
}

/*如果ITEM在HOT_LRU或者WARM_LRU中,同时LRU的大小超过限制,该ITEM移动COLD_LRU; 如果ITEM在COLD_LRU,移动到WARM_LRU,除非我们要强制清除 */
switch (cur_lru) {
case HOT_LRU:
limit = total_chunks * settings.hot_lru_pct / 100;
case WARM_LRU:
limit = total_chunks * settings.warm_lru_pct / 100;
if (sizes[id] > limit) {
itemstats[id].moves_to_cold++;
move_to_lru = COLD_LRU;
/*该方法只是把Item从LRU链表中移除*/
do_item_unlink_q(search);
it = search;
removed++;
break;
} else if ((search->it_flags & ITEM_ACTIVE) != 0) {
/* Only allow ACTIVE relinking if we're not too large. */
itemstats[id].moves_within_lru++;
search->it_flags &= ~ITEM_ACTIVE;
do_item_update_nolock(search);
do_item_remove(search);
item_trylock_unlock(hold_lock);
} else {
/* Don't want to move to COLD, not active, bail out */
it = search;
}
break;
case COLD_LRU:
it = search; /* No matter what, we're stopping */
if (do_evict) {
if (settings.evict_to_free == 0) {
/* Don't think we need a counter for this. It'll OOM. */
break;
}
itemstats[id].evicted++;
itemstats[id].evicted_time = current_time - search->time;
if (search->exptime != 0)
itemstats[id].evicted_nonzero++;
if ((search->it_flags & ITEM_FETCHED) == 0) {
itemstats[id].evicted_unfetched++;
}
/*想当于做了do_item_unlink_q和do_item_remove*/
do_item_unlink_nolock(search, hv);
removed++;
} else if ((search->it_flags & ITEM_ACTIVE) != 0
&& settings.lru_maintainer_thread) {
itemstats[id].moves_to_warm++;
search->it_flags &= ~ITEM_ACTIVE;
move_to_lru = WARM_LRU;
do_item_unlink_q(search);
removed++;
}
break;
}
if (it != NULL)
break;
}

pthread_mutex_unlock(&lru_locks[id]);

if (it != NULL) {
if (move_to_lru) {
it->slabs_clsid = ITEM_clsid(it);
it->slabs_clsid |= move_to_lru;
item_link_q(it);
}
/*能够进到这一步的item,我们需要手动减少refcount的值*/
do_item_remove(it);
item_trylock_unlock(hold_lock);
}

return removed;
}


3.Item失效和引用计数

Memcached从LRU链表的尾部进行Item的检查(跳过已经被其他线程加锁的Item),当满足以下的条件时,Item被清理,那Item满足失效的具体条件是什么呢。在介绍Item失效之前,我们先介绍一下Item的引用计数,引用计数的作用主要要为了防止多个线程的影响。打个比方,线程A在读取的数据的同时线程B在删除数据就会引发一定的问题。在Memcached中,当线程在使用Item的时候,该Item的引用计数加1,使用之后Item的引用计数减1,所以只有当Item的引用计数为0时,该Item才可以被真正的清理。理解这段逻辑对于Item的失效和回收非常重要。现在我们看看Item的失效条件。

1. Item已经过期,惰性回收,在访问的时候会进行判断回收;在Item内存分配时也会进行一定的回收检查。

2. Item被淘汰(这个有个flush_all命令,可以强制回收老的数据)。为了防止大量Item被回收造成的性能低下,Memcached也采用了惰性回收的机制。

3. Item不满足条件,但是Memcached设置了tail_repair_time(该设置主要是为了防止部分线程异常,没有减少refcount而导致异常。正常的refcount都是1),同时该Item的最后访问的时间小于(当前时间-tail_repair_time),该Item进行清理

在LRU链表的检查中,如果Item没有满足上面提到的清理条件,则Item会进行判断,看是否需要再不同级LRU之间移动,其具体的规则如下:

1. 如果当前Item在HOT_LRU或者WARM_LRU,则进行当前LRU最大limit的判断。当该LRU中Item数量>limit时,Item被移动到COLD_LRU中;当Item数量<=limit同时Item处于Active状态时,更新Item;

2. 如果当前Item在COLD_LRU中时,如果允许拒绝Item(do_evict=true),直接清理该Item;否则,如果该Item处于Active状态时,移动到WARM_LRU中。

Memcached的分级LRU策略把最新的数据尽量往HOT_LRU和WARM_LRU中分配,而COLD_LRU中的数据一般是最近最少使用的数据,这样可以很好地提高回收的效果。

4. LRU管理和爬虫机制

上面我们具体的分析了Memcached中LRU的分级策略,除了惰性回收机制,Memcached也给我们提供了强制清除的方法。LRU管理和爬虫机制。首先先看看Item可能发生回收的地方:

1. 在获取Item的时候,如果Item满足回收条件,则Item会被回收。

2. 在Item分配空间时会对LRU进行有限度的回收。它会进行最多5次的回收尝试。

3. LRU管理线程会定时对LRU进行检查,回收可以被回收的资源,同时根据资源的分配和使用情况,不同级LRU中进行移动。

4. Item爬虫线程会对每个LRU链表进行检查,回收满足回收条件的资源。同时,LRU管理线程结束也会促发Item爬虫线程的执行。

LRU管理线程主要是对分级LRU的管理,负责过期ITEM的回收和不同级LRU之间数据的移动。它的控制粒度比较大,是针对单个slabclass来说的。

/*数据在不同的LRU之间的转移,每次1000次循环;做的事情非常简单,对LRU的Item进行回收,如果HOT_LRU和WARM_LRU数据过多,移到COLDE_LRU;如果COLD_LRU数据过多,进行清除*/
static int lru_maintainer_juggle(const int slabs_clsid) {
    int i;
    int did_moves = 0;
    bool mem_limit_reached = false;
    unsigned int total_chunks = 0;
    /* TODO: if free_chunks below high watermark, increase aggressiveness */
    slabs_available_chunks(slabs_clsid, &mem_limit_reached, &total_chunks);
    if (settings.expirezero_does_not_evict)
        total_chunks -= noexp_lru_size(slabs_clsid);

    /* Juggle HOT/WARM up to N times */
    for (i = 0; i < 1000; i++) {
        int do_more = 0;
        if (lru_pull_tail(slabs_clsid, HOT_LRU, total_chunks, false, 0) ||
            lru_pull_tail(slabs_clsid, WARM_LRU, total_chunks, false, 0)) {
            do_more++;
        }
        do_more += lru_pull_tail(slabs_clsid, COLD_LRU, total_chunks, false, 0);
        if (do_more == 0)
            break;
        did_moves++;
    }
    return did_moves;
}

而爬虫机制则是针对每个LRU链表来进行清理的。Memcached为了提高性能,所以不能对某一个LRU进行加锁完成所有Item的检查回收。它采用的是在LRU链表中插入一个标记Item来进行定位清理。

/* 爬虫的实现是在LRU链表尾部加入爬虫的ITEM,然后该ITEM逐步向链表头移动,每次检查一个Item,看是否满足回收条件,满足则回收,当爬虫ITEM达到链表头则执行结束。该方法就是把爬虫ITEM前移的方法 */
static item *crawler_crawl_q(item *it) {
    item **head, **tail;
    assert(it->it_flags == 1);
    assert(it->nbytes == 0);
    assert(it->slabs_clsid < LARGEST_ID);
    head = &heads[it->slabs_clsid];
    tail = &tails[it->slabs_clsid];

    /* We've hit the head, pop off */
    if (it->prev == 0) {
        assert(*head == it);
        if (it->next) {
            *head = it->next;
            assert(it->next->prev == it);
            it->next->prev = 0;
        }
        return NULL; /* Done */
    }

    /* Swing ourselves in front of the next item */
    /* NB: If there is a prev, we can't be the head */
    assert(it->prev != it);
    if (it->prev) {
        if (*head == it->prev) {
            /* Prev was the head, now we're the head */
            *head = it;
        }
        if (*tail == it) {
            /* We are the tail, now they are the tail */
            *tail = it->prev;
        }
        assert(it->next != it);
        if (it->next) {
            assert(it->prev->next == it);
            it->prev->next = it->next;
            it->next->prev = it->prev;
        } else {
            /* Tail. Move this above? */
            it->prev->next = 0;
        }
        /* prev->prev's next is it->prev */
        it->next = it->prev;
        it->prev = it->next->prev;
        it->next->prev = it;
        /* New it->prev now, if we're not at the head. */
        if (it->prev) {
            it->prev->next = it;
        }
    }
    assert(it->next != it);
    assert(it->prev != it);

    return it->next; /* success */
}

/* 爬虫真正回收Item的方法
 */
static void item_crawler_evaluate(item *search, uint32_t hv, int i) {
    int slab_id = CLEAR_LRU(i);
    crawlerstats_t *s = &crawlerstats[slab_id];
    itemstats[i].crawler_items_checked++;
    if ((search->exptime != 0 && search->exptime < current_time)
        || is_flushed(search)) {
        itemstats[i].crawler_reclaimed++;
        s->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);
        assert(search->slabs_clsid == 0);
    } else {
        s->seen++;
        refcount_decr(&search->refcount);
        if (search->exptime == 0) {
            s->noexp++;
        } else if (search->exptime - current_time > 3599) {
            s->ttl_hourplus++;
        } else {
            rel_time_t ttl_remain = search->exptime - current_time;
            int bucket = ttl_remain / 60;
            s->histo[bucket]++;
        }
    }
}


本文来自网易实践者社区,经作者吕宗胜授权发布