🙌
LRUキャッシュをGoで実装してみた

2024/12/14に公開
 はじめにLRU（Least Recently Used）キャッシュは、最も最近使われたデータを優先的に保持し、使用頻度の低いデータから順に削除していくキャッシュアルゴリズムです。今回はGo言語でLRUキャッシュを実装してみました。

 キャッシュとは？キャッシュとは、計算や処理の結果を一時的に保存し、再利用できるようにする技術です。主にデータの取得速度を高速化する目的で使用され、データベースやWebアプリケーションなどで頻繁に利用されます。
以下は、キャッシュの仕組みを簡単に示した図です。

 キャッシュの仕組み

 効率的なキャッシュキャッシュはコンピュータのメモリを使ってデータを一時的に保存する仕組みですので、メモリには限りがあるため、保存できるデータの量も限られています。理想的には、これから頻繁に使われるであろうデータをキャッシュに保存し、アクセスが多くなるデータを素早く取り出せるようにすることが求められます。これを実現するのはLRUキャッシュです。

 LRUキャッシュとは？LRU（Least Recently Used）キャッシュは、最近使用されたデータが将来もアクセスされる可能性が高いと仮定し、そのデータをキャッシュに残し、逆に長期間アクセスされていないデータはキャッシュから削除すべきだという考え方です。

今回は、このLRUキャッシュをデータ構造の「双方向リスト（Doubly Linked List）」を利用して実装します。

双方向リスト（Doubly Linked List）はこちらの記事で紹介しています。

 LRUキャッシュの基本的な動作キャッシュのキーを双方向リストに格納
キャッシュに保存されたデータは、双方向リストというデータ構造を使って管理されます。リストの先頭が最も最近使われたデータを示し、末尾が最も古くて使われていないデータを示します。
キャッシュがヒットした場合
データがキャッシュに存在する場合、そのデータのキーを双方向リストの中で見つけ、リストの先頭に移動します。こうすることで、最も最近使われたデータをリストの先頭に保ちます。
キャッシュがヒットしなかった場合
キャッシュの容量がまだ余っていれば、新しいデータをキャッシュに追加し、そのキーをリストの先頭に挿入します。
キャッシュの容量を超えた場合、リストの末尾にある最も古いデータを削除し、新しいデータをリストの先頭に挿入します。

 LRUキャッシュの実装Goの標準ライブラリcontainer/listを使用して、LRUキャッシュを実装してみました。以下にそのコード例を紹介します。

 実装例package algorithm

import "container/list"

type LRUCache struct {
	cache map[int]*list.Element
	lst   *list.List
	cap   int
}

type entry struct {
	key   int
	value string
}

func NewLRUCache(cap int) *LRUCache {
	return &LRUCache{
		cache: make(map[int]*list.Element, cap),
		lst:   list.New(),
		cap:   cap,
	}
}

func (lru *LRUCache) Add(key int, value string) {
	if ele, exists := lru.cache[key]; exists {
		ele.Value.(*entry).value = value
		lru.lst.MoveToFront(ele)
		return
	}

	if len(lru.cache) == lru.cap {
		back := lru.lst.Back()
		if back != nil {
			delete(lru.cache, back.Value.(*entry).key)
			lru.lst.Remove(back)
		}
	}
	ele := lru.lst.PushFront(&entry{key: key, value: value})
	lru.cache[key] = ele
}

func (lru *LRUCache) Get(key int) (string, bool) {
	if ele, exists := lru.cache[key]; exists {
		lru.lst.MoveToFront(ele)
		return ele.Value.(*entry).value, true
	}
	return "", false
}

 テストコード次に、LRUキャッシュの実装が正しく動作するかを確認するためのテストコードです。
func TestLRUCache(t *testing.T) {
	lru := NewLRUCache(10)

	for i := 0; i < 10; i++ {
		lru.Add(i, strconv.Itoa(i)) //9 8 7 6 5 4 3 2 1 0
	}

	for i := 0; i < 10; i += 2 {
		lru.Get(i) //8 6 4 2 0 9 7 5 3 1
	}

	for i := 10; i < 15; i++ {
		lru.Add(i, strconv.Itoa(i)) //14 13 12 11 10 8 6 4 2 0
	}

	for i := 0; i < 10; i++ {
		v, ok := lru.Get(i)
		if i%2 == 0 { // 0, 2, 4, 6, 8 はキャッシュに残るべき
			if !ok || v != strconv.Itoa(i) {
				t.Errorf("key %d not found or incorrect value: got %v, want %v", i, v, strconv.Itoa(i))
			}
		} else { // 1, 3, 5, 7, 9 はキャッシュから削除されるべき
			if ok {
				t.Errorf("key %d should not be found, got %v", i, v)
			}
		}
	}
}

 まとめLRU（Least Recently Used）キャッシュは、限られたメモリ内で効率的にデータを管理し、最適なパフォーマンスを実現するために広く使用されています。

今回の記事では、Go言語を使用してLRUキャッシュを実装しました。
はじめに

キャッシュとは？

キャッシュの仕組み

効率的なキャッシュ

LRUキャッシュとは？

LRUキャッシュの基本的な動作

LRUキャッシュの実装

実装例

テストコード

まとめ

Discussion
