Полное название алгоритма LRU — алгоритм наименее недавно использовавшегося, который широко используется в механизме кэширования. Когда пространство, используемое кешем, достигает верхнего предела, необходимо удалить часть существующих данных, чтобы сохранить доступность кеша, а выбор исключенных данных осуществляется с помощью алгоритма LRU.
Основная идея алгоритма LRU — временная локальность, основанная на принципе локальности:
Если к элементу информации осуществляется доступ, вероятно, к нему снова будут обращаться в ближайшем будущем.
Как следует из названия, алгоритм LRU выберет для исключения данные, которые использовались реже всего.
принцип
В общем, LRU поддерживает порядок или время доступа к данным и самим данным в контейнере. При доступе к данным:
- Если данных нет в контейнере, установите наивысший приоритет данных и поместите их в контейнер.
- Если данные находятся в контейнере, приоритет обновления данных является наивысшим.
Когда общий объем данных достигает верхнего предела, данные с самым низким приоритетом в контейнере удаляются. На следующем рисунке показана простая схема принципа LRU:
если мы последуем7 0 1 2 0 3 0 4для доступа к данным, а верхний предел общего объема данных равен 3, как показано на рисунке выше, алгоритм LRU будет устранен в свою очередь7 1 2эти три данных.
Наивный алгоритм LRU
Теперь мы реализуем простой алгоритм LRU в соответствии с вышеуказанным принципом. Ниже есть три варианта:
-
на основе массива
Схема: К каждым данным прикрепляем дополнительный атрибут - метку времени, при каждом доступе к данным обновляем метку времени данных на текущее время. Когда пространство данных заполнено, сканируется весь массив и удаляются данные с наименьшей отметкой времени.
Недостаток: сохранение временных меток требует дополнительного места и сканирования всего массива при удалении данных.
-
Двусвязный список ограниченной длины
Схема: при доступе к фрагменту данных, когда данных нет в связанном списке, вставьте данные в заголовок связанного списка, а если они есть в связанном списке, переместите данные в заголовок связанного списка. Когда пространство данных заполнено, данные в конце связанного списка удаляются.
Недостаток: при вставке или извлечении данных необходимо сканировать весь связанный список.
-
На основе двусвязного списка и хеш-таблицы
Решение. Чтобы исправить описанный выше дефект, связанный с необходимостью сканирования связанного списка, взаимодействуйте с хэш-таблицей для формирования сопоставления между данными и узлами в связанном списке и уменьшите временную сложность операций вставки и чтения из O( от Н) до О(1)
Реализовать LRU на основе двусвязного списка + хэш-таблица
Далее мы реализуем алгоритм LRU на основе двусвязного списка и хеш-таблицы.
public class LRUCache {
private int size; // 当前容量
private int capacity; // 限制大小
private Map<Integer, DoubleQueueNode> map; // 数据和链表中节点的映射
private DoubleQueueNode head; // 头结点 避免null检查
private DoubleQueueNode tail; // 尾结点 避免null检查
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>(capacity);
this.head = new DoubleQueueNode(0, 0);
this.tail = new DoubleQueueNode(0, 0);
this.head.next = tail;
}
public Integer get(Integer key) {
DoubleQueueNode node = map.get(key);
if (node == null) {
return null;
}
// 数据在链表中，则移至链表头部
moveToHead(node);
return node.val;
}
public Integer put(Integer key, Integer value) {
Integer oldValue;
DoubleQueueNode node = map.get(key);
if (node == null) {
// 淘汰数据
eliminate();
// 数据不在链表中，插入数据至头部
DoubleQueueNode newNode = new DoubleQueueNode(key, value);
DoubleQueueNode temp = head.next;
head.next = newNode;
newNode.next = temp;
newNode.pre = head;
temp.pre = newNode;
map.put(key, newNode);
size++;
oldValue = null;
} else {
// 数据在链表中，则移至链表头部
moveToHead(node);
oldValue = node.val;
node.val = value;
}
return oldValue;
}
public Integer remove(Integer key) {
DoubleQueueNode deletedNode = map.get(key);
if (deletedNode == null) {
return null;
}
deletedNode.pre.next = deletedNode.next;
deletedNode.next.pre = deletedNode.pre;
map.remove(key);
return deletedNode.val;
}
// 将节点插入至头部节点
private void moveToHead(DoubleQueueNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
DoubleQueueNode temp = head.next;
head.next = node;
node.next = temp;
node.pre = head;
temp.pre = node;
}
private void eliminate() {
if (size < capacity) {
return;
}
// 将链表中最后一个节点去除
DoubleQueueNode last = tail.pre;
map.remove(last.key);
last.pre.next = tail;
tail.pre = last.pre;
size--;
last = null;
}
}
// 双向链表节点
class DoubleQueueNode {
int key;
int val;
DoubleQueueNode pre;
DoubleQueueNode next;
public DoubleQueueNode(int key, int val) {
this.key = key;
this.val = val;
}
}
По сути, описанная выше идея алгоритма LRU реализована в коде. Это относительно просто. Просто обратите внимание на указатели pre и next и синхронно обновите хэш-таблицу. Временная сложность операций put() и get() составляет O( 1), пространственная сложность равна O(N).
LRU на основе LinkedHashMap
На самом деле мы можем напрямую реализовать LRU в соответствии с LinkedHashMap, предоставленным JDK. Поскольку нижний слой LinkedHashMap представляет собой комбинацию двусвязного списка и хеш-таблицы, его можно использовать напрямую.
public class LRUCache extends LinkedHashMap {
private int capacity;
public LRUCache(int capacity) {
// 注意这里将LinkedHashMap的accessOrder设为true
super(16, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return super.size() >= capacity;
}
}
LinkedHashMap по умолчанию не удаляет данные, поэтому мы переписываем его метод removeEldestEntry().Когда количество данных достигает заданного верхнего предела, данные удаляются, а для accessOrder устанавливается значение true, что означает, что они сортируются в соответствии с порядком доступ. Объем кода всей реализации невелик, в основном используются характеристики LinkedHashMap.
Поскольку LinkedHashMap настолько прост в использовании, мы можем видеть кэш LRU Dubbo.LRUCacheОн также основан на нем.
Оптимизация алгоритма LRU
Простой алгоритм LRU смог удовлетворить требования к кэш-памяти, но все еще имеет некоторые недостатки. Когда есть много горячих данных, частота попаданий выше, но если есть случайные пакетные операции, горячие данные будут вытеснены из контейнера негорячими данными, что приведет к «загрязнению» кеша. Поэтому для устранения этого эффекта выводятся следующие методы оптимизации.
LRU-K
Алгоритм LRU-K является усовершенствованием алгоритма LRU.Изначальный критерий входа в очередь кеша изменен с одного посещения на K раз.Можно сказать, что простой алгоритм LRU – это LRU-1.
Алгоритм LRU-K имеет две очереди, одна из которых является очередью кэша, а другая — очередью истории доступа к данным. При доступе к фрагменту данных, во-первых, количество посещений накапливается в очереди истории доступа, и когда записи истории доступа превышают K раз, данные кэшируются в очереди кеша, тем самым избегая загрязнения очереди кеша. В то же время данные в исторической очереди могут быть удалены по правилам LRU. В частности, как показано на рисунке ниже:
Давайте реализуем кэш LRU-K:
// 直接继承我们前面写好的LRUCache
public class LRUKCache extends LRUCache {
private int k; // 进入缓存队列的评判标准
private LRUCache historyList; // 访问数据历史记录
public LRUKCache(int cacheSize, int historyCapacity, int k) {
super(cacheSize);
this.k = k;
this.historyList = new LRUCache(historyCapacity);
}
@Override
public Integer get(Integer key) {
// 记录数据访问次数
Integer historyCount = historyList.get(key);
historyCount = historyCount == null ? 0 : historyCount;
historyList.put(key, ++historyCount);
return super.get(key);
}
@Override
public Integer put(Integer key, Integer value) {
if (value == null) {
return null;
}
// 如果已经在缓存里则直接返回缓存中的数据
if (super.get(key) != null) {
return super.put(key, value);;
}
// 如果数据历史访问次数达到上限，则加入缓存
Integer historyCount = historyList.get(key);
historyCount = historyCount == null ? 0 : historyCount;
if (historyCount >= k) {
// 移除历史访问记录
historyList.remove(key);
return super.put(key, value);
}
}
}
Вышеупомянутая простая модель без добавления необходимого контроля параллелизма..
Вообще говоря, чем больше значение K, тем выше частота попаданий в кеш, но это также затрудняет удаление кеша. В целом показатели использования ЛРУ-2 самые лучшие.
Two Queue
Можно сказать, что Two Queue является вариантом LRU-2, изменяющим историю доступа к данным на очередь FIFO. Преимущества очевидны, FIFO проще и потребляет меньше ресурсов, но снизит частоту попаданий в кэш по сравнению с LRU-2.
// 直接继承LinkedHashMap
public class TwoQueueCache extends LinkedHashMap<Integer, Integer> {
private int k; // 进入缓存队列的评判标准
private int historyCapacity; // 访问数据历史记录最大大小
private LRUCache lruCache; // 我们前面写好的LRUCache
public TwoQueueCache(int cacheSize, int historyCapacity, int k) {
// 注意这里设置LinkedHashMap的accessOrder为false
super();
this.historyCapacity = historyCapacity;
this.k = k;
this.lruCache = new LRUCache(cacheSize);
}
public Integer get(Integer key) {
// 记录数据访问记录
Integer historyCount = super.get(key);
historyCount = historyCount == null ? 0 : historyCount;
super.put(key, historyCount);
return lruCache.get(key);
}
public Integer put(Integer key, Integer value) {
if (value == null) {
return null;
}
// 如果已经在缓存里则直接返回缓存中的数据
if (lruCache.get(key) != null) {
return lruCache.put(key, value);
}
// 如果数据历史访问次数达到上限，则加入缓存
Integer historyCount = super.get(key);
historyCount = historyCount == null ? 0 : historyCount;
if (historyCount >= k) {
// 移除历史访问记录
super.remove(key);
return lruCache.put(key, value);
}
return null;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return super.size() >= historyCapacity;
}
}
Здесь LinkedHashMap наследуется напрямую, а accessOrder по умолчанию имеет значение false, что означает сортировку в соответствии с порядком вставки, а их комбинация представляет собой очередь FIFO. Автоматически удалять самые старые вставленные данные, переопределяя метод removeEldestEntry().
Multi Queue
По сравнению с двумя вышеупомянутыми оптимизациями, реализация Multi Queue намного сложнее.Как следует из названия, Multi Queue состоит из нескольких очередей LRU. Каждая очередь LRU имеет соответствующий приоритет, и данные будут вычислять соответствующий приоритет в соответствии с количеством доступов и помещать их в очередь.
-
Вставка данных и доступ: когда данные вставляются в первый раз, они помещаются в очередь Q0 с самым низким приоритетом. При повторном доступе, согласно правилам LRU, он будет перемещен в начало очереди. При увеличении приоритета, рассчитанного на основе количества посещений, данные будут перемещены в начало очереди с более высоким приоритетом, а данные в исходной очереди будут удалены. Точно так же, когда приоритет данных снижается, они будут перемещены в очередь с более низким приоритетом.
-
Исключение данных: Исключение данных всегда выполняется с конца очереди с наименьшим приоритетом и добавляется в начало очереди Q-истории. В случае обращения к данным в Q-истории данных, приоритет данных пересчитывается и добавляется в очередь соответствующего приоритета. В противном случае он полностью устраняется по алгоритму LRU.
Multi Queue также можно рассматривать как вариант LRU-K, который расширяет исходные две очереди до нескольких очередей.
Суммировать
В этой статье объясняется базовый алгоритм LRU и несколько его стратегий оптимизации, а также сравниваются их сходства, различия, преимущества и недостатки. Я никогда не думал, что у LRU еще столько способов, и в будущем будут статьи о применении алгоритма LRU Redis и Mysql.