*LRUキャッシュとしてのRedisの使用

Redisをキャッシュとして使う場合、新しいデータを追加すると自動的に古いデータを削除するようにするとしばしば便利です。この挙動は人気のあるmemcached システムのデフォルトの挙動のため、開発者のコミュニティではよく知られています。

LRUは実際にはサポートされている削除方法の一つにすぎません。このページではメモリの使用量を一定量以下に制限するために使われる Redis のmaxmemory ディレクティブの一般的な話題と、Redisによって使われるLRUアルゴリズム、実際には正確なLRUの推定概算、についても詳しく説明します。

Redis バージョン 4.0 から新しいLFU (Least Frequently Used) 削除ポリシーが導入されました。これはこのドキュメントの別の章で説明されます。

*Maxmemory 設定ディレクティブ

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

例えば、100メガバイトのメモリ制限を設定するには、以下のコマンドを redis.conf ファイル内で使うことができます。

maxmemory 100mb

maxmemory を0に設定すると、メモリの制限がなくなります。これは64ビットのシステムではデフォルトの挙動ですが、32ビットのシステムは暗黙のメモリ制限である3GBが使われます。

指定されたメモリ量に到達すると、ポリシーと呼ばれる様々な動作の中から選択することができます。Redisはもっとメモリが使われることになるコマンドについてエラーを単純に返すか、新しいデータが追加される度に指定された制限に戻るためにいくらかの古いデータを削除することができます。

*削除ポリシー

maxmemoryの制限に到達した時のRedi sの正確な挙動はmaxmemory-policy 設定ディレクティブを使って設定されます。

以下のポリシーが利用可能です:

  • noeviction: メモリの制限に到達し、クライアントがもっとメモリを使うことになりそうなコマンド (ほとんどは書き込みコマンドですが、DEL とさらに幾つかは例外です) を実行しようとした時にエラーを返します。
  • allkeys-lru: 新しく追加されたデータのための空間を確保するために、使用頻度の低い (LRU) キーを最初に削除しようとすることでキーを削除します。
  • volatile-lru: 新しく追加されたデータのための空間を確保するために、使用頻度の低い (LRU) キー、ただしexpire setを持つキーだけを最初に削除しようとすることでキーを削除します。
  • allkeys-random: 新しく追加されたキーのための空間を確保するために、キーをランダムに削除します。
  • volatile-random: 新しく追加されたキーのための空間を確保するために、expire setを持つキーだけをランダムに削除します。
  • volatile-ttl: 新しく追加されたキーのための空間を確保するために、expire setを持つキーを削除し、まず有効期限 (TTL) が短いキーを削除しようとします。

前提条件に一致するキーが無い場合は、ポリシー volatile-lru, volatile-random および volatile-ttlnoeviction のような挙動をします。

アプリケーションのアクセスパターンによって適切な削除パターンを選択することが重要ですが、セットアップを調整するためにアプリケーションの実行中にポリシーを再設定し、Redis の INFO 出力を使ってキャッシュ ミスとヒットの数を監視することができます。

一般的な経験則として:

  • リクエストの人気にべき乗分布、つまり要素の部分が他のものよりはるかに頻繁にアクセスされることが期待される時にはallkeys-lru ポリシーを使ってください。よく分からない場合、これは良い選択です
  • 全てのキーが連続して走査される周期的なアクセスがある、あるいは分布が均一である(すべての要素が同じ確率でアクセスされる可能性が高い)と予想される時はallkeys-randomを使ってください。
  • キャッシュオブジェクトを作る時に異なるTTL値を使ってRedisに有効期限の候補としてヒントを提供できるようにする時にはvolatile-ttl を使ってください。

volatile-lruvolatile-randomポリシーは主にキャッシングと永続キーのセットの両方に1つのインスタンスを使いたい場合に役立ちます。ですが、そのような問題を解決するには通常2つのインスタンスを実行することをお勧めします。

キーに有効期限を設定するとメモリが消費されることに注意することにも価値があります。つまり、メモリの圧迫がある中でキーに有効期限を設定する必要が無いため、allkeys-lruのようなポリシーを使うとメモリ効率が高くなります。

*削除プロセスがどのように動作するか

削除プロセスが以下のように動作することを理解することが重要です:

  • クライアントが新しいコマンドを実行し、追加のデータが増えます。
  • Redisはメモリの使用量をチェックし、もし maxmemory 制限よりも大きくなると、ポリシーに応じてキーを削除します。
  • 新しいコマンドが実行されるなど。

つまり、メモリの制限を超え、そして制限を下回るためにキーを削除することで、メモリの境界を連続して横断します。

(新しいキーに格納されている大きな共通部分のように) コマンドが大量のメモリ使用をすることになると、メモリの使用量はしばらくの間かなりのの量だけ増えることがあります。

*近似 LRU アルゴリズム

Redis LRU アルゴリズムは正確な実装ではありません。Redisは削除のための最良の候補、つまり最も過去にアクセスされたアクセスを選択できないことを意味します。代わりに少数のキーをサンプリングし、サンプリングされたキーの中で(もっとも古いアクセス時間を持つ)最善のものを削除することで、LRUアルゴリズムの近似を実行しようとします。

しかし、Redis 3.0 以降、アルゴリズムは削除の良い候補のプールも取るように改良されました。これはアルゴリズムのパフォーマンスを改善し、実際のLRUアルゴリズムの挙動をより厳密に近似できるようになりました。

RedisのLRUアルゴリズムの重要な点は、各削除ごとにサンプルの数を変更することでアルゴリズムの精度を調整することができることです。このパラメータは以下の設定ディレクティブによって制御されます:

maxmemory-samples 5

Redisが本当のLRU実装を使用しない理由は、それがより多くのメモリを必要とするからです。ただし、近似はRedisを利用しているアプリケーションにとって実質的に同じです。以下はRedisによって使われているLRU近似が本当のLRUとどのように比較されるかをグラフで比較したものです。

LRUの比較

上のグラフを生成するためのテストでは、Redisサーバに所定の数のキーが入力されました。最初のキーがLRUアルゴリズムを使って削除の最良の候補になるように、キーは最初から最後までアクセスされました。古いキーの半分が削除されるように、後で50%のキーが追加されました。

グラフには3種類の点があり、3つの異なる帯が形成されます。

  • 薄い灰色の帯は削除されたオブジェクトです。
  • 灰色の帯は削除されなかったオブジェクトです。
  • 緑色の帯は追加されたオブジェクトです。

理論的なLRU実装では、古いキーの中で最初の半分が期限切れになると予想されます。RedisのLRUアルゴリズムは代わりに確率論的に古いキーを期限切れにするだけです。

御覧のように Redis 3.0 は Redis 2.8 と比較して5つのサンプルでより良い仕事をしますが、最近アクセスされた中のほとんどのオブジェクトはRedis 2.8 によってまだ保持されます。Redis 3.0 でサンプル サイズ 10 を使用すると、Redis 3.0 の理論上のパフォーマンスに非常に近くなります。

LRUは与えられたキーが将来どの程度アクセスされる可能性があるかを予測するためのモデルにすぎません。さらにもしデータのアクセスパターンがべき乗に非常に似ている場合、ほとんどのアクセスはLRU近似アルゴリズムでうまく処理できるキーのセットになります。

シミュレーションではべき乗アクセスパターンを使って、真のLRUとRedisの近似の間の差は最小あるいは存在しないことが分かりました。

しかし、真のLRUに密接に概算するために追加のCPU使用率を費やしてサンプルサイズを10に増やすことができ、これがキャッシュミス率に差があるかどうかを確認することができます。

CONFIG SET maxmemory-samples <count> コマンドを使ってサンプルサイズに異なる値を設定したプロダクションで実験することがとても簡単です。

*新しいLFUモード

Redis 4.0 から新しいLeast Frequently Used 削除モード が利用可能です。LFU Redisの使用はアイテムのアクセス頻度を追跡しようとするため、しばしば使われるものはメモリ内に残る可能性が高く、あまり使われないものは削除されるため、このモードは特定の場合においてうまく動作(より良いヒット/ミス率を提供)するかもしれません。

LRUを考えた時、最近アクセスされたが実際にはほとんど要求されないアイテムは期限切れにならないため、将来要求される可能性が高いキーを削除することは危険です。LFUはこの問題を持たず、一般的に様々なアクセスパターンにより適しているはずです。

LFUモードを設定するために、以下のポリシーが利用可能です:

  • volatile-lfu 有効期限が設定されたキーの間で近似LFUを使って削除します。
  • allkeys-lfu 近似LFUを使って任意のキーを削除します。

LFU はLRUのように近似されます: オブジェクトごとにほんの数ビットを使用してオブジェクトのアクセス頻度を推定するためにMorris counterと呼ばれるカウンタが時間とともに減少するように衰退期間を組み合わせた確率的カウンタを使用します: アルゴリズムがアクセスパターンの移動に適用できるように、たとえもしキーが過去にあったとしても頻繁にアクセスされるとみなす必要はもうありません。

これらの情報は削除の候補を選択するために(このドキュメントの前の章で説明したように)LRUで行われるものと同じようにサンプリングされます。

しかしLRUと異なり、LFUはある種の調整可能なパラメータを持ちます: 例えば、もしもうアクセスされない場合に頻度の高いアイテムをランク内でどれだけ早く下げるか?アルゴリズムを特定のユースケースによりよく適用するために、Morrisカウンタを調整することもできます。

デフォルトではRedis 4.0は以下のように設定されています:

  • 約100万リクエストでカウンタを飽和させます。
  • 1分ごとにカウンタを減衰させます。

これらは妥当な値でなければならず、実験的にテストされていますが、ユーザは最適な値を選択するためにこれらの構成設定を使用したい場合があります。

これらのパラメータを調整する方法についての説明はソース配布物の中の redis.confファイルの例で見つけることができますが、簡単にいうと以下の通りです:

lfu-log-factor 10
lfu-decay-time 1

減衰時間は明らかなもので、サンプリングされてその値よりも古いことが分った時にカウンタが減衰されるべき分の数です。特別な値 0 は以下を意味します: スキャンされる度に常にカウンタを減少させ、あまり役に立ちません。

カウンタ 対数係数 は周波数カウンタを飽和させるために必要なヒット数を変更します。これは 0-255 の範囲内です。係数が高いほど、最大数に達するために必要なアクセス数が増えます。次の表によると、係数が低いほど、アクセスの少ないカウンタの分解能が高くなります:

+--------+------------+------------+------------+------------+------------+
| factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
+--------+------------+------------+------------+------------+------------+
| 0      | 104        | 255        | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 1      | 18         | 49         | 255        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 10     | 10         | 18         | 142        | 255        | 255        |
+--------+------------+------------+------------+------------+------------+
| 100    | 8          | 11         | 49         | 143        | 255        |
+--------+------------+------------+------------+------------+------------+

つまり、基本的にこの係数は、アクセスの少ない項目をより良く識別するのと、アクセスが多い項目を識別するのとのトレードオフになります。詳細については、redis.confファイルの自己文章化コメントの例で利用可能です。

LFU は新しい機能のため、LRUと比較した場合のユースケースでのパフォーマンスに関するフィードバックを頂ければ幸いです。

TOP
inserted by FC2 system