Java-реализация алгоритма LRU

Java

Введение в алгоритм LRU

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

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

Алгоритм очень прост, вам нужно только отсортировать все данные по времени использования, а когда вам нужно отфильтровать данные LRU, вы можете выбрать более низкий ранг.

Реализация алгоритма

LRU в Redis

Объем данных в Redis обычно огромен, и если каждый раз сортировать полный объем данных, это неизбежно скажется на пропускной способности сервиса. Поэтому, когда Redis удаляет некоторые ключи в LRU, он использует выборку и вычисляет приблизительный LRU, поэтому локальные данные LRU исключаются.

Стратегия устранения памяти Redis

maxmemory-policyНастройте дополнительные параметры:

  • noeviction: Не устранено, команда записи вернет ошибку после превышения лимита памяти (например, OOM, кроме команд del)
  • allkeys-lru: Механизм LRU всех ключей Удалите ключи по принципу LRU наименее недавно использовавшегося во всех ключах, чтобы освободить место
  • volatile-lru: LRU энергозависимого ключа используется только для LRU в пределах диапазона ключа установленного времени истечения (если время истечения установлено, оно не будет устранено)
  • allkeys-random: Все ключи исключаются случайным образом без дискриминации, случайным образом
  • volatile-random: Случайный выбор для изменчивого ключа Установите случайный только в пределах диапазона ключа времени истечения срока действия.
  • volatile-ttl: исключение TTL для энергозависимых ключей Удаление приоритета в соответствии с ключом с наименьшим значением TTL

Эффекты Redis LRU

Вверху слева — теоретический эффект LRU; вверху справа — приблизительный LRU в Redis3.0 (выборочное значение 10); внизу слева — приблизительный LRU в Redis2.8 (выборочное значение 5); внизу справа — приблизительный LRU в Redis3.0 (выборочное значение 5). ))

светло-серый - устранено; серый - не устранено; зеленый - вновь записано

Дополнительные инструкции:

  • Удаление памяти будет выполняться только при достижении установленного порога использования памяти.
  • maxmemory-samplesКонфигурация представляет значение выборки, количество выборок, собираемых при каждом его удалении - значение выборки равно 10, что означает, что 10 ключей берутся из ключей, определенных в настройках для расчета LRU, и ключ, удаляющий LRU.
  • Алгоритм в Redis 3.0 создает «пул кандидатов», который повышает эффективность и точность алгоритма по сравнению с 2.8, поскольку диапазон уменьшается.

в заключении:

  • Redis3.0 повышает точность LRU за счет увеличения пула кандидатов, и эффект лучше, чем 2,8.
  • Чем выше значение выборки, тем ближе результат к теоретическому LRU (но чем выше значение выборки, тем ниже эффективность).
  • Достаточно точна почти частота дискретизации 5. Конечно, использование 10 в основном близко к теоретическому результату LRU, но теряет эффективность.

Идеи реализации LRU в Java

Согласно алгоритму LRU, реализация на Java требует выполнения следующих условий:

  • Базовые данные используют двусвязный список, который удобно удалять в любом месте связанного списка и добавлять в конец связанного списка.
    • Это более трудоемко использовать односвязный список, конечно, также трудоемко использовать такие структуры, как массивы
    • Конечно, двусвязный список также вызывает затруднения при поиске, но в сочетании с HashMap можно использовать следующее:
  • Связанный список необходимо отсортировать в порядке доступа (использования)
  • После того, как объем данных превысит определенный порог, наименее использовавшиеся данные необходимо удалить.

Простая реализация LRUCache на Java

Для приведенных выше идей реализацииjava.util.LinkedHashMap99% из них реализованы, поэтому реализовать LRUCache напрямую на основе LinkedHashMap очень просто.

Что LinkedHashMap прокладывает путь для LRUCache

  • Конструктор предоставляетaccessOrderПараметр, при включении которого метод get будет иметь дополнительные операции, чтобы убедиться, что порядок связанного списка находится в порядке, обратном порядку доступа.
  • Базовая структура использует двусвязный список для поиска функций, которые могут использовать HashMap.
  • Переопределяет родительский класс HashMapnewNodeМетоды иnewTreeNodeметод, эти два метода используются только для создания Node в HashMap, в то время как в LinkedHashMap не только создается Node, но и помещается Node в конец связанного списка
  • Родительский класс HashMap предоставляет 3 метода void Hook, которые ничего не делают:
    • afterNodeRemovalРодительский класс вызывается после удаления элемента, существующего в коллекции.
    • afterNodeInsertionРодительский класс вызывается после ввода, вычисления, слияния
    • afterNodeAccessРодительский класс будет вызываться после замены, вычисления, слияния и других значений замены, LinkedHashMap будет вызываться, когда accessOrder включен в get,Суть в том, что он будет вызываться, когда будет операция над данными
  • LinkedHashMap по существу повторно использует большинство функций HashMap, включая базовый Node[], поэтому он может поддерживать функции исходного HashMap.
  • Но LinkedHashMap реализует 3 метода Hook родительского класса HashMap:
    • afterNodeRemovalРеализовать операцию удаления связанного списка
    • afterNodeInsertion Операция вставки связанного списка не реализована, но добавлен новый метод Hookboolean removeEldestEntry, когда этот метод Hook возвращает значение true, удалите узел в начале связанного списка.
    • afterNodeAccessКак упоминалось выше, после включения accessOrder управляемый узел будет помещен в конец связанного списка, чтобы убедиться, что связанный список расположен в порядке, обратном порядку доступа.
  • Последние три метода используются для построения двусвязного списка, а LinkedHashMap также охватывает три метода родительского класса:
    • newNodeПри создании узла добавьте узел в конец связанного списка.
    • newTreeNodeПри создании TreeNode добавьте узел в конец связанного списка.
    • getКогда функция get завершена, если accessOrder включен, будет вызываться afterNodeAccess для перемещения узла в конец связанного списка. обложкаnewNodeиnewTreeNodeметод, вызываемый в методе putnewNodeиnewTreeNodeМетод также реализует операцию вставки связанного списка.

Таким образом, мы можем понять, почему LinkedHashMap может легко реализовать LRUCache.

  1. Унаследовав родительский класс HashMap, он имеет функцию HashMap, поэтому временная сложность поиска узла составляет O(1), плюс связанный список является двунаправленным, удалить любой узел в связанном списке очень просто
  2. С помощью 3 методов Hook, предоставляемых HashMap и охватывающих 2 метода создания Node, реализуется добавление и удаление собственного связанного списка, а построение собственного связанного списка гарантированно выполняется правильно, не затрагивая исходную функцию Array; этот процесс на самом деле. Исходные функции улучшены с помощью метода Hook, потому что метод Hook фактически используется для создания узлов в исходном HashMap.
  3. предоставить атрибутыaccessOrderи понялafterNodeAccessметод, поэтому самые последние использованные или недавно вставленные данные могут быть помещены в конец связанного списка в соответствии с порядком доступа или операции, а данные, которые давно не использовались, ближе к началу связанного list, понимая, что весь связанный список отсортирован согласно требованиям LRU
  4. Предоставляет метод Hookboolean removeEldestEntry, когда этот метод возвращает true, будет удален узел заголовка, то есть тот узел, который должен быть устранен в LRU, но реализация этого метода в LinkedHashMap всегда будет возвращать false

До сих пор реализация LRUCache проста: реализуйте этоremoveEldestEntryМетод Hook устанавливает порог для LinkedHashMap, и при превышении порога будет выполняться устранение LRU.

Реализация кода Java, которую можно увидеть повсюду в Интернете

	// 继承LinkedHashMap
	public class LRUCache<K, V> extends LinkedHashMap<K, V> {
		private final int MAX_CACHE_SIZE;

		public LRUCache(int cacheSize) {
			// 使用构造方法 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
			// initialCapacity、loadFactor都不重要
			// accessOrder要设置为true，按访问排序
			super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
			MAX_CACHE_SIZE = cacheSize;
		}

		@Override
		protected boolean removeEldestEntry(Map.Entry eldest) {
			// 超过阈值时返回true，进行LRU淘汰
			return size() > MAX_CACHE_SIZE;
		}

	}

То, что кажется решенным с помощью нескольких строк кода, на самом деле является лишь верхушкой айсберга.

использованная литература

Использование Redis в качестве кэша LRU — Redis

Эта статья адаптирована измой блог, добро пожаловать в гости!

Категории