RedisのLRUアルゴリズム改善についての雑記
Redisはキャッシュとして使われることが多く、その際には使用する最大メモリ容量を固定で指定します。新しいデータが届いたら、古いデータを削除して空きを作る必要があります。キャッシュとしてのRedisの効率は、どのデータを追い出すかという判断の良し悪しにかかっています。すぐに必要になるデータを削除するのは悪手であり、再びリクエストされる可能性が低いデータを削除するのは良い判断です。
言い換えれば、すべてのキャッシュにはヒット率とミス率があります。定性的に言えば、読み取りクエリのうちキャッシュが処理できた割合のことです。多くのワークロードでは、キャッシュのキーへのアクセスはデータセット全体に均等に分散していません。多くの場合、少数のキーがアクセス全体の大部分を占めます。さらにアクセスパターンは時間とともに変化することが多く、以前は頻繁にリクエストされていたキーがやがてあまりアクセスされなくなったり、逆にかつては人気がなかったキーが最もアクセスされるキーになったりします。
一般にキャッシュが目指すべきは、将来アクセスされる可能性が最も高いキーを保持することです。追い出しポリシー（新しいデータのために空きを作る方針）の観点から言えば、その逆になります。すなわち、将来アクセスされる可能性が最も低いキーをデータセットから削除すべきです。ただ一つ問題があります。Redisをはじめとするキャッシュは未来を予測できません。
LRUアルゴリズム
キャッシュは未来を予測できませんが、次のように考えることはできます。すなわち、再びリクエストされる可能性が高いキーは、最近頻繁にリクエストされたキーである、ということです。通常アクセスパターンは急激には変化しないため、これは有効な戦略です。しかし「最近頻繁にリクエストされた」という概念は、一見するよりも厄介です（これについては後ほど触れます）。そこでこの考え方はLRUと呼ばれるアルゴリズムに単純化されます。LRUでは各キーが最後にリクエストされた時刻だけを追跡します。アクセス頻度が高いキーは、めったにアクセスされないキーに比べて、アイドル時間（アクセスされていない時間）が短くなる確率が高くなります。
例として、4つの異なるキーの時間経過に伴うアクセスを図示します。「~」1文字が1秒を表し、末尾の「|」が現在時刻を示しています。
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|キーAは5秒に1回、キーBは2秒に1回、キーCとDはともに10秒に1回アクセスされています。
キーBはアクセス頻度が高いため、アイドル時間は最も短い部類に入ります。つまり、最後にアクセスされた時刻は4つのキーの中で2番目に新しいことになります。
同様に、AとCのアイドル時間がそれぞれ2秒と6秒であることは、両キーのアクセス頻度をよく反映しています。しかしご覧のとおり、この方法が常にうまくいくわけではありません。キーDは10秒に1回しかアクセスされないにもかかわらず、すべてのキーの中で最も新しいアクセス時刻を持っています。
それでも、長い目で見ればこのアルゴリズムは十分にうまく機能します。一般にアクセス頻度が高いキーほどアイドル時間は短くなります。LRUアルゴリズムは、最も長い間使われていない（Least Recently Used）キー、すなわちアイドル時間が最も長いキーを追い出します。実装はシンプルです。必要なのは各キーが最後にアクセスされた時刻を記録することだけですし、場合によってはそれすら不要です。追い出し対象のすべてのオブジェクトを連結リストでつないでおく方法もあります。オブジェクトにアクセスがあるたびにリストの先頭へ移動し、追い出すときは末尾から取り除きます。これで完了です。
RedisにおけるLRU：その誕生
当初、RedisにはLRUによる追い出し機能がありませんでした。メモリ効率が大きな課題となった後に追加されたものです。Redisのオブジェクト構造を少し変更することで24ビット分の空きを確保できました。オブジェクトを連結リストでつなぐための余裕はありませんでしたし（ポインタは重いのです）、実装は効率的である必要もありました。追い出すキーを選ぶ処理でサーバーの性能が大きく落ちてはならないからです。
オブジェクト内の24ビットは、現在のUNIX時刻（秒単位）の下位ビットを格納するのに十分です。この表現はRedisのソースコード内では「LRUクロック」と呼ばれており、オーバーフローするまで194日かかります。キーのメタデータはそれよりはるかに頻繁に更新されるため、これで十分でした。
しかし、もう一つ解決すべきより複雑な問題がありました。どうやってアイドル時間が最も長いキーを選んで追い出すか、ということです。Redisのキー空間はフラットなハッシュテーブルで表現されています。このメタデータのために別のデータ構造を追加する選択肢はありませんでした。ただ、LRU自体が本来達成したいことの近似であるなら、LRU自体を近似してはどうか、と考えました。
当初のRedisのアルゴリズムは、いたってシンプルでした。キーを追い出す必要があるときに、ランダムに3つのキーを選び、その中でアイドル時間が最も長いものを追い出すのです。基本的にキー空間からランダムにサンプリングし、その中で最も良いキーを追い出します。後にこの「ランダムに3つ」は設定可能な「ランダムにN個」になり、アルゴリズムの速度も改善されたため、性能を落とすことなくデフォルトのサンプル数は5に引き上げられました。これほど単純な割に、驚くほどよく機能しました。よく考えてみれば、このアルゴリズムでは常に最良の判断ができるわけではありませんが、極端に悪い判断をしてしまう可能性も非常に低いのです。データセットの中に非常に頻繁にアクセスされるキーの集合がある場合、5つのキーの中からアイドル時間が極端に短いキーだけを引いてしまうほど運が悪いことは滅多にありません。
しかし、このアルゴリズムを複数回実行するという観点で見ると、多くの有益な情報を捨ててしまっていることが分かります。N個のキーをサンプリングする際に、追い出し候補として優れたキーがたくさん見つかるかもしれませんが、結局はその中で最も良いものだけを追い出し、次のサイクルではまたゼロからやり直すことになります。
ファイトクラブの第一ルール：アルゴリズムを肉眼で観察する
あるとき、私は次期Redis 3.0のリリースに取り組んでいました。Redis 2.8はすでに多くの環境でLRUキャッシュとして活発に使われていましたが、Redisの追い出し精度について大きな不満の声はなかったものの、わずかなCPU時間も追加のメモリも使わずに改善できることは明らかでした。
しかし何かを改善するには、まずそれを観察する必要があります。LRUアルゴリズムを観察する方法はいくつかあります。例えば、異なるワークロードをシミュレートするツールを作り、最終的なヒット率とミス率を確認する方法です。私もそうしましたが、ヒット率とミス率はアクセスパターンに大きく依存するため、その情報に加えて、アルゴリズムの品質を視覚的に表示するユーティリティも作成しました。
プログラムは非常にシンプルです。一定数のキーを追加し、次に各キーのアイドル時間が順に短くなるように順番にアクセスします。最後にさらに50%分のキー（図では緑色で示されています）を追加し、古いキーの半分を追い出す必要がある状態にします。
理想的なLRU実装では、新しく追加されたキーは一つも追い出されず、古いデータセットのうち古い方の50%だけが追い出されます。
このプログラムが生成した、Redisのバージョンや設定ごとの比較がこちらです。
http://redis.io/images/redisdoc/lru_comparison.png
グラフを見る際には、これまで説明してきた実装がRedis 2.8のものであることを念頭に置いてください。Redis 3.0で見られる改善については、次のセクションで説明します。
LRU V2：貴重な情報を捨てない
新しい可視化ツールのおかげで、新しい手法を試して数分でテストできるようになりました。Redisで使われていた素朴なアルゴリズムを改善する最も分かりやすい方法は、捨てられていた情報を追い出し候補の「プール」に蓄積することでした。
基本的に、N個のキーのサンプリングを行った際に、その結果をより大きなキー（デフォルトでは16個）のプールに蓄積するようにしたのです。このプールではキーがアイドル時間順にソートされており、新しいキーは、プールに空きがあるか、プール内のいずれかのキーよりもアイドル時間が長い場合にのみプールに入ります。
この小さな変更により、アルゴリズムの性能は上記でリンクした画像のとおり劇的に向上し、実装もそれほど複雑ではありませんでした。数か所のmemmove()と多少のプロファイリングは必要でしたが、この周辺で大きなバグに悩まされた記憶はありません。
同時に、LRUの精度をテストするための新しいredis-cliのモードも追加されました（--lru-testオプションを参照してください）。これにより、べき乗則に従うアクセスパターンでLRUコードの性能を別のテストでも検証できるようになりました。このツールはより現実に近いワークロードで新しいアルゴリズムがより良く機能することを検証するためにも使われました。また、パイプライン処理を使い、1秒あたりのアクセス数も表示するため、異なる実装をベンチマークし、少なくとも明らかな速度低下がないかを確認する用途にも使えます。
Least Frequently Used（LFU：最使用頻度）
今回このブログ記事を書いているのは、数日前にRedisのキャッシュ追い出しコードを部分的に書き直し、さまざまな改善を行ったからです。
きっかけは一つのオープンな課題でした。Redis 3.2で複数のデータベースを使っている場合、アルゴリズムがデータベースごとに局所的な判断で追い出しを行ってしまうのです。例えば、データベース0にはアイドル時間が短いキーばかりがあり、データベース1にはアイドル時間が長いキーばかりがある場合、Redisは各データベースから1つずつキーを追い出します。より合理的なのは、まずデータベース1から追い出し始め、後から他のキーを追い出すことです。
通常、Redisをキャッシュとして使う場合に複数のデータベースが使われることは稀なので、これは大きな問題ではありません。しかし、これをきっかけに私は再び追い出しコードに取り組むことになりました。最終的に、プールにデータベースIDを含め、データベースごとに複数のプールを使うのではなく、すべてのデータベースで単一のプールを使うように修正できました。当初は遅くなりましたが、プロファイリングとチューニングを重ねた結果、最終的には元の実装より約20%高速になりました。
しかしそこで、このサブシステムへの好奇心が再び刺激され、さらに改善したくなりました。数日かけてLRU実装の改善を試みました。プールを大きくしてみるか、最適なキーを選択するまでの経過時間を考慮してみるか、といったことです。
しばらく試行錯誤し、ツールを磨き上げた結果、LRUアルゴリズムはデータベースからサンプリングするデータ量によって制約されており、それ以外では非常に優秀で改善が難しいことが分かりました。これは、異なるアルゴリズムを示した画像からも明らかです。1サイクルあたり10キーをサンプリングすれば、理論上のLRUとほぼ同等の精度が得られていました。
元のアルゴリズムの改善が難しいと分かったので、新しいアルゴリズムを試し始めました。ブログ記事の冒頭に戻れば、LRUは本来ちょっとしたごまかしだと言いました。本当に保持したいのは、将来アクセスされる可能性が最も高いキー、すなわち最も頻繁にアクセスされるキーであり、最後にアクセスされたキーが最も新しいものではないのです。
アクセス回数が最も少ないキーを追い出すアルゴリズムはLFUと呼ばれます。Least Frequently Usedの略で、空きを作るために削除しようとするキーの特徴を表しています。
理論上、LFUは各キーにカウンターを関連付けるだけのシンプルなものです。アクセスがあるたびにカウンターを増やし、あるキーが別のキーより頻繁にアクセスされていることを把握します。
ただ、Redisに限らずLFUの実装一般に共通する、少なくともいくつかの問題があります。
- LFUでは、LRUで使われるような「先頭に移動する」連結リストの手法を使って追い出し対象をソートされた状態で簡単に取得することができません。キー が「完全なLFU」ではアクセス回数順に並んでいる必要があるためです。アクセスされたキーを正しい位置に移動する処理は、同じスコアを持つキーが多数存在する可能性があるため、最悪の場合はO(N)になることがあります。しかも後述する2番目の理由のとおり、アクセスカウンターは常に少しずつ変化するわけではなく、突然大きく変化することもあります。
- LFUは、アクセスがあるたびに単純にアクセスカウンターを増やすだけ、というわけにはいきません。前述のとおりアクセスパターンは時間とともに変化するため、高いスコアを持つキーも、誰もアクセスしなくなれば時間とともにスコアを下げる必要があります。アルゴリズムは時間の経過に適応できなければなりません。
Redisでは、1番目の問題は問題になりません。LRUで使ったのと同じ手法、すなわちプールを用いたランダムサンプリングを使えばよいのです。2番目の問題は残ります。そのため通常のLFU実装では、アクセスカウンターを時々減算したり半減させたりする何らかの仕組みが用意されています。
24ビットでLFUを実装する
LFU自体にも実装上の癖がありますが、RedisではLFUをモデル化するために使えるのは24ビットのLRUフィールドだけです。わずか24ビットでLFUを実装するのは少し工夫が必要です。
24ビットで実現しなければならないことは次のとおりです。
- アクセス頻度カウンターのようなもの。
- カウンターを半減させるタイミングを判断するのに十分な情報。
私の解決策は、24ビットを2つのフィールドに分割することでした。
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+16ビットのフィールドは最後に減算を行った時刻で、Redisがカウンターを最後に減算した時刻を把握するためのものです。8ビットのフィールドが実際のアクセスカウンターです。
8ビットのカウンターはすぐに溢れてしまうのでは、と思われたかもしれません。そこで使ったのが、単なるカウンターではなく対数カウンターです。キーへのアクセス時にカウンターを増やす関数は次のとおりです。
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255;
double r = (double)rand()/RAND_MAX;
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;
return counter;
}基本的に、カウンターの値が大きいほど、カウンターが実際に増加する確率は低くなります。上記のコードでは、カウンターが大きくなるにつれて0から1の間でどんどん小さくなる数値pを計算しています。そして0から1の乱数rを取り出し、r < pが真の場合にのみカウンターを増やします。
カウンターをどれだけ積極的に増やすかはredis.confのパラメータで設定できますが、例えばデフォルト設定では次のようになります。
100回ヒットした後のカウンター値は10、1000回後は18、10万回後は142、100万回ヒットすると上限の255に達してそれ以上は増加しなくなります。
次に、このカウンターがどのように減算されるかを見てみます。16ビットはUNIX時刻を分単位に変換した下位ビットを格納するために使われます。Redisがキー空間をランダムサンプリングしてプールを埋めるために走査する際に出会ったすべてのキーは、減算が必要かどうかチェックされます。最後の減算からN分以上（Nは設定可能）経過している場合、カウンターの値が高ければ半減し、低い値であれば単に1だけ減らします（カウンターの分解能が非常に小さいため、アクセスが少ないキー同士をより適切に区別できるようにするためです）。
もう一つ問題があります。新しいキーにも生き残るチャンスを与える必要があります。素朴なLFUでは、追加されたばかりのキーのアクセススコアは0なので、追い出しの格好の候補になってしまいます。Redisでは新しいキーはLFU値が5から始まります。この初期値は増加および半減のアルゴリズムでも考慮されています。シミュレーションによれば、この変更によりキーがある程度アクセスを蓄積する時間が確保されます。スコアが5未満のキー（長い間アクセスされていない非アクティブなキー）が優先的に追い出されることになります。
コードと性能
上記で説明した実装は、Redisのunstableブランチにあります。私の初期テストでは、べき乗則のアクセスパターンにおいてLRUを上回りつつ、キーあたりのメモリ使用量は同じでした。ただし、実際のアクセスパターンは異なる可能性があります。アクセスの時間的・空間的局所性は大きく異なる変化を見せるため、実際のユースケースでLFUがどのように機能するか、またRedisのLFU実装で調整可能な2つのパラメータがワークロードごとに性能をどう変えるかについて、ぜひ知りたいと思っています。
また、指定されたキーの頻度カウンターを報告するOBJECT FREQサブコマンドも追加されました。これはアプリケーションのアクセスパターンを観察するのにも、LFU実装をデバッグするのにも役立ちます。
実行時にLRUとLFUのポリシーを切り替えると、24ビットカウンターに蓄積されたメタデータが新しく選択されたポリシーの意味と一致しなくなるため、ほぼランダムな追い出しから始まることになります。ただし、時間の経過とともに再び適応していきます。
おそらく改善の余地はまだ多くあります。
Ben Manes氏に、TinyLFUと呼ばれるアルゴリズムを説明した興味深い論文を教えてもらいました（http://arxiv.org/pdf/1512.00727.pdf）。
この論文には非常に巧妙なアイデアが含まれています。現在のオブジェクトのアクセス頻度を記憶するのではなく、これまでに見たすべてのオブジェクトのアクセス頻度を（確率的に）記憶するのです。これにより、名前からアクセスが少なそうだと判断した新しいキーをそもそも受け入れずに済ませ、キーを追い出すことでヒット率を下げてしまう事態を避けることができます。
この手法は、単純なGET/SETのLFUキャッシュとしては非常に興味深いものの、データ構造サーバーであるRedisの性質には適用できないと私は考えています。ユーザーはキーを作成した後、少なくとも数ミリ秒はそのキーが存在することを期待します。キーの作成自体を拒否するのは、Redisのセマンティクスとして誤っているように思えます。
ただしRedisは、キーが上書きされた際にもLFU情報を維持します。例えば次のように実行した後では、
SET oldkey some_new_value24ビットのLFUカウンターは古いキーに関連付けられていた新しいオブジェクトへコピーされます。
Redis unstableの新しい追い出しコードには、他にも良い点があります。
- ポリシーが「データベース横断」になりました。以前のRedisは本記事の冒頭で説明したように局所的な判断を行っていましたが、現在はLRUだけでなくすべてのポリシーでこれが修正されています。
- 有効期限が設定されたキーの残りTTLに基づいて追い出すvolatile-ttl追い出しポリシーも、他のポリシーと同様にプールを使うようになりました。
- プール内のSDSオブジェクトを再利用することで性能が向上しています。
想定よりもかなり長い記事になってしまいましたが、新しい機能や既存の機能の改善についていくつかの洞察を提供できていれば幸いです。Redisは特定の問題を解決するための「解決策」というよりも、汎用的なツールです。それを適切な方法で適用するのは、分別ある開発者の役割です。多くの方がRedisをキャッシュソリューションとして使っているため、この分野の改善は常に折に触れて検討されています。
Hacker Newsでのコメント: https://news.ycombinator.com/item?id=12185534