【エルアールユーキャッシュ】
LRUキャッシュ とは？
最終更新:
💡 最後に使った時点が、いちばん古いものから追い出す
Least Recently Usedのルールで、最後に使われてから最も長く時間がたった項目を追い出すキャッシュ。利用の新しさを基準にし、使用回数や登録順、データの有効期限とは区別します。
📌 このページのポイント
ひよこ LRUキャッシュって何？
ペンギン先生 容量が足りないとき、最後に使った時点がいちばん古い項目を追い出すルールだよ。登録した時点ではなく、最後に使った時点を見る。最近利用した項目を残し、また使う可能性に備えるんだ。
ひよこ 読むだけでも順序が変わるの？
ペンギン先生 厳密なLRUでは、利用した項目を最も新しい側へ移すよ。図は容量3で、A・B・Cの順に利用が新しい例。Bを読むとB・A・Cになり、Dを入れると最も長く使っていないCが追い出される。
ひよこ どう実装するの？
ペンギン先生 キーから項目を探すハッシュ表と、利用順を管理する双方向リストを組み合わせる方法がある。項目を見つけた後の付け替えはO(1)。検索はハッシュ表の平均O(1)という前提で、キーの計算や値の取得・生成まで全部一定時間になるわけではないよ。
ひよこ 使用回数が少ないものを消すの？
ペンギン先生 それはLFUの考え方。FIFOは登録順、LRUは最後の利用時点だよ。LRUでも大量の一度きりのデータを続けて読むと、また必要な項目が追い出されることがある。どのルールが合うかはアクセスのしかたによるんだ。
ひよこ Redisもまったく同じ動作？
もっと詳しく知りたい人へ
最近使ったデータなら最新の内容？
利用時点が新しいことと、元データと内容が一致することは別です。LRUは追い出す項目を選ぶルールで、TTL、更新時の無効化、再取得などの鮮度管理は別に設計します。
📖 おまけ：英語の意味
「Least Recently Used Cache」 ＝ 最も最近使われていないキャッシュ
💬 Least Recently Used、つまり「一番長く放置されてるやつ」を追い出すルールだよ