前回は、本体の情報が変わるとき、キャッシュをどの順番で更新するのか という話を見ました。
本体を先に直して、キャッシュはあとで作り直すのか。
キャッシュを入口にして、その更新を本体にも通すのか。
あるいは、先にキャッシュだけ直して、本体はあとにするのか。
これが キャッシュの書き込み戦略 の話でした。
今回は、その続きです。
テーマは、LRU と LFU です。
一言でいうと、キャッシュがいっぱいになったとき、何を残して、何を捨てるのか という話です。
📌 この記事でわかること
今回は、LRU と LFU の入口を見ていきます。
まずは細かいアルゴリズムよりも、ポケットに全部は入らないなら、追い出しルールが必要になる という感覚をつかむのが目的です。
🐣 レストランでの出来事
僕はすっかり、ポケット運用に慣れていた。
コーラ、オレンジジュース、ウーロン茶。
よく出るものをポケットに入れておけば、毎回冷蔵庫まで走らなくて済む。
その日も、ランチのピーク前にポケットを確認していた。
僕： よし
僕： コーラ、オレンジ、ウーロン茶
僕： 今日も完璧です
先輩： ポケット、何本入るんでしたっけ？
僕： 3本までです
先輩： ですよね
そこへ、お客さんの注文が飛んだ。
お客さん： メロンソーダ1つ！
僕： はい！
僕は冷蔵庫へ走り、メロンソーダを取った。
そして、そのままポケットに入れようとして止まった。
僕： ……あっ
僕： 入らない
先輩： そうです
先輩： ポケットは無限じゃありません
僕のポケットには、すでに
- コーラ
- オレンジジュース
- ウーロン茶
が入っている。
ここにメロンソーダを入れるには、どれか1本を出さなければならない。
僕： どれを捨てればいいんですかね……
僕： なんとなくで決めると事故りそうです
先輩： そうです
先輩： キャッシュで大事なのは、「何を入れるか」だけじゃありません
先輩： 新しく入れるために、何を捨てるか も同じくらい大事です
僕： ああ……
僕： たしかに、そこを決めておかないと、毎回その場で悩むことになりますね
先輩： ええ
先輩： 代表的なのは2つです
僕： 2つ？
先輩： 1つは、最近使っていないものを捨てる やり方
先輩： もう1つは、今まであまり使われていないものを捨てる やり方です
僕： なるほど……
僕： 似てるようで、ちょっと違いますね
先輩： 違います
先輩： たとえばウーロン茶が、昔すごく人気だったけど、最近はまったく出ていないならどうしますか
僕： うーん……
僕： 「最近使ってない」で考えるなら、捨てたいです
先輩： そうです
先輩： でも「今までの総回数」で考えると、昔たくさん出ていたぶん、まだ強いかもしれません
僕： あっ、ほんとだ
僕： 逆に、メロンソーダが今だけ急に流行ってるなら、「最近」のほうが強そうですね
先輩： そういうことです
僕： なるほど……
僕： 何を残したいのかで、ルールが変わるんですね
先輩： ええ
先輩： そして今日の話は、まさにそこです
その瞬間、僕は少しだけ腑に落ちた。
キャッシュの難しさは、
ただ 近くに置くこと でも、
どう更新するか だけでもなかった。
限られた場所に、何を残すか。
今日は、そのルールの重さが見え始めた日だった。
📝 システムデザインにおきかえると
今の話が、そのまま LRU と LFU の入口です。
ここで大事なのは、キャッシュには容量の限界があるから、新しいものを入れるたびに、何かを追い出す必要がある ということです。
つまり今日は、追い出しルール（Eviction Policy） の話です。
1️⃣ そもそも何が問題なのか
キャッシュは便利です。
でも、ポケットが3本までしか入らないように、キャッシュにも上限があります。
だから、新しいデータを入れたいときは、
- 何かを残す
- 何かを捨てる
を決めないといけません。
ここを何となくでやると、
本当は残すべき人気データを捨てたり、逆にほとんど使わないものを居座らせたりしてしまいます。
だから必要になるのが、追い出しルール です。
2️⃣ LRU
1つ目は、最近使っていないものを捨てる という考え方です。
これを LRU（Least Recently Used） と呼びます。
ざっくり言うと、
- 最後に使ったのが一番古いもの
- しばらく触られていないもの
を追い出します。
レストランでいえば、
- コーラはさっきも出た
- オレンジジュースも少し前に出た
- でもウーロン茶はずっと出ていない
なら、ウーロン茶をポケットから出す感じです。
この考え方の強みは、かなり直感に合うことです。
最近使ってないなら、しばらく要らないかもしれない。
そう考えるわけです。
メリット
- 直感的で分かりやすい
- 最近の流行に追いつきやすい
- 実務でもかなり使いやすい
デメリット
- 昔ずっと人気だったものでも、少し触られないと捨てられることがある
つまり LRU は、
「最近の動き」を重視する
ルールです。
3️⃣ LFU
2つ目は、今まであまり使われていないものを捨てる という考え方です。
これを LFU（Least Frequently Used） と呼びます。
ざっくり言うと、
- これまでの使用回数が少ないもの
- あまり注文されていないもの
を追い出します。
レストランでいえば、
- コーラは今日だけで20回出た
- オレンジジュースは10回出た
- ウーロン茶は2回しか出ていない
なら、ウーロン茶を出す感じです。
この考え方の強みは、長期的に人気のあるものを残しやすい ことです。
メリット
- 本当に人気のあるものを残しやすい
- 一時的なブームに振り回されにくい
デメリット
- 昔たまたま大人気だったものが、今は使われていなくても居座りやすい
つまり LFU は、
「これまでの累積の人気」を重視する
ルールです。
4️⃣ 2つを並べるとこう
| ルール | 何を捨てる？ | 強み | 弱み |
|---|---|---|---|
| LRU | 最近使っていないもの | 今の流行に追いつきやすい | 少し触られないだけで人気データを捨てることがある |
| LFU | 今までの使用回数が少ないもの | 長期的に人気のあるものを残しやすい | 昔の人気者が居座りやすい |
ここで大事なのは、
どちらも賢いけど、見ているものが違う ということです。
- LRU は 最近
- LFU は 回数
を見ています。
5️⃣ どっちが正しいのか
ここでも、いつものように どちらが絶対正しい、ではありません。
大事なのは、
- 最近の変化を重視したいのか
- 長期的な人気を重視したいのか
- データの流行が入れ替わりやすいのか
- 一部の人気データがずっと強い世界なのか
です。
かなりざっくり言うと、
- 流行が変わりやすいなら LRU
- 長く人気が偏るなら LFU
が向いていることがあります。
ただ、最初の入口としては、
まず LRU が直感的で理解しやすい です。
6️⃣ この回で本当に大事なこと
この回で一番大事なのは、キャッシュは「何を入れるか」だけでなく、「何を捨てるか」まで決めて初めて回る ということです。
ポケットは便利です。
でも、無限には入らない。
だから、新しいものを入れるたびに、何かを追い出す必要があります。
そのとき、
- 最近使っていないものを捨てるのか
- 今まであまり使われていないものを捨てるのか
で、キャッシュの性格が変わります。
一言でいうと、
LRU と LFU は、「限られたキャッシュの中で、何を残して何を捨てるか」を決めるルール
なのです。
🎭 今回のオチ
僕： なるほど……
僕： キャッシュって、何を入れるかだけじゃなくて、何を捨てるかまで決めないといけないんですね
先輩： そういうことです
そのとき、厨房で話を聞いていた店長が胸を張った。
店長： よし、俺もLRUで仕事をするぞ！
僕： なんですかそれ
店長： 一番最近使っていない記憶から捨てる！
僕： へえ
店長： というわけで、一番しばらく使っていなかった「お前の給料アップの約束」は、今脳内から追い出した！
僕： 都合のいいデータだけ消さないでください
先輩： はやく転職しないと....