@kyanny's blog

My thoughts, my life. Views/opinions are my own.

Redis の maxmemory-policy について

Redis をキャッシュストレージとして利用する場合、 maxmemory によって利用可能なメモリの最大値を指定できる。 maxmemory の値を超えるデータの追加が発生した場合の振る舞いを maxmemory-policy によって指定できる。デフォルトの maxmemory-policy は volatile-lru で、 LRU アルゴリズムに従って古いキーの値が優先的に破棄される。

maxmemory-policy は数種類から選べるが、そのうち

  • noeviction を選んだ場合、古いキーの値は破棄されず、新規追加はエラーとなる
  • allkeys-lru または allkeys-random を選んだ場合、 expire の有無に関わらず、全てのキーの中から破棄対象が選ばれる
  • その他を選んだ場合、 expire がセットされているキーのみが破棄対象となる

という違いがある。実装は redis.c の freeMemoryIfNeeded 関数で、テストコードは tests/unit/maxmemory.tcl にある (余談だが Redis のテストコードは Tcl で書かれていて、テスト時には実際に redis-server を起動しコマンドを発行するスタイルのようだ)

キャッシュストレージとして利用する場合、有効期限つきで古い順に消えていってくれると使い勝手が良い。有効期限をつけるには expire を設定すればよい。 そこで気になるのが「Redis は何をもってキーが古いとみなすのか?」という点だ。

maxmemory-policy のうち volatile-lruvolatile-ttl が、この「古い順に破棄する」という戦略だ。

  • volatile-lru は冒頭で触れたとおり LRU アルゴリズムを利用するので、最終アクセス時刻が古い順に破棄される
  • volatile-ttl は expire のタイムスタンプをみて、タイムスタンプがより過去のものから順に破棄される

どちらが良い悪いというものでもないが、個人的には expire で有効期限を指定するのならばそのタイムスタンプが古い順に消えていく volatile-ttl の振る舞いのほうが自然に感じられる。

さて、 volatile-ttl を選んだ場合でも、常にタイムスタンプの最も古いキーが削除されるわけではない。 ランダムに数個のキーを選びその中で最も古いものを削除対象として選ぶアルゴリズムになっているからだ。おそらく expire つきのすべてのキーのタイムスタンプを調べていると時間がかかるためだろう。 このサンプリングの回数を maxmemory-samples で指定できる (デフォルト値は 3) この数を大きくすれば、古いキーを選ぶ厳密さは増すが、パフォーマンスは落ちるだろう。

前置きが長くなったが、この振る舞いを確認したかったので簡単なプログラムを書いて実験を行った。 maxmemory-policy と maxmemory-samples の設定を変更しながら、意図的に maxmemory に収まらなくなるようにデータを追加していき、残っているキーを調べることで Redis が削除対象に選んだキーの傾向を調べた。なお、 LRU アルゴリズムによる古さの判定と expire のタイムスタンプによる古さの判定がかぶってしまうのを防ぐために、 LRU で古いものほど expire が長くなるように調整している。

https://gist.github.com/kyanny/5553300

結果は以下のようになった。

https://gist.github.com/kyanny/5553302

この実験で以下のことがわかった。

  • volatile-lru を選んだ場合、キーの先頭が a: に近いものほど古いと判定されるので、 z: ではじまるキーが多く残された
  • maxmemory-samples を大きな値にして実質全てのキーについて比較を行った場合、多少精度があがったが大きな違いは無かった
  • volatile-ttl を選んだ場合、キーの先頭が z: に近いものほど古いと判定されるので、 a: ではじまるキーが多く残されるはずだが、精度はまちまちだった
  • maxmemory-samples を大きな値にして実質すべてのキーについて比較を行った場合、著しい精度の向上が見られた

キーの数と maxmemory-samples の値の組み合わせによってパフォーマンスにどの程度影響が出るのかは調べていない。 要件によって許容できる速度低下はまちまちだろうし、 expire がより新しいキーが削除されてしまうことがどの程度まで許容できるのかも場合によりけりだろうから、 一概にどちらが良いとは言えないが、要求に最適な機能を提供できるように設定値ひとつでも上手に使い分けていきたいものだ。