Как работает двусвязный список в LRU кэше

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

Понимаете ли вы, зачем LRU нужна именно пара «хэш-таблица плюс двусвязный список» и почему каждая структура по отдельности не справляется. Следом просят написать Get и Put на Go и сделать кэш безопасным для нескольких горутин.

Как отвечать

Требование: Get и Put за O(1) и вытеснение ключа, к которому дольше всех не обращались.

• map: даёт поиск за O(1), но не знает порядка использования;
• двусвязный список: хранит порядок, в голове самый свежий элемент, в хвосте самый старый. Узел со ссылками prev и next вынимается из середины за O(1), если на него есть указатель. В односвязном списке для этого нужен предыдущий узел, а его поиск стоит O(n);
• связка: map[key]*node указывает прямо на узел списка.

Операции:

• Get: нашли узел в map, перенесли в голову, вернули значение;
• Put существующего ключа: обновили значение, перенесли в голову;
• Put нового ключа: если ёмкость исчерпана, сняли узел с хвоста и удалили его ключ из map через delete(m, node.key), затем вставили новый узел в голову.

Узел обязан хранить ключ, иначе при вытеснении не узнать, какую запись удалить из map. Фиктивные узлы head и tail избавляют от проверок на nil по краям.

В Go список не обязательно писать руками: пакет container/list даёт двусвязный список с MoveToFront, PushFront, Back и Remove, а в map кладётся *list.Element. Для конкурентного доступа нужен sync.Mutex. RWMutex тут не выигрывает: даже Get меняет порядок в списке, то есть пишет.

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

При вытеснении пишут m[key] = nil вместо delete(m, key). Длина map не уменьшается, а следующий Get по этому ключу найдёт nil и уронит программу паникой.

Забывают перенести элемент в голову при Get или при обновлении в Put, и кэш превращается в FIFO.

Берут RLock в Get, потому что «это же чтение», и получают гонку на указателях списка. Её сразу покажет go test -race.