LRUキャッシュ — 机からあふれた本はどれを返す?

キャッシュの置き場所には限りがあります。いっぱいになったら、何かを捨てて空きを作らなければなりません。では何を捨てるか? その定番の答えが LRU(Least Recently Used)— 「いちばん長く使われていないものから追い出す」です。

下の図1は、あなたの勉強机です。よく使う本は机の上(キャッシュ)に置けますが、4冊まで。それ以上は遠い本棚まで取りに行くことになります。本棚の本をクリックして、机の上がどう入れ替わるか試してください。

ルールは「使ったら手前に置き直す」だけ

図1のLRUがやっていることは、たった2つです。(1) 本を使ったら、机のいちばん手前に置き直す。(2) 机があふれたら、いちばん奥の本を本棚に返す。これだけで「最近使ったものは手前に、ずっと使っていないものは自然と奥に」並び、追い出すべき本を探す手間すらありません。奥の1冊を返すだけです。

この戦略が効くのは、アクセスには「最近使ったものは、近いうちにまた使われやすい」という偏り(時間的局所性)があるからです。CPUキャッシュ、OSのページ置換、Redisのmaxmemory-policy、ブラウザのキャッシュ — 至るところでLRUとその亜種が動いています。

LRUにも苦手な相手がいる

図1で A → B → C → D → E → A → B → C → D → E… と順繰りにクリックしてみてください。4冊の机に5冊を順番に使うと、次に使う本が毎回ちょうど追い出された直後になり、ヒット率0%が続きます。これがLRUの弱点で、全件を順になめるバッチ処理などで起こります。実務のシステムが「2回以上使われたものだけ守る」「アクセス頻度も見る(LFU)」といった亜種を使うのは、この弱点を補うためです。

まとめ

LRUは「使ったら手前へ、あふれたら奥から捨てる」だけの素朴なルールですが、アクセスの偏りを味方につけることで高いヒット率を出します。一方で、容量より少しだけ大きいループには全敗するという、はっきりした苦手も持っています。キャッシュのヒット率が思ったより出ないとき、「アクセスパターンとLRUの相性」を疑えるようになれば、この図は卒業です。