Memcached源码分析——内存管理


注：这篇内容极其混乱

推荐学习这篇博客。博客的地址：http://kenby.iteye.com/blog/1423989

基本元素item

item是Memcached中记录存储的基本单元，用户向memcached写入的key value键值对信息都以item的形式存入Memcached中。

 

item基本结构

首先用一张图来描述item的基本结构：

_stritem * _stritem * _stritem *h_next; nbytes; } item;

使用typedef定义结构体_stritem为item。这个就是item的定义了。从item的定义中，可以看到，结构体本身并不包含任何关于数据key value的定义。那么是否和图中的红色部分有违背呢？

 

堆上操作的宏定义技巧

答案是在操作item的时候肯定会在堆上分配空间，开发人员使用了宏定义的技巧，使得对内存的管理更加的灵活方便：

unsigned  size = (item) + settings.chunk_size;

上面是一个完整的chunk的大小的求解方法，可以看到除了sizeof以外，还额外负担了用户手动配置的chunk_size。可以看到一个item所占的空间由两部分构成，符合2.1.1中对item的定义。而chunk_size所指向的内存空间又是如何划分的？

首先撇开内存空间的定义，结构体item中最关键的data[]空数组的定义：

在_stritem结构体中定义了一个空的数组data[]，data[]不占用任何的空间。当item后续有数据时，data的地址就是紧接着item元数据部分的成员的首地址。有了这个就不难理解宏定义了。

cas是Memcached中为了支持多线程读写的一个标志，类似compare and swap（实际上是check and set），是可选的标志。当用户启动了cas特性后，则通过以下方式访问cas位：

item->data->cas;

 

而当用户没有启用cas的时候，则data就纯当指针基地址来使用了。有了以上的知识，我们来看几个宏定义的使用：

 ITEM_key(item) (((char*)&((item)->data)) \
         + (((item)->it_flags & ITEM_CAS) ? (uint64_t) :  ITEM_suffix(item) ((char*) &((item)->data) + (item)->nkey + 1 \
         + (((item)->it_flags & ITEM_CAS) ? (uint64_t) :  ITEM_data(item) ((char*) &((item)->data) + (item)->nkey + 1 \
         + (item)->+ (((item)->it_flags & ITEM_CAS) ? (uint64_t) : ))

使用四个宏定义来给予data指针计算不同成员的在堆空间上面的偏移量。来看第一个：ITEM_key(item)，首先将data的地址强制转换成char*指针，从而以步进为字节方式获得地址。随后判断当前flag是否包含cas的部分，如果包含，则指针加上uint64_t的大小（8个字节）越过cas占用的地址；如果没有包含，则加0，表明data的地址就是key的地址。

剩下求解suffix、data的地址采用类似相同的方式来完成。可以看到这个技巧的牛逼的地方。求解suffix、data地址的时候，可以看到有个+1的操作，这个原因是key的末尾有一个null终结符，占用1个字节的空间。因此需要加一操作。

为了求解整个item占用空间大小（不是chunk的占用空间），同样定义了宏来求解：

 ITEM_ntotal(item) (sizeof(struct _stritem) + (item)->nkey + 1 \
         + (item)->nsuffix + (item)->+ (((item)->it_flags & ITEM_CAS) ? (uint64_t) : ))

首先是_stritem本身的大小，随后是key的大小，空字节的大小，suffix的大小，value的大小，最后看当前是否使用了cas，如果使用了需要计算cas的大小。对每个分量求和便是整个item的大小。

从本小结的宏定义中我们看到了C语言项目对于内存的精细操作，纵观编程世界，可能也只有C能够做出这么精彩的内存操作。

 

item 元数据介绍

再来引入item的定义，这次直接截图了，写代码太占用空间了。

item** primary_hashtable = ;

用一个二级item指针就实现了hashtable，其实hashtable的实现都在业务逻辑中了。

Hash表的实际构成结构如下：

hashsize(n) ((ub4)1<<(n)) hashmask(n) (hashsize(n)-1)= hash(key, nkey, = primary_hashtable[hv & hashmask(hashpower)]

以上两个宏定义和两条语句求解hash表位置的item。其中hv的求解依赖自定义的hash函数，这个函数就不分析了。当求解出hv后，和宏2进行与操作就求出了hash表中桶的位置。而hashsize()就是将1左移n位，达到一个乘二的效果，而hashmask的目的是求出遮挡位：

以下为二进制：

原本：100000

遮挡：011111

可以看出遮挡位将首位变为0，剩余的都变为1。然后hv & hashmask的目的就是进行了一次求余数操作。这种求余操作避免了使用%这样消耗比较高的操作，缺点是只能应用于2的幂次的求余数操作。但一般为了快速，hash表的桶的个数也是2的幂次数。

求解出桶的位置之后，查找一个item就简单了。从桶的第0个元素的位置开始依次沿着h_next进行就可以了。

求余一般我都会直接使用%方法进行求解，开源项目能让人提炼自己的编程功力，提升基础。

 

hash表的扩张

hash表起始桶的个数为16，当存不下之后，hash表需要进行一次扩张操作。hash表的扩张需要一定时间，Memcached为了在表扩张时继续服务，使用了双hash表机制：

 item** primary_hashtable =  item** old_hashtable = ;

平常主要使用primary_hashtable，当hash表扩张的时候，临时使用old_hashtable，当hash表扩张完毕之后再切换到primary_hashtable。

Memcached使用assoc_maintenance_thread()这个函数对hash表进行管理，实质上是通过一个守护线程死循环处理：

通过一个while死循环，一直查看hash表的状态，当hash表满的时候对表进行扩容。

old_hashtable == calloc(hashsize(hashpower + ), ( * (settings.verbose > ++= = =+= hashsize(hashpower) * ( *=

开始扩张前，将old_hashtable指向主表，随即主表重新开始分配空间，可以看到新空间的大小是老空间的2倍。随后再状态位里面设置一些标记，记录hash表新使用的空间。最后将hash_is_expanding置为1，通知线程开始对hash表进行扩张操作。

线程do_run_maintenance_thread负责将老表中的所有数据依次拷贝到新表中。每个循环拷贝一个桶中的所有item，用户可以设置每个循环拷贝多个桶，通过改变hash_bulk_move变量的值。但是这样可能会导致堆cache锁占用的时间过长，影响Memcached对外提供的服务。hash表扩张拷贝的代码如下：

item *it, * (it = old_hashtable[expand_bucket]; NULL != it; it == it->= hash(ITEM_key(it), it->nkey, ) &->h_next ===++;

expand_bucket从0开始。拷贝时，将老表第0个桶中的所有元素依次取出，并重新计算在新表中的桶的位置，拷贝到新表中。如果新表当前桶中已经有了item了，那么就放到桶中的第一个位置中。随后将老表当前桶的位置置为空。最后对桶计数自增，进入下一个循环，继续拷贝数据。

 

元素的删除

memcached删除元素并不是真的删除，因为内存都是预先分配好的，hash表中存的东西相当于引用。指针变量退出函数后内存自动就释放了。因此元素的删除只是修改hash表的指针结构：

  item **before = (**--= (*before)->*before)->h_next = ;   
        *before = nxt;

就是将before->h_next=item->h_next操作，经典的跨指针删除法。函数_hashitem_before查找当前key对应元素的前一个item，以方便删除操作。

 

slab结构

Memcached将所有slab类组织在一起，构成了slab存储结构。

item * item *tails[LARGEST_ID];

在item.c文件中定义了两个全局的指针数组，这个就是当前系统中所有slabclass的LRU队列的头、尾指针。如果想要使用指定的LRU队列，使用head[id]以及tail[id]就可以对特定列表进行引用了。

v item插入

当系统新分配一个item时，需要将item放入LRU队列中进行保存。放入LRU队列的对首中：

= (item *)p->->slots = it-> (it->next) it->next->prev = ->sl_curr--= ( *)it;

 将slot链表中的第一个slot拿出来返回给调用者。如果当前slab类已经没有后空闲的slot链表，则需要重新分配内存，即调用函数：do_slabs_newslab()进行：

 ((mem_limit && mem_malloced + len > mem_limit && p->slabs > ) ||== ) ||
        ((ptr = memory_allocate((size_t)len)) == )) {

 

分配时，首先调用grow_slab_list()确保当前slab类有足够的空间。函数grow_slab_list()首先判断已经分配的slab个数是否已经赶上slab list的大小，如果赶上了说明slab list已经分配完了，调用realloc()将slab list的大小扩大一倍。

随后调用memory_allocate()分配1MB的空间出来，该函数将返回分配空间的指针mem_current，并将mem_current向前移动1MB大小，为下一次分配内存进行准备。又是一个手动管理内存的实例。

最后调用函数split_slab_page_into_freelist()将分配的内存初始化为slots，加入slot链表中。函数split_slab_page_into_freelist()将空间切分：

 slabclass_t *p = &
     (x = ; x < p->perslab; x+++= p->

依次将指针进行步进移动，划分为item，并将这个item进行fdo_slabs_free操作。而do_slabs_free()：

it = (item *->it_flags |=->prev = ->next = p-> (it->next) it->next->prev =->slots =->sl_curr++->requested -= size;

修改当前item的前后指针，将item移入slots链表中去。

 

在slab上删除一个item

有了前面小节的基础，当需要手动删除item时则比较简单了，调用函数do_item_unlink()完成。

 do_item_unlink(item *it, ->nkey, it->& ((it->it_flags & ITEM_LINKED) != ->it_flags &= ~-=-= ->nkey, hv);
        item_unlink_q(it);
        do_item_remove(it);
&

首先设置标志位，更新状态信息。随后调用assoc_delete()将item指针关系从hash表中删除。再调用item_unlink_q()将item指针关系从LRU队列中删除。最后调用do_item_remove()将item放入空闲slots队列中。

可以看出，删除item的时候并不真正的释放内存，而是巧妙的将空闲的item放入slots中，以备将来使用。优秀的内存管理操作使得Memcached的性能很高。

 

小结

本章对slab内存管理进行了介绍。可以看出，Memcached在对内存管理时，以slab类为核心，通过灵活改变操控hash表、LRU队列、slab空闲slots三类数据结构，改变item的具体行为以及位置，达成内存的分配与管理工作。设计非常合理与巧妙。

相关内容