hash链表是memcached核心的数据结构了，hash表用于快速读取、写入缓存数据（item结构），链表用于实现lru策略，lru用于内存不足时的兜底策略，有效防止了内存不足时造成宕机

缓存操作

memcached中使用struct _stritem结构体代表缓存，这个结构体被typedef定义成了item类型，对这个item结构体的操作都在item.c中，函数列表如下

可以看到这个item的操作就用到了hash表和链表，item是在hash表和链表上进行的，即对缓存item的操作，会同时影响到hash表和链表两种数据结构的构建

hash表构建

hash表的构建、crud操作都在assoc.c中

hash冲突的解决

不同的key，通过hash函数可能hash成了同一个32位的数字，这不会影响hash表插入(纯链表操作)，但是查找的时候，就不能只靠hash找item了，memcached采用的是开放寻址，即对比找到的item的key是否和查找的key相同，如不同，就是遇到了hash冲突，继续和链表的下一个item进行对比

item *it = hashtable[hv];

while (it) {
    if (strcmp(key, ITEM_key(it)) == 0)
        return it;
    it = it->h_next;
}
return 0;
复制代码

链表构建

lru链表定义在了items.c中，在item_init()函数中初始化成空指针

items.c

#define LARGEST_ID 255
static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
复制代码

item_init()

for(i=0; i<LARGEST_ID; i++) {
    heads[i]=0;
    tails[i]=0;
}
复制代码

LARGEST_ID常量是最大的内存slab数量，每个slab对应了一个头尾链表。

链表头维护时机

add/set时添加

add/set/replace时会把状态机置成conn_nread状态: conn_set_state(c, conn_nread)

通过nread -> complete_nread(c) -> item_link(it) -> item_link_q(it) 再item_link_q中把item放到lru链表头部(链表头指向新增的元素)，核心代码如下

head = &heads[it->slabs_clsid];
tail = &tails[it->slabs_clsid];
it->prev = 0;
it->next = *head;
*head = it;
if (*tail == 0) *tail = it;
复制代码

如果这时如果尾指针为空，表示lru链表都是刚构建，这时尾指针和头指针初始化都指向第一个it元素

replace时删除

item被replace、delete时，都需要把item从lru链表中删除，replace会调用item_link_q重新添加到lru链表中

item_unlink_q()核心代码如下

item **head, **tail;

head = &heads[it->slabs_clsid];
tail = &tails[it->slabs_clsid];

if (*head == it) {
    *head = it->next;
}
if (*tail == it) {
    *tail = it->prev;
}

if (it->next) it->next->prev = it->prev;
if (it->prev) it->prev->next = it->next;
复制代码

可以看到如果被删除的item正好是lru链表的头/尾指针时，需要多维护一下头尾指针，其他情况直接把item从lru链表中解除关系即可

链表尾维护时机

链表尾指针只会在lru链表都是刚构建的时候，指向第一个元素，以及删除lru链表元素时，刚好删到了尾指针，其它时候都不会再动了，这就保证了tail指针永远指向lru链表的最后一个元素

lru生效时机

lru生效发生在memcached无法从slab分配新内存的时候，会尝试使用lru链表尾指针往前进行查找出可以删除的item，进行删除释放内存空间给新增的元素使用

请到「今天看啥」查看全文