memcached: Slab Allocator

僕の務める会社でも memcached はほとんどのサービスで利用されています。
今は業務も少ないので、ひまつぶしにmemcachedのコードを読んでいました。

Slab Allocatorの部分に興味を持ったので、それについてわかったことのメモ。
以下のサイトで事前知識を付けてからコードを読みました。
memcachedを知り尽くす：第2回　memcachedのメモリストレージを理解する

Slab Allocator : メモリの確保・管理を行うメカニズム

　・メモリアロケーションでオーバーヘッドの大きいmalloc()を極力呼ばない
　・一度アロケートしたメモリ領域を再利用してメモリフラグメンテーションを抑える

これらを実現するために以下のルールでメモリアロケーションを行っています。
　・memcachedの初期化時にmalloc()で大きな領域(slabと呼ばれる, デフォルトで1MB)を確保
　・あるslab classに属するslabは全て同一サイズのchunkで構成される
　・chunkサイズはslab classにより異なる
　・各slabはどのchunkが使われていないかを指すポインタを持っている
　・chunkは不要になったらfree()されるのではなく、再利用するためにchunkリストに戻される
　・もし利用可能なchunkがなくなった場合は、malloc()して新しいslabを作成する

Slab Allocatorの実装は slabs.h, slabs.c
　・ slabclass_t 構造体
chunkサイズやslabのリストを持っています。
これを見ると、chunkのことをコード上ではitemと呼んでいる模様。

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

static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

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

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

} slabclass_t;

static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

　・Slab Allocatorは固定数のslabclass_t配列を持ち、chunkサイズでソートされている
　・slabclass_t配列のインデックス番号はclsidと呼ばれ、これはslab classを識別するためのidになっている

Slab Allocatorのメインインタフェース

unsigned int slabs_clsid(const size_t size);
void *slabs_alloc(size_t size, unsigned int id);
void slabs_free(void *ptr, size_t size, unsigned int id);

unsigned int slabs_clsid(const size_t size);

void *slabs_alloc(size_t size, unsigned int id);

void slabs_free(void *ptr, size_t size, unsigned int id);

malloc()が実際にメモリ割り当てを行っているのに対して、
slab_alloc()はあらかじめ確保した領域から、最適なサイズのchunkを返しているだけです。
同様に、free()が実際にメモリ解放を行っているのに対して、
slab_free()はchunkをリスト(slabclass_tのslots)に戻しているだけです。

unsigned int clsid;
item *it;
clsid = slabs_clsid(item_size);  // item_sizeに応じてclsidを決める
it = slabs_alloc(item_size, clsid); // item_sizeとclsidをもとにchunkの割り当てを行う
slabs_free(it, item_size, clsid); // chunkをリストに戻す

unsigned int clsid;

item *it;

clsid = slabs_clsid(item_size); // item_sizeに応じてclsidを決める

it = slabs_alloc(item_size, clsid); // item_sizeとclsidをもとにchunkの割り当てを行う

slabs_free(it, item_size, clsid); // chunkをリストに戻す

このSlab Allocatorの仕組みは、Linuxカーネルでも使われているとのことです。
時間があれば続きを読んでいきたいと思います。

memcached: Slab Allocator

Slab Allocator : メモリの確保・管理を行うメカニズム

Slab Allocatorのメインインタフェース

あわせて読む:

コメントを残す