谈一谈缓存

搬砖俱乐部

发布于 2020-01-17 15:42:47

3970

发布于 2020-01-17 15:42:47

文章被收录于专栏：BanzClubBanzClub

“ 在计算机世界里，缓存可以说无处不在，无论是硬件，还是软件，缓存都是一种最使用的优化手段，可以在操作系统读取磁盘数据时、也可以在应用访问数据库数据时，还可以是本地程序访问网络数据时……”

在开发一个应用时候，一般我们使用缓存先请求缓存，缓存不存在再请求数据库，当从数据库取到后，需要先更新缓存，再返回。这样一来，下次便可以直接从缓存中获取数据，不需要再访问数据库，避免数据直接访问磁盘而从内存直接读取，就是缓存真正的使用价值。

—

缓存淘汰算法

FIFO（First in First out）

比较容易实现的一种缓存淘汰策略，思想就是先进先出，是最简单、最公平的思想。即，最先进入缓存的数据，在空间不够的情况下，会被优先清理掉。

缺点：可能不符合数据的动态特征，比如某些热点数据会被频繁使用，但没有响应的机制来存储，直接使用缓存进入时间来淘汰缓存有点太暴力。

适用场景：优先保障最新数据可用

# 实现
# 每次插入链表，插入链表一端（头部），当超过长度时，将另一端（尾部）清除掉；

#LinkedHashMap实现
# 构造的 accessOrder 为false，表示每次访问元素时，不将被访问的元素移动到tail位置
public class FifoCache<K, V> extends LinkedHashMap<K, V> {
    // 容量
    private final int maxCapacity;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    private final Lock lock = new ReentrantLock();
    public FifoCache(int maxCapacity) {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, false);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return this.size() > maxCapacity;
    }

    @Override
    public V get(Object key) {
        try {
            lock.lock();
            return super.get(key);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public V put(K key, V value) {
        try {
            lock.lock();
            return super.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        try {
            lock.lock();
            return super.size();
        } finally {
            lock.unlock();
        }
    }

    public void clear() {
        try {
            lock.lock();
            super.clear();
        } finally {
            lock.unlock();
        }
    }
}

# Belady现象 https://www.jianshu.com/p/bcf2efe81eed

LRU（Least Recently Used）

最近最少使用策略，根据元素最后一次被使用的时间戳，清除最远使用时间戳的元素来释放空间。

缺点：当缓存经历一次大批量的顺序读写，就会将原本比较有价值的缓存，替换出去，缓存中都会被新的、无用的缓存数据填满；

使用场景：热点访问数据使用

# 实现
#每次插入链表，插入链表一端（头部），当超过长度时，将另一端（尾部）清除掉；
#当访问元素时，需要将被访问的元素移动到头部，保证最近访问的元素始终处在不被淘汰的位置，而最久未被使用的元素则会被淘汰；

# LinkedHashMap实现
# 构造的 accessOrder 为true，表示每次访问元素时，将被访问的元素移动到tail位置
public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    private final int maxCapacity;

    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private final Lock lock = new ReentrantLock();

    public LRUCache(int maxCapacity) {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return this.size() > maxCapacity;
    }

    @Override
    public V get(Object key) {
        try {
            lock.lock();
            return super.get(key);
        } finally {
            lock.unlock();
        }
    }

    @Override
    public V put(K key, V value) {
        try {
            lock.lock();
            return super.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        try {
            lock.lock();
            return super.size();
        } finally {
            lock.unlock();
        }
    }

    public void clear() {
        try {
            lock.lock();
            super.clear();
        } finally {
            lock.unlock();
        }
    }
}

LFU（least frequently used）

最少使用策略，根据元素使用次数为依据，清除使用次数最少的元素。

使用场景：按照数据使用频率优先的场景

# 实现
# 使用小顶堆实现，每次插入堆，根据元素的hitCount（命中次数）来移动堆内元素；
# 每次访问数据，需要更新元素的命中次数，并且也要重新移动堆内元素。

# 双向链表 + HashMap 实现
# HashMap记录链表节点，每个链表节点也保存在一个以频率为key，value为双向链表的Mao中
# 双向链表记录元素访问频次，头尾节点，移除元素在频率最低的双向链表中

class LFUCache {

    // 容量
    final int maxCapacity;

    // 元素长度
    int size;

    // 最小频率
    int minFreq;

    Map<Integer, Node> cache;

    // 存储每个频次对应的双向链表
    Map<Integer, DoublyLinkedList> freqMap;

    public LFUCache(int capacity) {
        cache = new HashMap<>(capacity);
        freqMap = new HashMap<>();

        this.maxCapacity = capacity;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        updateFreq(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (maxCapacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            updateFreq(node);
        } else { // 不存在
            if (size == maxCapacity) { // 只有添加的元素，原来不存在才涉及到 移除元素，否则修改原容器的元素
                Node deadNode = removeNode();
                cache.remove(deadNode.key);
                size--;
            }
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addNode(newNode);
            size++;
        }
    }

    void updateFreq(Node node) {
        // 从原freq对应的链表里移除, 并更新min
        int freq = node.freq;
        DoublyLinkedList linkedList = freqMap.get(freq);
        linkedList.update(node);
        if (freq == minFreq && linkedList.isEmpty()) {
            // 最小频率 为 仍未 当前元素 频率
            minFreq = freq + 1;
        }
        // 加入新freq对应的链表
        node.freq++;
        DoublyLinkedList newLinkedList = freqMap.get(freq + 1);
        if (newLinkedList == null) {
            newLinkedList = new DoublyLinkedList();
            freqMap.put(freq + 1, newLinkedList);
        }
        newLinkedList.put(node);
    }


    /**
     * 新增一个新节点
     *
     * @param node
     */
    void addNode(Node node) {
        DoublyLinkedList linkedList = freqMap.get(1);
        if (linkedList == null) {
            linkedList = new DoublyLinkedList();
            freqMap.put(1, linkedList);
        }
        linkedList.put(node);
        minFreq = 1;
    }

    /**
     * 移除双向链表中的，最小访问次数中的一个元素
     * <p>
     * - 更新最小频率个数？
     * 当得到当前元素为 最小元素 里唯一一个元素，则将 min 更新为当前元素 频率+1
     * - 如何保证双向中元素顺序？
     * 最小频率元素
     * 按照插入顺序，遍历
     *
     * @return
     */
    Node removeNode() {
        DoublyLinkedList linkedList = freqMap.get(minFreq);
        Node deadNode = linkedList.poll();
        linkedList.take(deadNode);
        return deadNode;
    }
}

class Node {

    Integer key;
    Integer value;

    Node last;
    Node next;

    int freq = 1;

    Node() {
    }

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}


class DoublyLinkedList {

    int size;

    Node head;
    Node tail;

    DoublyLinkedList() {
        head = new Node();
        tail = new Node();

        tail.last = head;
        head.next = tail;
    }

    /**
     * 每次插入都插到表头
     * 1、头的原来后继节点的前驱为 node
     * 2、node 的前驱 为 头
     * node的后继 为 头的原理后继
     * 3、头的后继为 node
     *
     * @param node
     */
    void put(Node node) {

        head.next.last = node;

        node.next = head.next;
        node.last = head;

        head.next = node;

        size++;
    }

    /**
     * 每次移除 表尾部节点
     */
    Node poll() {
        if (size == 0) {
            return null;
        }
        return tail.last;
    }

    void update(Node node) {
        Node last = node.last;
        Node next = node.next;

        // 清空
        node.last = null;
        node.next = null;

        last.next = next;
        next.last = last;

        size--;
    }

    void take(Node node) {
        node.last.next = tail;
        tail.last = node.last;

        // 清空
        node.last = null;
        node.next = null;

        size--;
    }

    boolean isEmpty() {
        return size == 0;
    }
}

其他淘汰策略：

随机清理
根据内容长度清理
MRU（Most recently used）：与LRU相反，当缓存区满了的时候，总是移除最近最常使用的条目
LRU-2（LRU-K）：一种对LRU的改进，它的基本思想是对每一个缓存单元，记住最近两次访问的时间。总是淘汰最近两次时间间隔最长的缓存单元
ARC（自适应缓存算法）

—

缓存使用常见问题

缓存穿透：

描述：不过有时候，有可能存在缓存和数据库都没有的情况，而用户不断发起这种不合逻辑（多半是攻击）的请求，这会导致频繁的返回缓存和数据库，导致数据库压力过大；

解决：缓存和数据库中都不存在的数据，在缓存中设置一个默认的空值，并且设置过期时间，可以有效避免频繁发生缓存未命中，而访问数据库；

缓存击穿：

描述：一般指缓存中的热点数据，通常热点数据为了抗住大量的并发访问，不过，有可能这些热点key在失效的瞬间，导致大量请求访问到了数据库；

解决：使热点数据永不过期；设置查询数据库时增加互斥锁，尽量保护数据库不会受到，大的并发而压垮；

缓存雪崩：

描述：可能由于缓存失效，或者缓存大面积失效，导致并发压力都集中到数据库，而使数据库负载过高；

解决：通过互斥锁机制，保证真实到数据库访问量不会过高；丢掉一部分请求（如随机数访问）；限流（如：令牌桶、漏洞桶等）；缓存不过期或者避免缓存同时失效；缓存服务器灾备；

—

其他

应用场景

操作系统-内存页淘汰
数据库缓冲区
分布式-缓存淘汰策略
单机-本地缓存淘汰策略

其他相关

缓存失效策略
- 主动失效：缓存过期
- 被动失效：底层数据变更通知缓存失效
预取（pre-fetch）

https://leetcode-cn.com/problems/lfu-cache/
https://blog.csdn.net/u011320646/article/details/85491103
https://www.cnblogs.com/wuchanming/p/3798924.html
https://blog.csdn.net/qq_34662278/article/details/85000540
https://www.oschina.net/translate/what-every-programmer-should-know-about-memory-part1?cmp
https://www.oschina.net/translate/what-every-programmer-should-know-about-cpu-cache-part2?cmp&
https://www.cnblogs.com/sbj-dawn/p/11116673.html

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除

https