Introduction to LRU algorithm

The full name of the LRU algorithm is Least Recently Used, which checks the Least Recently Used data. This algorithm is commonly used in memory flushing strategies to move less-used data out of memory to make room for more recently used “hot data.”

I don’t know whether it is in the operating system course or the computer composition principle course. It is also widely used in Redis, Guava and other tools, even one of the most core ideas. If you need to design your own system in the future, the idea of LRU will still be important, even if you don’t implement the algorithm yourself.

The algorithm is very simple. It only needs to sort all the data according to the use time. When it is necessary to screen out LRU data, it can take the lowest ranking.

Algorithm implementation

The LRU in Redis

The amount of data in Redis is usually very large, and if you sort the full amount of data each time, you will inevitably have an impact on service throughput. Therefore, when Redis removes partial keys from LRU, it takes samples and calculates approximate LRU, so local LRU data is eliminated.

Redis memory elimination strategy

This parameter is optional.

  • noevictionWrite commands will return an error (except for OOM and del commands)
  • allkeys-lru: LRU mechanism of all keys Deletes keys based on the least recently used LRU principle to release space
  • volatile-lru: LRU of losable key is used only for LRU within the range of key set expiration time (if the expiration time is set, it will not be eliminated)
  • allkeys-random: All keys randomly eliminated equally, randomly
  • volatile-randomRandomness in the Key expiration time range
  • volatile-ttl: TTL elimination for volatile keys The key with the smallest TTL is eliminated first

Redis LRU effect

Top left – Theoretical LRU effect; Upper right – Approximate LRU in Redis3.0 (sample value 10); Lower left – approximate LRU in Redis2.8 (sample value 5); Lower right – Approximate LRU in Redis3.0 (sample value 5)

Light grey – eliminated; Gray – not eliminated; Green – New write

Supplementary notes:

  • The memory is eliminated only when the memory usage threshold is reached
  • maxmemory-samplesThe configuration represents the sample value, the number of samples collected for each deletion — the sample value is 10, which means that 10 keys are taken from the keys defined in the Settings for LRU calculation and the key of the LRU is deleted
  • The algorithm in Redis3.0 establishes a “candidate pool” that makes the algorithm more efficient and accurate than 2.8 because the range is reduced

Conclusion:

  • Redis3.0 improves LRU accuracy by adding candidate pools, which is better than 2.8
  • The higher the sample value, the closer the result is to the theoretical LRU (but the more efficient the sample value is)
  • Almost the sampling rate of 5 is accurate enough. Of course, using 10 is basically close to the theoretical LRU result, but the efficiency is lost

Java LRU implementation ideas

According to the LRU algorithm, implementation in Java requires these conditions:

  • The underlying data uses a two-way linked list, which can be easily deleted anywhere in the list and added at the end of the list
    • That’s a little bit harder to do with a single linked list, but it’s also a little bit harder to do with arrays and things like that
    • Of course, bidirectional lists can be tricky to find, but the following can be used in conjunction with hashMaps
  • You need to sort the linked list in order of access (use)
  • If the data amount exceeds a certain threshold, delete the Least Recently Used data

Java in a simple LRUCache implementation

Java.util.LinkedHashMap already implements 99% of the above implementation ideas, so it is easy to implement LRUCache directly based on LinkedHashMap.

What does LinkedHashMap pave the way for LRUCache

  • The constructor providesaccessOrderIf enabled, the get method takes extra action to ensure that the list is sorted in reverse order of access
  • The underlying structure uses a bidirectional linked list to find features where HashMap can be used
  • Overrides the parent class HashMapnewNodeMethods andnewTreeNodeMethods are used to create nodes only in a HashMap, whereas in a LinkedHashMap nodes are created and placed at the end of the list
  • The parent class HashMap provides three void Hook methods that do nothing:
    • afterNodeRemovalThe superclass is called after removing elements that exist in a collection
    • afterNodeInsertionThe parent class is called after put, compute, merge
    • afterNodeAccessThe parent class is called after replacing values like replace, compute, merge, etc. LinkedHashMap is called when accessOrder is enabled in GET.It is called when there is an operation on data
  • LinkedHashMap essentially reuses most of the functionality of HashMap, including the underlying Node

    [], and therefore supports the functionality of the original HashMap
    ,>
  • But LinkedHashMap implements the three Hook methods of its parent HashMap class:
    • afterNodeRemovalDelete the linked list operation
    • afterNodeInsertion List inserts are not implementedBut a Hook method has been addedboolean removeEldestEntryWhen the Hook method returns true, the list header is removed
    • afterNodeAccessAs mentioned earlier, enabling accessOrder places the nodes being operated on at the end of the linked list, ensuring that the list order is in reverse order of access
  • LinkedHashMap also overwrites the parent class’s three methods:
    • newNodeWhen you create a Node, add Node to the end of the list
    • newTreeNodeAs you create the TreeNode, add Node to the end of the list
    • getAfterNodeAccess is called to move nodes to the end of the list if accessOrder is enabled while GET is donenewNodeandnewTreeNodeMethod, called in the PUT methodnewNodeandnewTreeNodeMethod also implements linked list insertion operations

To sum up, we can see why LinkedHashMap can easily implement LRUCache

  1. Inherits the parent class HashMap and has the function of HashMap, so the time complexity of searching a node is O(1). In addition, the linked list is bidirectional, so it is very simple to delete any nodes of the linked list
  2. Through three Hook methods provided by HashMap and covering two methods to create Node, the addition and deletion of its own linked list is realized, ensuring that the original Array function is not affected, and the correct completion of its own linked list construction; This process is actually Hook enhanced, because the original HashMap nodes are actually created using Hook methods
  3. Provides propertiesaccessOrderAnd implementedafterNodeAccessMethod, so that the most recently used or recently inserted data can be placed at the end of the linked list according to the order of access or operation, the longer the data has not been used, the closer to the head of the linked list, to achieve the whole list in accordance with the requirements of the LRU
  4. A Hook method is providedboolean removeEldestEntryWhen this method returns true, it removes the header node that should be eliminated from the LRU, but the implementation of this method in LinkedHashMap always returns false

At this point, implementing a LRUCache is simple: implement the removeEldestEntryHook method and set a threshold for the LinkedHashMap, beyond which LRU elimination will occur.

Java code implementations everywhere on the web

	/ / LinkedHashMap inheritance
	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 and loadFactor are not important
			// accessOrder is set to true and sorted by access
			super((int) Math.ceil(cacheSize / 0.75) + 1.0.75 f.true);
			MAX_CACHE_SIZE = cacheSize;
		}

		@Override
		protected boolean removeEldestEntry(Map.Entry eldest) {
			// Return true if the threshold is exceeded for LRU elimination
			returnsize() > MAX_CACHE_SIZE; }}Copy the code

What looks like a few lines of code is just the tip of the iceberg.

The resources

Using Redis as an LRU cache — Redis

This article moves my blog, welcome to visit!