LRUキャッシュ
実装:
data-structures/lru// 実行:go test ./data-structures/lru/
決まった数しか入らないキャッシュで、溢れたらいちばん長く使っていないものを捨てる。map で場所を引き、双方向リストで順を保つ二段構えで、出し入れが両方一定時間で済む。だが弱点がはっきりしていて、容量をたった1つ超える範囲をなめると、ヒット率が90%から0%へ崖のように落ちる。最も外れる順番で捨てているからだ。
この章で作るもの
容量が決まったキャッシュで「溢れたらいちばん長く使っていないものを捨てる」戦略、LRU(Least Recently Used)を実装する。次章のバッファプールが、これをそのまま追い出し器として使う。
「キー → 値」を引くだけなら map で十分になる。だが LRU にはいちばん長く使っていないものはどれかという問いに即答する責任がある。map はキーの順序を持たないので、これに答えるには全部を見るしかない。
そこで「最近使った順」に並んだ列を別に持つ。配列でやると、真ん中の要素を先頭に動かすのに後ろを全部ずらすことになる。双方向リストなら、前後のつなぎを替えるだけで済む。
┌─────────── map ───────────┐
│ "a"→● "b"→● "c"→● │ キーからノードへ一発で飛ぶ
└────┼───────┼───────┼───────┘
▼ ▼ ▼
先頭 ⇄ [ c ] ⇄ [ b ] ⇄ [ a ] ⇄ 末尾 双方向リスト(最近使った順)
最近使った側 次に捨てる側
容量 100 で、範囲を変えて 10 周まわったときのヒット率
範囲 50 個 ────────────────────────────── 90.0%
範囲 99 個 ────────────────────────────── 90.0%
範囲 100 個 ────────────────────────────── 90.0%
範囲 101 個 0.0% ← 崖
範囲 200 個 0.0%
1つ増えただけで、全部外れる順に見ていく。
- map だけでは足りない: 「いちばん古いのはどれか」に答えるための順序を、別に持つ必要がある
- 追い出したものを呼び出し側へ返す: 捨てる前の後始末を、キャッシュの外に任せられる
- 一巡なめる読みに弱い: 容量を1つ超えるだけで、ヒット率が崖のように落ちる
① map だけでは足りない
ノードは双方向リストの要素になる。値だけでなく前後のつなぎとキーを持つ(追い出すとき map からも消すためにキーが要る):
// entry は双方向リストのノード。リストは「最近使った順」に並ぶ。
type entry[K comparable, V any] struct {
key K
value V
prev, next *entry[K, V]
}
// Cache は容量固定の LRU キャッシュ。
type Cache[K comparable, V any] struct {
capacity int
items map[K]*entry[K, V]
head *entry[K, V] // 最近使った側
tail *entry[K, V] // 一番使われていない側(次に追い出される)
hits, misses int
}
// New は容量 capacity (>=1) のキャッシュを返す。
func New[K comparable, V any](capacity int) (*Cache[K, V], error) {
if capacity < 1 {
return nil, errors.New("lru: capacity must be >= 1")
}
return &Cache[K, V]{capacity: capacity, items: map[K]*entry[K, V]{}}, nil
}Get は「値を返す」だけの操作に見えて、実は触ったノードを先頭に動かすのが本体になる。これを忘れると「最近使った」が更新されず、ただの map になってしまう:
// Get は値を返し、そのキーを「最近使った」先頭に動かす。
// この移動こそが LRU の本体で、map だけでは実現できない部分。
func (c *Cache[K, V]) Get(key K) (V, bool) {
e, ok := c.items[key]
if !ok {
c.misses++
var zero V
return zero, false
}
c.hits++
c.moveToFront(e)
return e.value, true
}map が「キーからノードへの近道」、リストが「順序の担当」。どちらか片方では成立しない。map だけなら順序が無く、リストだけなら目的のノードを探すのに端から見ることになる。
2つのデータ構造を同じ要素に対して重ねて持つ、というのは他でもよく出てくる形になる。転置インデックスもB-Tree ページストアも、探す道と並べる道を別々に用意している。
② 追い出したものを呼び出し側へ返す
Put は容量を超えたら末尾を追い出す:
// Put は値を入れ、容量が溢れたら一番使われていない要素(tail)を追い出す。
// 追い出した要素を返すのは、利用側(バッファプール等)が
// 「捨てる前の後始末」(dirty ページの書き戻し)をできるようにするため。
func (c *Cache[K, V]) Put(key K, value V) (evictedKey K, evictedValue V, evicted bool) {
if e, ok := c.items[key]; ok {
e.value = value
c.moveToFront(e)
return
}
e := &entry[K, V]{key: key, value: value}
c.items[key] = e
c.pushFront(e)
if len(c.items) > c.capacity {
victim := c.tail
c.unlink(victim)
delete(c.items, victim.key)
return victim.key, victim.value, true
}
return
}ここで追い出した要素を捨てずに返しているのが設計の勘所になる。次章のバッファプールは、追い出す前に「書き換えられていたらディスクへ書き戻す」必要がある。キャッシュ自身がその後始末を知る必要は無いので、外へ渡す。
試してみる: A→B→C と入れると満杯。そこで A を使うと A が先頭に戻り、次に D を入れたとき追い出されるのは A ではなく B になる。使うと生き延びるのが LRU になる。
③ 一巡なめる読みに弱い
LRU の弱点は、言葉で言うと「スキャン耐性が無い」になる。だがどれくらい弱いのかは測ってみないと分からない。
数えられるようにしておく:
// Hits と Misses は当たった回数と外れた回数。
//
// キャッシュは「入っているか」ではなく「どれくらい当たるか」で評価する。
// 容量を1つ増やしただけで当たり方が変わるので、数えられるようにしておく。
func (c *Cache[K, V]) Hits() int { return c.hits }
func (c *Cache[K, V]) Misses() int { return c.misses }
// HitRate は当たった割合。1度も引いていなければ 0。
func (c *Cache[K, V]) HitRate() float64 {
n := c.hits + c.misses
if n == 0 {
return 0
}
return float64(c.hits) / float64(n)
}
// ResetStats は数え直す。
func (c *Cache[K, V]) ResetStats() { c.hits, c.misses = 0, 0 }容量 100 のキャッシュで、範囲を変えて 10 周まわしたときのヒット率がこうなった:
| なめる範囲 | ヒット率 |
|---|---|
| 50 個 | 90.0% |
| 90 個 | 90.0% |
| 99 個 | 90.0% |
| 100 個 | 90.0% |
| 101 個 | 0.0% |
| 200 個 | 0.0% |
90% が上限なのは、1周目が必ず全部外れるからだ(10周のうち1周ぶん)。つまり容量に収まっているうちは、2周目以降は1つも外さない。
そして 101 個。たった1つ増えただけで、1度も当たらなくなる。理由は単純で、周回するとき次に必要になるのは「いちばん昔に触ったもの」なのに、LRU が捨てるのはまさにそれだからだ。最も外れる順番で捨てていることになる。
テストで、この崖の両側を固定した。同時に、局所性のあるアクセス(狭い範囲を繰り返し引きながら、ときどき遠くを触る)なら、容量より広い範囲でも当たり続けることも固定した。落ちるのは一巡なめるときだけで、LRU が悪いわけではない。
これが実務で効いてくる場面はよくある。全件バッチが1本走っただけで、それまで温まっていたキャッシュが二度と使わないデータで埋まる。だから実物の DB は、新入りをいきなり先頭に置かない(midpoint 挿入)、2回目に触られて初めて昇格させる(2Q)といった手当てを入れている。
設計の観点
- 問いに答えるためのデータ構造を足す: 「いちばん古いのはどれか」に答えるには順序が要る
- 後始末を外に出す: 追い出したものを返すだけにして、何をするかは使う側が決める
- 弱点は測って言う: 「スキャン耐性が無い」より「101 個で 0% になる」のほうが判断に使える
- 崖があるところを知る: なだらかに悪くなるのではなく、境界で一気に落ちる形がある
- 近似で足りることがある: 全ノードを繋がなくても、数個を見比べれば近い効果が出る
- 測れる出口を用意する: ヒット率を数えられないと、容量を決める根拠が無い
対照と実例
| 方式 | 捨てるもの | 一巡なめる読みに | 要るもの |
|---|---|---|---|
| FIFO | いちばん先に入れたもの | 同じく弱い | 待ち行列だけ |
| LRU | いちばん長く使っていないもの | 弱い(崖がある) | map + 双方向リスト |
| LFU | いちばん使われていないもの | 強い | 回数の数え上げ |
| 2Q / SLRU | 1回しか触られていないもの | 強い | 段を2つ持つ |
| ARC | 最近と頻度を自動で配分 | 強い | 追い出したキーの履歴 |
| 近似 LRU(Redis) | 数個を見比べて古いほう | 弱い | 標本だけ |
裏どり:
- Redis の近似 LRU: Key eviction。全ノードを繋ぐ代わりに数個を標本として見比べる。厳密でなくても実用上ほぼ同じ効果が出ることを、作者が計測して示している
- MySQL InnoDB の midpoint 挿入: 新しく読んだページをリストの先頭ではなく途中(既定で 5/8 の位置)に入れる。一巡なめる読みで温まった側が押し出されるのを防ぐ
- 2Q(1994): 1回しか触られていないものと、2回以上触られたものを分ける。この章の崖への直接の答えになる
- ARC(2003): 最近性と頻度への配分を、追い出したキーの履歴を見て自動で調整する
- Go の実装:
hashicorp/golang-lruはこの章と同じ map + リスト構成で、2Q と ARC も入っている
簡略化したこと
- スレッド安全ではない: 使う側でロックする前提(バッファプールがそうしている)
- 崖への手当てなし: 2Q も midpoint 挿入も入れていない。素の LRU のまま
- TTL と重み付きの容量なし: 個数だけで容量を測る。大きさの違う値は扱わない
- 近似なし: 全要素をリストに繋ぐ。標本で済ませる形は扱わない
- 追い出しは1つずつ: まとめて追い出す形は無い
参考資料
- hashicorp/golang-lru — 実運用される Go 実装。ARC / 2Q も入っている
- Redis: Key eviction — 近似 LRU の実際
- Megiddo, Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache(2003)
- 実装: data-structures/lru