Shulou(Shulou.com)06/02 Report--

This article mainly explains the "implementation principle of the LRU algorithm". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "the implementation principle of the LRU algorithm".

Preface

We often use cache to improve the speed of data query. due to the limited cache capacity, when the cache capacity reaches the upper limit, we need to delete part of the data to set aside space, so that new data can be added. Cached data cannot be deleted randomly. In general, we need to delete cached data according to some algorithm. Commonly used elimination algorithm is LRU,LFU,FIFO, this article we talk about LRU algorithm.

Introduction to LRU

LRU is an acronym for Least Recently Used, and this algorithm assumes that the recently used data is hot and will most likely be used again next time. There is a good chance that data, which is rarely used recently, will not be used next time. When the cache capacity is full, priority is given to eliminating data that is rarely used recently.

Suppose the internal data is now cached as shown in the figure:

Here we call the first node in the list the header node and the last node the tail node.

When calling the cache to get the data of key=1, the LRU algorithm needs to move the node 1 to the header node, and the rest of the nodes remain the same, as shown in the figure.

Then we insert a key=8 node, and the cache capacity reaches the limit, so we need to delete the data before joining. Because each query will move the data to the head node, the unqueried data will sink to the tail node, and the tail data can be considered as the least accessed data, so delete the data of the tail node.

Then we add the data directly to the header node.

Here is a summary of the specific steps of LRU algorithm:

The new data is inserted directly into the list header

The cache data is hit and the data is moved to the list header

Remove the data at the end of the list when the cache is full.

Implementation of LRU algorithm

As you can see in the above example, the LRU algorithm needs to add a header node and delete the tail node. The time complexity of adding / deleting nodes in the linked list is O (1), which is very suitable to be used as a storage cache data container. However, ordinary one-way linked lists cannot be used. One-way linked lists have several disadvantages:

Every time the data of any node is obtained, it needs to be traversed from the header node, which leads to the complexity of the acquisition node is O (N).

When we move the intermediate node to the head node, we need to know the information of the previous node in the intermediate node, and the one-way linked list has to traverse again to get the information.

In view of the above problems, can be combined with other data structures to solve.

Using hash table storage nodes, the complexity of getting nodes will be reduced to O (1). The node movement problem can add a leading pointer to the node to record the last node information, so that the linked list changes from an one-way linked list to a two-way linked list.

In summary, a combination of two-way linked list and hash table is used, and the data structure is shown in the figure:

Two Sentinel nodes are specially added to the two-way linked list so as not to store any data. Using Sentinel nodes, you can add / delete nodes without considering the non-existence of boundary nodes, simplify programming difficulty and reduce code complexity.

The implementation code of the LRU algorithm is as follows. In order to simplify the key, val considers the int type.

Public class LRUCache {Entry head, tail; int capacity; int size; Map cache; public LRUCache (int capacity) {this.capacity = capacity; / / initialize the linked list initLinkedList (); size = 0; cache = new HashMap (capacity + 2);} / * * returns-1 if the node does not exist. If present, move the node to the header node and return the node's data. * * @ param key * @ return * / public int get (int key) {Entry node = cache.get (key); if (node = = null) {return-1;} / / Mobile node moveToHead (node); return node.value } / * add the node to the head node. If the capacity is full, the tail node * * @ 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 } / / does not exist. Add it first, and then remove the tail node / / delete the tail node if (size = = capacity) {Entry lastNode = tail.pre; deleteNode (lastNode); cache.remove (lastNode.key); size--;} / / add the header node Entry newNode = new Entry (); newNode.key = key NewNode.value = value; addNode (newNode); cache.put (key, newNode); size++;} private void moveToHead (Entry node) {/ / first delete the relationship of the original 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 algorithm Analysis

The cache hit rate is a very important indicator of the cache system. If the cache hit rate of the cache system is too low, it will cause the query to flow back to the database and increase the pressure on the database.

Combined with the above analysis of the advantages and disadvantages of LRU algorithm.

The advantage of LRU algorithm is that it is not difficult to implement, for hot data, LRU efficiency will be very good.

The disadvantage of LRU algorithm is that for occasional batch operations, such as batch query of historical data, it may make the hot data in the cache be replaced by these historical data, resulting in cache pollution, resulting in a decline in cache hit rate and slowing down the normal data query.

Improvement Scheme of LRU algorithm

The following solution sources and the improved MySQL InnoDB LRU algorithm

Split the linked list into two parts, divided into hot data area and cold data area, as shown in the figure.

After the improvement, the algorithm flow will be as follows:

If the access data is located in the hot data area, it is moved to the head node of the hot data area, as in the previous LRU algorithm.

When inserting data, if the cache is full, eliminate the data of the tail node. Then insert the data into the head node of the cold data area.

Each time the data in the cold data zone is accessed, the following judgment needs to be made:

If the data has been in the cache for more than a specified time, such as 1 s, it is moved to the head node of the hot data area.

If the data exists at a time less than the specified time, the position remains unchanged.

For occasional batch queries, the data will only fall into the cold data area and will soon be eliminated. The data in the hot data area will not be affected, which solves the problem of the decline of cache hit rate of LRU algorithm.

Thank you for your reading, the above is the content of "the implementation principle of LRU algorithm". After the study of this article, I believe you have a deeper understanding of the implementation principle of LRU algorithm, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.