Memcached源码解析--内存管理

小樱

        低版本的Memcached通过即时mallloc和free来实现内存分配和释放，这种方式会导致内存碎片，加重操作系统内存管理器的负担，最坏情况下会导致操作系统比Memcached进程本身还慢。为了解决该问题，Memcached采用Slab Allocator机制来管理内存。本系列文章以memcached-1.4.15为例，下载源码和查看相关信息可以点这里。
一、原理
        Slab Allocator的基本原理是按照预先规定的大小，将分配的内存分割为特定长度的块，以完全解决内存碎片问题。
        Memcached将分配的内存分割成各种大小的块（chunk），并把大小相同的块分成组（chunk的集合），如下图：

        

图1 Slab Allocator图

        Memcached分配的内存大小在启动时命令行参数指定，具体如下（Memcached安装见后面附注）：

图2 Slab Class数组定义信息图

        Memcached会重复利用已分配的内存，即分配的内存不释放而是重复利用。

二、流程
        在分析源码前，先对几个术语及关键数据结构进行介绍。
1、关键术语
        （1）Page
        向操作系统申请内存空间的最小单位，默认是1MB，Page分配给各个Slab Class之后根据规则被切分成特定尺寸的chunk。
        （2）Chunk
        用于缓存记录即item的内存空间，一个chunk存放一个item。
        （3）Slab Class
        特定大小的chunk的组，最大支持200组，且各slab class中，最大chunk尺寸默认为1MB（见图2中的slab class 42:chunk size 1048576）。一个slab class中是若干个slab（尺寸统一默认为1MB，除非用-I参数修改）。slabclass_t结构体的源码在slabs.c/26行：
        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_curr;   /* total free items in list */

    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 */
    size_t requested; /* The number of requested bytes */
} slabclass_t;

        （4）Item
        一条数据在Memcached中就是一个item，存放在一个chunk内。一个item结构体包含一个key+value和链表指针以及过期时间等管理信息，该结构体的源码在Memcached.h/327：
        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
" (no terminating null) */
    /* then data with terminating
(no terminating null; it's binary!) */
} item;

2、内存分配
        slabclass_t结构体中的size字段保存了
        在slabs.c/42行定义了如下静态数组：
        static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];
        该数组将所有slabclass_t串联起来，在slabs.c/slabs_init/115行会对所有slabclass_t进行初始化，图2中的信息正是这些初始化的信息。
        结构体slabclass_t中的size字段保存了每个slab所能保存的数据大小，而数组中每个slabclass_t的size字段都是递增的，递增的因子由slabs_init函数的第二个参数factor指定。比如：假设factor指定为2，那么如果第一个slabclass_t的size = sizeof(item) + settings.chunk_size;(slabs.c/slabs_init/115行)，那么数组中下一个slabclass_t的size就是 size*factor(这里忽略对齐的因素)。即假设factor为2且第一个slab能保存8byte的数据，那么数组中slab的size依次为16byte、32byte...。实际上，默认factor为1.25（Memcached.c/214），可以在启动memcached时根据需求由参数-f指定来调优（Memcached.c/4851）。
        Memcached根据收到数据的大小，选择最合适数据大小的slab，即slabclass数组中slabclass_t中字段size大于数据大小的最小尺寸的slab，Memcached中保存着slab内空闲chunk的列表，根据该列表选择chunk，然后将数据缓存与其中。例如：以前面那个slab模型为例，如果现在收到30byte，查找数组得到大于30byte的最小slab尺寸是32byte，于是就从这个slab中查找item分配给它。具体如下图：

图3 选择chunk存储item

        从上图可以看出，由于分配的是特定长度的内存，因此无法有效利用分配的内存，这里是将30byte的数据缓存到32字节的chunk中了，只是浪费了2byte，但是如果现在要分配的是16byte，那么就浪费了16byte，浪费了将近50%的内存，这是非常可耻的 。这时候前面提到的factor就可以大显身手了，使用者可以根据需要指定不同的增长factor以降低资源的浪费，这跟具体业务相关也很能考验架构师的能力。
        用Memcached的stats命令可以查看包括资源利用率在内的各种信息，具体如下：
        #telnet 主机名 端口号
        stats
        另外，如果安装了libmemcached这个C/C++客户端库，则可以使用memstat命令获取与telnet相同的信息，还能一次性从多台服务器获得信息，具体如下：
        #memstat --servers=server1, server2, server3, ...
        查看libmemcached的源码及相关资料可以点这里。
3、LRU机制
        Memcached采用LRU（即Least Recently Used）机制来淘汰最近最少使用的key。淘汰数据的规则是各层slab分别一个队列，刚放入的数据在对头，经常get的数据会移动到对头，从队尾淘汰，这样较老或者较少访问的数据会相对保留着队尾，淘汰/踢出数据时从队尾执行。所有最近使用的item保存在static item *tails[LARGEST_ID]（Item.c/40行）中，已经分配的内存以链表形式保存在这个数组中，如果对应的slab已经分配不到足够的内存了，就从这个链表中查找，淘汰的依据是item结构体中的exptime字段（Memcached.h/332行），具体流程如下图：

图4 LRU淘汰机制   

        Memcached过期采用Lazy Expiration技术，即Memcached内部不会监视记录是否过期，而是在get时查看记录的时间戳，检查记录是否过期，因此，Memcached不会在过期监视上耗费CPU时间。
        Memcached优先使用过期记录的内存，如果还是内存不够用，则会从最近未被使用的记录中搜索，并将其内存分配给新记录。但是如果通过参数-M关闭了LRU，则会在内存用尽时返回错误，具体如下：
        #memcached -M -m 1024
        如上则禁用LRU，并用-m限定最大内存大小，不指定时则默认是64M。
三、附注
        Memcached的安装非常简单，以Centos为例：
        #yum install libevent libevent-devel
        #yum install memcached
        这样Memcached的最新稳定版默认就会安装到/use/bin下。
        从终端执行如下命令即可启动Memcached：
        #memcached -u root -p 11211 -m 64m -vv
        Memcached有很多参数可以输入以完成一些特定功能，比如-d指定Memcached在后台启动。这些启动选项的详细帮助可以通过如下命令获取：
        #memcached -h

        需要注意的是：图2显示了slab class数组的全景信息，但未实际分配内存，也就是虽然在启动Memcached的时候使用参数-m指定了最大可用内存，但是默认情况下并不是启动就分配内存，而是按需分配即：
        （1）按需向操作系统申请内存，根据item长度在对应slab class分配page；
        （2）即使配置的内存用完，每个slab class也可以申请一个page。
        （3）Memcached启动时指定的内存是用于保存数据的量，不包括slab allocator本身占用的内存以及为保存数据而设置的管理空间，因此，Memcached实际占用内存要比指定的容量大。

liuda

不明觉厉

小樱

liuda 发表于 2014/5/25 00:12
不明觉厉

我会说是转来的么

manager

不明觉厉