Official account: Java Xiaokaxiu, website: Javaxks.com

Author: Yrion, link: cnblogs.com/wyq178/p/11…

Preface: before have written an article about the LRU link www.cnblogs.com/wyq178/p/99… LRU full name: Least Recently Used: policy for Least recent use

Preface: before have written an article about the LRU link www.cnblogs.com/wyq178/p/99… Full name of LRU: Least Recently Used: a strategy to judge the most Recently Used time, and the data furthest away from the current is preferentially eliminated. As an algorithm to change the order of the linked list according to the access time to achieve cache elimination, it is one of the elimination algorithms adopted by Redis. Redis also has a caching policy called LFU. What is LFU? We are going to divide the LFU in this blog:

The contents of this blog:

One: What is LRU

Two: the realization of LRU

3: test

Four: differences and defects between LRU and LFU

Five:

The body of the

One: What is LRU

LFU is the most Frequently Used policy. The data that is Used the Least Frequently in a period of time is eliminated. *Minimum use *(*LFU*) is a caching algorithm used to manage computer memory. It records and tracks the number of blocks used, and when the cache is full and more space is needed, the system will clear the memory at the lowest block usage rate. The simplest way to use the LFU algorithm is to assign a counter to each block loaded into the cache. Each time the block is referenced, the counter increases by one. When the cache reaches capacity and a new block of memory is waiting to be inserted, the system searches for the block with the lowest counter and removes it from the cache.

Insert elements at the beginning of the list, count each insert, reorder the list by number of insertions, or by insertion time if the number of insertions is the same, and select the obsolete data from the end of the list

Two: LRU implementation

2.1 Defining a Node

Node mainly contains key and value, because the main realization idea of LFU is to compare The Times of access. If the time of nodes needs to be compared when the number of times is the same, the earlier one is added, the faster it will be eliminated. Therefore, we need to add time and count attributes to Node nodes. It is used to record the access time and times of nodes respectively. In other versions, there is a new inner class to record the count and time of key, but I think it is not convenient, and I have to maintain a map independently, which costs a little bit too much. The other thing to note here is that we implement the Comparable interface, which overrides the Compare method. The main function of compare is to compare the number of times a node is accessed. In the case of the same number of visits, the access time of nodes is compared, in order to select the eliminated key by comparing keys in the sorting method

/** * Node */ public static class Node implements Comparable<Node>{// / / value Object value; /** * access time */ long time; /** ** int count; public Node(Object key, Object value, long time, int count) { this.key = key; this.value = value; this.time = time; this.count = count; } public Object getKey() { return key; } public void setKey(Object key) { this.key = key; } public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } public long getTime() { return time; } public void setTime(long time) { this.time = time; } public int getCount() { return count; } public void setCount(int count) { this.count = count; } @Override public int compareTo(Node o) { int compare = Integer.compare(this.count, o.count); If (compare==0){return long.pare (this.time,o.time); return long.pare (this.time,o.time); } return compare; }}Copy the code

2.2: Define the LFU class

Defines the LFU class, which uses generics, declares K and V, total capacity, and a Map(caches) to maintain all nodes. Size is passed in the constructor and a LinkedHashMap is created. The main reason for using a LinkedHashMap is to maintain the order of keys

Public class LFU<K,V> {/** * private int capacity; /** * All nodes */ private Map<K, node > caches; @param size */ public LFU(int size) {this.capacity = size; caches = new LinkedHashMap<K,Node>(size); }}Copy the code

2.3: Add elements

The logic of adding an element is to obtain the node from the cache according to the key. If it cannot obtain the node, it is proved to be the newly added element. Then compare the node with the preset capacity, and find the node with the smallest count (if the count is the same, select the node with the longest time), and remove the node. If the node is within the predetermined size, the new node is created. Note that the system.currentTimemillis () method is not used here, because the millisecond granularity does not distinguish between insertion times. Only system.nanotime () can distinguish key insertion times, and the default count is 1. If it is available, it overwrites the old value with the new value, counts + 1, and sets the key’s time to the current nanosecond. Finally, we need to sort. Here we can see that the logic for inserting elements is mainly to add elements into the cache, update the time and count of elements ~

/** * add element * @param key * @param value */ public void put(K key, V value) {Node Node = caches. // If (node == null) {// If (caches. Size () >= capacity) {// Remove count the smallest key K leastKey = removeLeastCount(); caches.remove(leastKey); } / / create a new node node = new node (key, value, System. NanoTime (), 1); caches.put(key, node); }else {// The existing element overrides the old value node.value = value; node.setCount(node.getCount()+1); node.setTime(System.nanoTime()); } sort(); }Copy the code

Each put or get element needs to be sorted. The main meaning of sorting is to rearrange the key order according to the cout and time of the key. Reorganize the entire map. The order of placing the values of keys and values into the original cache is reorganized. The difference between LRU and LRU is that it uses Java’s collection API, and LRU’s sorting is node movement. In LFU, however, the implementation is more complicated, because when you put, you have to compare not only the base but also the time. If you do not use Java API, you can maintain a new node frequency linked list, each time the key stored in the node frequency linked list to move the pointer, which can also indirectly achieve sorting ~

/** * sort */ private void sort() {List< map.entry <K, Node>> List = new ArrayList<>(caches. EntrySet ()); Collections.sort(list, new Comparator<Map.Entry<K, Node>>() { @Override public int compare(Map.Entry<K, Node> o1, Map.Entry<K, Node> o2) { return o2.getValue().compareTo(o1.getValue()); }}); caches.clear(); for (Map.Entry<K, Node> kNodeEntry : list) { caches.put(kNodeEntry.getKey(),kNodeEntry.getValue()); }}Copy the code

Remove the smallest element

Here the collections. min method is called, and the element with the smallest count and longest time is removed directly from the cache by comparing the key’s compare method

@return */ private K removeLeastCount() {Collection<Node> values = caches. Values (); Node min = Collections.min(values); return (K)min.getKey(); }Copy the code

2.4: Get elements

After obtaining the element, the node needs to be updated, counting + 1 and the time of refreshing the node. According to the principle of LFU, after obtaining the node at the current time, the node will temporarily become a hot node. But its Cout count can also be less than the count of a node, so

At this point, it can not be directly moved to the top of the list, but also need to carry out a sort, reorganization of its position ~

/** * get element * @param key * @return */ public V get(K key){Node Node = caches. if (node! =null){ node.setCount(node.getCount()+1); node.setTime(System.nanoTime()); sort(); return (V)node.value; } return null; }Copy the code

3: test

First declare an LRU, then the default maximum size is 5, put into A, B, C, D, E, F6, then find the element with the smallest count and the shortest time, will eliminate A(because count is 1). Remember to get the B element twice, so the count of the B element is 3, and the time is updated. B is going to move to the top, and then on getC, C is going to be up to date with count=2, so it’s still after B because its count is still less than B, and then getF is going to be up to date with count=2, So at the same count as C, the element F is updated, so the list will move, F will be before C, put C again, C count=3, and the time is the latest, so C count and B are the same now, Then they compare the time, C is obviously updated, so C will be placed before B, the final order should be: C->B->F->E->D

public static void main(String[] args) { LFU<Integer, String> lruCache = new LFU<>(5); lruCache.put(1, "A"); lruCache.put(2, "B"); lruCache.put(3, "C"); lruCache.put(4, "D"); lruCache.put(5, "E"); lruCache.put(6, "F"); lruCache.get(2); lruCache.get(2); lruCache.get(3); lruCache.get(6); // re-put node 3 lruCache. Put (3,"C"); final Map<Integer, Node> caches = (Map<Integer, Node>) lruCache.caches; for (Map.Entry<Integer, Node> nodeEntry : caches.entrySet()) { System.out.println(nodeEntry.getValue().value); }}Copy the code

Running results:

Iv. Differences between LRU and LFU and disadvantages of LFU

LRU and LFU have different emphases. LRU is mainly reflected in the use time of elements, while LFU is mainly reflected in the use frequency of elements. The drawback of LFU is that certain caches are accessed so frequently over a short period of time that they are immediately promoted to hot data, guaranteed not to be obsolete, and thus remain in system memory. In fact, this part of data is only briefly accessed with high frequency, and then will not be accessed for a long time. Transient high frequency access will accelerate the reference frequency of this part of data, and some newly added caches are easy to be deleted quickly, because their reference frequency is very low.

Five:

This blog has provided a brief introduction to LFU, detailed how to implement LFU in Java, and a brief comparison with LRU. For a caching strategy. LFU has its own unique usage scenarios, how to realize LFU and use the characteristics of LFU to realize some functions of the development process is what we need to think about. In practice, LRU is used more often than LFU, but knowledge of this algorithm is a must for programmers.