In Redis, there are three main methods for clearing expired keys: lazy clearing, scheduled clearing and insufficient memory clearing. Let’s take a look at these three methods in detail.

1, inert removal

If the key has expired, the key will be deleted.

2, regular cleaning

The Redis configuration item hz defines the execution period of serverCron tasks. By default, each cleaning time is 25ms. Each cleaning will traverse all DB in sequence and randomly remove 20 keys from DB. Otherwise start cleaning the next DB.

3. Clean up when the memory is insufficient

When the write command is executed, if the memory is found to be insufficient, the memory will be cleared according to the configured elimination strategy. There are generally six kinds of elimination strategy, and two kinds of elimination strategy are added after Redis4.0, mainly divided into three types:

The first type is not processed and waits for an error (default configuration)

Noeviction, won’t remove key when memory is out of order, error message will be returned when write command is executed. Redis default configuration is noeviction

The second type is culled from the keys in all result sets

Allkeys-random is a random selection of keys from allkeys

Allkeys-lru selects the most recently used key from all the keys and removes it

Allkeys-lfu selects the least frequently used key from allkeys to eliminate. (This is a new policy since Redis 4.0)

The third type is selected from keys that have an expiration date

In this way, a portion of the key is eliminated from the result set with an expires time. The selection algorithm includes:

Volatile -random Deletes randomly selected keys from the result set with expiration time.

Volatile -lru selects the most recent key from the result set with an expiration date and deletes it.

Volatile – TTL Selects the keys with the shortest lifespan from the result set with the expiration date and deletes them (i.e. deletes the keys that are about to expire first)

Volatile – lFU selects the least frequently used key from the result set at expiration time and starts removing it (a new policy since Redis 4.0)

LRU algorithm

The DESIGN principle of the LRU algorithm is that if a piece of data has not been accessed recently, it will not be accessed for some time. Therefore, when the number of elements reaches the limit value, the element with the longest time since the last use is removed first.

This can be done using HashMap<String, Node>. After each access to the element, move the element to the head of the list. When the element is full, remove the element at the end of the list. HashMap is used to get nodes by key, determine whether a Node already exists when adding nodes, and quickly find nodes when deleting nodes.

PS: Is it possible to use a one-way linked list? It is also possible. Although the nodes of a one-way linked list cannot obtain the information of the pre node, they can set the key and value of the next node on the current node, and then set the next node’s next pointer to the next node, which is equivalent to deleting the next node.

Public static class ListNode {String key; // The key is stored here so that when the element is full, the tail node can be removed quickly from the HashMap. ListNode pre = null; ListNode next = null; ListNode(String key, Integer value) { this.key = key; this.value = value; } } ListNode head; ListNode last; int limit=4; HashMap<String, ListNode> hashMap = new HashMap<String, ListNode>(); public void add(String key, Integer val) { ListNode existNode = hashMap.get(key); if (existNode! ListNode pre = existNode.pre; ListNode pre = existNode.pre; ListNode next = existNode.next; if (pre! =null) { pre.next = next; } if (next! =null) { next.pre = pre; } // Update the last node if (last==existNode) {last= existnode. pre; } // move to the front head. Pre = existNode; existNode.next = head; head = existNode; // Update the value existNode.value = val; } else {if (hashmap.size () == limit) {ListNode deleteNode = last; hashMap.remove(deleteNode.key); Last = deletenode.pre; deleteNode.pre = null; last.next = null; } ListNode node = new ListNode(key,val); hashMap.put(key,node); if (head==null) { head = node; last = node; } else {// insert the head node. Next = head; head.pre = node; head = node; } } } public ListNode get(String key) { return hashMap.get(key); } public void remove(String key) { ListNode deleteNode = hashMap.get(key); ListNode preNode = deleteNode.pre; ListNode nextNode = deleteNode.next; if (preNode! =null) { preNode.next = nextNode; } if (nextNode! =null) { nextNode.pre = preNode; } if (head==deleteNode) { head = nextNode; } if (last == deleteNode) { last = preNode; } hashMap.remove(key); }Copy the code

LFU algorithm

LFU algorithm design principle, if a data in recent period of time when accessed, the more so after probability can be accessed, the greater the basic implementation is each data has a reference count, every time after the data is accessed, the reference count + 1, need to eliminate the data, the selection reference counting the smallest data.

In the implementation of Redis, the reference count is incremented by a number p between 0 and 1 each time the key is accessed. The more frequently the key is accessed, the greater the p value is. Moreover, the reference count is reduced if the key is not accessed within a certain period of time.

Original link: juejin.cn/post/684490…

Wenyuan network, only for the use of learning, if there is infringement please contact delete.

I’ve compiled the interview questions and answers in PDF files, as well as a set of learning materials covering, but not limited to, the Java Virtual Machine, the Spring framework, Java threads, data structures, design patterns and more.

Follow the public account “Java Circle” for information, as well as quality articles delivered daily.