Как устроен LRU кэш и какими структурами данных реализовать его логику

Что проверяют

Понимаете ли вы, почему для O(1) нужны сразу хеш-таблица и двусвязный список, и умеете ли сделать кеш безопасным для горутин. Следом обычно спрашивают, какой мьютекс вы поставите и почему не sync.RWMutex.

Как отвечать

LRU вытесняет элемент, к которому дольше всех не обращались. Структуры:

• *`map[K]list.Element`**: доступ по ключу за O(1);
• двусвязный список из container/list: порядок использования. MoveToFront при чтении, PushFront при вставке, Back и Remove при вытеснении, всё за O(1);
• запись в элементе: в Value кладут структуру с ключом и значением, потому что при вытеснении хвоста ключ нужен для delete из map;
• типизация: container/list хранит any, и на каждом чтении нужно утверждение типа. С дженериками (Go 1.18+) удобнее написать свой типизированный список или взять hashicorp/golang-lru/v2, где есть и вариант с TTL.

Про конкурентность скажите отдельно: map в Go не безопасна для одновременной записи, гонку ловит go test -race, а без синхронизации рантайм может упасть с fatal error: concurrent map writes. Причём Get в LRU тоже пишет: он двигает элемент в списке. Поэтому RWMutex с RLock на чтении не подходит, нужен обычный sync.Mutex. Под высокой нагрузкой один мьютекс становится узким местом, и кеш шардируют: N независимых LRU, ключ распределяется по хешу.

Для больших кешей добавьте мысль о GC: миллион элементов с указателями сборщик вынужден обходить при каждой разметке. Поэтому кеши вроде bigcache хранят данные в байтовых срезах без указателей, а ristretto вместо чистого LRU использует допуск по частоте на основе TinyLFU.

Где спотыкаются

Ставят RLock в Get, потому что «это же чтение». Перемещение в списке это запись, и под нагрузкой такой кеш ломает собственную структуру.

Забывают хранить ключ в элементе списка и при вытеснении не могут удалить запись из map, кеш растёт без предела.

Путают LRU с TTL. LRU ограничивает размер, а устаревшие данные сам по себе не выкидывает; если данные протухают, нужен срок жизни поверх вытеснения.