define

  • Lru algorithm, full name is Least Recently Used.
  • Lru is an elimination algorithm that weeds out the least recently used elements. When data has not been accessed in a recent period of time, it is very unlikely that it will be accessed in a subsequent period of time, so when the datapool is full, the data that has not been accessed for the longest time is eliminated.

implementation

You can do that with an array

  • A data access count identifier can be maintained for data.
  • First, define an array of fixed length. When a data is added to an array, it first looks for the same data in the array. If not, it adds the data to the array space and sets the number of accesses to the data to 0, and the number of accesses to all other data in the array to +1. If we find the same data in the array, we set the number of accesses to that data to 0 and the number of accesses to all other data in the array to +1. If you add new data, there is no space left in the array. To judge the array of data access the largest number of data to eliminate.
  • The disadvantage of using an array is that each insertion has to traverse the data and change the number of times the data is accessed, so the time complexity is O(N).
  • And the data algorithms that are being eliminated here are not perfect. When the array is full when you finally insert new data, and you find that the array has two equal access identifications and both have maximum values, you should also find the data that has been in the array for a long time, and then eliminate this data.

You can do that with a linked list

  • Implementing with an array results in traversing the entire array, so we can find an ordered data structure to implement the LRU algorithm. Then you can use a linked list data structure.
  • First, we define a linked list. We insert data into the head node and eliminate data from the tail node. When a data is added, the list is first traversed, and if the corresponding data is found, the data is moved to the head node of the list. If new data is being added, then the data is also added from the list header. If the list data capacity is full, data can be eliminated from the end of the list.
  • The disadvantage of implementing the LRU algorithm with a linked list is the same as the disadvantage of implementing it with an array. The time complexity is O(n). Data will also be inserted before traversing the linked list to check whether the data already exists.

This can be implemented using HashMap + linkedHashMap

  • If we want a time complexity of O(1) implementation algorithm, the use of HashMap quick lookup and linkedHashMap bidirectional list ordered and quick insertion and deletion to achieve the algorithm.
  • Define a HashMap and linkedhashmap. When adding a data, first create a key for the data, and put the key and data together in the head of the linked list, and store the key and the linked list node as value in the HashMap. If there are duplicate keys in the hashMap, the data already exists, and the value node corresponding to the key in the hashMap is removed and re-added to the list header (this is not necessary if it is already in the header). Finally, if the added data is the data capacity of the linked list is full, then remove the data of the node at the end of the list and delete the corresponding key-value in the hashMap (here because the linked list node contains key and value data, so we can find the corresponding key-value in the hashMap according to the linked list).
  • There is no traversal of the list structure, the use of hashMap quick search and two-way list of fast deletion and insertion (one-way list in the deletion is unable to quickly know the previous node node) to achieve THE LRU algorithm. So the time efficiency is much faster than the above two.

The actual case

Use of lRU obsolescence algorithm in mysql

  • Mysql’s data is stored on disk, and disk IO is a very time-consuming operation, so mysql has designed a bufferPool to reduce disk IO. A bufferPool is a contiguous block of memory. The default size of a bufferPool is 128 MB. You can customize it by modifying the configuration file. The bufferPool is divided into several 16K data pages (about 15K of data in the bufferPool, and 1K of data describing various information about the current page, including the next page, the disk address of the data, and so on).
  • Since the cache pool is full, mysql uses the LRU algorithm to eliminate the data. The least used data in the pool is eliminated. However, mysql’s lRU list is divided into hot data and cold data because of preread operation or full table scan.

The use of LRU elimination algorithm in Redis

  • Redis has several default strategies for weeding out data when it runs out of memory.

    • Noenviction: default policy. Write requests do not continue (DEL requests can be processed) and read requests can continue. This can ensure that data will not be lost, but will make online business can not continue.
    • Volatile-lru: Eliminates the least recently used data from a data set with a set expiration time. Keys whose expiration time is not set will not be eliminated.
    • Volatile -random: Indicates that data is randomly selected from the data set with an expiration time.
    • Volatile – TTL: Selects the data to expire from the data set whose expiration time has been set.
    • Allkeys-lru: Unlike volatile-lru, the key object to be eliminated is the entire set of keys.
    • Allkeys-random: Randomly selects data from all data sets for elimination.
    • Volatile – LFU: Use the LFU elimination algorithm for keys with expiration time (new in REDDIS4.0)
    • Allkeys-lfu: adopt lfu elimination algorithm for allkeys (newly added in redis4.0)

  • Study with an open mind and make progress together

Lru detailed reference links