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.
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の層でコントロールすることはできるみたいです。これは、先程の保存先に対しての話につながりますね。
つまり、キャッシュエントリを保存する先に合わせて自分で作りましょう、と…。
Google Guava Cache
最後は、Google Guava Cache。Caffeineが登場した今となっては、使うことがないかもしれませんが。
GuavaのCacheの場合は、サイズ、時間、参照でのEviction設定が可能です（Evictionと言いつつ、Expireでは？という感じがするものもありますが）。
このうち、参照でSoftReferenceを使うと、LRUな感じになるようです。
とりあえず
このあたりの情報を、手始めに押さえておけばよいのではないでしょうか。