Portanto, você precisa de um cache pequeno e não pode justificar uma instância Redis ou memcached. Vamos ver o que é necessário para implementar um em Go. Por diversão, faremos isso usando genéricos para que seja reutilizável em nosso projeto.

Um cache LRU geralmente tem capacidade fixa e a política de ejeção mais simples: ejeta o elemento que possui o maior tempo desde que foi acessado. Um cache lru simples implementará a seguinte interface:

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
}

Sabemos que o cache armazenará um item de dados como uma entrada que é digitada por algum valor. Isso soa como um mapa. Que tal implementar a política de ejeção? Uma maneira de fazer isso é manter uma propriedade timeAccessed junto com cada item. Algo como:

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

No entanto, vamos pensar no desempenho, queremos ser capazes de procurar a chave de cache, bem como inserir e despejar a mais antiga, se necessário, o mais rápido possível.

Usar um mapa, que é uma tabela hash, nos proporcionará um desempenho bastante rápido para pesquisas. Que tal encontrar a entrada mais antiga? Se a estrutura do seu cache for semelhante a:

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

Precisaremos necessariamente percorrer o mapa para encontrar o mais antigo quando chegar a hora de despejar uma entrada.

Precisamos de uma maneira de armazenar entradas de uma forma que nos permita manter uma lista de entradas de cache ordenada de maneira eficiente. É preferível que não precisemos usar uma rotina de classificação.

Uma lista duplamente vinculada é uma boa maneira de fazer isso e não precisamos armazenar o tempo de acesso na entrada, a menos que realmente queiramos. Então, vamos supor que temos uma lista vinculada que implementa o seguinte junto com sua estrutura de nó:

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]
}

A estrutura do cache agora pode ser semelhante a:

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

A estrutura de entrada do cache será:

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

Realisticamente, você provavelmente usaria uma interface para a chave de cache. Estou usando uma string para manter o código simples.

Na implementação aqui, a entrada acessada mais recentemente no cache estará no início e a menos usada recentemente estará no final. Então, quando chega a hora de despejar, simplesmente removemos o elemento final da lista vinculada.

Implementar a função Get() é simples:

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 só precisa recuperar a entrada do mapa para a chave e, em seguida, mover o nó para o topo da lista, pois agora é o 'usado mais recentemente'.

A função Put() é onde trataremos do despejo se for necessário:

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)
    }
}

Para Put(), primeiro verificamos se já existe um valor para a chave fornecida. Nesse caso, atualize o valor e mova o nó para o topo da lista. Caso contrário, criamos uma nova entrada de cache, adicionamos-a à lista como cabeçalho e adicionamos-a ao nosso mapa.

Finalmente, não se esqueça de verificar a capacidade. Se a nova entrada nos ultrapassar a capacidade, expulsamos a entrada mais antiga, que é o final da lista, e excluímos a entrada do nosso mapa.

Observe que armazenar a chave como parte da entrada do cache nos permite excluir rapidamente a chave do mapa. Se tivéssemos armazenado os dados apenas na entrada do cache, precisaríamos iterar no mapa para encontrá-los.

Este cache está faltando algo crítico para um aplicativo multithread. Não há sincronização. Realisticamente, um cache seria acessado por vários threads. A sincronização é um tópico complexo. Para nossa implementação, podemos adicionar um mutex à estrutura de cache:

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

em seguida, adicione o seguinte no início de cada função.

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

Observe que estamos usando um bloqueio de leitura/gravação. Algumas das funções não alteram a estrutura do cache, então podemos usar o método read lock fornecido, por exemplo a função Len():

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

Observe que a estratégia de sincronização escolhida aqui pode falhar se houver um grande número de threads tentando acessar o cache. É um tópico complexo que poderia ser uma série de postagens.

Veja a implementação completa no repositório fornecido no link abaixo.

O que você faria de diferente para implementar um cache? Como você abordaria a sincronização? Estou interessado em ouvir sua opinião sobre este. Não há uma solução única para isso, então deixe seus comentários abaixo.

Obrigado!

O código desta postagem e de todas as postagens desta série pode ser encontrado aqui