キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム - 好奇心に殺される。

Computer Science キャッシュ機構 TinyLFU のアーキテクチャと、それを支えるアルゴリズム TinyLFUの論文を読んだので概要と、それを支えるアルゴリズムを紹介します。 Overview TinyLFU はアクセス頻度を近似し、軽量でハイパフォーマンスに設計されたキャッシュアルゴリズムです。最近、Database Internals を読んでいて TinyLFU を知ったのですが、Database Internals では TinyLFU の詳細が書かれていなかったので、TinyLFUが提案されている論文を読んでみました。その内容をザックリ解説してみようと思います。 論文はこちらです。 TinyLFU: A Highly Efficient Cache Admission Policy いきなりTinyLFUの紹介を始めると混乱するので、ベースとなる技術やアルゴリズム

[sh19910711]

"TinyLFU / LRUはLFUよりも多くのキャッシュサイズを必要 / Sの値がサンプルサイズ(W)に達すると、Sと近似スケッチのすべてのカウンタを2で割りるリセット法を提案 / Bloom Filter > O(k)時間で集合内に要素が無いことを確定できる"