📑

【Go】 Goのキャッシュライブラリ golang-lru のサンプルコードから内部実装を読む

2023/08/17に公開

Go のキャッシュライブラリの一つである golang-lru のソースコードリーディングを通して、LRUキャッシュアルゴリズムを自分なりにまとめたメモです。

記事公開前に追記

つい２週間前にv2がリリースされ、expirable な LRU キャッシュ機能が追加されたようです。

後で読みます。

LRUキャッシュアルゴリズムとは

LRU（Least Recently Used）キャッシュアルゴリズムは、使われていないデータから削除するキャッシュアルゴリズムです。
Wikipedia

参考としたライブラリ

Go でLRUキャッシュを採用している HashiCorp 社のライブラリを読んでみました。
https://github.com/hashicorp/golang-lru

サンプルコードを追ってみる

README のサンプルコードを追ってみます。

サンプルコードでは、はじめにキャッシュエントリーを128個保存できるキャッシュインスタンスを作成します。
その後、for ループ内で256個のエントリーを追加しますが、最終的には128個のエントリーしか保存されないことが表現されています。

128個のエントリーが登録された後、どのエントリーを破棄するか、を決定するアルゴリズムがキャッシュアルゴリズムです。
golang-lru では、ライブラリの名前の通り、LRUアルゴリズムにより、128個のエントリが順次削除されます。

package main

import (
	"fmt"
	"github.com/hashicorp/golang-lru/v2"
)

func main() {
	l, _ := lru.New[int, any](128)
	for i := 0; i < 256; i++ {
		l.Add(i, nil)
	}
	if l.Len() != 128 {
		panic(fmt.Sprintf("bad len: %v", l.Len()))
	}
}

ここから、内部の実装を追っていきます。
https://github.com/hashicorp/golang-lru

この記事はここまでにして、ぜひ、本体のソースコードを読んでみてください。

New関数

New で作成されるキャッシュインスタンスの構造体です。
メンバー変数 lru は、キャッシュエントリーを保存するための Map、キャッシュ可能なエントリー数、そしてどのエントリーを削除するか決定するためのリスト evictList を持っています。

// Cache is a thread-safe fixed size LRU cache.
type Cache[K comparable, V any] struct {
	lru         *simplelru.LRU[K, V]
	evictedKeys []K
	evictedVals []V
	onEvictedCB func(k K, v V)
	lock        sync.RWMutex
}

items はキャッシュエントリーを保存するための Map です。
キャッシュエントリーの構造体である、 Entry のメンバー変数 prev と next がそれぞれ自身の前後のエントリーのポインターを指します。
これにより、それぞれのキャッシュエントリーは、双方向連結リストの一部として表現されます。

また、evictList により、エントリーを双方向循環リストとして表現されます。
具体的には、 evictList （LruList構造体）のメンバー変数 root がリストの先頭（かつ末尾）となることで、リストを循環させています。
root.next がリストの先頭のエントリーを指し、 root.prev がリストの末尾のエントリーを指します。

// LRU implements a non-thread safe fixed size LRU cache
type LRU[K comparable, V any] struct {
	size      int
	evictList *internal.LruList[K, V]
	items     map[K]*internal.Entry[K, V]
	onEvict   EvictCallback[K, V]
}

Cache.Addメソッド

Addメソッドはその名の通り、キャッシュにエントリーを追加します。
内部では、既にキャッシュにエントリーが存在するかどうかを確認し、存在しない場合は新たにエントリーを作成します。

// Check for existing item
if ent, ok := c.items[key]; ok {
    c.evictList.MoveToFront(ent)
    if c.onEvict != nil {
        c.onEvict(key, ent.Value)
    }
    ent.Value = value
    return false
}

この時、双方向循環リスト evictList の先頭にエントリーを追加します。

既存のエントリーを evictList の先頭に追加するmoveメソッドでは、現在の前後のエントリーのポインターをそれぞれ書き換え、移動対象のエントリーeをリストから一時的に外します。（e自身は前後のエントリーのポインターを持ったままなので、正しくは外れてはいない。）
次に、moveメソッドの第二引数atに渡されたevictList の先頭のエントリーである root のポインターをeの前後のポインターに書き換えます。
その後、eの前のエントリーの後ろのポインター、eの後ろのエントリーの前のポインターを書き換えることで、エントリーを evictList の先頭に持ってきています。
（コードを見たほうが早いです。何書いてるかわからないです。）

// move moves e to next to at.
func (l *LruList[K, V]) move(e, at *Entry[K, V]) {
	if e == at {
		return
	}
	e.prev.next = e.next
	e.next.prev = e.prev

	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
}

続いて、キャッシュにエントリーが存在しない場合のエントリーの新規追加処理です。

エントリーが登録されていない場合は、エントリーを作成し、evictList の先頭に置きます。

// Add new item
ent := c.evictList.PushFront(key, value)
c.items[key] = ent

evict := c.evictList.Length() > c.size
// Verify size not exceeded
if evict {
    c.removeOldest()
}
return evict

双方向循環リストに追加すると同時に、リストのサイズ（=登録されているエントリーのサイズ）をインクリメントします。

// insert inserts e after at, increments l.len, and returns e.
func (l *LruList[K, V]) insert(e, at *Entry[K, V]) *Entry[K, V] {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

New関数で指定したキャッシュ可能な上限値をリストのサイズが超えた場合は、最も古いエントリーを削除します。
最も古いエントリーは、evictList の末尾にあるエントリー（c.evictList.Back()）です。

// removeOldest removes the oldest item from the cache.
func (c *LRU[K, V]) removeOldest() {
	if ent := c.evictList.Back(); ent != nil {
		c.removeElement(ent)
	}
}

// removeElement is used to remove a given list element from the cache
func (c *LRU[K, V]) removeElement(e *internal.Entry[K, V]) {
	c.evictList.Remove(e)
	delete(c.items, e.Key)
	if c.onEvict != nil {
		c.onEvict(e.Key, e.Value)
	}
}

前後のエントリーのポインターの書き換えと、自身のエントリーの前後のポインターの参照を nil にすることでエントリーの削除を行います。
avoid memory leaks とか、書いてくれているのいいですね。勉強になります。

// Remove removes e from its list, decrements l.len
func (l *LruList[K, V]) Remove(e *Entry[K, V]) V {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--

	return e.Value
}

Cache.Len()

キャッシュのサイズを返します。

以上です。

感想

LRUキャッシュアルゴリズムは完全に理解しました。
ちょうど先週末に読んでいたデータ構造に関する本で紹介されていた双方向循環リストにより実装されていることがわかり、改めてデータ構造の学習のモチベーションが上がりました。
ところどころ、細かくコメントを書いてあり、読みやすく勉強になりました。

ここまで書いて、改めてGitHubのリポジトリを除いていたら、v2がリリースされていたことに気が付きました。
v2では、expirable な LRU キャッシュ機能が追加されているようです。

MPL 2.0 のライセンスで公開されています。

GitHubで編集を提案