LRU: Least Recently Used — алгоритм кэширования, при котором вытесняются значения, которые дольше всего не запрашивались. Алгоритмическая сложность O(1), а потому кеш работает очень быстро и используется в memcached.
Кеш имеет очередь фиксированного размера. Когда новый элемент попадает в кеш, то добавляется в начало очереди. При запросе элемента очередь выталкивает элемент в начало, а если нужно освободить место, то из вытесняется последний элемент.
Свой memcached на Go
Писать будем потоко-небезопасную реализацию LRU кэша с фиксированным количеством ячеек. В основе алгоритма двусвязный список и хеш-таблица. Двусвязный список будет очередью, а в хеш-таблицу запишем соответствия ключа и ссылки на значение.
import (
"container/list"
)
type Item struct {
Key string
Value interface{}
}
type LRU struct {
capacity int
items map[string]*list.Element
queue *list.List
}
func NewLru(capacity int) *LRU {
return &LRU{
capacity: capacity,
items: make(map[string]*list.Element),
queue: list.New(),
}
}
Структура LRU содержит поле с количеством ячеек, поле двусвязного списка *list.List и поле для хранения хеш-таблицы map[string]*list.Element. А Item содержит поля для хранения ключа и значения кэшируемого элемента. Функция конструктор NewLru инициализирует LRU и возвращает ссылку на экземпляр.
Сохраняем значение в кэше
При сохранении элемента в кеше, инициализируем новую структуру Item и добавляем ее в начало очереди c.queue.PushFront(item). Возвращенный очередью *Element добавляем в хеш-таблицу, где ключ это идентификатор записи, а значение это ссылка на элемент очереди.
func (c *LRU) Set(key string, value interface{}) bool {
if element, exists := c.items[key]; exists == true {
c.queue.MoveToFront(element)
element.Value.(*Item).Value = value
return true
}
if c.queue.Len() == c.capacity {
c.purge()
}
item := &Item{
Key: key,
Value: value,
}
element := c.queue.PushFront(item)
c.items[item.Key] = element
return true
}
Перед добавлением в очередь проверяем нет ли уже такого ключа в хеш-таблице и если есть, то заменяем значение на новое и двигаем в начало очереди c.queue.MoveToFront(element).
Если количество элементов очереди равно максимальному количеству ячеек, то пора выбросить последний элемент из очереди и ключ из хеш-таблицы вызвав функцию purge().
func (c *LRU) purge() {
if element := c.queue.Back(); element != nil {
item := c.queue.Remove(element).(*Item)
delete(c.items, item.Key)
}
}
Получаем значение из кэша
При запросе элемента из кеша, ищем соответствие ключа в хеш-таблице и при нахождении получаем значение элемента через каст значения на структуру element.Value.(*Item).Value. Перед возвращением перемещаем элемент в начало очереди.
func (c *LRU) Get(key string) interface{} {
element, exists := c.items[key]
if exists == false {
return nil
}
c.queue.MoveToFront(element)
return element.Value.(*Item).Value
}
Дальше можно добавить mutex и сделать функцию потоко-безопасной. А еще можно заменить количество ячеек на размер кеша по объему памяти хранимых сущностей.
