Redis's capacity expansion, expiration deletion, update strategy and elimination mechanism

How to expand the capacity of Redis persistent data and cache?

  • If Redis is used as a cache, use consistent hash to achieve dynamic capacity expansion and reduction.

  • If Redis is used as a persistent storage, a fixed key to nodes mapping relationship must be used. Once the number of nodes is determined, it cannot be changed. Otherwise (that is, when Redis nodes need to change dynamically), a set of system that can rebalance data at runtime must be used, which is currently only available in Redis cluster.

Expiration deletion policy

  • In Redis, except that the string type has its own unique command setex to set the expiration time, other methods need to rely on the expire command to set the expiration time. In addition, the persist command can remove the expiration time of a key:

  • As we all know, Redis is a key value database. We can set the expiration time of the key cached in Redis. The expiration policy of Redis refers to how Redis handles when the cached key in Redis expires.

  • There are three kinds of expiration policies:

    • Timed Expiration: each key setting the expiration time needs to create a timer, which will be cleared immediately after the expiration time. This strategy can immediately clear the expired data and is very memory friendly; However, it will consume a lot of CPU resources to process expired data, which will affect the response time and throughput of the cache.

    • Lazy Expiration: only when a key is accessed will it be judged whether the key has expired. If it expires, it will be cleared. This strategy can maximally save CPU resources, but it is very unfriendly to memory. In extreme cases, a large number of expired keys may not be accessed again, so they will not be cleared and occupy a lot of memory.

    • Periodic Expiration: every certain time, a certain number of keys in the expires Dictionary of a certain number of databases will be scanned and the expired keys will be cleared. This strategy is a compromise between the first two. By adjusting the time interval of timing scanning and the limited time consumption of each scanning, the optimal balance of CPU and memory resources can be achieved under different conditions. (the expires dictionary will save the expiration time data of all keys with expiration time set, where key is the pointer to a key in the key space, and value is the expiration time represented by the UNIX timestamp with millisecond precision of the key. The key space refers to all keys saved in the Redis cluster.)

Redis update policy

  • 1. Delete the cache and update the database

    • This is easy to cause data inconsistency. When A read thread A and an update thread B access at the same time, if it is in the following order, B deletes the cache, A reads the cache without the key, A queries the old data in the database and inserts it into the cache, and B writes the new data into the database, which leads to the old data in the cache and the new data in the database.

  • The update database is deleting the cache

    • This strategy is slightly better than the first one, and it is also commonly used. When data inconsistency occurs, when reading thread A and updating thread B access at the same time, if thread A does not have the key in the cache at the beginning of the query (for example, the key is queried for the first time, or the key's cache is deleted by the update operation), A reads the old data in the data, B changes the old data in the database into new data, B deletes the cache, and A inserts the old data into the cache. This will also lead to the old data in the cache and the new data in the database.

  • Update cache and then update database

    • In this way, the data inconsistency occurs when two update threads AB are concurrent. For example, when a updates the cache to the new value of a, B also updates the cache to the new value of B, and B writes the data to the database, and then a writes the data to the database, resulting in the new value of B when the data in the cache is the data in the database, and the data in the database is the new value of A, Of course, because the general update operation is much less than the query operation, the probability of data inconsistency in the update cache is less than that in the delete cache.

  • 4. Update the database and then update the cache. This is the same as the third point. Data inconsistency will also occur between the two write threads.

Expiration strategy and elimination mechanism of Redis

Expiration Policies

  • When we set a key, we can give an expiration time, that is, the expiration time. For example, the key can only survive for 1 hour. We can specify that the cache will expire when it expires.

    • If you set that a batch of keys can only survive for one hour, how does redis delete these keys after the next hour?

      The answer is: regular deletion + inert deletion

    • Periodic deletion

      • It means that by default, redis randomly selects some key s with expiration time set every 100ms to check whether they have expired. If they have expired, they will be deleted.

        Note that this is not to traverse all the key s that set the expiration time every 100ms, which is a performance disaster.

        In fact, redis randomly selects some key s every 100ms to check and delete.

    • However, regular deletion may lead to many expired key s that have not been deleted at the time, so they have to be deleted by laziness.

    • Lazy deletion when you get a key, redis will check whether the key has expired if the expiration time is set? If it expires, it will be deleted at this time and nothing will be returned to you.

      It's not that the key is deleted when the time comes. It's that when you query the key, redis checks it lazily

      The above two methods are combined to ensure that expired key s will be killed.

  • But in fact, there is still a problem. What happens if you omit a lot of expired key s on a regular basis, and then you don't check them in time, so you don't delete them lazily?

    What if a large number of expired key s accumulate in memory, leading to the depletion of redis memory blocks?

    The answer is: take the memory elimination mechanism.

Elimination mechanism

  • All keys LRU: when the memory is insufficient to accommodate the newly written data, remove the least recently used key in the key space (this is the most commonly used)

  • Volatile random: when the memory is insufficient to hold the newly written data, a key is randomly removed from the key space with the expiration time set

  • Volatile TTL: when the memory is insufficient to accommodate the newly written data, the keys with earlier expiration time will be removed first in the key space with expiration time set

  • Allkeys LRU (least recently used): when the memory is insufficient to accommodate the newly written data, remove the least recently used key in the key space (this is the most commonly used)

  • Allkeys random: select any data from the data set (server.db[i].dict)

  • No eviction: it is forbidden to expel data, that is, when the memory is insufficient to accommodate the newly written data, the new write operation will report an error. No one should use this!

  • LRU

    • If the data has been accessed recently, it is more likely to be accessed in the future. ".

  • Implement a linked list to save cached data

    • step

      • Insert the new data into the head of the linked list;

        1. Whenever the cache hits (i.e. the cached data is accessed), move the data to the head of the linked list; (note the difference between jdk1.7 and 1.8. 1.8 will be placed at the end)

          1. When the linked list is full, the data at the end of the linked list will be discarded.

      • Hit rate: when there is hot data, the efficiency of LRU is very good, but occasional and periodic batch operations will lead to a sharp decline in LRU hit rate and serious cache pollution.

      • Complexity: when hitting, you need to traverse the linked list, find the hit data block index, and then move the data to the head.

  • Implementation of linked list + HashMap of LRUCache

    • Its principle: connect all locations of the Cache with a double linked list. When a location is hit, it will be adjusted to the position of the chain header by adjusting the direction of the linked list, and the newly added Cache will be directly added to the linked list header.

    • In this way, after multiple Cache operations, the most recently hit will be moved to the chain header, while those who fail to hit will want to move behind the chain list, and the tail of the chain list represents the least recently used Cache. When the content needs to be replaced, the last position of the linked list is the least hit position. We only need to eliminate the last part of the linked list.

    • Non thread safety. If safety is realized, lock the response method.

    • code implementation

    • import java.util.HashMap;
      import java.util.Map.Entry;
      import java.util.Set;
       
       
      public class LRUCache<K, V> {
       
          private int currentCacheSize;
          private int CacheCapcity;
          private HashMap<K,CacheNode> caches;
          private CacheNode first;
          private CacheNode last;
       
          public LRUCache(int size){
              currentCacheSize = 0;
              this.CacheCapcity = size;
              caches = new HashMap<K,CacheNode>(size);
          }
       
          public void put(K k,V v){
              CacheNode node = caches.get(k);
              if(node == null){
                  if(caches.size() >= CacheCapcity){
       
                      caches.remove(last.key);
                      removeLast();
                  }
                  node = new CacheNode();
                  node.key = k;
              }
              node.value = v;
              moveToFirst(node);
              caches.put(k, node);
          }
       
          public Object  get(K k){
              CacheNode node = caches.get(k);
              if(node == null){
                  return null;
              }
              moveToFirst(node);
              return node.value;
          }
       
          public Object remove(K k){
              CacheNode node = caches.get(k);
              if(node != null){
                  if(node.pre != null){
                      node.pre.next=node.next;
                  }
                  if(node.next != null){
                      node.next.pre=node.pre;
                  }
                  if(node == first){
                      first = node.next;
                  }
                  if(node == last){
                      last = node.pre;
                  }
              }
       
              return caches.remove(k);
          }
       
          public void clear(){
              first = null;
              last = null;
              caches.clear();
          }
       
       
       
          private void moveToFirst(CacheNode node){
              if(first == node){
                  return;
              }
              if(node.next != null){
                  node.next.pre = node.pre;
              }
              if(node.pre != null){
                  node.pre.next = node.next;
              }
              if(node == last){
                  last= last.pre;
              }
              if(first == null || last == null){
                  first = last = node;
                  return;
              }
       
              node.next=first;
              first.pre = node;
              first = node;
              first.pre=null;
       
          }
       
          private void removeLast(){
              if(last != null){
                  last = last.pre;
                  if(last == null){
                      first = null;
                  }else{
                      last.next = null;
                  }
              }
          }
          @Override
          public String toString(){
              StringBuilder sb = new StringBuilder();
              CacheNode node = first;
              while(node != null){
                  sb.append(String.format("%s:%s ", node.key,node.value));
                  node = node.next;
              }
       
              return sb.toString();
          }
       
          class CacheNode{
              CacheNode pre;
              CacheNode next;
              Object key;
              Object value;
              public CacheNode(){
       
              }
          }
       
          public static void main(String[] args) {
       
              LRUCache<Integer,String> lru = new LRUCache<Integer,String>(3);
       
              lru.put(1, "a");    // 1:a
              System.out.println(lru.toString());
              lru.put(2, "b");    // 2:b 1:a 
              System.out.println(lru.toString());
              lru.put(3, "c");    // 3:c 2:b 1:a 
              System.out.println(lru.toString());
              lru.put(4, "d");    // 4:d 3:c 2:b  
              System.out.println(lru.toString());
              lru.put(1, "aa");   // 1:aa 4:d 3:c  
              System.out.println(lru.toString());
              lru.put(2, "bb");   // 2:bb 1:aa 4:d
              System.out.println(lru.toString());
              lru.put(5, "e");    // 5:e 2:bb 1:aa
              System.out.println(lru.toString());
              lru.get(1);         // 1:aa 5:e 2:bb
              System.out.println(lru.toString());
              lru.remove(11);     // 1:aa 5:e 2:bb
              System.out.println(lru.toString());
              lru.remove(1);      //5:e 2:bb
              System.out.println(lru.toString());
              lru.put(1, "aaa");  //1:aaa 5:e 2:bb
              System.out.println(lru.toString());
          }
       
      }
      

Tags: Redis

Posted by Jaguar on Sun, 15 May 2022 21:29:43 +0300