キャッシュアルゴリズムの評価項目

algorithm

キャッシュアルゴリズムを選定する際の基本的な評価項目。これらを広く満たすほど汎用性が高くなる。

ヒット率(ワークロード)

用途を特定できないがLRUよりヒット率の高いキャッシュアルゴリズムを求める場合LRUより有意にヒット率の低い代表的ワークロードのあるキャッシュアルゴリズムは基本的に避けるべきである。特定の用途で使う場合ヒット率は目的のワークロードに近いベンチマークを参考にしなければならない。DS1はERPアプリケーションによる(おそらく反復的)データベースディスクアクセス、S3はウェブ検索エンジンによるデータベースディスクアクセス、OLTPはトランザクションにより歪んだデータベースディスクアクセス、GLIはループアクセスである。ベンチマークの多くはブロック単位のディスクI/OであるためKVSによるキャッシュサーバーの参考にはしにくいがウェブ検索エンジンのアクセスであるS3とコンテンツの統計的頻度を表すZipfはある程度参考になるだろう。なおキーと値が64bit数値または平均8文字の英数字であればDWCはLRUの95%、ARCの176%、LIRSの402%、W-TinyLFUの211%のキャッシュサイズを同じメモリサイズで使用できることからDWCのメモリあたりのヒット数はW-TinyLFUと同等か大きく超える。

耐性(レジスタンス)

ベンチマーク上のヒット率が高くとも実際には耐性の欠如によりヒット率が大幅に低下する可能性がある。基本的にはScan耐性とLoop耐性があればよくこの耐性がない主要キャッシュアルゴリズムはLRU、SLRU、ARCである。基本的耐性があっても固有の脆弱性を抱えるものもあり特定の集中的アクセスによりLIRSは履歴が肥大化、TinyLFUはヒット率が低下する。基本的耐性を完備し脆弱性のないものはDWCとW-TinyLFUだけである。

空間計算量(メタデータ)

キャッシュアルゴリズムには履歴などキャッシュサイズに比例して増加するメタデータを保持するものが多いことに注意しなければならない。除去されたエントリのキーを保持して履歴とするキャッシュアルゴリズムはGC付き言語では履歴保持に使用するLinked ListをGCが管理するコストにより履歴サイズに比例して低速化する。またマップも履歴を保持しなければならないため肥大化し低速化する。キーまたはキーの参照先のサイズが大きい場合履歴がこれを保持しメモリを解放できないためメモリを大きく圧迫する。履歴のキーサイズは本体と合わせて2倍のものが一般的だがLIRSは最大2500倍にもなり当然メモリ不足でクラッシュする。厳密には履歴サイズを減らせばそのぶんキャッシュサイズを増やしてヒット率とヒット数を上げることができメモリ効率が上がるため履歴サイズの異なるアルゴリズムを同じキャッシュサイズとヒット率で比較することはできずメモリあたりのヒット数で比較しなければならない。

時間計算量(レイテンシ)

キャッシュアルゴリズムには一括処理により長時間停止しレイテンシスパイクが生じるものがあることに注意しなければならない。(W-)TinyLFUはキャッシュサイズの10倍のブルームフィルタ4個を一定間隔ごとに反復処理により一括リセットするため反復1回10nsとしてもキャッシュサイズ10,000,000(エントリ)でリセットに1秒から8秒を要する計算になる。LIRSも履歴を適宜一括削除する処理があり最大2500倍の履歴に対して無制限の一括削除が実行される。メモリのランダムアクセスレイテンシが約100nsであるため履歴の一括削除はLinked Listで保持されるものだけでも10,000,000エントリで1秒を要し辞書の削除と合わせるとさらに悪化する。

レイテンシ(スループット)

キャッシュは原則としてキャッシュヒットのレイテンシがキャッシュミスのレイテンシ以下でなければならない(このレイテンシは本質的にはスループットであるがキャッシュの速度は理論的にはアクセス単位で測定されるため一定時間内のスループットでなくアクセスのレイテンシとして説明される)。これはインメモリKVSやメモ化で顕著な問題であり履歴など線形に増加するメタデータを保持するキャッシュアルゴリズムはメタデータを保持しないLRUなどの単純なキャッシュアルゴリズムより2倍以上低速となり高速化可能な対象が大幅に減る結果になりやすい。どれだけヒット率が高くともキャッシュしたほうが遅くなるならそのキャッシュアルゴリズムは役に立たないし使われないのである。(W-)TinyLFUはブルームフィルタをインクリメンタルリセットする場合でも1アクセスごとに配列要素を40個(10x4)から80個(20x4)もリセットしなければならずこのオーバーヘッドによるレイテンシ増大は同期処理において許容できないほど大きい場合も多いだろう。キャッシュミスがほとんどない場合はClock系アルゴリズムのほうが並べ替えを行わないぶん高速に動作する。特にレイテンシが重要な場合サンプリングによりヒット率を低下させてでも高速化される。

言語差(実装可能性)

キャッシュアルゴリズムには実装可能性(現実的に意味のあるものが実装可能か)が言語に依存するものがある。(W-)TinyLFUはキーをブルームフィルタに変換できなければならないためこの変換コストが高いJavaScriptなどでは低レイテンシな実装が困難となり用途が制限される。またLinked ListはGCの管理により非常に低速となるためARCやLIRSなど履歴保持にLinked Listを使用するキャッシュアルゴリズムはGCなしで実装できる言語かによってレイテンシと適用範囲からのLRUに対する優位性、ひいては有用性が大きく異なる。さらにLinked Listで実装されるLRU自体も同様に低速となるため配列で実装されたClockのほうがLRUより高速となる可能性がありビット演算により高速化されたClockはLRUより高速となる可能性が高い。LRUはJavaScriptにおいて主要というか事実上唯一のキャッシュアルゴリズムだがほとんどの場合より高速なClockに対して何ら優位性がなくGC管理下の遅いLRUを無意味に使い続けているだけである。

比較

主要キャッシュアルゴリズムの具体的比較は以下を参照。

falsandtru.hatenablog.com