【ITニュース解説】Is your cache the right size? fliplru can tell you

コンピューターシステムにおいて、データへのアクセス速度は非常に重要である。特に、頻繁に利用されるデータを一時的に保存し、高速に読み書きできるようにする仕組みを「キャッシュ」と呼ぶ。キャッシュは、遅いストレージ（例えばハードディスクやネットワーク越しにあるデータベース）からデータを取得する代わりに、速いメモリ上から直接データを提供することで、アプリケーション全体の性能を向上させる。しかし、このキャッシュの「容量（サイズ）」をどれくらいに設定するかは、多くのシステム開発者にとって長年の課題であった。

キャッシュが小さすぎると、「スラッシング」と呼ばれる現象が発生する。これは、必要なデータがキャッシュからすぐに追い出されてしまい、再び必要になったときにキャッシュに存在しないため、結局遅い元のストレージからデータを再取得しなければならない状況を指す。結果として、キャッシュを使うメリットがほとんど失われ、かえってシステム全体の処理が遅くなることもある。逆に、キャッシュが大きすぎると、必要のないデータのために貴重なメモリ領域を消費することになる。これは、システムのコスト増や他のアプリケーションに割り当てられるメモリの減少を意味し、資源の無駄遣いである。多くの一般的なLRU（Least Recently Used：最も最近使われていないものから追い出す）キャッシュでは、現在設定されているキャッシュサイズが適切かどうかを具体的に知る方法が提供されていないため、開発者は勘や経験に頼って設定せざるを得ないのが実情であった。

このような課題に対し、「fliplru」という新しいRust製のLRUキャッシュライブラリが登場した。fliplruは、組み込みシステムなどの標準ライブラリに依存しない環境（no_std）でも動作し、安全かつ高速であることに加え、自身のキャッシュサイズが適切であるかを測定し、その結果を明確な「診断（verdict）」として開発者に伝える機能を持つ。これにより、開発者はシステムにとって最適なキャッシュサイズをより客観的に判断できるようになる。

fliplruの最大の特徴は、その独自の内部構造にある。fliplruは、二つのハッシュマップ（キーと値を高速に検索するためのデータ構造）を内部に保持している。一つは「現在の世代（current generation）」、もう一つは「以前の世代（previous generation）」と呼ばれる。新しくキャッシュに追加されたキーや、最近利用されたキーは「現在の世代」に格納される。そして、「現在の世代」が設定された容量に達すると、キャッシュは「フリップ」と呼ばれる動作を行う。このフリップにより、「現在の世代」が「以前の世代」となり、それまで「以前の世代」にあった古いデータは破棄され、新しい空の「現在の世代」が始まる。もし、データを探したときにそれが「以前の世代」で見つかった場合、そのキーは再び「現在の世代」に移動される。この仕組みによって、「フリップ」を乗り越えてもまだ使われ続けるデータはキャッシュに残り続けることができる。

この設計にはいくつかの利点がある。第一に、最近使われたキーを検索する際、ハッシュテーブルを一度検索するだけで済み、従来のLRUキャッシュで必要となるリンクリストの更新などのオーバーヘッドがないため高速である。第二に、このキャッシュは常に少なくとも設定容量と同じ数の最近使われたキーを保持し、最大でその2倍のキーを保持できる可能性がある。なぜなら、「以前の世代」にもまだ有効なキーが残っていることがあるためである。そして最も重要な第三の利点として、この「フリップ」の回数が、キャッシュ内のデータの入れ替わり具合（ターンオーバー）を測定する指標となる。フリップが全く発生しないということは、使っているデータがすべてキャッシュに収まっていることを意味し、フリップがアクセス回数を容量で割った値に近づくほど、データが再利用される前にほとんど追い出されていることを示唆する。

fliplruは、このフリップ回数とその他の統計情報を組み合わせて、キャッシュのサイズに関する具体的な診断結果を生成する。fliplruが提供する統計情報には、「ヒット」（現在の世代で見つかった検索）、「プロモーション」（以前の世代で見つかった検索）、「ミス」（どちらの世代にも見つからなかった検索）、そしてデータの追加や更新、フリップの回数、これまでにキャッシュが保持した最大のエントリ数（peak_entries）などが含まれる。この中で特に注目すべきは「プロモーション」である。プロモーションは、キーが「以前の世代」で見つかったことを意味し、これは、もしキャッシュ容量がもう少し大きければ、このキーは「現在の世代」に留まり、より安定したヒットになった可能性があったことを示唆する。従来のLRUキャッシュでは、このように「惜しいヒット」を区別して報告する機能はなかった。

これらの統計情報を基に、stats().sizing()メソッドは、以下のような6種類の診断結果のいずれかを返す。「NotEnoughData」は、まだ十分なデータが収集されていない場合である。「Oversized { needed }」は、キャッシュが大きすぎる場合で、実際には指定された「needed」数のエントリしか必要なかったことを示す。「Thrashing」は、キャッシュが機能しておらず、ほとんど何も再利用されていない状態を指す。「TooSmall」や「MuchTooSmall」は、キャッシュが小さすぎることを示し、前者では容量を少し増やせば多くの恩恵が得られ、後者では大幅な容量増加が必要であることを示唆する。「Fits」は、現在のキャッシュサイズが適切であり、これ以上大きくしても大きな改善は見込めない状態である。これらの診断ルールは、ヒット率やプロモーションが全ヒットに占める割合などに基づいて決定される。

これらの診断ルールの正確性は、様々なシナリオで厳密に検証された。開発者は、まず設定されたキャッシュ容量でテストワークロードを実行し、次に容量を半分、2倍、4倍にして再度実行した。もし容量を半分にしても性能に変化がなければ「Oversized」であり、2倍にすることで性能が大幅に向上すれば「TooSmall」であると判断した。この検証には、容量に対するデータの量が異なる21種類のワークロードが使用され、容量1,000、10,000、100,000のそれぞれで実行された。例えば、キャッシュ容量10,000に対して8,000個のキーが循環的に使われるワークロードでは「Oversized { needed: 8000 }」と診断され、12,000個のキーが使われるワークロードでは「TooSmall」と診断された。このような詳細な検証により、fliplruの診断結果は高い信頼性を持つことが確認されている。当初は「TooSmall」とされていたシナリオが、実際にははるかに大きな容量を必要としていることが判明し、その結果「TooSmall」と「MuchTooSmall」の二つの診断が設けられるなど、検証を通じてルールはさらに改善された。

fliplruは性能面でも優れている。Apple M1チップでのベンチマークテストでは、一般的なLRUキャッシュライブラリと比較して、特にデータの書き込み（put）操作において非常に高速であることが示された。これは、二つの世代が効率的なハッシュテーブルである「hashbrown」を共有し、キーのハッシュ計算が一度で済むように設計されていることや、フリップ時にメモリが再利用されることなど、細部にわたる最適化の結果である。しかし、fliplruを選ぶ最大の理由は速度だけではない。キャッシュミスがデータベースへの問い合わせなど、時間のかかる操作を伴う場合、ヒット率がわずかに向上する方が、1回のヒットにかかる時間が数ナノ秒短縮されるよりも遥かに重要である。fliplruは、フリップ時に「以前の世代」全体を一度に破棄する設計のため、古典的なLRUキャッシュと比較して、同メモリ量でのヒット率がわずかに低くなる場合があることが示されている。もし最高のヒット率が最優先されるのであれば、「quick_cache（S3-FIFO）」のような他のキャッシュがより適している場合もある。

したがって、fliplruは、キャッシュ操作が非常に頻繁に行われ、かつキャッシュミスによるコストが比較的低い（例えば、小さな計算結果のメモ化や、文字列のインターニング、書き込みが多いキャッシュなど）ようなユースケースに最も適している。そして何よりも、キャッシュのサイズが適切かどうかをシステム自身に診断させたい場合に、fliplruはその真価を発揮する。また、fliplruはno_std環境に対応しており、組み込みシステムなどのリソースが限られたターゲットでも利用可能である。キャッシュ作成時に必要なメモリをすべて事前に割り当て、フリップの際にそのメモリを再利用する設計であるため、実行中に動的なメモリ割り当てが発生せず、ヒープの断片化が問題となるような環境でも安心して使用できる。

fliplruの開発では、二つの世代ではなく一つのテーブルで実現する試みや、「プロベーション世代」（新しいキーが本キャッシュに入る前に一時的に評価される期間）を設ける試みも行われたが、これらは最終的に採用されなかった。一つのテーブル案は、書き込み性能の低下という問題があったためである。プロベーション世代案は、特定のトラフィックには有効であったものの、fliplruの持つ「直近の容量分のキーは常にキャッシュに存在する」という重要な保証を破ってしまうため、サイズ診断機能の根幹に関わる部分に影響を与えると判断された。

ベンチマークテストから得られた教訓もいくつかある。例えば、ベンチマークの実行順序が結果に影響を与えることがあるため、公平な比較のためには各キャッシュを交互に実行し、実行順序をローテーションさせるなどの工夫が必要である。また、キャッシュの性能を評価する際には、単に処理時間だけでなく「ヒット率」も合わせて報告することが重要である。ヒット率が低いキャッシュは、キャッシュミスに伴う異なる種類の処理（例えば、データベースからのデータ取得）を行っているため、単純な時間比較だけでは不公平な評価になる可能性がある。さらに、各キャッシュライブラリが提供する最も効率的なAPI（例えば、「get_or_insert」のようなメソッド）を使って比較を行うべきである。

fliplruは、Rustプロジェクトに簡単に導入でき、stats().sizing()メソッドを使って、既存のキャッシュが本当に適切なサイズであるかを診断できる。もし、現在のキャッシュ設定について新たな発見があれば、それはシステム性能改善の大きな手がかりとなるだろう。