1. Введение в LRU
1.1 Обзор
Ресурсы кэша обычно дороже.Обычно, когда объем данных велик, можно удовлетворить как можно больше обращений из меньшего количества кэшей.Здесь предполагается, что к данным, к которым недавно обращались, скорее всего, будут обращаться впоследствии. Исходя из этого предположения, все данные сортируются по времени доступа, а старые данные выбрасываются, тогда кэшированные данные являются горячими данными, что не только экономит ресурсы памяти, но и значительно удовлетворяет доступу. используемый) алгоритм представляет собой алгоритм замены кеша, основанный на этом предположении.
1.2 Схема алгоритма
Предположим, что размер кеша равен 4, а порядок записи ABCDED F. Порядок доступа делится на две операции: запись и чтение.Запись должна обновить время доступа, и когда данные достигают максимального кеша, данные должны быть вытеснен, в то время как для чтения требуется только время доступа будет обновлено, а алгоритм замены записи показан на рисунке выше.
Когда размер кэша не достигнут, все данные сохраняются в том виде, в каком они были записаны, и записывается порядок записи.
При записи в E кеш уже заполнен, а значение E не существует.Необходимо вытеснить данные A, к которым не обращались дольше всего.В это время содержимое кеша равно E D C B.
Следующая запись в D, D находится в кеше, и непосредственно обновляется порядок доступа к D. В это время содержимое кеша D E C B
Следующая запись в F, F не находится в кеше, последний C в кеше удаляется, а содержимое кеша в это время F D E C
2 перейти к реализации
2.1 идеи
Используя go, вы можете использовать list plus map для реализации кэша LRU Конкретные идеи:
При записи сначала запрашивайте карту, если ее можно запросить, если значение можно запросить, переместите значение вперед в списке.Если значение не может быть запрошено, то оцените, достигла ли текущая карта максимального значения , если он достигает максимального значения. Значение состоит в том, чтобы удалить последнее значение из списка и одновременно удалить значение на карте, если емкость карты не достигает максимального значения, запишите карту и поместите значение в верхней части списка одновременно.
При чтении запрос из карты, если значение может быть запрошено, непосредственно переместите значение в списке на передний план и верните результат запроса.
Для обеспечения безопасности параллелизма необходимо ввести блокировки чтения-записи.
Кроме того, есть случай чтения карты контраста содержимого в Списке, потому что объект-контейнер объявлен для сохранения ключа и значения одновременно, а ссылки на объект-контейнер хранятся в Списке и в карте .
Внедрить атомарные объекты для подсчета попаданий и промахов и других индикаторов
2.2 Ключевой код
Полный код смотрите по адресу:cache
- Установить (операция записи)
func (c *MemCache) Set(key string, value interface{}) {
c.mutex.Lock()
defer c.mutex.Unlock()
if c.cache == nil {
c.cache = make(map[interface{}]*list.Element)
c.cacheList = list.New()
}
//判断是否在map中,如果在map中,则将value从list中移动到前面.
if ele, ok := c.cache[key]; ok {
c.cacheList.MoveToFront(ele)
ele.Value.(*entry).value = value
return
}
//如果不再map中,将值存到List最前面
ele := c.cacheList.PushFront(&entry{key: key, value: value})
c.cache[key] = ele
//判断是否到达容量限制,到达容量限制时删除List中最后面的值.
if c.maxItemSize != 0 && c.cacheList.Len() > c.maxItemSize {
c.RemoveOldest()
}
}
- Получить (чтение операции)
func (c *MemCache) Get(key string) (interface{}, bool) {
c.mutex.RLock()
defer c.mutex.RUnlock()
c.gets.Add(1)
//如果读取到值,移动在List中位置,并返回value
if ele, hit := c.cache[key]; hit {
c.hits.Add(1)
c.cacheList.MoveToFront(ele)
return ele.Value.(*entry).value, true
}
return nil, false
}