转载：Memcached源码分析之内存管理（1.2）

memcached-1.2.8版本

http://kenby.iteye.com/blog/1423989

Memcached源码分析之内存管理篇

使用命令 set(key, value) 向 memcached 插入一条数据, memcached 内部是如何组织数据呢

一 把数据组装成 item

memcached 接受到客户端的数据后, 把数据组装成 item, item 的格式如下:

 
   图1 struct item 的结构

源码中这样定义 struct item:

/**
 * Structure for storing items within memcached.
 */
typedef struct _stritem {
    struct _stritem *next;
    struct _stritem *prev;
    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;
    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 */
} item;

从源码可以得出 item 的结构分两部分, 第一部分定义 item 结构的属性, 包括连接其它 item 的指针 (next, prev), 还有最近访问时间(time), 过期的时间(exptime), 以及数据部分的大小, 标志位, key的长度, 引用次数, 以及 item 是从哪个 slabclass 分配而来. 

item 结构体的定义使用了一个常用的技巧: 定义空数组 data, 用来指向 item 数据部分的首地址, 使用空数组的好处是 data 指针本身不占用任何存储空间, 为 item 分配存储空间后, data 自然而然就指向数据部分的首地址. 

第二部分是 item 的数据, 由 CAS, key, suffix, value 组成.

二 为 item 分配存储空间

把数据组装成 item 之前, 必须为 item 分配存储空间, memcached 不是直接从操作系统分配内存的, memcached 内部使用了类似内存池的东西, 即slab机制, 来管理内存. 内存的分配和回收都交给 slab 子系统实现. 所以我们先理解slab, 再回过头来看如何为 item 分配存储空间.

三 使用 slab 管理内存

memcached 中, 内存的分配和回收, 都是通过 slab 实现的, slab机制相当于内存池机制, 实现从操作系统分配一大块内存, 然后 memcached 自己管理这块内存, 负责分配与回收. 接下来我们详细剖析 slab 机制.

3.1 关于 slabclass

像一般的内存池一样,  从操作系统分配到一大块内存后, 为了方便管理, 把这大块内存划分为各种大小的 chunk,chunk的大小按照一定比例逐渐递增, 如下图所示:

  图2: 各个 slabclass 的 chunk size 按比例递增

从 slab 分配内存的时候, 根据请求内存块的大小, 找到大小最合适的 chunk 所在的 slabclass, 然后从这个slabclass 找空闲的 chunk 分配出去. 所谓最合适就是指 chunk 的大小能够满足要求, 而且碎片最小. 如下图所示:

图3 寻找最合适的 slabclass

这种分配方式的缺点是存在内存碎片, 例如, 将 100字节的 item 存储到一个 128 字节的 chunk, 就有 28 字节的内存浪费, 如下图所示:

图5 内存碎片

3.2 slabclass 的内部实现

slabclass 是由 chunk size 确定的, 同一个 slabclass 内的 chunk 大小都一样,  每一个 slabclass 要负责管理一些内存, 初始时, 系统为每个 slabclass 分配一个 slab, 一个 slab 就是一个内存块,  其大小等于 1M.  然后每个slabclass 再把 slab 切分成一个个 chunk, 算一下, 一个 slab 可以切分得到 1M/chunk_size 个chunk. 

先来看一下源码中 slabclass 的定义:

typedef struct {
//item大小
    unsigned int size; /* sizes of items */
//每个slab中有多少个item
    unsigned int perslab; /* how many items per slab */

//是一个指针数组
//用于存储空闲的item
    void **slots; /* list of item ptrs */
//slots数组的最大长度
    unsigned int sl_total; /* size of previous array */
//slots数组当前的长度。当前有多少个空闲的item
    unsigned int sl_curr; /* first free slot */

//指向一个空闲的slab中第一个空闲的item
    void *end_page_ptr; /* pointer to next free item at end of page, or 0 */
//当前空间的item个数
    unsigned int end_page_free; /* number of items remaining at end of last alloced page */

//申请了多少个slab
    unsigned int slabs; /* how many slabs were allocated for this class */

//指向已经分配的内存
    void **slab_list; /* array of slab pointers */
//slab_list数组的当前下标值
    unsigned int list_size; /* size of prev array */

    unsigned int killing; /* index+1 of dying slab, or zero if none */
} slabclass_t;

slabclass 的结构图如下所示:

图6 slabclass 结构图

 结合 slabclass 的结构图, 我们说明一下 slabclass 结构体的各个属性:

(1) size 和 perslab

size 定义该 slabclass 的 chunk 大小, perslab 表示每个 slab 可以切分成多少个 chunk, 如果一个 slab 等于1M, 那么就有 perslab = 1M / size

(2) slots 和 sl_curr

slots 是回收的 item 链表, 从某个 slabclass 分配出去一个 item, 当 item 回收的时候, 不是把这 item 使用的内存交还给 slab, 而是让这个 item 挂在 slots 链表的尾部. sl_curr 表示当前链表中有多少个回收而来的空闲 item.

(3) slab_list 和 list_size

前面说过, 初始时, memcached 为每个 slabclass 分配一个 slab, 当这个 slab 内存块使用完后, memcached 就分配一个新的 slab, 所以 slabclass 可以拥有多个 slab, 这些 slab 就是通过 slab_list 数组来管理的, list_size表示当前 slabclass 有多少个 slab.

(4) end_page_ptr 和 end_page_free

在 subclass 内, 只有最后一个 slab 存在空闲的内存, 其它 slab 的 chunk 都分配出去了, end_page_ptr指向最后一个 slab 中的空闲内存块, end_page_free 表示最后一个 slab 中还剩下多少个空闲 chunk.  图6中绿色部分的 chunk 表示空闲 chunk

(5) static item *heads[LARGEST_ID];

    static item *tails[LARGEST_ID];

 当 memcached 没有足够的内存使用时, 必须选择性地回收一些 item, 回收采用 LRU 算法, 这就需要维护一个按照最近访问时间排序的 LRU 队列. 在 memcached 中,每个 slabclass 维护一个链表, 比如 slabclass[i] 的链表头指针为 heads[i], 尾指针为 tails[i],已分配出去的 item 都存储在链表中. 而且链表中 item 按照最近访问时间排序, 这样一些链表相当于LRU 队列.