Самодельный потокобезопасный кэш с LRU‑очисткой

Условие

Необходимо создать упрощённую реализацию сервиса, аналогичного Redis, которая будет работать в многопоточной среде. Реализация должна обеспечивать безопасный конкурентный доступ к хранимым данным и включать механизм LRU (Least Recently Used) для автоматического удаления наименее часто используемых записей.

type ThreadSafeCache interface {
    Get(key string) (result string)
    Set(key, value string)
}

Для обеспечения потокобезопасности следует использовать синхронизацию (например, mutex’ы) и продумать стратегию обновления порядка использования элементов, чтобы корректно работать с LRU‑политикой при одновременных запросах.

Ответ

LRU удаляет наименее недавно использованный ключ, не наименее частый. Нужны map, двусвязный список и один mutex, включая Get.

Интерфейс не различает промах и сохранённую пустую строку — сохраняем это ограничение.

import (
    "container/list"
    "sync"
)

type cacheItem struct { key, value string }
type LRUCache struct {
    mu sync.Mutex
    capacity int
    order *list.List
    items map[string]*list.Element
}
func NewLRUCache(capacity int) *LRUCache {
    if capacity < 1 { panic("capacity must be positive") }
    return &LRUCache{
        capacity: capacity,
        order: list.New(),
        items: make(map[string]*list.Element),
    }
}
func (c *LRUCache) Get(key string) string {
    c.mu.Lock()
    defer c.mu.Unlock()
    e, ok := c.items[key]
    if !ok { return "" }
    c.order.MoveToFront(e)
    return e.Value.(cacheItem).value
}
func (c *LRUCache) Set(key, value string) {
    c.mu.Lock()
    defer c.mu.Unlock()
    if e, ok := c.items[key]; ok {
        e.Value = cacheItem{key, value}
        c.order.MoveToFront(e)
        return
    }
    c.items[key] = c.order.PushFront(cacheItem{key, value})
    if c.order.Len() > c.capacity {
        old := c.order.Back()
        delete(c.items, old.Value.(cacheItem).key)
        c.order.Remove(old)
    }
}

Создавайте кеш через конструктор и не копируйте его после использования. Get меняет порядок, поэтому обычной read-lock недостаточно. Сложность операций в среднем O(1), лимит задан в количестве записей, не байтах. Это локальный кеш, не распределённый Redis.