理解 Memcached 源码 - LRU I

多半情况下,LRU 会和 哈希表一起使用,然后我们把这个组合称为

LRU 缓存

LRU缓存 中,哈希表提供了快速随机访问对象的能力;而LRU(算法)则用于淘汰很久没用 (least recently used) 的对象,来避免缓存无限增加。我们先大致看下 LRU 组成。

链表

从技术上来说,LRU 算法是在链表上完成的 - 当一个表项被使用(访问或更新),LRU 会先做移除,然后把它重新插入到表头。这样,越接近表尾的对象就是 越久没使用 (least recently used),淘汰起来比较简单。

哈希表

链表是不支持快速的随机访问的,所以需要和 哈希表 一起使用。之前我们之前已经读过, 子系统的空闲列表是通过链表把 里的 (chuck) 串起来形成的。在 LRU缓存 里也差不多,而这次用链表串起来的是表项。大致看起来是这样:

hash map perspective

从另外一个维度看起来可能会更直观一点:

linked list perspective

核心数据结构 - item

typedef struct _stritem {
/* Protected by LRU locks */
struct _stritem *next;
struct _stritem *prev;
/* Rest are protected by an item lock */
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 {
... // scr: cas
char end; // scr: flexible array member indicating the item header "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;
do_item_unlink@item.cSourceRead

使用到的字段

next, prev - LRU 链表 指针, 在 do_item_alloc (LRU III) 初始化, 被 item_link_q, item_unlink_q 使用。

h_next - hash 冲突链表 的指针, 在 do_item_alloc (LRU III) 初始化, 被 assoc_insert, assoc_delete, 多个模块 (LRU II) 使用。

time - 最后访问时间, 在 do_item_link 中设置, 被 lru_pull_tail (LRU III) 使用。

exptime - 超时时间(由请求参数指定), 在 do_item_alloc (LRU III) 初始化, 被 lru_pull_tail (LRU III) 使用。

nbytes - 数据大小(由请求参数指定),在 do_item_alloc (LRU III) 初始化。

refcount - 引用计数, 在 do_slabs_alloc (Slab III) 初始化, 被 do_item_link 使用。

nsuffix - 在 do_item_alloc (LRU III)item_make_header 初始化。

it_flags - 在 do_item_alloc (LRU III) 初始化, 被 do_item_link, do_item_unlink 使用。

slabs_clsid - 当前对象存在的具体的 LRU 链表 , 被 do_item_alloc (LRU III) 初始化, 在 item_link_q, item_unlink_q 使用。

nkey - 键大小, 在 do_item_alloc (LRU III) 中计算, 被 assoc_delete 使用。

块的内存布局

我们在 do_slabs_free 提到过 。这次我们直接通过数据结构来看下它的构造。

item chunk

下面我们来读直接操作 LRU 的相关代码。

do_item_link

int do_item_link(item *it, const uint32_t hv) { // scr: -------------------> 1)
...
it->it_flags |= ITEM_LINKED; // scr: -------------------> 2)
it->time = current_time;

... // scr: stat

/* Allocate a new CAS ID on link. */
... // scr: cas
assoc_insert(it, hv); // scr: -------------------> 3)
item_link_q(it); // scr: -------------------> 4)
refcount_incr(&it->refcount); // scr: -------------------> 5)
... // scr: stat

return 1;
}
do_item_link@item.cSourceRead

1) 正常理解, hv 应该就是哈希值 “hashed value” 的缩写。

2) 设置 it->it_flagsITEM_LINKED 标志, 然后将当前时间赋值给 it->time


The field it_flags is used in do_slabs_free and do_slabs_alloc

3) 将 对象 添加到哈系表。

4) 将 对象 添加到链表。

5) 递增 reference count


这个字段的初始值是 1do_slabs_alloc

要注意 引用计数 代表了有几个子模块同时在使用该资源。这个字段是决定是否回收该资源的关键参考 (在这里,对象 同时被 LRU 在使用)。我在 另一篇文章 里详细讨论了C++里相似的机制。

item_link_q 是主力函数 do_item_link_q 的线程安全的简单包装。

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]; // scr: -------------------> 1)
tail = &tails[it->slabs_clsid];
assert(it != *head);
assert((*head && *tail) || (*head == 0 && *tail == 0));
it->prev = 0; // scr: -------------------> 2)
it->next = *head;
if (it->next) it->next->prev = it;
*head = it;
if (*tail == 0) *tail = it;
sizes[it->slabs_clsid]++; // scr: -------------------> 3)
return;
}
do_item_link_q@item.cSourceRead

1) 从对应的 LRU 链表 (由slabs_clsid指定)获取 headtail。注意 slabs_clsid 是用队列类型加过盐的,所以每个 板组 可能会包含复数个列表。

2) 标准动作,”添加表头项”。

3) 增加全局的数组 大小


static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
...
static unsigned int sizes[LARGEST_ID];

item.c:59SourceRead

assoc_insert - 添加至哈希表

int assoc_insert(item *it, const uint32_t hv) { // scr: again, hv -> hash value
unsigned int oldbucket;

... // scr: expanding related operations
} else {
it->h_next = primary_hashtable[hv & hashmask(hashpower)]; // scr: 1)
primary_hashtable[hv & hashmask(hashpower)] = it; // scr: 2)
}

... // scr: expanding related operations
}
assoc_insert@assoc.cSourceRead

1) 冲突处理。没冲突?将 h_next 直接设置为 null

2) 将 对象 添加到 primary_hashtable 的桶。


...
static item** primary_hashtable = 0;
...

assoc.c:42SourceRead

扩容的逻辑先留个坑,下篇 再来讲。

do_item_unlink

void do_item_unlink(item *it, const uint32_t hv) {
MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);
if ((it->it_flags & ITEM_LINKED) != 0) {
it->it_flags &= ~ITEM_LINKED; // scr: -------------------> 1)
... // scr: stat
assoc_delete(ITEM_key(it), it->nkey, hv); // scr: ---------------> 2)
item_unlink_q(it); // scr: -------------------> 3)
do_item_remove(it); // scr: -------------------> *)
}
}
do_item_unlink@item.cSourceRead

1) 清除 it->it_flagsITEM_LINKED 位。

2) 从哈希表移除 对象

3) 从链表移除 对象

*) 实际释放 对象 的逻辑后面会讲。

同上,item_unlink_q 只是一个对于实调函数 do_item_unlink_q 线程安全的简单封装。

static void do_item_unlink_q(item *it) {
item **head, **tail;
head = &heads[it->slabs_clsid]; // scr: -------------------> 1)
tail = &tails[it->slabs_clsid];

if (*head == it) { // scr: -------------------> 2)
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]--; // scr: -------------------> 3)
return;
}
do_item_unlink_q@item.cSourceRead

1) 同样, 获取 由 slabs_clsid 指定的 LUR 链表headtail

2) 标准的 “移除链表项” 操作。

3) 减少全局的数组 大小


static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
...
static unsigned int sizes[LARGEST_ID];

item.c:59SourceRead

assoc_delete - 从哈希表移除

static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
item **pos;
unsigned int oldbucket;

... // scr: expanding related operations
} else {
pos = &primary_hashtable[hv & hashmask(hashpower)]; // scr: -----> 1)
}

while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
pos = &(*pos)->h_next; // scr: ----------------------------------> 2)
}
return pos;
}

...

void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
item **before = _hashitem_before(key, nkey, hv);

if (*before) {
item *nxt;
...
nxt = (*before)->h_next; // scr: --------------------------------> 3)
(*before)->h_next = 0; /* probably pointless, but whatever. */
*before = nxt; // scr: ------------------------------------------> 4)
return;
}
/* Note: we never actually get here. the callers don't delete things
they can't find. */
assert(*before != 0);
}
assoc_delete@assoc.cSourceRead

1) 通过 hv 获取桶。

2) 遍历冲突链表并比较 key。注意这里的返回值是 指定元素上一个元素的 next 字段的地址。而当没有冲突时,这个地址就是桶本身。

3) 将找到的下一个元素赋值给 nxt

4) 更新 指定元素上一个元素的 next 字段

打包带走

试下这个

That's it. Did I make a serious mistake? or miss out on anything important? Or you simply like the read. Link me on -- I'd be chuffed to hear your feedback.