株式会社ミクシィ 研究開発グループの前坂です。前回の記事でmemcachedは分散に長けた高速なキャッシュサーバであることが紹介されました。今回はmemcachedの内部構造がどう実装されているのか、そしてメモリがどう管理されているのかをご紹介します。また、memcachedの内部構造の事情による弱点も紹介します。

メモリを整理して再利用するSlab Allocationメカニズム

昨今のmemcachedはデフォルトでSlab Allocatorというメカニズムを使ってメモリの確保・管理を行っています。このメカニズムが登場する以前のメモリ確保の戦略は、単純にすべてのレコードに対してmallocとfreeを行うといったものでした。しがしながら、このアプローチではメモリにフラグメンテーション（断片化）を発生させてしまい、OSのメモリマネージャに負荷をかけ、最悪の場合だとmemcachedのプロセスよりも重くなってしまうという問題が発覚しました。この問題を克服するために生まれたのがSlab Allocatorです。

Slab Allocatorの仕組みを見てみましょう。以下がmemcachedのドキュメントから引用したslab allocatorの目標です：

the primary goal of the slabs subsystem in memcached was to eliminate memory fragmentation issues totally by using fixed-size memory chunks coming from a few predetermined size classes.

つまりSlab Allocatorの基本は確保したメモリをあらかじめ決められたクラスサイズに応じた固定長の固まりに分けて、フラグメンテーション問題を完全に克服するということです。

Slab Allocationの仕組みは簡素で、確保したメモリをさまざまなサイズの固まり（chunk）に分けて、同じサイズの固まりをクラス（chunkの集合、またはchunkのサイズを定めるクラス）に整理します（図1⁠）⁠。

また、slab allocatorには「確保したメモリは再利用する」という目標もあります。したがって、memcachedは一度確保したメモリは解放せず、常にchunkを再利用します。

Slab Allocatorの主な用語

Page

デフォルトで1MB確保され、Slabに割り当てられるメモリ領域。Slabに割り当てられた後に、slabのサイズに応じたchunkに切り分けられる。

Chunk

レコードをキャッシュするためのメモリ領域。

Slab Class

特定のサイズのchunkをまとめるクラス。

Slabにレコードをキャッシュする仕組み

クライアントから送信されたデータを、memcachedはどのようにslabを選び、chunkにキャッシュするかを説明します。

memcachedは受けとったデータのサイズを参照し、データサイズにもっとも適したslabを選びます（図2⁠）⁠。memcachedはslab内の使用可能なchunkのフリーリストを保持しているので、このリストを基にchunkを選び、そこにキャッシュします。

ここまで紹介したSlab Allocatorですが、利点ばかりではなく弱点も存在します。次はその弱点を説明します。

Slab Allocatorの弱点

Slab Allocatorの開発により、当初の課題であったフラグメンテーション問題は解消されましたが、新たなメカニズムにより新しい課題がmemcachedに生まれました。

その問題は、固定長なメモリ確保のアプローチにより、確保したメモリを有効活用できないということです。例えば100バイトのデータを128バイトのchunkにキャッシュすると、余りの28バイトが無駄になります（図3⁠）⁠。

この問題に対する完全なソリューションは現状存在しませんが、ドキュメントに効率的なソリューションが記載されています：

The most efficient way to reduce the waste is to use a list of size classes that closely matches (if that's at all possible) common sizes of objects that the clients of this particular installation of memcached are likely to store.

つまり、クライアントが送ってくるデータの共通サイズがあらかじめ解っている、もしくは同じサイズのデータしかキャッシュしないユースケースであれば、そのサイズに適したクラスのリストを使い、無駄を抑えることが可能ということです。

ただし残念なことに、現状ではこのチューニングを行うことはできず、将来の課題として残っています。しかしながら、slab classたちのサイズ差をチューニングすることは可能なので、次にgrowth factorオプションについて説明します。

Growth Factorを使ったチューニング

memcachedはスタートアップ時にGrowth Factorという因子を指定して（-f オプション⁠）⁠、slab間のサイズをある程度制御することが可能です。デフォルト値は1.25ですが、このオプションが開発される以前は“⁠powers of 2⁠”戦略といって、2が固定でした。

では、実際に以前の設定でmemcachedをverboseモードで起動してみましょう：

$ memcached -f 2 -vv

以下がスタートアップ後のverbose出力です：

slab class   1: chunk size    128 perslab  8192
slab class   2: chunk size    256 perslab  4096
slab class   3: chunk size    512 perslab  2048
slab class   4: chunk size   1024 perslab  1024
slab class   5: chunk size   2048 perslab   512
slab class   6: chunk size   4096 perslab   256
slab class   7: chunk size   8192 perslab   128
slab class   8: chunk size  16384 perslab    64
slab class   9: chunk size  32768 perslab    32
slab class  10: chunk size  65536 perslab    16
slab class  11: chunk size 131072 perslab     8
slab class  12: chunk size 262144 perslab     4
slab class  13: chunk size 524288 perslab     2

ご覧の通り、128バイトのクラスから始まって、クラスのサイズが2倍づつ大きくなっています。この設定の問題は、slab間の差が比較的に大きいため、ユースケース次第で相当なメモリが無駄に消費されることです。そういった背景から問題をなるべく解消するためにgrowth factorオプションが2年前に追加されました。

では、現在のデフォルト設定（f = 1.25）の出力を見てみましょう（長いのでクラス10まで⁠）⁠：

slab class   1: chunk size     88 perslab 11915
slab class   2: chunk size    112 perslab  9362
slab class   3: chunk size    144 perslab  7281
slab class   4: chunk size    184 perslab  5698
slab class   5: chunk size    232 perslab  4519
slab class   6: chunk size    296 perslab  3542
slab class   7: chunk size    376 perslab  2788
slab class   8: chunk size    472 perslab  2221
slab class   9: chunk size    592 perslab  1771
slab class  10: chunk size    744 perslab  1409

ご覧の通り、クラスのサイズ差が因子を2で起動した場合より小さく、数百バイトのレコードをキャッシュするのにより適していることが解ります。また、この出力をみてサイズ計算に若干の誤差があると感じた方もいるかもしれませんが、この誤差は内部的にバイト数のアライメントを保つために故意に行われています。

memcachedをプロダクションに導入することを検討している、もしくは考えずにデフォルトでデプロイしている場合は、ぜひ一度、平均データサイズの予想値を計算して、growth factorのチューニングでそのユースケースで最適なセッティングを調べることをおすすめします。メモリは貴重なリソースなので、無駄に使うにはもったいないです。

次にmemcachedのstatsを使ってslabsの利用率や色々な情報を調べる方法を紹介します。

memcachedの内部状態を調べる

memcachedにはstatsというコマンドがあり、statsを発行することにより、さまざまな情報を取得することが可能です。コマンドの発行方法は色々ありますが、telnetがもっとも手軽だと思います：

$ telnet ホスト ポート番号

memcachedに繋がったら、statsと入力してenter keyを叩き、リソースの使用率を含めたさまざまな情報を取得します。そのほかにも“⁠stats slabs⁠”や“⁠stats items⁠”と入力するとslabやキャッシュされているレコードの情報が取得できます。終了したい時はquitと入力します。

これらのコマンドの詳しい内容は、memcachedのパッケージ内にあるprotocol.txtという仕様書に記載されています。

$ telnet localhost 11211
Trying ::1...
Connected to localhost.
Escape character is '^]'.
stats
STAT pid 481
STAT uptime 16574
STAT time 1213687612
STAT version 1.2.5
STAT pointer_size 32
STAT rusage_user 0.102297
STAT rusage_system 0.214317
STAT curr_items 0
STAT total_items 0
STAT bytes 0
STAT curr_connections 6
STAT total_connections 8
STAT connection_structures 7
STAT cmd_get 0
STAT cmd_set 0
STAT get_hits 0
STAT get_misses 0
STAT evictions 0
STAT bytes_read 20
STAT bytes_written 465
STAT limit_maxbytes 67108864
STAT threads 4
END
quit

また、libmemcachedというC／C++言語用のクライアントライブラリをシステムにインストールすると、memstatというプログラムも一緒にインストールされます。使い方が簡単で同じ情報をtelnetより少ない手順で取得できたり、複数のサーバから情報を取得できるというメリットがあります。

$ memstat --servers=server1,server2,server3,...

libmemcachedは以下のURLから入手できます：

• http://tangent.org/552/libmemcached.html

Slabsの使用状況を調べる

memcachedの生みの親であるBradが書いたmemcached-toolというPerlスクリプトを使うと、slabたちの使用状況を簡単に把握することが可能です（memcachedの返り値を読みやすく整形してくれます⁠）⁠。スクリプトは以下のURLから入手できます：

• http://code.sixapart.com/svn/memcached/trunk/server/scripts/memcached-tool

使い方も至って簡単で、以下のように使用します：

$ memcached-tool ホスト:ポート オプション

Slabsの使用状況を調べるにはオプションを指定する必要がありません。したがって使用状況は以下のように取得できます：

$ memcached-tool ホスト:ポート

取得した情報は以下のように出力されます：

 #  Item_Size   Max_age  1MB_pages Count   Full?
 1     104 B  1394292 s    1215 12249628    yes
 2     136 B  1456795 s      52  400919     yes
 3     176 B  1339587 s      33  196567     yes
 4     224 B  1360926 s     109  510221     yes
 5     280 B  1570071 s      49  183452     yes
 6     352 B  1592051 s      77  229197     yes
 7     440 B  1517732 s      66  157183     yes
 8     552 B  1460821 s      62  117697     yes
 9     696 B  1521917 s     143  215308     yes
10     872 B  1695035 s     205  246162     yes
11     1.1 kB 1681650 s     233  221968     yes
12     1.3 kB 1603363 s     241  183621     yes
13     1.7 kB 1634218 s      94   57197     yes
14     2.1 kB 1695038 s      75   36488     yes
15     2.6 kB 1747075 s      65   25203     yes
16     3.3 kB 1760661 s      78   24167     yes

カラムの意味は以下の通りです：

このスクリプトで習得できる情報は設定のチューニングにとても便利なので、おすすめです。

メモリストレージのまとめ

今回はmemcachedのキャッシュメカニズムやチューニングを簡単にご説明させていただきました。memcachedのメモリ管理の仕組みや、その仕組みの良いところや弱点をご理解いただけたかと思います。

次回は今回ご説明できなかったLRUやExpireなどの仕組みに加えて、memcachedの最新動向であるプラガブルアーキテクチャについて説明させていただきます。