Go に LRU キャッシュを実装する

したがって、小規模なキャッシュが必要ですが、Redis または memcached インスタンスを正当化することはできません。 Go でこれを実装するには何が必要かを見てみましょう。楽しみのために、プロジェクトで再利用できるようにジェネリックを使用して作成します。

LRU キャッシュは通常、固定容量と最も単純な排出ポリシーを持ち、アクセスされてから時間が最も長い要素を排出します。単純な lru キャッシュは次のインターフェイスを実装します:

type LRUCache[T any] interface {
    Get(key string) (value T, found bool)
    Put(key string, value T)
    Keys() []string
    Remove(key string) bool
    Clear()
    Capacity() int
    Len() int
}

キャッシュは、何らかの値をキーとするエントリとしてデータ項目を保存することがわかっています。それは地図のように聞こえます。排除ポリシーの導入についてはどうですか?これを行う 1 つの方法は、各項目とともに timeAccessed プロパティを保持することです。次のようなもの:

type cacheEntry[T any] struct {
  Data T
  LastAccessed time.time
}

ただし、パフォーマンスについて考えてみましょう。キャッシュ キーを検索できるだけでなく、必要に応じて最も古いものをできるだけ早く挿入および削除できるようにしたいと考えています。

ハッシュテーブルであるマップを使用すると、検索のパフォーマンスが非常に高速になります。最も古いエントリを見つけるにはどうすればよいでしょうか?キャッシュ構造体が次のようになっている場合:

type LRUCache[T any] {
  capacity int
  keyMap map[string]cacheEntry[T]
}

エントリを削除する際には、必ずマップを反復処理して最も古いものを見つける必要があります。

キャッシュ エントリのリストを効率的に並べ替えて維持できる方法でエントリを保存する方法が必要です。ソートルーチンを使用する必要がないことが望ましいです。

二重リンク リストはこれを行う良い方法であり、実際に必要でない限り、エントリにアクセス時間を保存する必要はありません。そこで、ノード構造体とともに以下を実装するリンク リストがあると仮定しましょう:

type DoubleLinkedList[T any] interface {
    Head() *DoubleNode[T]
    Tail() *DoubleNode[T]
    // Append inserts new item at tail
    Append(data T) *DoubleNode[T]
    // Push appends new item at head
    Push(data T) *DoubleNode[T]
    Remove(node *DoubleNode[T]) *DoubleNode[T]
    RemoveTail() *DoubleNode[T]
    MoveToHead(node *DoubleNode[T])
}
type DoubleNode[T any] struct {
    Data T
    Prev *DoubleNode[T]
    Next *DoubleNode[T]
}

キャッシュ構造体は次のようになります。

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]*DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
}

キャッシュ エントリの構造体は次のようになります:

type lruCacheEntry[T any] struct {
    key   string
    value T
}

現実的には、おそらくキャッシュ キーにインターフェイスを使用するでしょう。コードをシンプルにするために文字列を使用しています。

ここでの実装では、キャッシュ内で最近アクセスされたエントリが先頭にあり、最も最近使用されていないエントリが末尾になります。したがって、削除するときは、リンクされたリストの末尾要素を削除するだけです。

Get() 関数の実装は簡単です。

func (l *lruCache[T]) Get(key string) (value T, found bool) {
    if node, ok := l.keyMap[key]; ok {
        l.list.MoveToHead(node)
        return node.Data.value, ok
    }
    var zero T
    return zero, false
}

Get では、キーのマップ エントリを取得し、ノードが「最近使用された」ノードとなるため、リストの先頭に移動するだけです。

Put() 関数は、必要に応じてエビクションを処理する場所です。

func (l *lruCache[T]) Put(key string, value T) {
    if node, ok := l.keyMap[key]; ok {
        node.Data = lruCacheEntry[T]{
            key:   key,
            value: value,
        }
        // move the element to the most recent position
        l.list.MoveToHead(node)
    } else {
        // insert the new element at the head
        newNode := l.list.Push(lruCacheEntry[T]{
            key:   key,
            value: value,
        })
        l.keyMap[key] = newNode
    }
    // is eviction necessary
    if len(l.keyMap) > l.capacity {
        nodeRemoved := l.list.RemoveTail()
        delete(l.keyMap, nodeRemoved.Data.key)
    }
}

Put() の場合、まず、指定されたキーの値がすでに存在するかどうかを確認します。存在する場合は、値を更新し、ノードをリストの先頭に移動します。それ以外の場合は、新しいキャッシュ エントリを作成し、それを先頭としてリストに追加し、マップに追加します。

最後に、容量を確認することを忘れないでください。新しいエントリが容量を超えた場合は、リストの最後尾である最も古いエントリを削除し、そのエントリをマップから削除します。

キャッシュ エントリの一部としてキーを保存すると、マップからキーを迅速に削除できることに注意してください。データをキャッシュ エントリにのみ保存した​​場合は、マップを反復処理してデータを見つける必要があります。

このキャッシュには、マルチスレッド アプリにとって重要な何かが欠けています。同期はありません。現実的には、キャッシュは複数のスレッドによってアクセスされます。同期は複雑なトピックです。私たちの実装では、キャッシュ構造体にミューテックスを追加できます:

type lruCache[T any] struct {
    capacity int
    keyMap   map[string]DoubleNode[lruCacheEntry[T]]
    list     DoubleLinkedList[lruCacheEntry[T]]
    mutex    sync.RWMutex
}

次に、各関数の先頭に次のコードを追加します。

    l.mutex.Lock()
    defer l.mutex.Unlock()

読み取り/書き込みロックを使用していることに注意してください。一部の関数はキャッシュの構造を変更しないため、提供されている読み取りロック メソッド、たとえば Len() 関数を使用できます。

func (l *lruCache[T]) Len() int {
    l.mutex.RLock()
    defer l.mutex.RUnlock()
    return len(l.keyMap)
}

キャッシュにアクセスしようとするスレッドが多数ある場合、ここで選択した同期戦略が失敗する可能性があることに注意してください。これは複雑なトピックであり、それ自体が一連の投稿になる可能性があります。

以下のリンクにあるリポジトリの完全な実装を参照してください。

キャッシュを実装するには何が違うでしょうか?同期についてはどのように対処しますか?これについてあなたの考えを聞きたいです。これに対する単一の解決策はありませんので、以下にコメントを書き込んでください。

ありがとうございます!

この投稿とこのシリーズのすべての投稿のコードはここにあります

以上がGo に LRU キャッシュを実装するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。