memcached中的经典数据结构hash链表和LRU删除策略的应用

1,917 阅读4分钟

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

缓存操作

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

函数 作用
item_init 初始化lru链表头尾指针、item数量数组
item_make_header 计算一个item占用的内存字节数
item_alloc 从slab中分配出item的内存
item_free 把item内存还给slab
item_size_ok 检查item内存大小是否超过了slab允许的范围
item_link_q 把item加入到lru链表头
item_unlink_q 从链表中删除item
item_link 把item插入hash表,同时加入lru链表中(item_link_q)
item_unlink 把item从hash表中删除,同时从lru链表中删除(item_unlink_q)
item_remove 把item内存还给slab,带异常检查
item_update 修改item,同时按照lru规则重建这个item在lru链表中的位置
item_replace 替换item,和item_update的区别时,这个不会修改item的最后访问时间
item_cachedump 获取指定slab的所有item的key和value的大小
item_stats 获取所有lru链表的大小
item_stats_sizes 统计item的大小

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

hash表构建

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

函数 作用
hash 将字符串char*散列成8字节32位的数字
assoc_init 为hash表分配内存空间,默认大小是hashsize(HASHPOWER) * sizeof(void*)
assoc_find 通过hash表找到对应hash的value
assoc_insert 将新key插入hash表
assoc_delete 从hash表中删除指定key的hash

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,进行删除释放内存空间给新增的元素使用

核心代码在items.c中,调用slabs_alloc(ntotal)分配内存失败时

it = slabs_alloc(ntotal);
if (it == 0) {
    int tries = 50;
    item *search;
    if (tails[id]==0) return 0;

    for (search = tails[id]; tries>0 && search; tries--, search=search->prev) {
        if (search->refcount==0) {
            item_unlink(search);
            break;
        }
    }
    it = slabs_alloc(ntotal);
    if (it==0) return 0;
}

memcached一共会尝试最后50个元素进行lru淘汰,如果仍然没有元素可删除,这个时候就直接返回错误了,最新版lru对这个简单的策略改进了很多,参考:do_item_alloc_pull()

一些注意的点

本文基于memcached 1.2.0

telnet调试memcached时value跟在最后,命令以回车(\n)结束,核心代码如下

el = memchr(c->rcurr, '\n', c->rbytes);
if (!el)
    return 0;

参考资料

  1. github.com/memcached/m…
  2. www.journaldev.com/16/memcache…
  3. blog.csdn.net/sky2098/art…