Por lo tanto, necesita un caché pequeño y no puede justificar una instancia de Redis o Memcached. Veamos qué se necesita para implementar uno en Go. Por diversión, lo haremos usando genéricos para que sea reutilizable en nuestro proyecto.

Un caché LRU generalmente tiene una capacidad fija y la política de expulsión más simple: expulsa el elemento que lleva más tiempo desde que se accedió. Un caché lru simple implementará la siguiente interfaz:

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 la caché almacenará un elemento de datos como una entrada codificada por algún valor. Eso suena como un mapa. ¿Qué pasa con la implementación de la política de expulsión? Una forma de hacerlo es mantener una propiedad timeAccessed junto con cada elemento. Algo como:

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

Sin embargo, pensemos en el rendimiento, queremos poder buscar la clave de caché, así como insertar y desalojar la más antigua, si es necesario, lo más rápido posible.

El uso de un mapa, que es una tabla hash, nos brindará un rendimiento bastante rápido para las búsquedas. ¿Qué tal encontrar la entrada más antigua? Si su estructura de caché se ve así:

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

Necesariamente necesitaremos iterar sobre el mapa para encontrar el más antiguo cuando llegue el momento de desalojar una entrada.

Necesitamos una forma de almacenar entradas de una manera que nos permita mantener ordenadas de manera eficiente una lista de entradas de caché. Es preferible que no necesitemos utilizar una rutina de clasificación.

Una lista de doble enlace es una buena manera de hacer esto y no necesitamos almacenar el tiempo de acceso en la entrada a menos que realmente lo queramos. Entonces supongamos que tenemos una lista vinculada que implementa lo siguiente junto con su estructura de nodo:

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

La estructura de caché ahora puede verse así:

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

La estructura de entrada de caché será:

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

De manera realista, probablemente usarías una interfaz para la clave de caché. Estoy usando una cadena para mantener el código simple.

En la implementación aquí, la entrada de la memoria caché a la que se accedió más recientemente estará al principio y la utilizada menos recientemente estará al final. Entonces, cuando llega el momento de desalojar, simplemente eliminamos el elemento final de la lista vinculada.

Implementar la función Get() es simple:

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 solo necesita recuperar la entrada del mapa para la clave, luego mover el nodo al principio de la lista, ya que ahora es el "usado más recientemente".

La función Put() es donde manejaremos el desalojo si es necesario:

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(), primero verificamos si ya existe un valor para la clave dada. Si es así, actualice el valor y mueva el nodo al principio de la lista. De lo contrario, creamos una nueva entrada de caché, la agregamos a la lista como encabezado y la agregamos a nuestro mapa.

Finalmente, no olvides verificar la capacidad. Si la nueva entrada nos supera la capacidad, desalojamos la entrada más antigua que está al final de la lista y eliminamos la entrada de nuestro mapa.

Tenga en cuenta que almacenar la clave como parte de la entrada de caché nos permite eliminar rápidamente la clave del mapa. Si solo hubiéramos almacenado los datos en la entrada de la caché, entonces necesitaríamos recorrer el mapa para encontrarlos.

A este caché le falta algo crítico para una aplicación de subprocesos múltiples. No hay sincronización. De manera realista, varios subprocesos accederían a un caché. La sincronización es un tema complejo. Para nuestra implementación, podemos agregar un mutex a la estructura de caché:

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

luego agregue lo siguiente al inicio de cada función.

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

Observe que estamos usando un bloqueo de lectura/escritura. Algunas de las funciones no cambian la estructura del caché, por lo que podemos usar el método de bloqueo de lectura proporcionado, por ejemplo la función Len():

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

Tenga en cuenta que la estrategia de sincronización elegida aquí puede fallar si hay una gran cantidad de subprocesos intentando acceder al caché. Es un tema complejo que podría abarcar una serie de publicaciones en sí mismo.

Vea la implementación completa en el repositorio que figura en el siguiente enlace.

¿Qué harías diferente para implementar un caché? ¿Cómo abordarías la sincronización? Estoy interesado en escuchar tu opinión sobre este. No existe una única solución para esto, así que deja tus comentarios a continuación.

¡Gracias!

El código de esta publicación y todas las publicaciones de esta serie se pueden encontrar aquí