那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

memcached内存管理算法

简单的写写,看完了memcached的这部分代码之后觉得跟我的ccache还是很像的.

1) 分配
memcached中的内存全部由类型为slabclass_t的结构体保存
typedef struct {
    unsigned 
int size;      /* sizes of items */
    unsigned 
int perslab;   /* how many items per slab */

    
void **slots;           /* list of item ptrs */
    unsigned 
int sl_total;  /* size of previous array */
    unsigned 
int sl_curr;   /* first free slot */

    
void *end_page_ptr;         /* pointer to next free item at end of page, or 0 */
    unsigned 
int end_page_free; /* number of items remaining at end of last alloced page */

    unsigned 
int slabs;     /* how many slabs were allocated for this class */

    
void **slab_list;       /* array of slab pointers */
    unsigned 
int list_size; /* size of prev array */

    unsigned 
int killing;  /* index+1 of dying slab, or zero if none */
} slabclass_t;
有一个全局的slabclass_t的数组,slabclass_t中的size字段保存每个slab所能保存的数据大小.在这个slabclass_t数组中,size字段都是递增的,递增的因子由slabs_init函数中的第二个参数factor参数指定.比如说,假如factor是2,那么如果第一个slabclass_t的size是unsigned int size = sizeof(item) + settings.chunk_size;(也是在slabs_init函数中的语句),那么下一个slabclass_t的size就是size*factor(这里忽略对齐的因素).
于是乎,假设第一个slab能保存8byte的数据,factor为2,那么接下来的slab的size依次为16byte,32byte...
每次需要分配内存,都需要根据所需分配的尺寸查找大于该尺寸的最小尺寸的slab,比如还是前面的那个slab模型,如果现在需要分配30byte的空间,查找得到大于30byte的最小slab尺寸是32byte,于是就从这个slab中查找item分配给它.
但是这里有一个问题,就是多余资源的浪费,前面说的30byte只是浪费了2byte,但是如果现在要分配的是17byte,那么就浪费了15byte,浪费了将近50%!因此才有了前面需要指定factor的原因,使用者可以根据需要指定不同的增长factor,以降低资源的浪费.

2) 淘汰
淘汰采用的是LRU算法,所有的最近使用的item保存在static item *tails[LARGEST_ID];(item.c)中,已经分配的内存会以链表的形式保存在这个数组中,如果对应的slab已经分配不到足够的内存,就到这个链表中查询,淘汰的依据是item结构体中的exptime字段.

简单分析到此,需要更详细的解释就去看代码吧,memcached中与这部分的代码在slab.h(.c)/item.h(.c)中,两个关键的结构体是item和slabclass_t.



posted on 2009-03-09 22:24 那谁 阅读(6976) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构Linux/Unixmemcached


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理