したがって、小規模なキャッシュが必要ですが、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)
}

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

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

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

ありがとう！

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