предисловие
Мы часто используем кеш для повышения скорости запроса данных.Из-за ограниченной емкости кеша, когда емкость кеша достигает верхнего предела, необходимо удалить некоторые данные, чтобы переместить пространство, чтобы можно было добавить новые данные. Кэшированные данные не могут быть удалены случайным образом, обычно нам нужно удалять кешированные данные по определенному алгоритму. Распространенными алгоритмами исключения являются LRU, LFU, FIFO В этой статье мы поговорим об алгоритме LRU.
Введение в ЛРУ
LRUЭто аббревиатура Наименее недавно использованные, Этот алгоритм считает, что недавно использованные данные являются популярными данными и будут использоваться снова в следующий раз с высокой вероятностью. А данные, которые редко использовались в последнее время, с большой вероятностью не будут использованы в следующий раз. Когда емкость кэша заполнена, приоритет отдается данным, которые редко использовались в последнее время.
Предполагая, что кэшированные внутренние данные теперь такие, как показано:
Здесь мы называем первый узел списка головным узлом, а последний узел — хвостовым узлом.
При вызове кеша для получения данных с ключом=1 алгоритму LRU необходимо переместить узел 1 в головной узел, а остальные узлы остаются без изменений, как показано на рисунке.
Затем мы вставляем узел key = 8. В это время емкость кеша достигает верхнего предела, поэтому данные необходимо удалить перед присоединением. Поскольку каждый запрос будет перемещать данные в головной узел, данные, которые не были запрошены, опустятся в хвостовой узел, а данные в хвосте можно рассматривать как наименее используемые данные, поэтому удалите данные в хвостовом узле.
Затем мы добавляем данные непосредственно в головной узел.
Вот краткое изложение конкретных шагов алгоритма LRU:
- Новые данные вставляются прямо в начало списка
- Данные кэша попали, переместите данные в начало списка
- Когда кеш заполнится, удалите данные в конце списка.
Реализация алгоритма LRU
Как вы можете видеть в приведенном выше примере, алгоритм LRU должен добавлять головные узлы и удалять хвостовые узлы. Временная сложность добавления/удаления узлов в связанном списке составляет O(1), что очень подходит в качестве контейнера данных кеша хранилища. Однако обычные односвязные списки использовать нельзя.У односвязных списков есть несколько недостатков:
- Каждый раз, когда вы получаете какие-либо данные узла, вам нужно пройти от головного узла, что приводит к сложности получения узла O (N).
- Чтобы переместить промежуточный узел в головной узел, нам нужно знать информацию о предыдущем узле промежуточного узла, и для получения информации необходимо снова пройти односвязный список.
Ввиду вышеперечисленных проблем ее можно решить путем объединения с другими структурами данных.
Используя хэш-таблицу для хранения узлов, сложность получения узлов будет снижена до O(1). Для проблемы перемещения узла к узлу можно добавить указатель-предшественник для записи информации о предыдущем узле, так что связанный список изменится с односвязного списка на двусвязный список.
Таким образом, используется комбинация двусвязного списка и хеш-таблицы, а структура данных показана на рисунке:
Два «сторожевых» узла намеренно добавлены в двусвязный список и не используются для хранения каких-либо данных. Используя контрольные узлы, вы можете добавлять/удалять узлы, не учитывая отсутствие граничных узлов, что упрощает программирование и снижает сложность кода.
Код реализации алгоритма LRU выглядит следующим образом: для упрощения ключа val считается типом int.
public class LRUCache {
Entry head, tail;
int capacity;
int size;
Map<Integer, Entry> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
// 初始化链表
initLinkedList();
size = 0;
cache = new HashMap<>(capacity + 2);
}
/**
* 如果节点不存在，返回 -1.如果存在，将节点移动到头结点，并返回节点的数据。
*
* @param key
* @return
*/
public int get(int key) {
Entry node = cache.get(key);
if (node == null) {
return -1;
}
// 存在移动节点
moveToHead(node);
return node.value;
}
/**
* 将节点加入到头结点，如果容量已满，将会删除尾结点
*
* @param key
* @param value
*/
public void put(int key, int value) {
Entry node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
// 不存在。先加进去，再移除尾结点
// 此时容量已满 删除尾结点
if (size == capacity) {
Entry lastNode = tail.pre;
deleteNode(lastNode);
cache.remove(lastNode.key);
size--;
}
// 加入头结点
Entry newNode = new Entry();
newNode.key = key;
newNode.value = value;
addNode(newNode);
cache.put(key, newNode);
size++;
}
private void moveToHead(Entry node) {
// 首先删除原来节点的关系
deleteNode(node);
addNode(node);
}
private void addNode(Entry node) {
head.next.pre = node;
node.next = head.next;
node.pre = head;
head.next = node;
}
private void deleteNode(Entry node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
public static class Entry {
public Entry pre;
public Entry next;
public int key;
public int value;
public Entry(int key, int value) {
this.key = key;
this.value = value;
}
public Entry() {
}
}
private void initLinkedList() {
head = new Entry();
tail = new Entry();
head.next = tail;
tail.pre = head;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1));
cache.put(3, 3);
System.out.println(cache.get(2));
}
}
Анализ алгоритма LRU
Частота попаданий в кеш — очень важный показатель системы кеширования.Если частота попаданий в кеш системы кеширования слишком низкая, запрос будет возвращаться обратно в базу данных, что увеличит нагрузку на базу данных.
В сочетании с приведенным выше анализом преимуществ и недостатков алгоритма LRU.
Преимущество алгоритма LRU в том, что алгоритм не сложен в реализации, для горячих данных эффективность LRU будет очень хорошей.
Недостатком алгоритма LRU является то, что для случайных пакетных операций, таких как пакетный запрос исторических данных, можно заменить популярные данные в кеше этими историческими данными, вызывая загрязнение кеша, что приводит к падению частоты попаданий в кеш и замедлению. вниз обычные запросы данных.
Схема улучшения алгоритма LRU
Следующие решения получены из улучшенного алгоритма MySQL InnoDB LRU.
Разделите связанный список на две части, которые разделены на область горячих данных и область холодных данных, как показано на рисунке.
После доработки алгоритм станет следующим:
- Если данные доступа расположены в области горячих данных, они перемещаются в головной узел области горячих данных, как и в предыдущем алгоритме LRU.
- При вставке данных, если кэш заполнен, данные в хвостовом узле удаляются. затем преобразовать данныеВставить холодную область данныхголовной узел.
- Каждый раз при доступе к данным в области холодных данных необходимо принимать следующие решения:
- Если данные находились в кэше дольше указанного времени, например 1 с, перейдите к головному узлу области горячих данных.
- Если данные существуют в течение времени меньше указанного времени, позиция остается неизменной.
Для случайного пакетного запроса данные просто попадают в зону холодных данных, а затем быстро удаляются. Данные в популярной области данных не будут затронуты, что решает проблему снижения частоты попаданий в кэш алгоритма LRU.
Другие методы улучшения включают алгоритмы LRU-K, 2Q, LIRS, и заинтересованные студенты могут обратиться к ним самостоятельно.
Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: программа для общения, ежедневный толчок галантерейных товаров. Если вас интересует мой рекомендуемый контент, вы также можете подписаться на мой блог:studyidea.cn