Memcached深度分析

Memcached初始化的时候，会初始化slab（前面可以看到，在main函数中调用了slabs_init()）。它会在slabs_init()中检查一个常量DONT_PREALLOC_SLABS，如果这个没有被定义，说明使用预分配内存方式初始化slab，这样在所有已经定义过的slabclass中，每一个id创建一个slab。这样就表示，1.2在默认的环境中启动进程后要分配41MB的slab空间，在这个过程里，memcached的第二个内存冗余发生了，因为有可能一个id根本没有被使用过，但是它也默认申请了一个slab，每个slab会用掉1MB内存

当一个slab用光后，又有新的item要插入这个id，那么它就会重新申请新的slab，申请新的slab时，对应id的slab链表就要增长，这个链表是成倍增长的，在函数grow_slab_list函数中，这个链的长度从1变成2，从2变成4，从4变成8……：

CODE:[Copy to clipboard]static int grow_slab_list (unsigned int id) {
    slabclass_t *p = &slabclass[id];
    if (p->slabs == p->list_size) {
        size_t new_size =  p->list_size ? p->list_size * 2 : 16;
        void *new_list = realloc(p->slab_list, new_size*sizeof(void*));
        if (new_list == 0) return 0;
        p->list_size = new_size;
        p->slab_list = new_list;
    }
    return 1;
}
在定位item时，都是使用slabs_clsid函数，传入参数为item大小，返回值为classid，由这个过程可以看出，memcached的第三个内存冗余发生在保存item的过程中，item总是小于或等于chunk大小的，当item小于chunk大小时，就又发生了空间浪费。

◎Memcached的NewHash算法

Memcached的item保存基于一个大的hash表，它的实际地址就是slab中的chunk偏移，但是它的定位是依靠对key做hash的结果，在primary_hashtable中找到的。在assoc.c和items.c中定义了所有的hash和item操作。

Memcached使用了一个叫做NewHash的算法，它的效果很好，效率也很高。1.1和1.2的NewHash有一些不同，主要的实现方式还是一样的，1.2的hash函数是经过整理优化的，适应性更好一些。

NewHash的原型参考：http://burtleburtle.net/bob/hash/evahash.html。数学家总是有点奇怪，呵呵～

为了变换方便，定义了u4和u1两种数据类型，u4就是无符号的长整形，u1就是无符号char(0-255)。

具体代码可以参考1.1和1.2源码包。

注意这里的hashtable长度，1.1和1.2也是有区别的，1.1中定义了HASHPOWER常量为20，hashtable表长为hashsize(HASHPOWER)，就是4MB（hashsize是一个宏，表示1右移n位），1.2中是变量16，即hashtable表长65536：

CODE:[Copy to clipboard]typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */

#define hashsize(n) ((ub4)1<<(n))
#define hashmask(n) (hashsize(n)-1)
在assoc_init()中，会对primary_hashtable做初始化，对应的hash操作包括：assoc_find()、assoc_expand()、assoc_move_next_bucket()、assoc_insert()、assoc_delete()，对应于item的读写操

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!