理解 Memcached 源码- Slab I

Slab分配器是这个缓存系统的核心，并在很大程度上决定了核心资源 - 内存 - 的利用效率。其它的三个部分，用来淘汰（超时）对象的LRU算法；和基于libevent的事件驱动；以及用于分布数据的一致性哈希，可以看作是围绕Slab来开发的。

在其他系统，比如内核，都能看到 Slab 分配器 的身影。无论它出现在哪里，都是为了对抗同一个性能问题，内存碎片。而本文就主要讨论 Slab 分配器 在memcached 中的实现（废话）。

memcached version: 1.4.28

首先我们来回答一些问题。

前言

啥是Slab

Slab翻译过来就是（一块）板，具体来说，它是是被预先分配好的，大小为1M的内存块。这些 板 可以被进一步分割成一些相同大小的 块 (chunk)，对象就存写在每一个 块 上面。所有的 板 会根据所存储对象的大小分成 板组（slab class）。

刚刚提到的内存碎片是啥

具体来说，板分配器 解决的其实是 内在碎片 （internal memory fragmentation）。这种碎片存在于分配的内存单元的内部。拿内核来说，内存的分配单元叫页（page），所有的内存分配的请求本质上都是在页里面拿走一块，同时产生的碎片也就自然产生于每页的内部了。

和内在碎片不一样，外在碎片（external memory fragmentation）则存在于分配的内存单元之间。解决外在碎片的一般做法则是用buddy，就不在本文范围内了。

我们再看下制造内存碎片过程，

1）malloc一堆小对象，

2）随机free一些上述小对象。

于是本来是整片的内存就会出现很多空洞，这些空洞，或者说碎片，因为太小而且分散，大概率永远无法被后续的malloc利用。

内存碎片引起的问题

继续往后说。这些碎片由于不能被 malloc 使用，基本也就和 内存泄漏 差不多了。引发的具体问题也差不多 - 定期重启。

怎么办

板分配器 并不消除内存碎片，而是将它们收敛起来，并锁定在某个固定的内存区域。具体来说，1）将大小相近的对象分组；2）同一组的的对象只会用对应的板组（slab class）来分配内存。

接下来看代码。

reminder: memcached version is 1.4.28

核心数据结构：

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 */

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

static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

slabclass_t@slabs.c

模块初始化

本节我们来看slabs_init，和 slabclass[MAX_NUMBER_OF_SLAB_CLASSES] 的初始化。 这个函数主要给 slabclass_t.size ，和 slabclass_t.perslab 赋值。第一个域表示 Slab 组 所对应的对象大小，第二个域则表示一个 Slab 上可以放多少个该类的对象。最后，slabs_init 是在系统初始化的过程被调用（如以下代码），

...
    assoc_init(settings.hashpower_init);
    conn_init();
    slabs_init(settings.maxbytes, settings.factor, preallocate,
               use_slab_sizes ? slab_sizes : NULL);
...

main@memcached.c:5977

在这个阶段，slab_sizes 和 settings.factor 共同决定了后续逻辑的走向，并且确定各个 板组 所存储的对象大小，

uint32_t slab_sizes[MAX_NUMBER_OF_SLAB_CLASSES];

main@memcached.c:5372

settings.factor = 1.25;

settings_init@memcached.c:217

如果 slab_sizes 不是 NULL, 用此数组的里面的值直接初始化各 板组 所对应的对象大小（支线a）；

反之，则用base size×n×settings.factor 来初始化上述的目标。这里 n 是 slabclass 的下标（支线b）。

除了写死的默认值，上述两个变量也能用 命令行参数赋值 。

...
        case 'f':
            settings.factor = atof(optarg);
            if (settings.factor <= 1.0) {
                fprintf(stderr, "Factor must be greater than 1\n");
                return 1;
            }
            break;
...
        case 'o': /* It's sub-opts time! */
...
            case SLAB_SIZES:
                if (_parse_slab_sizes(subopts_value, slab_sizes)) {
                    use_slab_sizes = true;
                } else {
                    return 1;
                }
            break;
...

main@memcached.c:5558, 5810

本函数的另外两个参数 settings.maxbytes 和 preallocate ，会在 后续 讨论。这里我们假设 preallocate 为 false，并忽略其对应的逻辑。

下面我们来看 slabs_init 本身。

void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes) {
    int i = POWER_SMALLEST /* scr: 1 */ - 1;
    unsigned int size = sizeof(item) + settings.chunk_size; // scr: ---------> b 1)
...
    memset(slabclass, 0, sizeof(slabclass));

    while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1) {
        if (slab_sizes != NULL) { // scr: -----------------------------------> a 1)
            if (slab_sizes[i-1] == 0)
                break;
            size = slab_sizes[i-1];
        } else if (size >= settings.item_size_max / factor) {
            break;
        }
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES) // scr: ---------------------------------> 2)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

        slabclass[i].size = size;
        slabclass[i].perslab = settings.item_size_max / slabclass[i].size; // -> 3)
        if (slab_sizes == NULL)
            size *= factor; // scr: -----------------------------------------> b 4)
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }
    // scr: -------------------------------------------------------------------> 5)
    power_largest = i;
    slabclass[power_largest].size = settings.item_size_max;
    slabclass[power_largest].perslab = 1;
...
}

slabs_init@slabs.c

支线 a

1) 使用 slab_sizes 里面的值；

2) 将 size 用 CHUNK_ALIGN_BYTES 对其，并赋值给 slabclass[i].size；

3) 计算 slabclass[i].perslab;

5) 用 settings.item_size_max 初始化最后一个 板组。

这里要注意 settings.item_size_max 是 slab 本身的大小，也即是 memcached 能存的最大对象。类似的，settings.item_size_max 也可以在 运行时 确定

settings.item_size_max = 1024 * 1024;

settings_init@memcached.c:226

case 'I':
    buf = strdup(optarg);
    unit = buf[strlen(buf)-1];
    if (unit == 'k' || unit == 'm' ||
        unit == 'K' || unit == 'M') {
        buf[strlen(buf)-1] = '\0';
        size_max = atoi(buf);
        if (unit == 'k' || unit == 'K')
            size_max *= 1024;
        if (unit == 'm' || unit == 'M')
            size_max *= 1024 * 1024;
        settings.item_size_max = size_max;
    } else {
        settings.item_size_max = atoi(buf);
    }
    free(buf);
    if (settings.item_size_max < 1024) {
        fprintf(stderr, "Item max size cannot be less than 1024 bytes.\n");
        return 1;
    }
    if (settings.item_size_max > 1024 * 1024 * 128) {
        fprintf(stderr, "Cannot set item size limit higher than 128 mb.\n");
        return 1;
    }
    if (settings.item_size_max > 1024 * 1024) {
        fprintf(stderr, "WARNING: Setting item max size above 1MB is not"
            " recommended!\n"
            " Raising this limit increases the minimum memory requirements\n"
            " and will decrease your memory efficiency.\n"
        );
    }
    break;

main@memcached.c:5626

支线 b

1) 用 settings.chunk_size 加上给每个对象附着的元数据（meta data）来计算基础大小（对象 item 会在后面讨论）；

2) 将 size 用 CHUNK_ALIGN_BYTES 对其，并赋值给 slabclass[i].size（同支线a）；

3) 计算 slabclass[i].perslab（同支线a）；

4) 用 factor(settings.factor) 计算下一个 板组 的大小；

5) 用 settings.item_size_max 初始化最后一个 板组。

引用

memcached wiki

第2回　memcachedのメモリストレージを理解する

Memcached源码分析之存储机制Slabs（7）

Understanding Malloc

Ch8 - Slab Allocator

The Slab Allocator:An Object-Caching Kernel Memory Allocator