1 first come first out (FIFO)

Invalidation algorithms are common in cache systems. Because the cache often occupies a large amount of memory, and the memory space is relatively expensive and the space is limited, some values should be invalidated or removed according to the corresponding algorithm.

1.1 general

First In First Out. This algorithm removes the earliest inserted data if the queue is full every time a new data is inserted.

1.2 realization

It can be easily implemented with the help of LinkedList, because the newly added elements will be pushed back

package com.oldlu.release;
import java.util.Iterator;
import java.util.LinkedList;
public class FIFO {
    LinkedList<Integer> fifo = new LinkedList<Integer>();
    int size = 3;
    //Add element
    public void add(int i){
        //Push new data to the first place every time
        fifo.addFirst(i);
        if (fifo.size() > size){
            fifo.removeLast();
        }
        print();
    }
    //Cache Hit 
    public void read(int i){
        Iterator<Integer> iterator = fifo.iterator();
        while (iterator.hasNext()){
            int j = iterator.next();
            if (i == j){
                System.out.println("find it!");
                print();
                return ;
            }
        }
        System.out.println("not found!");
        print();
    }
    //Print cache
    public void print(){
        System.out.println(this.fifo);
    }
    //test
    public static void main(String[] args) {
        FIFO fifo = new FIFO();
        System.out.println("add 1‐3:");
        fifo.add(1);
        fifo.add(2);
        fifo.add(3);
        System.out.println("add 4:");
        fifo.add(4);
        System.out.println("read 2:");
        fifo.read(2);
        System.out.println("read 100:");
        fifo.read(100);
        System.out.println("add 5:");
        fifo.add(5);
    }
}

1.3 result analysis

Resolution:
1-3 put them in order, no problem
If 4 is put in, then 1 is put in first and is squeezed out
Read 2 and read it, but it will not affect the queue order (2 is still the oldest)
Read 100, can not read, and will not have any impact
5 joined and kicked out 2, regardless of whether 2 had been used before (irrational)

1.4 advantages and disadvantages

The implementation is very simple
Regardless of the use of elements, even if some data will be used frequently, it will be kicked out for the longest time

2 longest unused obsolescence (LRU)

2.1 general

The full name of LRU is Least Recently Used, that is to eliminate the value with the longest time of last use. FIFO is very rude. Whether it is used or not, it directly kicks out elements that have been used for a long time. LRU believes that the data that has been used frequently recently will be used frequently to a large extent in the future, so it will eliminate those lazy data. LinkedHashMap, array and linked list can implement LRU. The following is still taking the linked list as an example: the newly added data is placed in the head, and the recently accessed data is also moved to the head. When the space is full, the tail element is deleted.

2.2 realization

package com.oldlu.release;
import java.util.Iterator;
import java.util.LinkedList;
public class LRU {
    LinkedList<Integer> lru = new LinkedList<Integer>();
    int size = 3;
    //Add element
    public void add(int i){
        lru.addFirst(i);
        if (lru.size() > size){
            lru.removeLast();
        }
        print();
    }
    //Cache Hit 
    public void read(int i){
        Iterator<Integer> iterator = lru.iterator();
        int index = 0;
        while (iterator.hasNext()){
            int j = iterator.next();
            //Put it first when you read it
            if (i == j){
                System.out.println("find it!");
                lru.remove(index);
                lru.addFirst(j);
                print();
                return ;
            }
            index++;
        }
        System.out.println("not found!");
        print();
    }
    //Print cache
    public void print(){
        System.out.println(this.lru);
    }
    //test
    public static void main(String[] args) {
        LRU lru = new LRU();
        System.out.println("add 1‐3:");
        lru.add(1);
        lru.add(2);
        lru.add(3);
        System.out.println("add 4:");
        lru.add(4);
        System.out.println("read 2:");
        lru.read(2);
        System.out.println("read 100:");
        lru.read(100);
        System.out.println("add 5:");
        lru.add(5);
           }
}

2.3 result analysis

Resolution:
1-3 join, no problem
4 join, kick 1, no problem
Read 2, read, notice that 2 has been moved to the head of the team!
Read 100, can't read, no impact
5 joined because 2 was used before and will not be eliminated. 3 and 4 are not used, but 3 is longer and will be eliminated

3 least recently used (LFU)

3.1 general

Least Frequently Used, i.e. least recently used. It needs to eliminate the value that has been used the least times in the recent period of time. It can be considered that it has one more judgment than LRU. LFU needs reference indicators in two dimensions: time and times. It should be noted that the two dimensions may involve the same access times in the same time period, so a counter and a queue must be built in. The counter counts and the access time when the queue places the same count.

3.2 realization

 package com.oldlu.release;
public class Dto implements Comparable<Dto> {
    private Integer key;
    private int count;
    private long lastTime;
    public Dto(Integer key, int count, long lastTime) {
        this.key = key;
        this.count = count;
        this.lastTime = lastTime;
    }
    @Override
    public int compareTo(Dto o) {
        int compare = Integer.compare(this.count, o.count);
        return compare == 0 ? Long.compare(this.lastTime, o.lastTime) : compare;
    }
    @Override
    public String toString() {
        return String.format("[key=%s,count=%s,lastTime=%s]",key,count,lastTime);
    }
    public Integer getKey() {
        return key;
    }
    public void setKey(Integer key) {
        this.key = key;
    }
    public int getCount() {
        return count;
    }
    public void setCount(int count) {
        this.count = count;
    }
    public long getLastTime() {
        return lastTime;
    }
    public void setLastTime(long lastTime) {
        this.lastTime = lastTime;
    }
}

 package com.oldlu.release;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class LFU {
    private final int size = 3;
    private Map<Integer,Integer> cache = new HashMap<>();
    private Map<Integer, Dto> count = new HashMap<>();
    //Launch
    public void put(Integer key, Integer value) {
        Integer v = cache.get(key);
        if (v == null) {
            if (cache.size() == size) {
                removeElement();
            }
            count.put(key, new Dto(key, 1, System.currentTimeMillis()));
        } else {
            addCount(key);
        }
        cache.put(key, value);
    }
    //read
    public Integer get(Integer key) {
        Integer value = cache.get(key);
        if (value != null) {
            addCount(key);
            return value;
        }
        return null;
    }
    //Eliminate elements
    private void removeElement() {
        Dto dto  = Collections.min(count.values());
        cache.remove(dto.getKey());
        count.remove(dto.getKey());
    }
    //Update counter
    private void addCount(Integer key) {
        Dto Dto = count.get(key);
        Dto.setCount(Dto.getCount()+1);
        Dto.setLastTime(System.currentTimeMillis());
    }
    //Print cache structure and counter structure
    private void print(){
        System.out.println("cache="+cache);
        System.out.println("count="+count);
         }
    public static void main(String[] args) {
        LFU lfu = new LFU();
        //The first three capacities are not full, and 1, 2 and 3 are added
        System.out.println("add 1‐3:");
        lfu.put(1, 1);
        lfu.put(2, 2);
        lfu.put(3, 3);
        lfu.print();
        //1,2 yes, 3 no, join 4, eliminate 3
        System.out.println("read 1,2");
        lfu.get(1);
        lfu.get(2);
        lfu.print();
        System.out.println("add 4:");
        lfu.put(4, 4);
        lfu.print();
        //2 = 3 times, 1,4 = 2 times, but 4 is added late. When adding 5, 1 will be eliminated
        System.out.println("read 2,4");
        lfu.get(2);
        lfu.get(4);
        lfu.print();
        System.out.println("add 5:");
        lfu.put(5, 5);
        lfu.print();
    }
}

3.3 result analysis

Resolution:
1-3 join, no problem, the counter is once
Access 1 and 2, and the usage counter rises to 2 times. 3 has no access and is still 1
4 joined and 3 had the least number of visits (1), so 3 was kicked out and 124 remained
Access 2 and 4, the counter rises, 2 = 3 times, 1 and 4 = 2 times, but 1 takes a long time
5 join, kick out 1, and finally leave 2, 4, 5

4 application cases

redis is a typical application scenario of cache invalidation. The common strategies are as follows:
noeviction: do not delete the policy. When the maximum memory limit is reached, if more memory is needed, an error message will be returned directly (more dangerous).
Allkeys LRU: for all keys, priority is given to deleting the least recently used key (LRU).
All keys random: for all keys, delete some randomly (sounds unreasonable).
Volatile LRU: it is limited to the keys with expire set, and the least recently used key (LRU) is deleted first.
Volatile random: it is limited to the key s with expire set, and some of them are deleted randomly.
Volatile TTL: only for keys with expire set. Priority is given to deleting keys with short TTL.