LRU implementation with expiration time

[[382833]]

I saw this algorithm a long time ago when I was studying operating systems. Later, I saw it more and more, and even saw it when I was reviewing the interview experience. To summarize:

1. What is LRU

LRU stands for Least Recently Used, which means the data that has not been used for the longest time. In other words, if a piece of data has not been used in the recent period, the chance of it being used in the future is also relatively small.

The common usage scenario is caching, such as the page replacement algorithm in the operating system. There are many implementation schemes. I have read many blogs, and most of them give four or five schemes. For the sake of simplicity, only one scheme with an expiration time is given here. Other implementations are similar, so I will leave it to you who are smart!!

Solution: Use linked list plus HashMap

Every time a new data comes, first check whether it is contained in the map. If so, move it to the head of the queue. If not, create a new node and put it in. For functions with expiration time, you only need to set an expiration time for each node, and delete it directly when this time is reached.

There is another problem: locks should be added in a multi-threaded environment. In order to ensure the flexibility of locks, we use ConcurrentHashMap.

OK, let's start implementing it:

2. Code Implementation

1. Define nodes

 //This Node uses each node in the HashMap
 class Node implements Comparable<Node> {
 private String key ;
 private Object value;
 private long expireTime; //Note that this expiration time is a time point, such as 11:11
 public Node(String key , Object value, long expireTime) {
 this.value = value;
 this.key = key ;
        this.expireTime = expireTime;
 }
 // Sort by expiration time
 @Override
 public   int compareTo(Node o) {
        long r = this.expireTime - o.expireTime;
 if (r > 0) return 1;
 if (r < 0) return -1;
 return 0;
 }
 }

2. LRU Implementation

 public class LRU {
 // Variable 1: used to set the thread pool for clearing expired data
    private static ScheduledExecutorService swapExpiredPool
                  = new ScheduledThreadPoolExecutor(10);
 // Variable 2: User storage data. To ensure thread safety, ConcurrentHashMap is used.
    private ConcurrentHashMap<String, Node> cache = new ConcurrentHashMap<>(1024);
 // Variable 3: Save the latest expired data, the data with the shortest expiration time is placed at the front of the queue
    private PriorityQueue<Node> expireQueue = new PriorityQueue<>(1024);
 // Construction method: As long as there is a cache, the expired cleanup thread starts working
 public LRU() {
        swapExpiredPool.scheduleWithFixedDelay(new ExpiredNode(), 3,3,TimeUnit.SECONDS);
 }
 //And some code...
 }

Now we have defined several variables and a constructor, which means that once the LRU is started, it will start clearing. The clearing thread is ExpiredNode. Let's take a look:

3. Expired thread clearing method

This method is ExpiredNode, which is treated as an inner class in LRU.

 public class ExpiredNode implements Runnable {
 @Override
 public void run() {
 // Step 1: Get the current time
            long now = System.currentTimeMillis();
 while ( true ) {
 // Step 2: Pop the first element from the expired queue, and return if it does not exist or is not expired
                Node node = expireQueue.peek();
                if (node ​​== null || node.expireTime > now) return ;
 // Step 3: If it expires, delete it from the cache and pop it from the queue
                cache.remove( node.key );
                expireQueue.poll();
 }// This process is while( true ), and the judgment and deletion operations are performed continuously
 }
 }

Now that you know how to clear expired data, let's see how to add data.

4. set method

 public Object set (String key , Object value, long ttl) {
 // Step 1: Get the expiration time
        long expireTime = System.currentTimeMillis() + ttl;
 // Step 2: Create a new node
        Node newNode = new Node( key , value, expireTime);
 // Step 3: If there is one in the cache, overwrite it, if not, add a new one, and also add the expiration time queue
        Node old = cache.put( key , newNode);
        expireQueue.add (newNode);
 // Step 4: If the key has data, delete it from the expiration time queue
 if (old != null ) {
            expireQueue.remove(old);
 return old.value;
 }
 return   null ;
 }

5. get method

This method is relatively simple, you can get it directly.

 public Object get(String key ) {
 //Step 1: Get directly from cache. Note that this cache is a HashMap
    Node n = cache.get( key );
 //Step 2: If n is empty, it returns null , if it is not empty, it returns the corresponding value
 return n == null ? null : n.value;
 }

Note that the above 345 codes are all stored in LRU.

We already know the expiration time. In fact, we just add an expiration time queue and an expiration clearing thread. When clearing, use while(true) to determine whether the head of the queue is expired, and then determine whether to return and clear. When setting the method, we also need to add the new node to the queue and remove the old one. And we use ConcurrentHashMap to ensure thread safety.

OK, that’s all for today’s code.

This article is reprinted from the WeChat public account "Yugong Yaoyishan". You can follow it through the following QR code. To reprint this article, please contact the public account "Yugong Yaoyishan".