Интервьюер попросил меня спроектировать кэш LRU, и результат...

задняя часть
Интервьюер попросил меня спроектировать кэш LRU, и результат...

Друг Сяо Хэя недавно пошел на собеседование и в процессе задал ему несколько вопросов, связанных с кэшем.

Пусть ответит,Как спроектировать кэш LRU

Что касается моего друга, то он, наверное, плохо подготовил этот контент, да и не ответил на него, так что. . . Просто отпустите его домой и ждите уведомления.

Сегодня Сяо Хей расскажет вам об алгоритме LRU и о написании кэша LRU.

Какова стратегия ликвидации кеша?

В нашей обычной разработке мы часто используем кеш, например некоторые горячие товары, данные конфигурации и т.д., чтобы улучшить скорость доступа, они будут помещены в кеш, но емкость кеша часто ограничена, и мы не может поместить все данные в кеш Необходимо установить емкость для кеша.Когда емкость заполнена, когда новые данные помещаются в кеш, данные в исходном кеше должны быть удалены в соответствии с определенной стратегией, то эта стратегия называетсяПолитика удаления кеша.

Существует много вариантов стратегий удаления кеша, наиболее распространенными из которых являются FIFO (первый ввод — первый вывод), LRU (наименее недавно использованный), LFU (наименее часто используемый) и так далее.

Что такое ЛРУ

LRU — это сокращение от «наименее недавно использовавшиеся», что означаетНаименее недавно использованный, что означает, что наименее использовавшиеся данные удаляются.

Например, у нас есть следующая структура кэша:

В начале времени и пространства кеша мы помещаем в кеш элементы 5, 6 и 9 соответственно. Затем, когда мы помещаем элемент 3, пространство кеша было израсходовано, поэтому нам нужно удалить элемент и освободить Будьте уверены, элемент, в соответствии с логикой алгоритма LRU, последний использованный элемент в кэше в это время равен 5, поэтому 5 удаляется и помещается в элемент 3.

Далее давайте подумаем о том, как реализовать такую ​​структуру кэша LRU.Прежде чем мы начнем писать код, мы должны сначала уточнить условие, которому должен соответствовать наш кэш.

  • Емкость кэша ограничена
  • Когда емкость кэша израсходована, необходимо использовать алгоритм LRU для исключения элементов при добавлении новых элементов.
  • Временная сложность добавления элементов и запроса элементов должна быть O(1)
  • Работа кэша должна поддерживать параллелизм

Из-за некоторых из вышеперечисленных требований давайте сначала подумаем над следующим вопросом.

Как обеспечить временную сложность всех операций O(1)?

Чтобы найти ответ на этот вопрос, мы должны немного глубже задуматься о характеристиках кэша LRU.

Прежде всего, согласно нашей картинке в начале, кэш LRU должен быть структурой очереди, если элемент пересматривается, то элемент должен быть повторно помещен в начало очереди;

Тогда у нашей очереди есть предел вместимости: всякий раз, когда новый элемент должен быть добавлен в кеш, он добавляется в начало очереди, когда элемент должен быть удален, он удаляется из хвоста очереди;

Это гарантирует, что временная сложность добавления и удаления элементов равна O(1), так что, если мы хотим запросить элементы из кеша?

Думали ли вы обойти очередь и найти соответствующий элемент? Очевидно, что таким способом элемент можно найти, но временная сложность O(n), и когда количество данных в нашем кеше велико, время запроса элемента не фиксировано, оно может быть очень быстрым, и это может быть очень медленно.

Если вы просто используете очередь, временная сложность операции запроса не может быть O (1).

Как временная сложность запроса может стать O(1)?

Очереди не могут, а HashMap может.

Но проблема возникает снова, еслиИспользуя только HashMap, хотя временная сложность запроса может стать O (1), когда элементы удаляются, нет возможности удалить их с временной сложностью O (1)..

мы можем использоватьСвязанный список HashMap+Комбинация способов завершения структуры кэша LRU.

В приведенной выше структуре мы можем использовать ключ данных для кэширования в качестве ключа HashMap, чтобы гарантировать, что данные могут быть быстро найдены при запросе элементов;

В случае двусвязного списка гарантируется работа с головным узлом и хвостовым узлом при добавлении новых элементов и удалении элементов, возможно, за время O(1).

Разве теперь не очень ясна идея?

Хорошо, давайте теперь напишем идею реализации:

Во-первых, если ключ включен в HashMap, кеш попадает и элемент извлекается; если нет, это означает промах кеша.

Если кеш попадает:

  • Удалить элемент из списка и добавить элемент в начало списка;
  • Сохраните головной узел как значение в HashMap;

Если пропустите:

  • Добавьте элемент в начало связанного списка;
  • Сохраните головной узел связанного списка в HashMap.
  • Ну вот мы и можем написать код.

Код

Во-первых, мы определяем интерфейс Cache и определяем, какие методы есть у Cache в этой структуре:

/**
 * @author 小黑说Java
 * @ClassName Cache
 * @Description
 * @date 2022/1/13
 **/
public interface Cache<K, V> {
    
    boolean put(K key, V value);

    Optional<V> get(K key);

    int size();

    boolean isEmpty();

    void clear();
}

Далее давайте реализуем наш класс LRUCache, реализующий интерфейс Cache:

public class LRUCache<K, V> implements Cache<K, V> {
    private int size;
    private Map<K, LinkedListNode<CacheElement<K, V>>> linkedListNodeMap;
    private DoublyLinkedList<CacheElement<K, V>> doublyLinkedList;

    public LRUCache(int size) {
        this.size = size;
        this.linkedListNodeMap = new ConcurrentHashMap<>(size);
        this.doublyLinkedList = new DoublyLinkedList<>();
    }
    // ...其他方法
}

Во-первых, мы определяем Map и наш пользовательский двусвязный список DoublyLinkedList в LRUCache, который инициализируется в конструкторе.

Ниже приведен метод реализации конкретной операции.

поставить операцию

public boolean put(K key, V value) {
    CacheElement<K, V> item = new CacheElement<K, V>(key, value);
    LinkedListNode<CacheElement<K, V>> newNode;
    // 如果包含元素，表示缓存命中
    if (this.linkedListNodeMap.containsKey(key)) {
        // 从map中取出
        LinkedListNode<CacheElement<K, V>> node = this.linkedListNodeMap.get(key);
        // 将数据更新到链表最前面
        newNode = doublyLinkedList.updateAndMoveToFront(node, item);
    } else {
        // 未命中，如果缓存容量已用完，执行淘汰策略
        if (this.size() >= this.size) {
            this.evictElement();
        }
        // 创建新节点，添加到链表中
        newNode = this.doublyLinkedList.add(item);
    }
    if(newNode.isEmpty()) {
        return false;
    }
    // 将链表节点放入map中
    this.linkedListNodeMap.put(key, newNode);
    return true;
}

Во-первых, определите, существует ли Карта. Если есть попадание в кеш, обновите данные до головы связанного списка. В противном случае это указывает на промах. Вам нужно добавить новый узел в кеш, определить, нужна ли стратегия устранения для выполнения и, наконец, поместите новый элемент в карту.

существуетupdateAndMoveToFront()В методе узел в связанном списке обновляется на передний план, а код выглядит следующим образом:

public LinkedListNode<T> updateAndMoveToFront(LinkedListNode<T> node, T newValue) {
    // 节点不为空，并且该节点必须是在当前链表下
    if (node.isEmpty() || (this != (node.getListReference()))) {
        return dummyNode;
    }
    // 将原节点从链表中分离
    detach(node);
    // 新节点加入链表中
    add(newValue);
    return head;
}

Выполняется при реализации стратегии исключенияevictElement()Методы, как показано ниже:

private boolean evictElement() {
    // 移除尾节点
    LinkedListNode<CacheElement<K, V>> linkedListNode = doublyLinkedList.removeTail();
    if (linkedListNode.isEmpty()) {
        return false;
    }
    linkedListNodeMap.remove(linkedListNode.getElement().getKey());
    return true;
}

получить операцию

public Optional<V> get(K key) {
    LinkedListNode<CacheElement<K, V>> linkedListNode = this.linkedListNodeMap.get(key);
    if(linkedListNode != null && !linkedListNode.isEmpty()) {
        // 将命中节点移动到链表的头部，然后放入到Map中
        linkedListNodeMap.put(key, this.doublyLinkedList.moveToFront(linkedListNode));
        return Optional.of(linkedListNode.getElement().getValue());
    }
    return Optional.empty();
}

Операция получения очень проста.Во-первых, определите, существует ли узел или нет.Если он существует, переместите узел в начало связанного списка, а затем поместите его обратно на карту. Одно отличие от операции put заключается в том, что здесь используетсяmoveToFront()метод:

public LinkedListNode<T> moveToFront(LinkedListNode<T> node) {
    return node.isEmpty() ? dummyNode : updateAndMoveToFront(node, node.getElement());
}

На этом основные функции нашего кэша завершены. Но есть ли проблема?

Это проблематично, потому что мы не рассматривали сценарии параллелизма.Чтобы сделать наш LRUCache потокобезопасным, нам нужно сделать так, чтобы все операции поддерживали синхронизацию.

Для достижения синхронизации можно использовать synchronized или lock.Поскольку в сценарии использования кеша нет проблемы параллелизма между чтением и чтением, требуется только синхронизация между чтением и записью, а synchronized не поддерживает блокировки чтения-записи, поэтому мы можем использовать ReentrantReadWriteLock.

public class LRUCache<K, V> implements Cache<K, V> {
    private int size;
    private final Map<K, LinkedListNode<CacheElement<K,V>>> linkedListNodeMap;
    private final DoublyLinkedList<CacheElement<K,V>> doublyLinkedList;
	// 定义一个锁
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

    public LRUCache(int size) {
        this.size = size;
        this.linkedListNodeMap = new ConcurrentHashMap<>(size);
        this.doublyLinkedList = new DoublyLinkedList<>();
    }
// ...
}

блокировка записи

В нашем LRUCache операциями, которые должны добавить блокировки записи, являются put() и evictElement().

public boolean put(K key, V value) {
        // 加锁
        this.lock.writeLock().lock();
        try {
            CacheElement<K, V> item = new CacheElement<K, V>(key, value);
            LinkedListNode<CacheElement<K, V>> newNode;
            if (this.linkedListNodeMap.containsKey(key)) {
                LinkedListNode<CacheElement<K, V>> node = this.linkedListNodeMap.get(key);
                newNode = doublyLinkedList.updateAndMoveToFront(node, item);
            } else {
                if (this.size() >= this.size) {
                    this.evictElement();
                }
                newNode = this.doublyLinkedList.add(item);
            }
            if (newNode.isEmpty()) {
                return false;
            }
            this.linkedListNodeMap.put(key, newNode);
            return true;
        } finally {
            // 解锁
            this.lock.writeLock().unlock();
        }
    }

evictElement:

private boolean evictElement() {
    // 加锁
    this.lock.writeLock().lock();
    try {
        LinkedListNode<CacheElement<K, V>> linkedListNode = doublyLinkedList.removeTail();
        if (linkedListNode.isEmpty()) {
            return false;
        }
        linkedListNodeMap.remove(linkedListNode.getElement().getKey());
        return true;
    } finally {
        // 解锁
        this.lock.writeLock().unlock();
    }
}

блокировка чтения

При чтении данных нам также необходимо добавить блокировку чтения.

public Optional<V> get(K key) {
    // 添加读锁
    this.lock.readLock().lock();
    try {
        LinkedListNode<CacheElement<K, V>> linkedListNode = this.linkedListNodeMap.get(key);
        if (linkedListNode != null && !linkedListNode.isEmpty()) {
            linkedListNodeMap.put(key, this.doublyLinkedList.moveToFront(linkedListNode));
            return Optional.of(linkedListNode.getElement().getValue());
        }
        return Optional.empty();
    } finally {
        // 解锁
        this.lock.readLock().unlock();
    }
}

Теперь LRUCache может поддерживать одновременное использование.

резюме

Алгоритм LRU является широко используемым алгоритмом исключения. Когда есть горячие данные, эффективность очень хорошая. Однако алгоритм LRU также имеет некоторые недостатки. Например, если некоторые операции с пакетными данными выполняются время от времени, некоторые непопулярные данные сохраняются в кеш.Горячие данные будут удалены, что приведет к снижению эффективности. Эта ситуация называетсязагрязнение кеша.

Для решения проблемы загрязнения кеша можно использовать алгоритм расширения LRU LRU-K и еще один часто используемый алгоритм LFU.

Выше приведено все содержание этого выпуска.Если это поможет вам, поставьте лайк Сяо Хэю.

Я Сяо Хей, программист, который «выслеживает» Интернет.

Текущая вода не соревнуется за первое, а говорить дорого

Категории