Blog Dice

Random notes on improving the Redis LRU algorithm

Salvatore Sanfilippo

RedisのLRUアルゴリズム改善についての覚え書き

原文は Salvatore Sanfilippo により に公開されました。 このブログを購読する

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時間を目立って増やすことも、1ビットたりとも追加のメモリを使うこともなく改善できるのは明らかだった。

ただ、何かを改善するには、まずそれを観察しなければならない。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

私が今このブログ記事を書いているのは、数日前にRedisのキャッシュ追い出しコードを部分的に再実装し、いくつかの改善に取り組んだからだ。

きっかけは一つのオープンなissueだった。Redis 3.2で複数のデータベースを使っている場合、アルゴリズムは局所的な判断で追い出しを行う。例えば、DB 0にはアイドル時間が短いキーばかりがあり、DB 1にはアイドル時間が長いキーばかりがある場合、RedisはそれぞれのDBから1つずつキーを追い出してしまう。より合理的なのは、まずDB 1から追い出し始め、後になってから他のキーを追い出すことだ。

Redisをキャッシュとして使う場合、複数のDBを使うことはめったにないので、通常これは大きな問題にはならない。しかし、これをきっかけに私は再び追い出しコードに取り組み始めた。最終的に、プールにデータベースIDを含めるように修正し、複数のプールを使う代わりにすべてのDBで単一のプールを使うようにした。当初は遅くなったが、プロファイリングとチューニングを重ねた結果、最終的には元の実装より約20%高速になった。

しかしその時点で、このサブシステムに対する好奇心が再び刺激され、さらに改善したいと思うようになった。数日かけてLRU実装の改善を試みた。プールを大きくしてみるか？ 最良のキーを選んでいる間に経過する時間を考慮するか？

しばらくして、ツールを磨き上げていくうちに、LRUアルゴリズムはデータベースからサンプリングするデータ量に制約されているだけで、それ以外は非常に優秀で改善が難しいことがわかってきた。実際、これはさまざまなアルゴリズムを示した画像からもある程度明らかだ。1サイクルあたり10キーをサンプリングすれば、理論上のLRUとほぼ同等の精度になっていた。

元のアルゴリズムの改善が難しいとわかったので、新しいアルゴリズムのテストを始めた。ブログ記事の冒頭に少し戻ると、LRUはある種のトリックにすぎないと述べた。本当に保持したいのは、将来アクセスされる確率が最も高いキー、つまり最も最近アクセスされたキーではなく、最も頻繁にアクセスされるキーだ。

アクセス回数が最も少ないキーを追い出すアルゴリズムはLFUと呼ばれる。Least Frequently Used（最も頻繁に使われていないもの）の略で、新しいキーのために領域を確保する際に削除しようとするキーの特徴を表している。

理論上、LFUは各キーにカウンタを紐づけるだけのシンプルなものだ。アクセスのたびにカウンタがインクリメントされるため、あるキーが別のキーよりも頻繁にアクセスされていることがわかる。

ただ、LFUの実装には、Redisに限らない一般的な問題が少なくともいくつかある。

  1. LFUでは、LRUで使われる「先頭に移動する」連結リストのトリックを使って、追い出し対象の要素を簡単にソートされた状態で取得することができない。というのも、「完全なLFU」ではキーはアクセス回数で順序付けされなければならないからだ。アクセスされたキーを正しい位置に移動させるのは、同じスコアを持つキーが多数存在しうるため問題になりうる。キー頻度カウンタがわずかに変化しただけでも、最悪の場合この操作はO(N)になりうる。また、後述する「2」の点で見るように、アクセスカウンタは常にわずかに変化するだけとは限らず、突然大きく変化することもある。
  2. LFUは、単にアクセスのたびにアクセスカウンタをインクリメントする、といった単純なものではありえない。前述した通り、アクセスパターンは時間とともに変化するので、誰もアクセスし続けなければ、高いスコアを持つキーは時間の経過とともにスコアを下げていく必要がある。アルゴリズムは時間の経過に適応できなければならない。

Redisでは1つ目の問題は問題にならない。LRUで使ったトリック、すなわち候補プールを用いたランダムサンプリングをそのまま使えるからだ。残るのは2つ目の問題だ。そのため通常のLFU実装では、アクセスカウンタを時々デクリメント、あるいは半減させる何らかの仕組みが用意されている。

24ビットでのLFU実装

LFU自体にも実装上の癖があるが、RedisではLFUをモデル化するために使えるのは24ビットのLRUフィールドだけだ。オブジェクトあたりわずか24ビットでLFUを実装するのは、少しトリッキーになる。

24ビットで実現しなければならないことは次の2つだ。

  1. 何らかのアクセス頻度カウンタ。
  2. カウンタをいつ半減させるかを判断するのに十分な情報。

私の解決策は、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氏が、TinyLRUと呼ばれるアルゴリズムを解説した興味深い論文を教えてくれた（http://arxiv.org/pdf/1512.00727.pdf）。

この論文には非常に巧妙なアイデアが含まれている。現在のオブジェクトのアクセス頻度を覚える代わりに、これまでに見たすべてのオブジェクトのアクセス頻度を（確率的に）記憶しておくというものだ。そうすれば、キー名からアクセスが少ないと判断できる場合には、新しいキーの受け入れ自体を拒否できる。キーを追い出すことでヒット率が下がるのであれば、そもそも追い出し自体が不要になるというわけだ。

私の感覚では、この手法は単純なGET/SETを行うLFUキャッシュとしては非常に興味深いものの、データ構造サーバーとしてのRedisの性質には適さない。ユーザーは、キーを作成したら少なくとも数ミリ秒は存在することを期待している。キーの作成自体を拒否するのは、Redisのセマンティクスとして間違っているように思える。

ただしRedisでは、キーが上書きされた際にもLFU情報は保持される。例えば次のように実行した後でも、

SET oldkey some_new_value

古いキーに関連付けられた新しいオブジェクトに、24ビットのLFUカウンタがコピーされる。

Redis unstableの新しい追い出しコードには、他にも良いニュースがある。

  1. ポリシーが「DB横断」になった。以前はこのブログ記事の冒頭で説明したようにRedisは局所的な判断を行っていたが、現在はLRUだけでなくすべてのポリシーで修正されている。
  2. expireが設定されたキーの残り生存時間に基づいて追い出すvolatile-ttlポリシーも、他のポリシーと同様にプールを使うようになった。
  3. キーのプール内でSDSオブジェクトを再利用することで、パフォーマンスが向上した。

この記事は予想よりもかなり長くなってしまったが、新しい機能や既存のものの改善についていくつかの洞察を提供できていれば幸いだ。Redisは特定の問題を解決する「ソリューション」というよりも、汎用的なツールだ。それを正しい方法で適用するのは、賢明な開発者次第である。多くの人がRedisをキャッシュソリューションとして使っているため、この分野の改善は常にある程度の頻度で検討されている。

Hacker Newsコメント: https://news.ycombinator.com/item?id=12185534

この記事は「muse-spark-1.2-contributor」を使用して翻訳されました。

コメント