MemcachedLRU 淘汰策略，以及数据丢失问题
0x01 问题说明：
有两个服务，⼀个服务A会先通过get操作到memcached中拿图⽚c，如果返回为空会去对象存储系统中拿图⽚c然后缓存在memcached 中，超时时间设置为⼀周，然后返回mc_key信息，另外⼀个服务B会拿这个mc_key信息去memcached中获取保存的图⽚。这个是个异步的过程。
然后线上出现⼀个诡异的问题，A服务已经在memcached中get到了这个图⽚（⽇志中打印：picture already in memcached），但是B 服务拿着mc_key去取这个图⽚的时候却不到这个图了，看⽇志相隔时间不超过50ms左右
memcached memcached -m 16384M -p 11211 -c 8096 -I 20M
memcached版本是1.5.4
内存⾜够⼤不⾄于50ms就把⼀个位于LRU头部的数据给淘汰了。以前⽤的是1.4.x的版本，最近升级到1.5.x发现有这个问题。0x02 memcached 内存模型
然后我们就来看看memcached的LRU吧。
⾸先要知道的概念：
slab: memcached中会有多个，是内存分级⽤的。不同层级的slab归做⼀类，叫做：slabclass，结构体如下：
chunk：slab中的⼀个内存空间。slab就是按照不同⼤⼩的chunk来分级的。从下图中可以看到chunk的size是逐渐增⼤，这个增⼤的量级是由增长因⼦决定的，默认1.25。 可以⽤如下命令查看： 之间的关系就是这样的： slabclass是由chunk size确定的, 同⼀个slabclass内的chunk⼤⼩都⼀样, 每⼀个slabclass 要负责管理⼀些内存, 初始时, 系统为每个 slabclass 分配⼀个 slab, ⼀个 slab 就是⼀个内存块, 其⼤⼩等于1M（这个可通过-I指定）. 然后每个slabclass 再把 slab 切分成⼀个个 chunk, 算⼀下, ⼀个 slab 可以切分得到 1M/chunk_size 个chunk.item： memcached中保存数据的结构体，也是LRU链表中的node，数据也就是保存在item中的，结构如下：typedef struct {
unsigned int size;      /* sizes of items */
unsigned int perslab;  /* how many items per slab */
//这个是⽤来保存空闲item 的
void *slots;          /* list of item ptrs */
access被淘汰了吗unsigned int sl_curr;  /* total free items in list */
void *end_page_ptr;        /* pointer to next free item at end of page, or 0 */
unsigned int end_page_free; /* number of items remaining at end of last alloced page */
unsigned int slabs;    /* how many slabs were allocated for this class */
void **slab_list;      /* array of slab pointers */
unsigned int list_size; /* size of prev array */
unsigned int killing;  /* index+1 of dying slab, or zero if none */
size_t requested; /* The number of requested bytes */
} slabclass_t;
⼤体是这个样⼦的：
memcached的LRU就是靠item连接成的双向链表。添加⼀个item的⽅法：（可以看到新节点都是之间添加到链表头部的）
/** * Structure for storing items within memcached.
*/
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;
移除⼀个item：static void do_item_link_q(item *it) { /* item is the new head */
item **head, **tail;
assert((it->it_flags & ITEM_SLABBED) == 0);    head = &heads[it->slabs_clsid];
tail = &tails[it->slabs_clsid];
assert(it != *head);
assert((*head && *tail) || (*head == 0 && *tail == 0));
it->prev = 0;
it->next = *head;
if (it->next) it->next->prev = it;
*head = it;
if (*tail == 0) *tail = it;
sizes[it->slabs_clsid]++;
return;
}
static void do_item_unlink_q(item *it) {    item **head, **tail;
head = &heads[it->slabs_clsid];
tail = &tails[it->slabs_clsid];
if (*head == it) {
assert(it->prev == 0);
*head = it->next;
}
if (*tail == it) {
assert(it->next == 0);
*tail = it->prev;
}
assert(it->next != it);
assert(it->prev != it);
if (it->next) it->next->prev = it->prev;
if (it->prev) it->prev->next = it->next;
sizes[it->slabs_clsid]--;
return;
}
整体是这样的：
0x03 新版本的分段LRU
基本知识了解这些差不多够了。在⽼版本中memcached的LRU是⼀个很典型的实现了，最近访问的应该bump到head位置，但是新版本做了⼀些改变，将LRU分段了（Segmented LRU）。这也就是导致我开篇就说的问题的原因，具体我慢慢分析。
我们先看看memcached的官⽅⽂档，将LRU分成了：HOT WARM COLD TEMP 为什么要分段？主要是为了降低锁竞争，提升效率。 每个 item 有⼀个 flag，存储在其元数据中，标识其活跃程度：
FETCHED：如果⼀个 item 有请求操作，其 flag 等于 FETCHED。
ACTIVE：如果⼀个 item 第⼆次被请求则会标记为 ACTIVE；当⼀个 item 发⽣ bump 或被删除了，flag 会被清空。
INACTIVE：不活跃状态。
item在他们之间的变化规则是这样的：
新来的item都加到HOT中
⼀个item被访问两次就标记为active状态
（随着新item不断的加⼊），如果item移动到了链表的bottom。
如果是在HOT LRU中且为active状态，则把这个item直接移⼊WARM，否则加⼊COLD；
如果是在WARM中，且是active状态那么把这个item提到WARM链表的开头，否则移动到COLD中；
COLD中的item是最惨的，他们都是inactive状态。当内存满了的时候就要开始淘汰他们中的⼀些
COLD中的item如果变成了active状态后，会被放⼊队列，然后异步（注意是异步的哦）移动到WARM中
HOT和WARM的⼤⼩是受限的，占该slab class内存量的N%, COLD ⼤⼩是不受限的
具体状态图如下：
上⾯第5点要关注哦。是异步，并不是⽴马就移动到WARM中，所以，在COLD中的item变成active后还是可能被淘汰。
引⽤下别⼈的，当新来⼀个item时候的流程：
1.do_item_alloc进⼊新增item的内存申请流程。
2.do_item_alloc_pull进⼊item申请的逻辑处理，最多处理10次。
3.do_item_alloc_pull内部逻辑是尝试通过slabs_alloc申请内存，失败则尝试通过lru_pull_tail⽅法释放LRU队列中的item变成可⽤
item。
4.lru_pull_tail执⾏释放LRU队列中item的过程，内部包括各种过期item的回收
5.在lru_pull_tail当中调⽤do_item_unlink_nolock进⾏item回收
6.在do_item_unlink_nolock当中调⽤do_item_unlink_q释放LRU链表，调⽤do_item_remove回收item为可⽤item。
下⾯这两段代码是⼀个新的item来的时候如何处理：
item *do_item_alloc(char *key, const size_t nkey, const unsigned int flags,
const rel_time_t exptime, const int nbytes) {
uint8_t nsuffix;
item *it = NULL;
char suffix[40];
size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
unsigned int id = slabs_clsid(ntotal);
unsigned int hdr_id = 0;
if (ntotal > settings.slab_chunk_size_max) {
int htotal = nkey + 1 + nsuffix + sizeof(item) + sizeof(item_chunk);
if (settings.use_cas) {
htotal += sizeof(uint64_t);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。