缓存淘汰策略

面试题

• 生产上redis的内存设置多少？
• 如何配置修改redis的内存大小？
• 如果内存满了怎么办？
• redis清理内存的方式是什么？定期删除和惰性删除了解过吗？
• redis缓存淘汰策略有哪些？
• redis的lru了解过吗？可否手写一个lru算法？
• ...

redis内存相关

redis内存满了怎么办

• redis默认内存是多少？在哪里查看？如何修改配置？
  • 查看redis最大占用内存----单位为byte，注意换算
    • 配置文件查看
      • redis.conf
    • 命令查看
      • config get maxmemory
  • redis默认内存多少可用
    • 如果不设置最大内存大小或者设置最大内存大小为0，在64位操作系统小不限制内存大小，在32位操作系统下最多使用3GB内存。
  • 一般生产如何配置
    • 推荐设置为物理内存的四分之三
  • 如何修改redis内存设置
    • 通过修改配置文件
    • 通过命令修改
      • config set maxmemory 104857600
  • 什么命令查看redis内存使用情况
    • info memory
• 内存真满了怎么办？如果redis内存使用超出了设置的最大值会怎样？
  • OOM
• 结论
  • 设置了maxmemory的选项，假如redis内存使用达到上限，会OOM
  • 没有加上过期时间就会导致数据写满maxmemory

redis缓存淘汰策略

• 往redis里写的数据是怎么没了的
  • redis过期键的删除策略
    • 如果一个键是过期的，那它到期之后是马上就从内存里面被删除吗？
      • 不是！！！
    • 如果不是，到期后什么时候被删除？是什么操作？
  • 三种不同的删除策略
    • 定时删除 - 对cpu不友好，用处理器性能换取存储空间，时间换空间
      • Redis不可能时时刻刻遍历所有被设置了生存时间的key，来检测数据是否已经到达过期时间，然后对它进行删除。
      • 立即删除能保证内存中数据的最大新鲜度，因为它保证过期键值会在过期后马上被删除，其所占用的内存也会随之释放。但是立即删除对cpu是最不友好的。因为删除操作会占用cpu的时间，如果刚好碰上了cpu很忙的时候，比如正在做交集或排序等计算的时候，就会给cpu造成额外的压力，让CPU心累，时时需要删除，忙死。。。。。。。
      • 这会产生大量的性能消耗，同时也会影响数据的读取操作。
    • 惰性删除 - 对memory不友好，用存储空间换取处理器性能，空间换时间
      • 数据到达过期时间，不做处理。等下次访问该数据时，如果未过期，返回数据；发现已过期，删除，返回不存在。
      • 惰性删除策略的缺点是，它对内存是最不友好。
      • 如果一个键已经过期，而这个键又仍然保留在数据库中，那么只要这个过期键不被删除，它所占用的内存就不会释放。
      • 在使用惰性删除策略时，如果数据库中有非常多的过期键，而这些过期键又恰好没有被访问到的话，那么它们也许永远也不会被删除（除非用户手动执行FLUSHDB），我们甚至可以将这种情况看作是一种内存泄漏-无用的垃圾数据占用了大量的内存，而服务器却不会自己去释放它们，这对于运行状态非常依赖于内存的Redis服务器来说，肯定不是一个好消息
    • 定期删除 - 定期抽样key，判断是否过期 - 有漏网之鱼
      • 定期删除策略是前两种策略的折中
      • 定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响。
      • 周期性轮询redis库中的时效性数据，采用随机抽取的策略，利用过期数据占比的方式控制删除频度特点
        • 特点1：CPU性能占用设置有峰值，检测频度可自定义设置
        • 特点2：内存压力不是很大，长期占用内存的冷数据会被持续清理
      • 总结：**周期性抽查存储空间（随机抽查，重点抽查）**举例
        • redis默认每个100ms检查，是否有过期的key，有过期key则删除。注意：redis不是每隔100ms将所有的key检查一次而是随机抽取进行检查（如果每隔100ms，全部key进行检查，redis直接进去ICU）。因此，如果只采用定期删除策略，会导致很多key到时间没有删除。
      • 定期删除策略的难点是确定删除操作执行的时长和频率：如果删除操作执行得太频繁，或者执行的时间太长，定期删除策略就会退化成定时删除策略，以至于将CPU时间过多地消耗在删除过期键上面。如果删除操作执行得太少，或者执行的时间太短，定期删除策略又会和惰性删除束略一样，出现浪费内存的情况。因此，如果采用定期删除策略的话，服务器必须根据情况，合理地设置删除操作的执行时长和执行频率。
  • 还有什么漏洞
    • 定期删除时，从来没有被抽查到
    • 惰性删除时，从来没有被点中使用过----大量过期key堆积在内存中，导致redis内存空间紧张或者很快耗尽
  • 内存淘汰策略登场----兜底方案
• 有哪些淘汰策略(redis6.0)
  • LRU means Least Recently Used
  • LFU means Least Frequently Used
  • 淘汰策略
    • allkeys-lru:对所有key使用lru算法删除
    • volatile-lru:对所有设置了过期时间的key使用lru算法进行删除
    • allkeys-random:对所有key随机删除
    • volatile-random:对所有设置了过期时间的key随机删除
    • allkeys-lfu:对所有key使用lfu算法进行删除
    • volatile-lfu:对所有设置了过期时间的key使用lfu算法进行删除
    • volatile-ttl:删除马上要过期的key
    • noevication:不会驱逐key
  • 结论
    • 2*4得8
    • 2个维度
      • 所有键中筛选
      • 过期键中筛选
    • 4个方面
      • LRU
      • LFU
      • random
      • ttl
    • 8个选项
• 平时用哪一种
  • allkeys-lru
• 如何配置，修改
  • 配置文件
  • 命令
    • config set maxmemory-policy allkeys-lru

lru算法

• 是什么
  • LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的数据予以淘汰。
• 算法来源
  • https://leetcode-cn.com/problems/lru-cache/ (opens new window)
• 设计思想
  • 1所谓缓存，必须要有读+写两个操作，按照命中率的思路考虑，写操作+读操作时间复杂度都需要为O（1）
  • 2特性要求
    • 2.1必须要有顺序之分，一区分最近使用的和眼久没有使用的数据排序。
    • 2.2写和读操作一次搞定。
    • 2.3如果容量（坑位）满了要删除最不长用的数据，每次新访问还要把新的数据插入到队头（按照业务你自己设定左右那一边是队头查找快、插入快、删除快，且还需要先后排序---->什么样的数据结构可以满足这个问题？你是否可以在O（1）时间复杂度内完成这两种操作？如果一次就可以找到，你觉得什么数据结构最合适？？
  • LRU算法的核心是哈希链表
    • 本质就是HashMap+DoubleLinkedList,时间复杂度是O（1）
  • 动画说明
• 编码实现----见手写lru

手写lru

方法1-巧用JDK中的LinkedHashMap

public class LRUCache1<K,V> extends LinkedHashMap<K,V> {
    private int capacity;
    public LRUCache1(int capacity){
        super(capacity,0.75f,true);
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K,V> entry){
        return super.size() > capacity;
    }
}

方法2-HashMap + DoubleLinkedList

public class LRUCache2{
    private int capacity;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLinkedList<Integer,Integer> doubleLinkedList;
    public LRUCache2(int capacity){
        this.capacity = capacity;
        map = new HashMap();
        doubleLinkedList = new DoubleLinkedList();
    }
    //saveOrUpdate
    public void put(int key,int value){
        if(map.containsKey(key)){
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key,node);
            doubleLinkedList.remove(node);
            doubleLinkedList.addTail(node);
        }else{
            if(map.size() == capacity){
                Node<Integer,Integer> head = doubleLinkedList.getHead();
                map.remove(head.key);
                doubleLinkedList.remove(head);
            }
            Node<Integer,Integer> node = new Node<>(key,value);
            map.put(key,node);
            doubleLinkedList.addTail(node);
        }
    }
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedList.remove(node);
        doubleLinkedList.addTail(node);
        return node.value;
    }
    class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> prev;
        private Node<K,V> next;
        public Node(){};
        public Node(K key,V value){
            this.key = key;
            this.value = value;
        }
    }
    class DoubleLinkedList<K,V>{
        private Node<K,V> head = new Node<>();
        private Node<K,V> tail = new Node<>();
        public DoubleLinkedList(){
            head.next = tail;
            tail.prev = head;
        }
        public void addTail(Node<K,V> node){
            node.prev = tail.prev;
            node.next = tail;
            tail.prev.next = node;
            tail.prev = node;
        }
        public void remove(Node<K,V> node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }
        public Node<K,V> getHead(){
            return head.next;
        }
    }
}

test

public class LRUCacheTest {
    public static void main(String[] args) {
        System.out.println("--------------------LRUCache1-------------------");
        LRUCache1 lruCache1 = new LRUCache1<>(3);
        lruCache1.put(1,1);
        lruCache1.put(2,2);
        lruCache1.put(3,3);
        System.out.println(lruCache1.keySet());
        lruCache1.put(4,4);
        System.out.println(lruCache1.keySet());
        System.out.println("--------------------LRUCache2-------------------");
        LRUCache2 lruCache2 = new LRUCache2(3);
        lruCache2.put(1,1);
        lruCache2.put(2,2);
        lruCache2.put(3,3);
        System.out.println(lruCache2.map.keySet());
        lruCache2.put(4,4);
        System.out.println(lruCache2.map.keySet());
    }
}