愛と勇気と缶ビール

ふしぎとぼくらはなにをしたらよいか

ぼくらのLRU

LRUにも色々あるよねーって話。ちなみにmemcachedとRedisのどっちがいいか的な話ではない。

memcachedのLRU

memcachedは起動時のオプション-mで最大何バイトまでmemcachedにメモリを食わせるかを指定することが出来て、この値を超えてmemcachedにデータをぶっ込もうとするとデータの追い出し(eviction)が発生します。どのデータが追い出されるかはいわゆるLRU(Least Recently Used)で、つまり最近使われていないデータが追い出されます。なので、「memcachedはLRUだよ」と言われると「ふーん」と分かったような気分になりますが、実はmemcachedのLRUはデータ全体におけるLRUではなくslab classごとのLRUなので、この辺を勘違いしていると痛い目に合います。

slab allocatorそのものについてはここでは説明しません。この辺の記事を読めばどういうものかは分かるかと。→ 第2回 memcachedのメモリストレージを理解する：memcachedを知り尽くす｜gihyo.jp … 技術評論社
以降、上の記事に準じて "slab class" "chunk" といった言葉を使います。

例えばmemcached -m 64 -p 11211 -vv のようにmemcachedを起動するとこんな風な出力が出ることもあり、memcachedが以下のようにメモリを確保するようなイメージを持っている人もいるのではないかと思います。

が、実際にはmemcachedは起動時に全てのメモリを確保してchunkに切り分けているわけではなく、データを入れた際にchunkが足りなければmallocする(-Lでpreallocateしている場合は一番最初にmallocしたでかい領域から切り出す)、という動作をするので、サービスを動かしてデータを入れていくと実際にはslab classごとのchunkは以下のようになります。

要は、サイズごとに偏りができます。よく使われるデータサイズに対応したslab classにはchunkが沢山割り当てられて、あまり使われないslab classについてはchunkはずーっと割り当てられないままになるからですね。

この状態でmemcachedの使える最大メモリまでに全然余裕があるならいいのですが、既にmax memory sizeに達してしまっている場合、新たに異なるサイズのデータをmemcachedに入れようとした時に困ったことになります。

memcachedのLRUがslab classごとであるということは既に書きましたが、当然データの追い出しもslab classごとに行われます。そのため、既に使える分のメモリを確保してしまった状態でchunkがちゃんと割り当てられていないslab classにデータを入れようとすると、memcachedは以下のような動作をします。

  1. データを入れるためのchunkがない...
  2. よし、お父さんmallocして新たなchunkを作っちゃうぞー
  3. あーもうmaxに達してんじゃん。だめだめー
  4. しょうがないから、既にあるchunkを再利用しよーっと（追い出し）

chunkが少ない所にデータを入れていくとこれが連続で発生するため、「データは一応入るけど一瞬で追い出されてしまう、なぜなんだぜ？」という悲しい状態になってしまいます。さっきまでの図で書くと以下のような感じ。

既に一杯割り当てられているslab classから持ってくればいいじゃねーか！と思う人もいるかもしれませんが、memcachedはデフォルトではそんな気の利いたことはしてくれないのです。新し目のmemcachedではautomoveという名前でそういうことをしてくれるっぽいですが、僕の会社のproductionのversionだと使えないので調べるのが面倒なのでこれについてはあまり真面目に調べていません。誰か調べて。automoveやmoveの機能がないmemcachedでchunkの再割当てをして欲しい場合、memcached自体を再起動してのちしかるべきサイズのデータを入れてあげるしかない、と思います。現状。

そんなわけで、memcachedに今まで入れたことのないサイズのデータを新たに入れる場合は注意が必要です。chunkの割り当て具合や追い出しの発生具合はmemcached-toolとかで見れるので、確認するといいでしょう。そもそも色々な種類のデータを混ぜずに細かく系統分けろや！って話かもしれません。これはmemcachedの挙動がどうというより運用の話ですね。

RedisのLRUというか追い出し戦略

最近だと「それは危険なほどのスピード」ということでRedisにセッション等を入れている人も多いかと思うので、じゃあRedisとかはどないなっとんねん、ということについても少し書きます。

…と思いましたが、Redisのmaxmemory-policy | Siguniang's Blog にスゲーいい感じでまとまっているのでここを読めば大体分かります。

要は全てのkey集合から追い出しの対象を選ぶか、volatileなkeyの集合(expireが指定されているkeyの集合)から選ぶかを選択できて、さらに削除のstrategyとしてLRUかTTLかRandomかを選べる、ってことですね。上の記事にあるようにLRUもTTLもランダム・サンプリングしたいくつかのkey（デフォルトは3つ）の中から適したものを選ぶ、という挙動になっているので、サンプリングの具合によっては比較的よく使われているkeyが消されたり、まだexpireまで時間のあるkeyが消されたりすることも当然あり得ると思います。

Redisは永続的なデータ（例えばsorted setで保持されたリアルタイムランキング）と非永続的なデータ（例えばhashで保持されたDBのデータのキャッシュ）の両方を扱うことを想定しているので、volatileなkeyのみから追い出し対象を選ぶことが出来るようになっているのでしょう。一つのRedisに基本消えてほしくないリアルタイムランキングのデータと別に消えても構わないキャッシュデータが載っている場合でも、後者のみが追い出されるような設定が可能になっています。が、現実にはこういう扱いの違うデータは混ぜこぜにせずにRedisの系統を分けた方がいいんじゃないかと思います。

結語

そんなわけで、LRUといっても実際の挙動はミドルウェアごとにまちまちだったりするので注意しましょう、みたいな。