キャッシュアルゴリズムの比較

algorithm

アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。

LRU

最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScript(NPM)はパッケージ数100万以上を誇るにもかかわらずLRUしかまともなキャッシュの実装がなくnodeやTinyLFUのような人気のフレーズを付けた名前に名前と無関係の実装を貼り付けたクリックバイトの詐欺パッケージとすぐエラーを吐く壊れたガラクタばかり豊富なスラムみたいな状態となっている。後発のRust(10万パッケージ未満)とGoは理論的に優れた実装がガンガン追加されてるのに全体的に理論的に優れた実装に乏しくキャッシュも最も初歩的で原始的なLRUしか使えない超低空飛行プログラミングに疑問も不満も感じず理論的教養を持つ天上界のプログラマに仕事か気まぐれで運よく優れた実装を恵んでいただけるまで刃の潰れた斧を延々使い続け時間ができても流行りのスコップで飽きもせず同じ穴を何度も掘っては埋め続けるか偽ブランド作りに勤しむ、それがJSerクオリティー。注目を集めるために著名な名前を偽装して名前空間と検索結果を汚染する最低水準のプログラマが集まってろくに管理されてないのでとにかく質と治安が悪い。使う側も容量超えるとクラッシュするキャッシュもどきをキャッシュと思い込んで毎週200万DLして使ってるポアな世界。質は量から生まれるとは何だったのか。

Clock

主にOSがページングのために使用する、LRUの高速な近似アルゴリズム。エントリの追加がO(n)であるためアプリケーションなどで使用する一般的なキャッシュアルゴリズムとしてはLRUより低速と認識されその領域では使用されていないが広く蔓延した誤った認識である。リストを使用しないClockはGC管理下の低速なリストにより実装されたLRUよりも高速になりうるものでありさらにビット演算により最悪計算量O(n)を少なくとも32倍高速化できる。JavaScript(V8)における筆者の実装では最も人気かつ主要実装の中で最速のLRU実装であるIsaacsのLRU(ISCCache: lru-cache。LRUCache: 筆者によるより高速な、JavaScriptにおける最速のLRU実装。DW-Cache: Dual Window Cache)の等倍から2倍の速度を実現しており他の多くの言語でも同様にO(n)のClockのほうがO(1)のLRUより高速になる可能性がある。また近似というと低性能の印象があるが上記主要ベンチマークで比較するとClockのほうがLRUよりヒット率が1-2%前後高い場合が多く5-10%以上高い場合もありヒット率の観点からもLRUよりClockのほうが優れている。なぜ我々は長年LRUに甘んじていたのか。

github.com

'Clock    new x 982,257 ops/sec ±4.80% (102 runs sampled)'

'ISCCache new x 11,457 ops/sec ±1.49% (117 runs sampled)'

'LRUCache new x 21,184,221 ops/sec ±0.18% (123 runs sampled)'

'DW-Cache new x 5,459,649 ops/sec ±0.41% (123 runs sampled)'

'Clock    simulation 100 x 10,520,040 ops/sec ±2.24% (120 runs sampled)'

'ISCCache simulation 100 x 8,148,950 ops/sec ±1.87% (119 runs sampled)'

'LRUCache simulation 100 x 9,110,929 ops/sec ±2.52% (118 runs sampled)'

'DW-Cache simulation 100 x 6,778,262 ops/sec ±2.27% (120 runs sampled)'

'Clock    simulation 1,000 x 8,738,216 ops/sec ±2.20% (118 runs sampled)'

'ISCCache simulation 1,000 x 7,298,708 ops/sec ±1.85% (119 runs sampled)'

'LRUCache simulation 1,000 x 8,120,011 ops/sec ±2.55% (117 runs sampled)'

'DW-Cache simulation 1,000 x 6,656,796 ops/sec ±2.28% (119 runs sampled)'

'Clock    simulation 10,000 x 8,546,724 ops/sec ±2.24% (119 runs sampled)'

'ISCCache simulation 10,000 x 6,479,979 ops/sec ±1.81% (120 runs sampled)'

'LRUCache simulation 10,000 x 7,455,903 ops/sec ±2.42% (120 runs sampled)'

'DW-Cache simulation 10,000 x 6,469,169 ops/sec ±1.95% (121 runs sampled)'

'Clock    simulation 100,000 x 5,733,062 ops/sec ±1.61% (118 runs sampled)'

'ISCCache simulation 100,000 x 3,179,438 ops/sec ±1.84% (109 runs sampled)'

'LRUCache simulation 100,000 x 3,746,025 ops/sec ±2.09% (116 runs sampled)'

'DW-Cache simulation 100,000 x 3,319,309 ops/sec ±2.16% (114 runs sampled)'

'Clock    simulation 1,000,000 x 2,949,250 ops/sec ±3.75% (104 runs sampled)'

'ISCCache simulation 1,000,000 x 1,487,123 ops/sec ±3.06% (100 runs sampled)'

'LRUCache simulation 1,000,000 x 1,725,359 ops/sec ±4.29% (106 runs sampled)'

'DW-Cache simulation 1,000,000 x 1,740,517 ops/sec ±2.10% (110 runs sampled)'

SLRU (Segmented LRU)

LRUを固定比率で分割しキャッシュヒットの有無で格納先を変える。適切な比率であればLRUより高い性能が期待できるが適切な比率は用途と状況により異なり当然動的な変化には対応できず汎用のLRU、特化のSLRUの関係にある。しかし試用区間(基本20%)を超える再利用距離のデータは間に他のデータへのヒットが区間超過分ない限り絶対にヒットしないため対象のワークロードにおいて試用区間が不足しないか事前調査を要する。SLRUにはキャッシュが埋まるまでは規定の本来の試用区間を超えて最大で100%まで試用区間が延長されることで本来より捕捉可能な再利用距離が長く高いヒット率で開始されさらに保護区間へのヒットにより捕捉可能再利用距離が延長された状態で動作する暗黙の初回ボーナスがある。このため使用開始直後は初回ボーナスによりヒット率が高くともワークロードやトレンドが大きく変化すると保護区間へのヒットの減少すなわち捕捉可能再利用距離の減少により捕捉可能再利用距離が本来の試用区間に近づき徐々にまたは急激にヒット率が低下する可能性がある。つまり初回ボーナスによるブーストを失うと二度と取り戻せずワークロードの一部を切り取った一般的なベンチマークではヒット率が過大となる可能性があるため正確な比較と評価ができない。このように20%という試用区間の小ささによりワークロードによってはキャッシュが全く機能しなくなるまたはワークロードやトレンドの変化に追従できずヒット率が低下する可能性があるという理論的問題と信頼性の低さがSLRUが先進的キャッシュアルゴリズムの比較対象に含まれない理由であろう。高いヒット率を得られる状況でも逆に保護区間の不足によりヒット率が伸びず相対的に低下する可能性があり帯に長く襷に短い扱いにくさがある。

ARC (Adaptive Replacement Cache)

SLRUの比率をキャッシュサイズの(本体と合わせて)2倍の履歴とキャッシュヒットにより動的に変更することで動的な変化に対応する。高いヒット率から人気があったが特許により使用が制限されていることと4つのリストを操作するオーバーヘッドの高さから忌避されている。そのため多くのプロダクトがLRUに甘んじるかSLRUを劣化版ARCとして任意の固定比率で妥協して使うか粉飾欠陥クソアルゴリズムのLIRSを騙されて採用し当然クラッシュするもいまさら低性能な(S)LRUに戻すこともできず惰性で騙し騙し使うはめになった(プロプライエタリでは特許に抵触しないよう改変したARCを使う場合もあるようだ)。その後はすっぱい葡萄もあってかキャッシュアルゴリズムの性能はワークロードに依存しARCはそれほど優れたアルゴリズムではないとディスられ続けている(代わりの優れたアルゴリズムを提示できるわけでもないのに)。実際ARCはスキャン耐性が低くループ耐性もないため現在では時代遅れのアルゴリズムと言っても過言ではなく実装に使うビルトインAPIの制限によりLRUより履歴のぶん少ないサイズしか指定できない場合もある(JavaScriptのV8のMapは最大224エントリだがより少ない1000万でもLRUが落ちる場合が見られARCはわずか500万で落ちた)。なおARCの基本特許はすでに切れている*1がすでに上位互換のDWCがあるため用済みでありいまさら戻ってこいと言われてももう遅い！

LIRS

キャッシュサイズの最大2500倍の履歴を保持するため採用プロダクトをメモリ不足でクラッシュさせてきた詐欺アルゴリズム。どこも他のアルゴリズムに変えるか履歴サイズをパラメータ化して責任転嫁して無理やり使っているため本当の性能は誰にもわからない。論文が著名で多数の有名プロダクトで採用実績があっても信頼できる優れたアルゴリズムである証明にはならないのである。履歴はLIR末尾またはHIRエントリにヒットするか最大値に達するまで拡大し続けヒットすると条件を満たすまで履歴をたどり一括削除するためレイテンシスパイクの原因ともなる。メインメモリのランダムアクセスレイテンシ約100nsを基準とするとLinked Listだけでも履歴含め10,000,000エントリの一括削除で1秒の停止とスパイクとなり辞書の削除を合わせるとさらに悪化する。またスループットもリストなどの非常に長い参照のGCには急速に所要時間が増える転換点がある場合があり数倍の履歴でもスループットが急速に低下するためそのようなGCを持つ言語ではメモ化などのキャッシュによる高速化が50%以下と低い場合履歴サイズが転換点を超えるとLRUやキャッシュなしのほうが速くなるリスクが高い(JavaScriptのV8ではDoubly Linked Listは1万から10万ノード、Mapは10万から100万エントリ付近からスループットがノード数10倍あたり約1/2から1/3に急速に低下するよう変化する)。キーの検索にマップを使っていれば当然マップも履歴のぶん肥大化および低速化し、LIRSの実用的な履歴サイズの推奨値は3−10倍である。クラッシュの実害とこれらの問題にもかかわらず使われ続けたのは当時ループ耐性のある高性能キャッシュアルゴリズムが他になくいまさら(S)LRUに戻せなかったからであろうが現在は他にもループ耐性を持つDWCとW-TinyLFUがありとっくに唯一の選択肢ではなくなっているためあえて危険で性能もわからないLIRSを使う必要はない。なお近年の研究ではキーの履歴サイズはキャッシュサイズの2倍が規範的標準となっている様子が伺え今後適切な履歴サイズが定まるまでせいぜい3倍が限度だろう。

TinyLFU

非常に高性能な新キャッシュアルゴリズムとして知られているが実際には本当に性能が高いのはW-TinyLFUだけでTinyLFUのヒット率は総合的にはLRUより悪いことが論文に明記されており、人気の高いRistrettoは特に論文通りのSLRUでなくLFUをメインキャッシュに使用しているためヒット率が大きく低下するワークロードが生じていることに注意しなければならない(OLTPではLRUより大幅に悪く、トレンドの変化が大きいワークロードではLFUの特性により同様に性能が低い可能性がある)。ブルームフィルタ(CountMinSketch)は削除操作不可能であるためキャッシュエントリを削除するほど偽陽性および偽陰性が増え一定期間内の任意または有効期限超過による削除数に比例して性能が低下する。またブルームフィルタがバーストアクセスで飽和し性能がSLRUの水準にまで低下する可能性があるため性能劣化の脆弱性を抱えているに近い状態であり適切にオートスケールできなければ攻撃や肝心な大量アクセスで想定以上の急速な性能劣化に耐えられない可能性がある。スキャン耐性皆無のLRUほどではないがW-TinyLFUの危険(不安全)な未完成品というのがTinyLFUの実態であり用途に対してトレードオフが許容可能か検討と検証なしに使うべきでないアルゴリズムである。さらに定期的にブルームフィルタの一括リセットのための非常に大きな反復処理が走りレイテンシスパイクが生じる。ブルームフィルタのサイズはキャッシュサイズ(最大エントリ数)の10倍であるためキャッシュサイズが10,000,000で100,000,000回(Ristrettoなど実装とサイズによっては最大でさらに2x4で8倍の800,000,000回、メモリ消費は1要素8bit(1byte)であるため400MB(100MBx4)から800MB(200MBx4))の反復処理となり、反復1回10nsでも1秒(8秒)の停止とスパイクが生じ、キャッシュサイズ、言語、実装により容易に悪化する。(W-)TinyLFUのレイテンシは許容限度を超えており少なくとも現在の実装ではオンラインサービスなどレイテンシが考慮される用途ではエンタープライズレベルではスケーラビリティが低すぎて使い物にならないだろう(にもかかわらずオンラインで使ってるところはおそらくキャッシュサイズがさほど大きくないかスパイクに気づいてないか放置している)。(W-)TinyLFUは近年人気の高いキャッシュアルゴリズムだがレイテンシに重大な欠陥が存在するにもかかわらずこれを認識せず盲目的に使われているように見える。なお(W-)TinyLFUはキーをブルームフィルタに変換する必要があるためキーのポインタのアドレスを取れないような変換コストが高い言語ではオーバーヘッドが高い(JavaScriptは非常にオーバーヘッドが高くなる言語の一つである)。またポインタのアドレスを使用する場合はアドレスの再利用により偽陽性が生じヒット率が低下する可能性がありどのような状況でどの程度低下するかは未知数である(同じアドレスが頻繁に再利用されれば当然著しく低下する)。ベンチマークに使用されているブロックアクセスにおいても書き込み範囲のアドレスにおいて同じ問題が生じるはずでありブルームフィルタから減算するとしないとにかかわらず精度が低下するが公式実装であるCaffeineにおいてもこの精度低下が生じない方法で測定(書き込み範囲はキャッシュに追加または無効化されなければならないはずだが単に処理が省略されている)されているため書き込みを含むワークロードの公表されているヒット率は誤った測定方法による不正確なものである疑いがある。

W-TinyLFU

最もヒット率の高いキャッシュアルゴリズムだが削除頻度が高いかレイテンシ要件がある場合は前述の問題のため採用できないだろう。よく見られるW-TinyLFUのヒット率はおそらく動的ウインドウのもの(まさか比率指定を隠したチェリーピッキングではなかろう)で固定ウインドウの実装を使うならば適切なウインドウ比率を自分で設定しなければならない。動的ウインドウのW-TinyLFUはキャッシュを頻繁に作り直さずレイテンシに寛容またはキャッシュサイズが小さくエントリを頻繁に削除せずその言語で効率的に実装できるのであれば優れた性能を期待できる。ただしCaffeineでは動的ウインドウとインクリメンタルリセットが実装されているものの両方を使用した場合のヒット率は明らかでなく動的ウインドウとインクリメンタルリセットを備えた実装が期待通り全般的に高性能であることを実証するデータはない。またインクリメンタルリセットする場合でも1アクセスごとに配列要素を40個(10x4)もリセットしなければならず本質的にオーバーヘッドが高いためレイテンシへの要求水準の高いインメモリKVSやメモ化などでの有用性は限定的とならざるを得ない。エントリサイズが小さければ前述のようにオーバーヘッドの比率が上がりヒット率で補えないほどキャッシュサイズごとヒット率が下がる。さらにOSや言語のメモリ割り当て方法によっては前述のようにメモリアドレスの頻繁な再利用によりヒット率が著しく低下する可能性があるため信頼性が低い。要するに性能低下要因が多くDWCのように何も考えず何にでも使えるアルゴリズムではなく取り回しが悪い。DWCは万能な軽量級でありW-TinyLFUは条件を満たせば最高性能を発揮する重量級である。なおW-TinyLFUは形式的にはエヴィクションアルゴリズムなしには機能しないアドミッションアルゴリズムだが動的ウインドウを備えたものは本質的にはARCやDWCと同様にウインドウキャッシュ(LRU)とメインキャッシュ(SLRU)の2つのキャッシュ比率を適応的に調整するエヴィクションアルゴリズムであると言える。

評価項目

falsandtru.hatenablog.com

*1:https://patents.google.com/patent/US7167953B2/en、もう一つ追加の特許https://patents.google.com/patent/US20070106846A1/enがあるがどう関係するかよくわからない