キャッシュ追い出し
キャッシュが満杯のとき何を捨てるかを決める仕組み。役に立つキャッシュとメモリを食うだけのキャッシュの差は、ほぼここで決まる。
容量が無限なら方針は要らない。現実のキャッシュはデータ全体に比べて小さく、新しい項目を入れるたびに古い項目を犠牲にする必要がある。一般的なのは最も長く使われていないものを捨てるLRUで、LFUは使用回数を数えて頻繁に要求されるものを残し、FIFOは人気に関係なく最古のものを捨てる。ランダム方式は、管理コストがわずかなのにLRUに驚くほど近い性能を出す。
追い出しと有効期限は別物だ。TTLは古くなったから削除し、追い出しは空きがなくなったから削除する。Redisでは別の設定項目で、メモリが満杯のとき何も捨てずに書き込みを拒否する構成もできる。最悪のケースはキャッシュスラッシングで、作業セットがキャッシュよりわずかに大きいと、各項目が再利用される直前に必ず追い出され、ヒット率が限りなくゼロに近づく。