The introduction

Redis stores data in the memory, the memory is limited, if you keep putting data in it, there will always be a full day, if you do not carry out special processing, put elements after full will be OOM(personal feeling), so Redis has a lot of elimination strategies, the following is the specific elimination strategy provided

  • Noeviction: Errors will be returned when memory usage exceeds configuration, no keys will be expelled
  • Allkeys-lru: When adding a key, if the limit is exceeded, the lRU algorithm will first expel the key that has not been used for the longest time
  • Volatile -lru: Expelling the oldest unused key from the set of expired keys if the limit is exceeded
  • Allkeys-random: if the number of keys added exceeds the threshold, allkeys will be randomly deleted
  • Volatile -random: Randomly expel expired keys from the set if the number of keys added exceeds the limit
  • Volatile – TTL: Expels keys that are about to expire from keys with expiration time configured
  • Volatile – lFU: Expels the least frequently used key from all keys with expiration time configured
  • Allkeys-lfu: removes the least frequently used key from allkeys

implementation

Then how to achieve the specific elimination strategy algorithm, take LRU(Least Recently Used) to use the elimination strategy for example, which is often asked in the interview. The specific scenario is to design a container that provides the following operations

  • Initialization: You can set the size of the container to hold elements
  • Add: Add elements to a container. If the container is full, the original element needs to be eliminated
  • Query: Queries an element in a container
  • Delete: To remove an element from a container

Two-way linked list method

We can easily think of using a linked list to implement the LRU elimination strategy. The specific implementation is to maintain a linked list. Every operation, we need to traverse the linked list to determine whether the current element exists in the linked list, and then remove some elements and put them into the head of the linked list, the specific implementation is as follows

/** * @program: * @description: Implement LRU elimination strategy with bidirectional list * @create: **/ public class SimpleLRU<K, V> {private static final int DEFAULT_CAPACITY = 10; private int capacity; Private int length; Private Node<K, V> headNode; Private Node<K, V> tailNode; Public SimpleLRU() {this(DEFAULT_CAPACITY); } public SimpleLRU(int capacity) { this.capacity = capacity; headNode = new Node<>(); tailNode = new Node<>(); this.length = 0; } /** * add * @param key * @param value */ public void add(K key, V value) {Node<K, V> Node = getNode(key); if (node ! = null) { node.value = value; moveToHead(node); } else {// there is no Node<K, V> newNode = newNode <>(key, value); If (++length > capacity) {// If (++length > capacity) {popTail(); // Remove the last node in the list --length; } addNode(newNode); } } private void addNode(Node<K,V> node) { headNode.next.prev = node; node.next = headNode.next; node.prev = headNode; headNode.next = node; } private void popTail() { tailNode.prev.prev.next = tailNode; tailNode.prev = tailNode.prev.prev; } private void moveToHead(Node<K,V> node) { headNode.next.prev = node; node.next = headNode.next; headNode.next = node; node.prev = headNode; } @param key * @return */ public V get(K key) {Node<K, V> Node = getNode(key); if (node == null) return null; moveToHead(node); return node.value; } public Node getNode(K key) { Node<K, V> dummyNode = headNode.next; While (dummyNode! = null && dummyNode.key ! = key) { dummyNode = dummyNode.next; } if (dummyNode == null) return null; return dummyNode; } @param key */ public void remove(K key) {Node<K, V> Node = getNode(key); if (node == null) return; removeNode(node); } private void removeNode(Node<K,V> node) { node.prev.next = node.next; node.next.prev = node.prev; } static class Node<K, V> { K key; V value; Node prev; Node next; public Node() {} public Node(K key, V value) { this.key = key; this.value = value; }}}Copy the code

Hash table + bidirectional linked list method

Because each operation needs to traverse the entire list, O(N) time complexity, this implementation is definitely not feasible in practical application scenarios, the more elements in the container, the slower the operation. The key point is that each operation needs to traverse the whole linked list and compare to obtain the elements we want one by one. In this case, hash table can be introduced to obtain the value according to the key. The time complexity is O(1) and the performance is better

/** * @program: * @description: * core: * Least Recently Used * time complexity O(1), using hash table and bidirectional linked list to complete * provided operations: * 1. Add element * 2 to the collection. Last use is the first to eliminate * 3. There is an initial length * * @create: **/ public class LRUDemo<K, V> {private static final Integer DEFAULT_CAPACITY = 10; private int length; private int capacity; private DNode<K, V> headNode; private DNode<K, V> tailNode; private Map<K, DNode<K, V>> table; public LRUDemo() { this(DEFAULT_CAPACITY); } public LRUDemo(int capacity) { this.capacity = capacity; length = 0; headNode = new DNode<>(); tailNode = new DNode<>(); headNode.next = tailNode; tailNode.prev = headNode; table = new HashMap<>(); } static class DNode<K, V> { private K key; private V value; private DNode prev; private DNode next; DNode() { } DNode(K key, V value) { this.key = key; this.value = value; Public void add(K key, V value) {DNode<K, V> node = table.get(key); if (node == null) { DNode<K, V> newNode = new DNode<>(key , value); if (++length > capacity) { DNode<K, V> tail = popTail(); removeNode(tail); } table.put(key, newNode); addNode(node); } else { node.value = value; moveToHead(node); } } private DNode<K,V> popTail() { DNode<K, V> tail = tailNode.prev; removeNode(tail); return tail; } private void addNode(DNode<K,V> node) { headNode.next.prev = node; node.next = headNode.next; this.headNode.next = node; node.prev = headNode; } private void moveToHead(DNode<K,V> node) { removeNode(node); addNode(node); } public V get(K key) {DNode<K, V> node = table.get(key); if (node == null) { return null; } moveToHead(node); return node.value; } @param */ public void removeNode(DNode<K, V> node) {node.prev.next = node.next; node.next.prev = node.prev; table.remove(node.key); }}Copy the code

conclusion

In general, this algorithm is implemented through the introduction of data structures, through a certain algorithm, linked list class, you need to draw their own more on paper, node and node between the prev and next pointer, a picture, it is very clear, the next thing to do is pointer assignment