Redis を LRU キャッシュとして使う

Redis をキャッシュとして使う際、新しいデータを追加するときに自動的に古いデータを追い出すようにできると便利です。この振る舞いは、人気の高い memcached システムのデフォルトの振る舞いであるため、開発者の間では非常によく知られています。

LRU は、実際にはエビクション・メソッドのひとつにすぎません。このページでは Redis のメモリ使用量を制限するための ‘maxmemory’ ディレクティブについて、より一般的なトピックを扱います。また、Redis で使用されている LRU アルゴリズムについても扱います。Redis の LRU アルゴリズムは、実際には正確な LRU ではなく、その近似です。

メモリ設定のためのディレクティブ

‘maxmemory’ ディレクティブは、データセットに対して指定された量のメモリを使用するように、 Redis を設定するために使います。この値を設定するには、’redis.conf’ ファイルに書くか、または実行時に CONFIG SET コマンドを使っても指定できます。

たとえばメモリの制限を 100 MB に設定するためには、以下のディレクティブを ‘redis.conf’ ファイルに書きます。

maxmemory 100mb

‘maxmemory’ に 0 を指定すると、使用メモリに制限をかけない、という意味になります。これは 64 bit システムではデフォルトの振る舞いですが、32 bit システムでは暗黙的に 3GB の制限がかかります。

指定されたメモリ使用量に達した場合、 ポリシー と呼ばれるいくつかの異なる振る舞いのなかから、ひとつを選択することができます。Redis は、追加のメモリを必要とするコマンドに対して単純にエラーを返すことも、新しいデータが追加される度に古いデータを消去し、指定された制限を超えないようにすることも可能です。

エビクション・ポリシー

‘maxmemory’ に達したときの Redis の正確な振る舞いは、’maxmemory-policy’ 設定ディレティブに従います。

以下のポリシーが選択できます:

  • noeviction : メモリ使用量が制限に達しており、クライアントが追加のメモリを要求するコマンド(DEL やいくつかの例外を除く、ほとんどの書き込みコマンド)を実行しようとした場合はエラーを返す。

  • allkeys-lru : 新しいデータのためにスペースを空けるため、もっとも最近使われていない(LRU)キーから削除するよう試みる。

  • volatile-lru : 新しいデータのためにスペースを空けるため、もっとも最近使われていない(LRU)キーから削除するよう試みる。ただし、 expire set が指定されたキーのみを対象とする。

  • volatile-random : 新しいデータのためにスペースを空けるため、ランダムなキーを選んで削除する。ただし、 expire set が指定されたキーのみを対象とする。

  • volatile-random : 新しいデータのためにスペースを空けるため、ランダムなキーを選んで削除する。ただし、 expire set が指定されたキーのみを対象とする。

  • volatile-random : 新しいデータのためにスペースを空けるため、ランダムなキーを選んで削除する。ただし、 expire set が指定されたキーのみを対象とする。

volatile-lru, volatile-random, volatile-ttl ポリシーは、前提条件にマッチするキーが存在しない場合、 noeviction と同じ振る舞いをします。

アプリケーションのアクセスパターンによって、適切なエビクション・ポリシーを選択することは重要です。アプリケーションを稼働させながら、実行時にポリシーを再設定することも可能です。また、設定のチューニングのため、 INFO コマンドの出力からキャッシュミスやヒット数を監視することができます。

一般的な経験則:

  • リクエストの大半がべき乗分布に従う、つまり、全体のあるサブセットがその他よりもより頻繁にアクセスされる、と期待できる場合は、 allkeys-lru を使う。 これは、アクセスパターンが不確かな場合にも良い選択といえる。

  • すべてのキーが継続的にスキャンされるような、周期的なアクセスがある場合、またはアクセスが平均的に分布している(すべてのキーが同じ確率でアクセスされる可能性がある)と期待される場合は、 allkeys-random を使う。

  • Redis に、有効期限切れとするべき候補を選ぶためのヒントを与えたい場合は、 volatile-ttl を使う。キャッシュオブジェクトを生成するときに、異なる TTL を指定する。

allkeys-lruvolatile-random ポリシーは、ひとつのインスタンスを、キャッシュ用途と一部キーの永続化用途の、両方の目的で使用する際に有用です。しかし、このような問題に対しては 2 つの Redis インスタンスを使うほうが良い考えでしょう。

キーの有効期限を指定するとメモリを消費する、という点に触れておくことには価値があります。 メモリが逼迫している環境では、 allkeys-lru のようなポリシーを使用すると、除去対象キーに有効期限を設定しなくても良いため、よりメモリ効率が良くなります。

エビクション処理の仕組み

エビクション処理が以下のように働くことを理解しておくことは大事です:

  • クライアントが、データを追加する新規コマンドを発行する

  • Redis はメモリ使用量をチェックし、もし ‘maxmemory’ 制限を超えていたら、ポリシーに従ってキーを除去する

  • 新規コマンドが実行される

このようにして、メモリ制限をチェックし、キーを削除して制限以下まで引き戻す、という操作により、引き続きメモリ制限の境界線上に留まり続けることになります。

もし、あるコマンドが多くのメモリを消費する場合 (たとえば、大きな共通集合操作の結果を新しいキーにセットする) は、しばしば、メモリ使用量が制限を大きく上回ることがあるでしょう。

近似的な LRU アルゴリズム

Redis の LRU アルゴリズムは正確な実装ではありません。Redis は除去されるべき 最良の候補, すなわち最も過去にアクセスされた候補, を選択することはできない、ということです。代わりに、Redis は少数のキーのサンプリングを行い、その中でもっとも古いアクセス時刻をもつものを除去することで、 LRU アルゴリズムの近似を試みます。

しかし、Redis 3.0 (現在 beta ステータス) では、除去に適した候補のプールをもつことで、アルゴリズムが改善されています。これはアルゴリズムの性能を向上させ、より本物の LRU アルゴリズムに近づけます。

Redis の LRU アルゴリズムで重要なことは、毎回の除去の際にチェックするサンプル数を変更することにより、アルゴリズムの精度を チューニング可能 ということです。

maxmemory-samples 5

Redis が正確な LRU の実装を使わない理由は、それが多くのメモリを消費するためです。しかし、Redis を使うアプリケーションから見れば、この近似は実際上、本物と同等のものです。下図は、Redis で使用される LRU の近似と、本物の LRU とを視覚的に比較したものです。

LRU comparison

LRU comparison

上記のグラフを生成するため、Redis サーバーをある特定の数のキーでいっぱいにしました。キーは最初から最後まで順にアクセスされており、LRU アルゴリズムによると最初のキーが最良の除去候補になります。その後、半数の古いキーを除去するため、さらに 50% のキーを追加しています。

グラフ中の 3 種類の点は、 3 つの異なる部分を表します。

  • ライトグレーの部分は、除去されたオブジェクトを表します。

  • グレーの部分は、除去されなかったオブジェクトを表します。

  • 緑の部分は、追加されたオブジェクトを表します。

理論的な LRU の実装においては、古いキーのうちの最初の半分が除去されることが期待されます。Redis の LRU アルゴリズムはその代わりに、 確率的に 古いキーを除去します。

Redis 3.0 は、5 サンプルを使う場合に 2.8 よりも良い結果を出していますが、2.8 においても、最近アクセスされたキーのうちのほとんどは除去されずに残っています。Redis 3.0 でサンプルサイズを 10 個にすると、近似は理論上の性能に非常に近くなります。

LRU は、あるキーが将来アクセスされる可能性を予測する、ひとつのモデルにすぎないことに注意してください。加えて、もしあなたのデータアクセスパターンがべき乗則に近いなら、近似 LRU アルゴリズムは大半のアクセスに対してうまく働くでしょう。

べき乗則に従うアクセスパターンにおけるシミュレーションにおいては、本物の LRU アルゴリズムと Redis の近似的なアルゴリズムの差異は小さいか、まったく存在しないことが観察されています。

しかし、より正確に LRU を近似するために、いくらか追加の CPU コストと引き換えにサンプルサイズを 10 に引き上げることも可能です。それがキャッシュミス率に影響を及ぼすか、確認してみてください。

プロダクション環境で ‘CONFIG SET maxmemory-samples <count>’ コマンドを使い、異なるサンプルサイズを試してみるのがシンプルな方法です。