memcachedとRedisの生存戦略、というかmemory allocation戦略

ちょっとmemcached & Redisについて調べたのでめも。

ちなみに、生存戦略って言葉は最近Twitterでよく見るから使ってみただけで、実際に何かは知りません。歌か何かかな。

ちなみに見ているソースについては、memcachedは1.4.6、Redisは現時点でのgitの最新(多分)。

memcachedに関して、特定のサイズのchunkを管理するslab classっていうものがあるよーん、とかは説明するとめんどくさいので飛ばします。↓の記事とかに書いてあります。

http://gihyo.jp/dev/feature/01/memcached/0002?page=1

memcached

起動時の-Lオプションが付いてる場合、初めに全部mallocしちゃう。付いていない && DONT_PREALLOC_SLABSがdefineされている場合はchunkのpreallocateが行われず、defineされていない場合はchunkのpreallocateが行われる。

突然chunkのpreallocateとか言われてもよく分からんと思うのでmemcachedの起動時から追っていくと、まずmemcached.cの4764行目のslabs_initでslab allocatorの初期化が行われる。

    slabs_init(settings.maxbytes, settings.factor, preallocate);

setttings.maxbytesは-mオプションで渡された数値に1024*1024を乗じてMBに直したもの、settings.factorは各slab classにおけるchunkのサイズを大きくしていく比率(デフォルトで1.25倍のアレ)、preallocateは-Lオプションの有無(まぎわらしいけどchunkのpreallocateとは別)。起動オプションのデフォルト値についてはまとめてmemcached.cの192〜214行目あたりに書いてあり、分り易い。

static void settings_init(void) {
    settings.use_cas = true;
    settings.access = 0700;
    settings.port = 11211;
    settings.udpport = 11211;
    /* By default this string should be NULL for getaddrinfo() */
    settings.inter = NULL;
    settings.maxbytes = 64 * 1024 * 1024; /* default is 64MB */
    settings.maxconns = 1024;         /* to limit connections-related memory to about 5MB */
    settings.verbose = 0;
    settings.oldest_live = 0;
    settings.evict_to_free = 1;       /* push old items out of cache when memory runs out */
    settings.socketpath = NULL;       /* by default, not using a unix socket */
    settings.factor = 1.25;
    settings.chunk_size = 48;         /* space for a modest key and value */
    settings.num_threads = 4;         /* N workers */
    settings.num_threads_per_udp = 0;
    settings.prefix_delimiter = ':';
    settings.detail_enabled = 0;
    settings.reqs_per_event = 20;
    settings.backlog = 1024;
    settings.binding_protocol = negotiating_prot;
    settings.item_size_max = 1024 * 1024; /* The famous 1MB upper limit. */
}

slabs_initの中身はだいたいこんな感じになっていて

if (prealloc) {
  // 引数で渡されたmax_bytesをここで一気にmalloc
}
while() {
  // POWER_SMALLEST (=0) .. POWER_LARGEST (=200) までslab classを初期化。現在処理しているslab classにおけるchunk sizeが item_size_max (=1MB, -Iオプションで変化) ÷ factor(=1.25) になると終了。chunk sizeは1.25倍されていく。
}

 // 最後の一つのslab classを初期化。このslab classではperslab(slub classにおけるchunkの数) = 1となり、chunk size = item_size_maxとなる。デフォルト設定で-vvつけて起動すると一番下に出てくるslab classがこれ。

#ifndef DONT_PREALLOC_SLABS
 // 初期化された各slab classにおけるchunkのpreallocate処理
 // デフォルトではこの処理は#define DONT_PREALLOC_SLABSによってOFFになっているが、ONでも別に構わない気がする。何か問題があるのだろうか。
#endif

whileで最後のひとつ前まで処理して、その後最後のやつを初期化、という部分以外はストレートな処理。slab classの数は、chunk_sizeの初期値とitem_size_maxとfactorで決まるのが分かる。

chunkのpreallocate処理は、初期化したslab classのみについて行われ、中身は順にdo_slab_newslabを呼んでいるだけ。

do_slab_newslabは、境界チェックやらポインタ設定やらの処理を除くとほとんどmemory_allocateを呼んでいるだけ。

一番low levelな処理となるmemory_allocateは、

if (初めに全mallocしてない) {
  malloc
}
else
  全mallocした領域から切り出して返す
}

というだけの処理。memcachedでは、実行時のmemory割り当て関数(do_slabs_alloc)も間接的にこのmemory_allocateをコールしている。つまり、memcachedのmemory allocationは -L があれば最初から持っている巨大なカタマリから全て行われ、-Lがない場合はもろもろの条件判定をして足りなくなった場合にmalloc、という戦略になっている。再利用とかについてはもうちょっと詳しく読んでもいいけど、大枠が分かったので省略。

Redis

redis.cの901行目、関数initServerの中にzmalloc(sizeof(redisDb) + server.dbnum)という記述があるのでその辺から追う。server.dbnumのデフォルト値は16(redis.h)。

redisDbの定義もredis.hにある。redisDbはdict4つとint型の値からなる構造体で、dict型は…と追ってもいいけどやめてzmallocを見る。見た感じ、Redis内部のmemory allocationはzmallocが握っているよう。中二病っぽい名前だ。

zmalloc.hには以下のような宣言がある。

void *zmalloc(size_t size);
void *zcalloc(size_t size);
void *zrealloc(void *ptr, size_t size);
void zfree(void *ptr);
char *zstrdup(const char *s);
size_t zmalloc_used_memory(void);
void zmalloc_enable_thread_safeness(void);
float zmalloc_get_fragmentation_ratio(void);
size_t zmalloc_get_rss(void);

いかにもってカンジ。

zmalloc.cの96行目、mallocの代わりに使われるぽいzmalloc関数を見ると一行目でさっそく生のmallocを渡されたsize + PREFIX_SIZEで呼んでいる。なんだかダマされた気分。

zmallocの中には#ifdefによる分岐があり、HAVE_MALLOC_SIZEがdefineされている場合はzmalloc_sizeというマクロを使って実際にallocateされたメモリサイズを取り、そうでない場合はmallocに自分が渡したサイズをもって「allocateされたサイズ」とするようだ。どうもPREFIX_SIZEはHAVE_MALLOC_SIZEがあるときは0になっているところからみて、なんしかallocateされたサイズを計算するためのモノらしい。

HAVE_MALLOC_SIZEが定義されるのは、mallocの実装としてjemallocが使われているか、あるいはプラットフォームがMac OS Xのとき。おそらくjemalloc優先。ちなみにjemallocは、Facebookが開発したmalloc実装 (http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919)、だったはず。

取ったサイズを何に使っているかというと、これは単にused_memoryという変数に足し込んでいるだけ。この変数はzmalloc_used_memoryやらzmalloc_get_rssという関数で使われる。

zmallocの目的は、memcachedのような独自メモリ管理とかではなくて、今までmallocされた領域のサイズをできるだけ正確に保持してRedis側からそれが見れるようにしておきたい、それだけらしい。zmallocはそのためのmallocの薄いラッパーで、何ら壮大なことはやっていない。

jemallocを使える場合のifdefやらが書いてあること、mallocを都度そのまま使っていることから、Redisはどうも下層のmalloc実装が賢いことを期待してmemory allocationを行っているように見える。