LRUキャッシュ

実装: data-structures/lru/ / 実行: go test ./data-structures/lru/

決まった数しか入らないキャッシュで、いっぱいになったら「一番長く使っていないもの」から捨てる作戦を作る。map で場所を一発で引き、双方向リストで使った順番を保つ、という二段構えがLRUの正体。次のバッファプールが、これをそのまま「どのページを捨てるか」に使う。

この章で作るもの

容量が決まったキャッシュで「溢れたら一番長く使っていないものを捨てる」戦略、 LRU(Least Recently Used)を実装する。次章のバッファプールがこれをそのまま追い出し器として使う。

この章の肝は3つ。

LRU は map + 双方向リストの組み合わせ。単独ではどちらも足りない
map で「そのキーがどこにあるか」を O(1) で引く
リストで「最近使った順」を O(1) で並べ替える

なぜ map だけでは足りないか

「キー → 値」なら map で十分。しかし LRU には「一番長く使っていないものはどれか」という問いに即答する責任がある。 map はキーの順序を持たないので、これに答えるには全走査するしかない — O(n)。

そこで「最近使った順」に並んだ列を別に持つ。これを配列でやると、真ん中の要素を先頭に動かすのに後続を全部ずらすので O(n)。 双方向リストなら、前後のポインタを繋ぎ替えるだけで O(1) で動かせる。

      ┌─────────── map ───────────┐
      │  "a"→●   "b"→●   "c"→●     │   キーからノードへ O(1) で飛ぶ
      └────┼───────┼───────┼───────┘
           ▼       ▼       ▼
  先頭 ⇄ [ c ] ⇄ [ b ] ⇄ [ a ] ⇄ 末尾      双方向リスト(最近使った順)
  最近使った側              次に捨てる側

map はキーからリストのノードへの近道。リストは最近使った順を保つ。この二段構えで get も put も O(1)

実装

ノードは双方向リストの要素。値だけでなく前後のポインタとキーを持つ (追い出すとき 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] // 一番使われていない側(次に追い出される)
}

// 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 {
		var zero V
		return zero, false
	}
	c.moveToFront(e)
	return e.value, true
}

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 を使う(Get)と A が先頭に戻り、次に D を入れたとき追い出されるのは A ではなく B になる。「使うと生き延びる」のが LRU。

デモLRUキャッシュ(容量3)0/3

キーを使う:

メリット / デメリット

メリット

get / put が両方 O(1)。実装も短い
「最近使ったものは近いうちにまた使う」(時間的局所性)が成り立つ場面で高いヒット率

デメリット

スキャン耐性がない: 大きなデータを1回だけ舐める処理(全件バッチ等)が走ると、二度と使わないページで有用なページを全部押し出してしまう。実物の DB は midpoint 挿入(新入りをいきなり先頭に置かない)等で対策する
ポインタとキーのぶんメモリを食う(値そのものより重いこともある)

実例

Go の groupcache/lru、 hashicorp/golang-lru — この章と同じ map+list 構成
Redis の maxmemory-policy allkeys-lru(厳密には近似 LRU。全ノードを繋ぐ代わりにサンプリングで近い効果を出す)
次章のバッファプール — OS のページキャッシュや DB のバッファ管理の土台

簡略化したこと

スレッド安全ではない: 利用側でロックする前提(バッファプールがそうしている)
TTL・重み付きサイズなし: エントリ数だけで容量を測る
スキャン耐性なし: 上記の通り、素の LRU のまま

参考資料

hashicorp/golang-lru — 実運用される Go 実装。 ARC / 2Q など LRU の改良版も入っている
Redis: Key eviction — 近似 LRU の実際

LRUキャッシュ ​

この章で作るもの ​

なぜ map だけでは足りないか ​

実装 ​

メリット / デメリット ​

簡略化したこと ​

参考資料 ​