Edited at

JavaのキャッシュライブラリとEviction Policy


TL;DR


  • キャッシュとEvictionについて、簡単にまとめてみました

  • 合わせて、Javaの代表的なキャッシュライブラリが採用しているEviction Policyについてもまとめてみました


Eviction?

Evictionというのは、日本語で「追い出し」などを指します。

キャッシュの文脈では、キャッシュで保持できる容量を超えて新しいデータを保存しようとした時に、「新しくキャッシュに保存する容量を確保するために、どのデータを消せばよいか?」という戦略で扱われます。

「キャッシュで保持できる容量を超えて」で指す上限というのは、キャッシュ内に保持するエントリ数だったり、オブジェクトのサイズだったりと、上限の設定はキャッシュを扱う製品によって様々です。

Expire(有効期限)とはまた違うので、注意しましょう。


代表的なEviction Policy

Wikipediaを見ると、Eviction Policyの例が書かれています。

キャッシュアルゴリズム

例えば、LRU、LFU、ARCなど。


有名どころ


LRU(Least Recently Used)

LRUは、もっとも使われていないデータを削除対象とするアルゴリズムです。

とても有名どころで、わかりやすいアルゴリズムですが、例えばバッチ処理なのでキャッシュに格納したデータのほとんどにアクセスするようなケースだと、あまり効率の良いキャッシュの使い方にならなかったりします。


LFU(Least Frequently Used)

LFUは、データのアクセス頻度を保持し、頻繁に使われていないデータを削除対象とするアルゴリズムです。


Javaのキャッシュライブラリで実装されている、Eviction Policy


Caffeine

最近の有名どころ、Caffeineから。

Caffeineは、Google Guava Cacheにインスパイアされたキャッシュライブラリです。

Caffeineで実装されているEviction Policyは、TinyLFUです。


Caffeine uses the Window TinyLfu policy due to its high hit rate and low memory footprint.


Efficiency


Ehcache 3

Ehcache 2の頃はJavaでのキャッシュライブラリといえばEhcacheでしたが、今はあまり聞かなくなったような気がするEhcache 3です。

Ehcache 3では、Eviction Policyがなくなっています。ヒープ、オフヒープなどの保存先がある状況に対して、効率的にEvictionを実装するのが難しい、という結論みたいです。

How to specify ehcache3 eviction strategy when cache is full ?

ちなみに、Ehcache 2.xの頃は、LRU、LFU、FIFOがありました。

Built-in Memory Store Eviction Algorithms

Ehcache 3でも、Eviction Advisorを作成すればPersistenceの層でコントロールすることはできるみたいです。これは、先程の保存先に対しての話につながりますね。

Eviction Advisor

つまり、キャッシュエントリを保存する先に合わせて自分で作りましょう、と…。


Google Guava Cache

最後は、Google Guava Cache。Caffeineが登場した今となっては、使うことがないかもしれませんが。

GuavaのCacheの場合は、サイズ、時間、参照でのEviction設定が可能です(Evictionと言いつつ、Expireでは?という感じがするものもありますが)。

CachesExplained / Eviction

このうち、参照でSoftReferenceを使うと、LRUな感じになるようです。


とりあえず

このあたりの情報を、手始めに押さえておけばよいのではないでしょうか。