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

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

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

用途を特定できないがLRUよりヒット率の高いキャッシュアルゴリズムを求める場合LRUより有意にヒット率の低い代表的ワークロードのあるキャッシュアルゴリズムは基本的に避けるべきである。特定の用途で使う場合ヒット率は目的のワークロードに近いベンチマークを参考にしなければならない。DS1は連続的(おそらく反復的)ディスクアクセス、S3は非連続的ディスクアクセス、OLTPはトランザクションにより歪んだディスクアクセスである。ベンチマークの多くはディスクアクセスであるためキャッシュサーバーの参考にはしにくいが非連続的アクセスであるS3とコンテンツの統計的頻度を表すZipfは参考になるだろう。

耐性(レジスタンス)

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

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

キャッシュアルゴリズムには履歴などキャッシュサイズに比例して増加するメタデータを保持するものが多いことに注意しなければならない。除去されたエントリのキーを保持して履歴とするキャッシュアルゴリズムはGC付き言語では履歴保持に使用するLinked ListをGCが管理するコストにより履歴サイズに比例して低速化する。またマップも履歴を保持しなければならないため肥大化し低速化する。キーまたはキーの参照先のサイズが大きい場合履歴がこれを保持しメモリを解放できないためメモリを大きく圧迫する。履歴のキーサイズは本体と合わせて2倍のものが一般的だがLIRSは最大2500倍にもなり当然メモリ不足でクラッシュする。(W-)TinyLFUも履歴をキーサイズで他のアルゴリズムと比較できず論文のタイトルで高効率が謳われているので小さいと錯覚しそうになるが実際には1エントリあたり40byteから80byteのオーバーヘッドがありARCなどと同様にキーを直接保持する方式に換算すると32bit整数キーで10倍から20倍、8文字の文字列キーで5倍から10倍の履歴サイズとなり実際の空間効率(空間計算量)はむしろLIRSの一般的履歴サイズ3倍から10倍より悪いとすら言える。

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

キャッシュアルゴリズムには一括処理により長時間停止しレイテンシスパイクの原因となるものがあることに注意しなければならない。(W-)TinyLFUは一定間隔ごとにブルームフィルタを一括リセットしキャッシュサイズ10,000,000(エントリ)でリセットに1秒から8秒以上かかる計算になる。LIRSも履歴を適宜一括削除しなければならず最大2500倍の履歴に対して無制限の一括削除が実行される。

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

キャッシュは原則としてキャッシュヒットのレイテンシがキャッシュミスのレイテンシ以下でなければならない(このレイテンシは本質的にはスループットであるがキャッシュの速度は理論的にはアクセス単位で測定されるため一定時間内のスループットでなくアクセスのレイテンシとして説明される)。これはインメモリ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を完全に無意味に使い続けているだけである。

比較

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

github.com

github.com

falsandtru.hatenablog.com

PjaxとSPAの違い

PjaxとSPAが全く同じ技術構成なのを知らずにPjaxを過去の技術だと思ってる知ったかぶりが多いので最も高度で完成度の高いPjaxライブラリであるpjax-apiの作者の自分が説明しておこう。

SPAとはPjaxをバンドルしたフレームワーク

Pjaxとはその語源からしてpushState+Ajaxである。そしてSPAの技術構成はフレームワーク+pushState+Ajaxである。すなわちSPAとは本質的にPjaxをバンドルしたフレームワークに過ぎない(Pjaxと対比されるSPAはツールセットとしてのSPAでありこれはアプリケーションフレームワークとしてしか存在し得ない。字義通りのSPAはSPAフレームワークで作ろうとPjaxで作ろうと何で作ろうとSingle Page ApplicationであればSPAである)。SPAを使っている限りPjaxも使っているのでありPjaxが過去の技術のごとき言説は無知を晒しているだけである。なおウェブ標準的にはAjaxはfetchに置き換えられているがPjaxも内部のAjaxをfetchに置き換えるのに何の支障もないので名前が古いままになるだけである。

実質的差異はデータフォーマットだけ

PjaxはAjaxなどの非同期通信APIによりHTMLを取得しページを更新するがSPAはJSONを取得しページを更新する。PjaxとSPAの共通部分の実質的差異は取得するデータのフォーマットがHTMLかJSONかという非同期通信の運用上の差異しかないのである。

HTMLとJSONで何が変わるか

データフォーマットをHTMLからJSONに変える主な利益はデータサイズである。HTMLよりもJSONのほうが簡潔で小さい。しかしPjaxでもそのような実装はやろうと思えば当然可能であり設計方針の違いでしかない。それよりもSPAがサーバーサイドの技術選択を制限する不利益のほうが大きい。

クライアントサイドにおいてはJSONを使用するSPAのほうが効率的に見えるがHTMLベースのPjaxでもHTMLリクエスト先のURLをテンプレートに書き換えることでローカルキャッシュを使わせ並行してリクエストした差分JSONとテンプレートを合成したHTMLを使用してページを更新できpjax-apiはこの更新方法をサポートしている。初回ページ遷移時のテンプレートリクエスト分のデータサイズはかかるが数百文字程度しかなく差分データやSPAにより肥大化したHTMLとCSSとJavaScriptに比べれば微々たるものである。

サーバーサイドにおいてもSPAは専用のフレームワークやライブラリのサーバー上での使用を要求しこれはほとんどの場合JavaScriptであるためJavaScriptという低速な言語によりサービスのスループットもレイテンシも非常に悪く不経済なものとなる。GoやRustなど他の高速な言語との組み合わせは不可能ではないが一般的とは言い難く自力で解決しなければならない部分が多いだろう。対してPjaxはブラウザ上で完結したライブラリであるためサーバーサイドの制約がなく任意の高速な言語と技術構成でサーバーを構築できる。

SPAとPjaxの実用上の違いはフレームワークとライブラリの違いであり既成品の組み立てキットを組み立てるか自分で図面を引いて部品を作って組み立てるかの違いである。設計能力も実装能力も兼ね備えた優れた開発者にとってフレームワークは耐え難く不自由でライブラリでなければ思い通りのものを作れない。設計能力の欠けた者、セミオーダーの既成品を量産するような仕事をしている者、とにかく早くプロトタイプを作らなければならない者にはフレームワークが適しているが最高の一点物を作るにはライブラリである。必要ならフレームワークもライブラリも自分で作るのが最高峰の世界である。

将来のPjax

Pjaxを構成するpushStateなどのHistory APIに代わるNavigation APIが現在策定中でありこれが標準化されればPjaxは名称と実装が完全に異なるものとなってしまうがライブラリとしては依然として内部実装を更新するだけで済むことである。機能的にもNavigation APIは基本的に既存APIを使いやすく再構成した便利API集で、現在のSPAとPjaxがすでに特に不足のないサービスを実現しているように基本機能は既存APIで足りている。従来不可能だったことが可能になる部分もあるものの現在特に不便を感じないように実際上ほとんど必要にならないものである。具体的にはリンクなどによるページ遷移の完全な捕捉と、厳密な遷移状態と遷移履歴の提供であるがオーバーエンジニアリングとユーザーの行動追跡が促進されるだけである。そんなことより既存の標準APIを正しく実装しろと言いたい。History APIの一部であるscrollRestoration APIはFirefoxではずっと壊れており、Chromeでは正しく動作していたが最近壊れて共に用をなさなくなった。いずれFirefoxが修正すると思って放置してたがまさかChromeが壊してくるとは思わなかった。おかげで諦めて独自のワークアラウンドを実装することになったがこのようにNavigation APIがなくともほとんどのことはできるのである。むしろ単機能のHistory APIすら実装できてないのに遥かに複雑な統合的APIであるNavigation APIを正しく実装できるのか疑問になる。Navigation APIのプロダクションレベルのブラウザ互換が確保されるまで標準化から早くとも5年程度はかかるだろう。ちなみに他のPjaxライブラリを使うのはやめとけどれだけ有名でもクソ実装だ。

ACVDはなぜ失敗したのか - マップとリスポンと没入感

ACVで毎日一時間以上待ッチングしてた自分だがACVDは大幅に短い時間でマッチングできるようになったにもかかわらずわずか数ヶ月でやめた。何が悪かったのか？

マップがミスマッチング

ACVではほとんどのマップが比較的狭く遮蔽物の多い要所で至近距離から一気に乱戦に持ち込み決戦できるようにデザインされていたのに対しACVDは遮蔽物に乏しい開所を被弾しながら突破しなければならないマップが多い。これは数十人でリスポンしながら戦うFPSのマップデザインである。おそらくACVDのマップデザイナーはFPSのマップデザインをそのまま輸入したのだろう。もちろんこれは4vs4リスポンなしのACVDにマッチしない。このような多数の犠牲を出しながら物量で突破する上陸戦や要地攻略のような戦闘はFPSのように多人数でリスポンしながら戦わなければ成立しない。にもかかわらずACVDでは侵攻側は明らかに集中砲火を受けるだだっ広い開所に突撃することを強いられ防衛側は豊富な遮蔽物に隠れながら集中砲火を浴びせることができる。このような地理的優劣はACVにもあったがACVDの地理的優劣の格差はACVの何倍も大きく著しく不利な戦闘をリスポンなしで強いられるうえ侵攻序盤の開所のマップのほうが終盤の閉所のマップより接近困難で不利なマップになっており難易度が序盤が難しくと終盤が易しいと序盤と終盤で逆転している。さらにACVDの開所のマップは開所であるゆえACVと違い侵攻ルートからの逸脱を制限し正しい侵攻ルートに誘導することが困難であり初心者ほど容易に無意味に分散し各個撃破される誘引が序盤ほど強い。これほど初心者に不利なゲームデザインではユーザーが離脱して当然である。ヘビーユーザーでランクマ上位の自分ですら離脱したのだ。アーマードコアは大型機械に乗って広い空間を機動するゲームであるが個の力がいかに強大であろうとわずか4vs4で万単位の兵力をぶつけ合う軍事作戦を再現することは不可能であり4vs4の集団戦は本質的にはむしろ少数精鋭の特殊部隊の襲撃作戦に近い。したがってアーマードコアの対人戦はどれだけ軍事的要点を押さえた戦場を再現しようとその戦闘は特殊部隊の市街戦や屋内戦のように豊富な遮蔽物を利用して接近し近距離で決戦を行うものでなければならないのである。

リスポンの不在

マップと戦闘を適切にデザインしても死亡後リスポンできず戦闘終了まで無力感を味わい続けることを強制されるのはやはり優れたゲームデザインとは言えない。何かしらの十分な希望を持って戦闘の経過を見られるようにすべきだろう。生き残ったプレイヤーとしてもチェスの終盤戦のように貧弱な戦力で長期戦になるのは退屈であり将棋のように最後まで劇的な戦いができたほうが面白いのは明らかである。したがってやはりゲームとしてリスポンは提供するべきである。しかしリアル寄りのゲームで4vs4でゾンビのように復活して戦ってもリアリティが損なわれ面白くない。そこでストック制を提案したい。出撃部隊は最大出撃数、ACVDなら4機から残存機体数を引いた数を上限として倒した敵の数だけリスポンをストックしリスポンできる。つまり4機生存してるなら1機もストックできず3機生存なら1ストック可能、1機生存なら3機ストック可能、全滅してもストックがあればリスポン可能となる。実際の出撃数でなく最大出撃数を基準とすることで少人数で出撃または回線落ちした側に戦力差を補う優位性を与えることができる。

没入感がない

ACVと比べてACVDはなんか後方視点から見える自機が小さく見えて没入感がなかった。これがACVDを短期間でやめた一番大きな理由かもしれない。ベースサイズよりブースト時の最小サイズ？視界は広いほうが戦闘に有利だが戦い続けることが第一なので調整できるようにしてもらいたい。

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

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

LRU

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

• https://www.npmjs.com/package/tinylfu
• https://www.npmjs.com/package/w-tinylfu
• https://www.npmjs.com/package/node-cache

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より高速になる可能性がある(ClockProなどは履歴を要するためLRUより低速になる可能性が高い)。また近似というと低性能の印象があるが上記主要ベンチマークで比較するとClockのほうがLRUより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%)を超える再利用距離のデータは間に他のデータへのヒットが区間超過分ない限り絶対にヒットせずそのようなワークロードは案外あるので案外使いどころが限られ事前調査を要する。

ARC (Adaptive Replacement Cache)

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

DWC (Dual Window Cache)

時間空間ともに定数計算量でありながら高水準のヒット率と耐性を実現する最高性能の定数計算量キャッシュアルゴリズム。DWCよりヒット率の高い主要アルゴリズムはLIRSと(W-)TinyLFUしかないが後述するようにLIRSは性能を粉飾したために致命的欠陥が生じており(W-)TinyLFUも用途に制限があるためDWCがすべての主要汎用キャッシュアルゴリズムの中で最小の計算量でありながら最高の性能となる(マイナーな他のアルゴリズムは共通のベンチマーク結果を公開していないため比較不能、W-TinyLFUは動的ウインドウとインクリメンタルリセットを備えたものはおそらく最高性能の汎用アルゴリズムだが現在該当する実装はCaffeine以外見当たらず、Caffeineにおいても両機構使用時のベンチマーク結果はなく、論文そのままの固定ウインドウと一括リセットの実装は汎用性が低いため無調整で全般的に高性能なDWCと同等以上の汎用性をCaffeineが実際に備えていることを実証する具体的資料はない。また1エントリあたり40byteのオーバーヘッドがあるためエントリが小さい場合W-TinyLFUのオーバーヘッドの分DWCのキャッシュサイズを増やしたほうが全体的な性能が高い可能性もある)。LIRSとTinyLFUは一般的ワークロードにおいてLRUより大幅に劣る場合があるがARCは最大性能が低いものの安定してLRUより性能が高くARC系のDWCも非常にキャッシュサイズが小さい場合を除き全般的にLRUより性能が高い。またLRUより高性能なアルゴリズムの多くがエントリ削除後もキーを保持し履歴として使用する線形空間計算量のアルゴリズムであり標準ライブラリなどの標準的なキャッシュAPIではLRU同様エントリ削除と同時にメモリ解放可能な定数空間計算量のアルゴリズムが第一に求められるだろう(LRUを一般的に置換・陳腐化可能なアルゴリズム、(S)LRUより大幅に高性能な定数計算量アルゴリズム、ループ耐性のある定数計算量アルゴリズム、たぶんすべてにおいて史上初)。ただし情報量(履歴)の不足を補うため全体的に統計精度への依存度が上がっており標本サイズが小さくなるほど情報量と統計精度の低下により性能低下しやすくなる。メインアルゴリズムの統計精度が1パーミルであるため推奨キャッシュサイズは1,000以上となる。LRUしかない地獄のJavaScript界で絶対にLRUなんて使いたくない作者により作られた。主に3つの新機構による複合構成となっている。名前はメインアルゴリズムにおいて概念上キャッシュ比率の計算に2つのSliding windowを使用することに由来するが実装上は1つのウインドウから両方の計算結果を算出するよう簡略化している。単にSliding Window Cacheとしたほうが簡潔だが多くの論文で異なるセマンティクスでSliding windowが用いられているため混乱を避けるためこの名前を避けている。上記のグラフは主要ベンチマークにおける主要アルゴリズムの比較でありDWCが定数計算量でありながら先進的な線形計算量アルゴリズムと同等の性能を実現している画期的アルゴリズムであることを示している。このような定数計算量キャッシュアルゴリズムは他になくDWCが唯一である。

github.com

LIRS

キャッシュサイズの最大2500倍の履歴を保持するため採用プロダクトをメモリ不足でクラッシュさせてきた詐欺アルゴリズム。どこも他のアルゴリズムに変えるか履歴サイズをパラメータ化して責任転嫁して無理やり使っているため本当の性能は誰にもわからない。論文が著名で多数の有名プロダクトで採用実績があっても信頼できる優れたアルゴリズムである証明にはならないのである。履歴はLIR末尾またはHIRエントリにヒットするか最大値に達するまで拡大し続けヒットすると条件を満たすまで履歴をたどり一括削除するためレイテンシスパイクの原因ともなりメインメモリのランダムアクセスレイテンシ約100nsを基準とすると履歴含め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の実態であり用途に対してトレードオフが許容可能か検討と検証なしに使うべきでないアルゴリズムである(SLRUをDWCに置き換え最悪性能を底上げすることで相当程度軽減できるだろう)。さらに定期的にブルームフィルタの一括リセットのために非常に大きなループ処理が定期的に走りレイテンシスパイクが生じる。ブルームフィルタのサイズはキャッシュサイズ(最大エントリ数)の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は近年人気の高いキャッシュアルゴリズムだがレイテンシに重大な問題が存在するにもかかわらずこれを認識せず盲目的に使われているように見える。空間計算量(メモリ使用量)も履歴をキーサイズで他のアルゴリズムと比較できず論文のタイトルで高効率が謳われているので小さいと錯覚しそうになるが実際には1エントリあたり40byteから80byteのオーバーヘッドがありARCなどと同様にキーを直接保持する方式に換算すると32bit整数キーで10倍から20倍、8文字の文字列キーで5倍から10倍の履歴サイズとなり実際の空間効率(空間計算量)はむしろLIRSの一般的履歴サイズ3倍から10倍より悪いとすら言える。

W-TinyLFU

最もヒット率の高いキャッシュアルゴリズムだが削除頻度が高いかレイテンシ要件がある場合は前述の問題のため採用できないだろう。よく見られるW-TinyLFUのヒット率はおそらく動的ウインドウのもの(まさか比率指定を隠したチェリーピッキングではなかろう)で固定ウインドウの実装を使うならば適切なウインドウ比率を自分で設定しなければならない。動的ウインドウのW-TinyLFUはキャッシュを頻繁に作り直さずレイテンシに寛容またはキャッシュサイズが小さくエントリを頻繁に削除しないのであれば非の打ち所のない性能だろう。Caffeineではインクリメンタルリセットが実装されておりヒット率は明らかでないが2回目以降のリセットは相対間隔が等しいことから本質的に等価と考えられる。ただし動的ウインドウとインクリメンタルリセットを備えた実装が期待通り全般的に高性能であることを実証するデータはない。またインクリメンタルリセットする場合でも1アクセスごとに配列要素を40個(10x4)もリセットしなければならず本質的にオーバーヘッドが高いためレイテンシへの要求水準の高いインメモリKVSやメモ化などでの有用性は限定的とならざるを得ない。さらに(W-)TinyLFUはキーをブルームフィルタに変換する必要があるためキーのポインタのアドレスを取れないような変換コストが高い言語ではオーバーヘッドが高い(JavaScriptは非常にオーバーヘッドが高くなる言語の一つである)。W-TinyLFUは形式的にはエヴィクションアルゴリズムなしには機能しないアドミッションアルゴリズムだがウインドウ比率を動的に変更する最も高度なW-TinyLFU(Caffeine)は本質的にはARCやDWCと同様にウインドウLRUと(S)LRUの2つのキャッシュ比率を適応的に調整するエヴィクションアルゴリズムであると言える。

評価項目

falsandtru.hatenablog.com

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

地球火星人学の論理的誤謬 (脅威インテリジェンスの教科書/石川朝久)

脅威インテリジェンスの教科書(初版1刷)の中に論理的誤謬を発見したので記録しておく。本書コラムの地球火星人学において著者石川朝久はヘンペルのカラスの代わりに説明する論理的に同一の説明として地球火星人学(初出はおそらく村上陽一郎教授)を提示している。地球火星人学は火星に行けない地球人が火星人が四本足であることを地球上で証明するには四本足でなければ火星人でないことを証明すればよいと説き著者はこれをすべての星を調査しなければならず非現実的であると解説するがここまでに3つもの誤謬を犯している。

1. 四本足でないものをすべて調査するためには火星の四本足でないもの(火星にいる五本足の火星人は火星を調査しなければ発見できない)も調査しなければならず火星を調査範囲から除外して四本足でなければ火星人でない(火星を含め四本足でない火星人がおらず四本足でない火星人が存在しないことから火星人は四本足でしか存在しえない)ことは証明できないことから火星を調査しないというこの証明の制約を満たすことは不可能であることが証明される。
2. 火星に行けない代わりの証明方法でありながら火星も調査しなければならないことから他のすべての星を調査する証明コストは論ずるに及ばないものであり他のすべての星の調査をするまでもなく証明方法に誤りがあることを指摘しなければならない。
3. ヘンペルのカラスは本来の証明対象こそ調査せずともよいが特定範囲外すべてにおいて調査証明すれば特定範囲内においては調査証明せずともよしとする除外範囲を認める論理ではないため非網羅的調査範囲という要素を追加する地球火星人学はそもそもヘンペルのカラスと論理的に全く異なる。
4. 大目に見て数に含めていないがそもそも火星を調査する代わりに他のすべての星を調査しなければならないことを自ら解説した時点で火星に行けない代わりという前提から破綻していることに気づかなければならない。

以上の致命的誤謬があることから読者はこのコラムを正しいと誤解してはならず著者はこのコラムを削除または全面改訂すべきである。

Reverseパターン

非純粋関数を合成可能な擬似純粋関数にするデザインパターン。非純粋関数の返り値を逆操作関数にすることで疑似純粋化し逆操作関数を無引数無返り値に統一することで合成可能化する。操作は逆操作により副作用を残さず中止および終了され複数の操作はArrow演算により単一の操作に合成される。

function proc(): () => void {
  return aggregate(
    bind(el, type, listener),
    bind(el, type, listener));
}

function bind(el, type, listener): () => void {
  el.addEventListener(type, listener);
  return () => el.removeEventListener(type, listener);
}

function aggregate(...as: (b => c)[]): b => c[] {
  return b => as.map(f => f(b));
}

https://github.com/falsandtru/spica/blob/master/src/arrow.test.ts

ゼロトラストセキュリティの基本概念

境界防御からゼロトラストセキュリティへの変遷を通してゼロトラストセキュリティの基本概念を解説する。

境界防御

水際防御とも呼ばれる境界防御は概ね単一かつ唯一の防衛線を設置しこの最終防衛線を死守するセキュリティモデルである。 一度でも突破されればもはや守るもののない一度たりともミスの許されない脆弱なセキュリティモデルでありトロイの木馬により容易に内部に侵入できるITセキュリティと極めて相性が悪い。

多層防御

セキュリティに何よりも求められるのは侵入の検知から対処までの時間的猶予である。多層防御は複数の防衛線を設置し可能な限り外側の防御線で早期に侵入を検知することでさらに内側の防御線の突破に要する時間を対処までの時間的猶予に変えるものでありその概念は縦深防御との同一性から容易に理解できる。しかしながらトロイの木馬による侵入容易性に対する解決にはならず内側の未突破の防衛線以外に基本的に侵入および展開を遮るものがないため侵入箇所より内側の防衛線より外側すべてが侵害可能範囲となり致命的ではなくとも非常に大きい被害が生じる可能性が高い。

ゼロトラストセキュリティ

ゼロトラストセキュリティは微視的には多層防御の縦の防御に横の防御と内側への防御を加えるものであり、全ノードが全周防御、いわば要塞化することでこれを実現し被害の周辺部への拡大を防ぎ局所化するセキュリティモデルである。巨視的には侵入者が重要部を制圧するまでに突破する必要のある防衛線の数と強度を十分に確保できるノード配置および動線の設計であり、被害の局所化はその効果、全（周辺）ノードのセキュア化はその前提である。

ゼロトラストセキュリティは本土防衛戦争と解釈すると理解しやすい。侵入者は国内に侵攻または国内で武装蜂起した敵軍であり我が方は首都の防衛成功を勝利条件とする。首都防衛を達成するためには侵攻および蜂起箇所から首都までの間に防衛線を設置しここで食い止める必要がある。ゼロトラストセキュリティにおいて防衛線はサーバーおよびネットワーク機器等の各ノードが個々に展開する多層防御でありこれは要塞化された都市に相当する。我が方は敵軍が首都を制圧するまでに可能な限り多くの要塞都市を経由させることで可能な限り多くの防衛線の突破を強いなければならず、よって要塞都市を迂回できる街道のごときいかなる物理的・電子的経路もあってはならない。ここから一部の部門でだけゼロトラストセキュリティを導入して要塞化しても他の要塞化されてない部門を突破して中心部へ侵攻できるため意味がなく、終着地である首都に相当する部門は必ず要塞化し防衛線を設置しなければならないことがわかる。また重要部では防衛線を迂回して都市へ侵入できないよう検問も実施しなければならない。企業の提案するゼロトラストセキュリティおよびその製品は基本的にこうした各都市の要塞化や検問ための装備にすぎず最終目標である首都防衛のための総合的防衛戦略ではないことに注意しなければならない。なお要塞による拠点防衛は軍事的には縦深防御から退化しているがITにおいては距離と補給の制約がないなど各種前提の相違から有効なものである。要塞は実世界では火砲の的だがITにおける火砲であるDDOSはインターネットに接続した一部の端末を潰すだけで陽動や拘束程度にしかならず、事業的にはともかくセキュリティ上の脅威度は低い（社内業務のための予備系統を利用できる場合）。ITにおいて脅威なのは巡航ミサイルによる中枢部への精密攻撃のようなものであり強いて言えば各都市にはこの発見および撃墜も期待される。閑話休題。

このように構築した都市と国家を俯瞰すると敵軍にはより多くの都市を経由させなければならず、都市はすべて防衛線を持つよう要塞化されていなければならず、もって敵軍が首都を制圧するために突破しなければならない防衛線を最大限多くかつ強固にするのがゼロトラストセキュリティの本質たる基本概念であることがわかる。逆に首都制圧までに突破を強いる防衛線の数と強度を勘案せず単にセキュリティ製品を購入し装備するとそのセキュリティ強度は首都との間に偶然存在する防衛線の数および強度に依存する確率的で非効率な信頼性の低いものとなる。ゼロトラストセキュリティを導入し全ノードをセキュア化したが結局少なくともいくつの防衛線および検問が必ず機能する機会が確保されているかおよびこのセキュリティレベルで十分であるかが明確でない場合がこれに該当する。