Memcache-内存模型-源码分析

memcached-version-1.4.25

介绍

memcache 使用了 Slab Allocator 的内存分配机制， 按照预先规定的大小， 将待分配的内存划分不同的区域并分割成特定长度的块，每个区域块只存放相对应大小的数据，以达到解决内存碎片问题， 因为不断的 malloc() 不同大小的内存块会产生大量的内存碎片，所以 memcache 实现了自己的内存管理机制，下面就让我们看一下 memcache 内部是如何实现内存管理并划分不同长度的块.

数据结构

存放 key-value 数据的结构体 item

typedef struct _stritem {
    struct _stritem *next;    /* next item */
    struct _stritem *prev;      /* prev item */
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;   /* 引用计数,只要有线程操作该item就会++1 */
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;
        char end;
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

slabclass 是什么？

memcache 内存模型会对初始化申请的 (内存区域) 进行切分，会切分成不同大小的item区域，比如切分成三块区域 item-24Byte -> item-48Byte -> item-96Byte 这样在每个切分的区域，只保存对应大小的item、而slabclass数组就是记录每个item区域的使用情况即详情.

item 在对应大小的区域又是如何保存？

现在已经有对应大小的item区域了, 然后在该区域里面又会以 chunk 进行划分，默认每个chunk为1M，就是先有 slabclass 然后在每个 slabclass 指向区域划分chunk , 然后在chunk区域进行划分item
例如:
slabclass[1] -> chunk_1 -> [item-24Byte、item-24Byte、item-24Byte] chunk_2 -> [item-24Byte、item-24Byte、item-24Byte]

记录每个item区域使用情况的结构体 slabclass

#define MAX_NUMBER_OF_SLAB_CLASSES (63 + 1)   slabclass 数组大小 , 最多不超过 64 
static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES]; 

typedef struct {
    unsigned int size;      /* item区域大小 */
    
    unsigned int perslab;   /* 每个chunk下可以保存item数量 */

    void *slots;            /* 空闲的item */
    unsigned int sl_curr;   /* 空闲的item数量 */

    unsigned int slabs;     /* chunk指针数组数量 */
    
    void **slab_list;       /* chunk指针数组 */
    
    unsigned int list_size; /* 预申请chunk指针数组的数量 */

    size_t requested; /* The number of requested bytes */
} slabclass_t;

memcache 内存模型

memcache 内存模型

三个主要的配置参数：

• settings.maxbytes 存放数据内存大小默认64M
• settings.factor 增长因子 1.25
• preallocate 是否预申请内存

增长因子factor是什么?

因为 memcache 会对内存进行划分不同区域大小的块，但是会默认一个最小存放数据区域块大小 size = 80/Byte 而增长因子就是以最小区域块为基础，每次递增的倍数，但是最大递增不能超过 62 个且 size*factor < 1M，下面代码会有说明，就是保证我们最多有 62 个不同大小的内存区域块，每个区域块都是 factor 倍数，且最后一个区域块一定是 1M ， 所以我们可以根据实际使用情况来调节增长因子大小

例：
按照默认 1.25 进行增长，一共初始化 43 个区域，且每个区域之间都是 1.25 倍数，倒数第二个区域乘于 1.25 一定小于 1M ， 因为最后一个区域等于 1M，这也说明Memcache存放数据的最大为1M.

增长因子初始化内存区域大小

源码实现

(一) slabs_init 初始化内存

void slabs_init(const size_t limit, const double factor, const bool prealloc) {
    int i = POWER_SMALLEST - 1; //#define POWER_SMALLEST 1
    
    //最小数据块size
    //sizeof(item) 存放数据的结构体 = 32 
    //settings.chunk_size 默认存放物理数据大小 = 48
    //size = 48 + 32 = 80/Byte 
    unsigned int size = sizeof(item) + settings.chunk_size;
    
    //申请的内存总大小默认64M
    mem_limit = limit;
    
    //是否预申请一块内存区域,并直接指向该内存区域
    if (prealloc) {
        /* Allocate everything in a big chunk with malloc */
        mem_base = malloc(mem_limit);
        if (mem_base != NULL) {
            mem_current = mem_base;
            mem_avail = mem_limit;
        } else {
            //.......
        }
    }
    
    //slabclass数组置空
    memset(slabclass, 0, sizeof(slabclass));
    
    //按照 size * factor 填充 slabclass 数组 
    //不能超过 MAX_NUMBER_OF_SLAB_CLASSES - 1 &&  保证 size * factor 不能大于 settings.item_size_max
    while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1 && size <= settings.item_size_max / factor) {
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES) //8字节对其
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
        
        //每个slabclass组可存放item的大小
        slabclass[i].size = size;
        //每个chunk下可以保存item数量
        slabclass[i].perslab = settings.item_size_max / slabclass[i].size;
        //乘与增长因子继续填充
        size *= factor;
        //.....
    }

    //保存最后一个元素的索引位置
    power_largest = i;
    //保证slab组最后一个可存放的item大小为settings.item_size_max 也就是1M
    slabclass[power_largest].size = settings.item_size_max;
    slabclass[power_largest].perslab = 1;
    //.....
    
    //为测试提供的，模拟先占用多少内存
    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = (size_t)atol(t_initial_malloc);
        }
    }
    
    //如果是预申请则按照每个 slabclass[i].size 区域大小去划分
    //chunk_1 -> [item-24Byte、item-24Byte、item-24Byte]
    //chunk_1 -> [item-48Byte、item-48Byte、item-48Byte]
    if (prealloc) {
        slabs_preallocate(power_largest);
    }
}

(二) slabs_preallocate 对预申请的内存进行划分

static void slabs_preallocate (const unsigned int maxslabs) {
    int i;
    unsigned int prealloc = 0;

    //循环执行
    for (i = POWER_SMALLEST; i < MAX_NUMBER_OF_SLAB_CLASSES; i++) {
        // 判断是否超出当前slabclass最大索引
        if (++prealloc > maxslabs)
            return;
        //一个一个进行划分
        if (do_slabs_newslab(i) == 0) {
            fprintf(stderr, "Error while preallocating slab memory!\n"
               "If using -L or other prealloc options, max memory must be "
                "at least %d megabytes.\n", power_largest);
            exit(1);
        }
    }
}

(三) do_slabs_newslab 根据每个slabclass区域大小进行划分

static int do_slabs_newslab(const unsigned int id) {
    
    slabclass_t *p = &slabclass[id]; //根据索引取出slabclass
    slabclass_t *g = &slabclass[SLAB_GLOBAL_PAGE_POOL];
    
    // 获取待申请chunk大小，理论上每个 chunk <= 1M(1048576/Byte)
    // 但是有些情况 size * perslab 不会正好等于 1M 而是小于 1M
    // 那么我们按照1M申请就会有一些字节浪费掉.
    // 比如第一个slabclass的区域是 80/Byte 如果按每个chunk为1M 那么 perslab = 1M/80 = 13107/item 
    // 就是一个chunk里面会有13107个item , 但是 13107 * 80 = 1048560/Byte 小于 1M(1048576/Byte)
    // 所以这里的判断就是按照什么方式去申请这chunk空间，如果不想有字节浪费掉就   p->size * p->perslab
    
    int len = settings.slab_reassign ? settings.item_size_max
        : p->size * p->perslab;
        
    char *ptr;
    
    // 判断内存使用是否超过最大设定
    if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0
         && g->slabs == 0)) {
        mem_limit_reached = true;
       MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }
    
    // grow_slab_list 获取chunk指针数组，就是 void **slab_list 、 list_size
    // get_page_from_global_pool 忽略.
    // memory_allocate 申请一块 chunk 区域,并更新内存使用量
    if ((grow_slab_list(id) == 0) ||
        (((ptr = get_page_from_global_pool()) == NULL) &&
        ((ptr = memory_allocate((size_t)len)) == 0))) {

        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }
    
    // chunk指针初始化置空
    memset(ptr, 0, (size_t)len);
    
    // chunk区域有了，就在chunk中进行划分item
    split_slab_page_into_freelist(ptr, id);
    
    // 保存当前chunk的指针, 并更新 p->slabs++ 
    p->slab_list[p->slabs++] = ptr;
    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);

    return 1;
}

(四) grow_slab_list 获取chunk指针数组，不存在则创建，存在且空间不够则扩容

static int grow_slab_list (const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    // 判断当前 chunk指针数组索引 是否等于 list_size 如果等于就会进行扩容
    // 初始化情况会等于
    if (p->slabs == p->list_size) {
        // 默认 slab_list 数组大小 16 
        // 之后在扩充每次2的倍数进行扩容
        size_t new_size =  (p->list_size != 0) ? p->list_size * 2 : 16;
        void *new_list = realloc(p->slab_list, new_size * sizeof(void *));
        if (new_list == 0) return 0;
        // 预申请 chunk 指针数组的数量
        p->list_size = new_size;
        // 指向该数组
        p->slab_list = new_list;
    }
   return 1;
}

(五) memory_allocate 申请一块 chunk 区域 , 并更新内存使用量

static void *memory_allocate(size_t size) {
    void *ret;
    
    // 判断是否为预申请模式，如果不是则每次 malloc 申请 1M
    if (mem_base == NULL) {
        /* We are not using a preallocated large memory chunk */
       ret = malloc(size);
    } else {

        //当前内存使用位置
        ret = mem_current;
        
        // size 不能大于最大的mem_avail内存块
        if (size > mem_avail) {
            return NULL;
        }

        /* mem_current pointer _must_ be aligned!!! */
        if (size % CHUNK_ALIGN_BYTES) {
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
        }
        
        // 获取一块size大小内存,并更新内存使用位置
        mem_current = ((char*)mem_current) + size;
        
        // 更新一下mem_avail，就是还剩多少内存
        if (size < mem_avail) {
            mem_avail -= size;
        } else {
           mem_avail = 0;
       }
    }
    
    //更新一下内存使用量， 就是已使用了多少内存 
    mem_malloced += size;
    
    // 返回当前申请的内存，也就是 chunk 区域 
    return ret;
}

(六) split_slab_page_into_freelist 根据给定的 chunk区域指针 进行划分item

static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    int x;
    // 当前chunk区域共有多少 perslab 就是 item
    for (x = 0; x < p->perslab; x++) {
        // 一个一个进行划分
        do_slabs_free(ptr, 0, id);
        ptr += p->size;
    }
}

(七) do_slabs_free 划分item

static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;
    item *it;

    assert(id >= POWER_SMALLEST && id <= power_largest);
    if (id < POWER_SMALLEST || id > power_largest)
        return;

    MEMCACHED_SLABS_FREE(size, id, ptr);
    p = &slabclass[id];

    it = (item *)ptr; //强制转换成item结构体指针
    it->it_flags = ITEM_SLABBED; 
    it->slabs_clsid = 0;
    // 每一个item都已双向链表形式连接
    it->prev = 0;
    it->next = p->slots;
    if (it->next) it->next->prev = it;
    
    // slots 一直指向这个空闲item链表
    p->slots = it;
    
    // 更新一下当前可使用item数量
    p->sl_curr++;
    p->requested -= size;
    return;
}

结束

上面介绍的函数就是Memcache启动的时候，初始化内存所涉及到的所有核心函数实现