关于几种常见的缓存算法

2020/01/07 Development 算法生活技能缓存算法

目前常见的几种缓存算法包括但不限于 FIFO、LRU、LFU、MRU。下面我们一一介绍并深入一下。

FIFO 算法

FIFO（First In First Out）是比较常见的算法了，队列（Queue）就是实现了这种算法的最好例子。这是最简单、最公平的一种算法思想，它认为 如果一个数据是最先进入的，那么在将来它被访问的可能性是最小的。空间满的时候，最先进入的数据会被淘汰掉。

下图展示 FIFO 算法在访问顺序是 A、B、C、D、E、D、F 的情况下，缓存列表的更新情况（链表大小假定为 4）：

白色代表无数据，灰色代表未更新数据，绿色代表被更新数据

FIFO 的实现比较简单，可以维护一个 FIFO 队列，按照时间顺序将各数据链接起来组成队列，并将置换指针指向队列的队首。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。

优点：实现简单

缺点：判断一个缓存算法优劣的指标就是命中率，而 FIFO 算法的一个显著的缺点是，在某些特定的时刻，命中率反而会随着缓存量的增加而减少，这称为 Belady 现象。产生 Belady 现象的原因是，FIFO 置换算法 与进程访问内存的动态特征是不相容的 ，被置换的数据往往是被频繁访问的，或者没有给进程分配足够的缓存空间，因此 FIFO 算法会使一些数据 频繁地被替换和重新申请内存，从而导致命中率降低。因此，现在几乎不再使用 FIFO 算法。

LRU 算法

LRU

LRU（Least recently used）算法会根据数据的 历史访问记录 来进行淘汰数据，其核心思想是『如果数据最近被访问过，那么将来被访问的几率也更高』。

下图展示了访问顺序是 A、B、C、D、E、D、F 情况下，缓存列表的更新情况：

白色代表无数据，灰色代表未更新数据，绿色代表被更新数据

由上图可以总结一下 LRU 算法的几个特点：

新来的数据会插入链表的头部
如果链表已满（达到最大长度），则会丢弃掉链表尾部的数据
如果访问时命中，则要移动数据的位置 ^{注 1}

LRU 的实现一般是使用 LinkedHashMap，即包含了用来表示『位置』的双向链表，也包含用来『存储和获取』的 HashMap。

优点：实现起来相对简单。

缺点：当存在热点数据时，LRU 的效率很好；但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。

我们来写个代码简单实现一下 LRU 算法：

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.logging.Level;
import java.util.logging.Logger;

public class LruCache<K, V> extends LinkedHashMap<K, V> {

    private int cacheSize;

    public LruCache(int cacheSize) {
        // 三个参数分别是：初始大小、负载因子、是否开启访问顺序（accessOrder）
        // 开启访问顺序后，被命中的数据会移动到链表的头部
        super(16, (float) 0.75, true);
        this.cacheSize = cacheSize;
    }

    // 复写该方法，来决定是否要移除最旧的数据，该方法在 LinkedHashMap 中默认返回 false
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > cacheSize;
    }

    public void print()
    {
        Iterator itr = this.keySet().iterator();
        while (itr.hasNext()) {
            System.out.print(itr.next() + "");
        }

        System.out.println();
    }

    public static void main(String[] args) {
        LruCache lruCache = new LruCache(4);

        for(int i = 0; i < 10; i++) {
            lruCache.put("K" + i, i);
        }

        lruCache.print();

        lruCache.put("K10", 10);

        lruCache.print();

        lruCache.get("K7");

        lruCache.print();
    }
}

输出结果如下：

K6 K7 K8 K9
K7 K8 K9 K10
K8 K9 K10 K7

很明显这个实现类是线程不安全的，因为 LinkedHashMap 本身就是线程不安全的。

LRU-K

LRU-K 中的 K 代表 最近使用的次数 ，所以，LRU 可以被认为是 LRU-1。LRU-K 的主要目的是为了解决 LRU 算法『缓存污染』的问题，其核心思想是将『 最近使用过 1 次 』的判断标准扩展为『 最近使用过 K 次』。

于是，相比 LRU，LRU-K 需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到 K 次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K 会淘汰 第 K 次访问时间距当前时间最大的数据。

Android 中的 LruCache

Android 中的 LruCache 实现与上面直接使用 LinkedHashMap 的特性不一样，它自定义了数据插入的位置、获取的策略和丢弃的策略。

话不多说，直接上代码，在注释中进行详解：

// android.util.LruCache.java
package android.util;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 这是一个缓存，里面的数据都是强引用，包含有限数量的数据。
 * 每次当某个数据被访问，它会被移动到队列的头部。当缓存已满，新数据来临时，队列尾部的数据会被丢弃，GC 就可以回收它了。
 * 
 * 如果你缓存的数据需要被显式地释放掉，那就重写 entryRemoved 方法。
 *
 * 如果缓存未命中时，需要计算并获取对应的 key，重写 create 方法。
 * 
 * 默认情况下，缓存的大小以 Entry 的个数界决的，你可以重写 sizeOf 方法用不同的单位来决定缓存空间的大小。
 * 比如，下面这个缓存的上限是 4MB 的 bitmap：
 *
 * int cacheSize = 4 * 1024 * 1024; // 4MiB
 * LruCache bitmapCache = new LruCache(cacheSize) {
 *     protected int sizeOf(String key, Bitmap value) {
 *         return value.getByteCount();
 *     }
 * }
 *
 * 这个 LruCache 类是线程安全的。可以用下面的方法来安全地插入和获取数据：
 *
 * synchronized (cache) {
 *   if (cache.get(key) == null) {
 *       cache.put(key, value);
 *   }
 * }
 *
 * 该类不允许 null key 或者 null value。当 get、put、remove 方法返回 null 时，它的意思很明确：key 不在缓存中
 */
public class LruCache<K, V> {
    private final LinkedHashMap map;

    private int size;
    private int maxSize;

    // 插入次数
    private int putCount;
    // 新建次数
    private int createCount;
    // 丢弃次数
    private int evictionCount;
    // 命中次数
    private int hitCount;
    // 未命中次数
    private int missCount;

    // maxSize 就是没有重写 sizeOf 方法的缓存大小，也即 Entry 的条目数量
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap(0, 0.75f, true);
    }

    public void resize(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }

        synchronized (this) {
            this.maxSize = maxSize;
        }
        trimToSize(maxSize);
    }

    public final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        // 尝试根据 key 创建一个 value。
        // 因为这段代码不是同步的，所以在 create 方法结束的时候，map 的内容可能已经变化了。
        // 如果 create 方法返回的值与 map 中的值冲突，我们就释放 create 的值，并保留 map 中的值。
        // 目前 create 总是返回 null。
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }

        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }

        if (mapValue != null) {
            entryRemoved(false, key, createdValue, mapValue);
            return mapValue;
        } else {
            trimToSize(maxSize);
            return createdValue;
        }
    }

    // value 会被放到队列的头部
    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }

        trimToSize(maxSize);
        return previous;
    }

    private void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                if (size <= maxSize) {
                    break;
                }

                // BEGIN LAYOUTLIB CHANGE
                // get the last item in the linked list.
                // This is not efficient, the goal here is to minimize the changes
                // compared to the platform version.
                Map.Entry toEvict = null;
                for (Map.Entry entry : map.entrySet()) {
                    toEvict = entry;
                }
                // END LAYOUTLIB CHANGE

                if (toEvict == null) {
                    break;
                }

                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

    public final V remove(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V previous;
        synchronized (this) {
            previous = map.remove(key);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, null);
        }

        return previous;
    }

    // 这个方法在调用时，是线程不安全的
    // 当有 Entry 被丢弃或删除时调用。
    protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {}

    // 这个方法在调用时，是线程不安全的
    protected V create(K key) {
        return null;
    }

    ...
    private int safeSizeOf(K key, V value) {
        int result = sizeOf(key, value);
        if (result < 0) {
            throw new IllegalStateException("Negative size:" + key + "=" + value);
        }
        return result;
    }
    ...
}

可见，Android 对 LruCache 有了自己的实现，最重要的是，它是 线程安全 的，但是效率会相对低一些，不过缓存的使用概率本身相对较低，所以稍低的效率也是可以忍受的。

LFU 算法

LFU（Least Frequently Used，最近最少使用）也是一种常见的缓存算法。它认为 如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

在实现时，考虑到 LFU 会淘汰访问频率最小的数据，我们需要一种合适的方法 按大小顺序 维护数据访问的频率。LFU 算法本质上可以看做是一个 top K 问题 (K = 1)，即选出频率最小的元素，因此我们很容易想到可以用 二项堆 来选择频率最小的元素，这样的实现比较高效。最终实现策略为小顶堆 + 哈希表。

缺点：最新加入的数据常常会被踢除，因为其起始方法次数少。

MRU 算法

MRU（Most Recently Used，最近最常使用）算法的思想与 LRU 算法正好相反，它认为 如果一个数据最近被访问过，那么它接下来被访问的概率就会更低。

附注

注 1

在移动数据的位置时，在 java1.7（含）之前采用的是 头插法 ，数据会被移动到 链表的头部 。而在 java1.8 之后，采用了 尾插法 ，所以移动数据的话，就会被移动到 链表的尾部。

我们看看代码是如何写的：

// LinkedHashMap java1.7
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V> {
    
    private transient Entry header;

    ...
    public V get(Object key) {
        Entry e = (Entry)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }
    ...
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        Entry before, after;
        ...
        private void addBefore(Entry existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(HashMap m) {
            LinkedHashMap lm = (LinkedHashMap)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                // 这里可以看出，将被访问的 Entry 重新放置在了 header 的前面，也即成为了新的链表头
                addBefore(lm.header);
            }
        }
    }
    ...
}

// LinkedHashMap java1.8

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V> {

    ...
    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry head;    // 表头，最老的数据

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry tail;    // 表尾，最新的数据
    ...
    public V get(Object key) {
        Node e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

    void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

打赏

支付宝

微信

关于注解

HashMap 解析

本文作者：CodingRabbit

永久链接：http://localhost:4000/cache-algorithms/