Итак, вам нужен небольшой кеш, и вы не можете оправдать использование экземпляра 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
}

Мы знаем, что кеш будет хранить элемент данных как запись, связанную с некоторым значением. Это похоже на карту. А как насчет реализации политики изгнания? Один из способов сделать это — сохранить свойство 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)
}

Обратите внимание, что выбранная здесь стратегия синхронизации может дать сбой, если большое количество потоков пытается получить доступ к кешу. Это сложная тема, которая сама по себе может представлять собой серию публикаций.

Полную реализацию смотрите в репозитории, указанном по ссылке ниже.

Что бы вы сделали по-другому для реализации кэша? Как бы вы отнеслись к синхронизации? Мне интересно услышать ваши мысли по этому поводу. Единого решения этой проблемы не существует, поэтому оставляйте свои комментарии ниже.

Спасибо!

Код этого поста и всех постов из этой серии можно найти здесь