ConcurrentLruCache

今天看到 Spring 中的 ConcurrentLruCache 实现，本文简要记录。

/**
 * Simple LRU (Least Recently Used) cache, bounded by a specified cache limit.
 *
 * <p>This implementation is backed by a {@code ConcurrentHashMap} for storing
 * the cached values and a {@code ConcurrentLinkedDeque} for ordering the keys
 * and choosing the least recently used key when the cache is at full capacity.
 *
 * @author Brian Clozel
 * @author Juergen Hoeller
 * @since 5.3
 * @param <K> the type of the key used for cache retrieval
 * @param <V> the type of the cached values
 * @see #get
 */
public class ConcurrentLruCache<K, V> {

    private final int sizeLimit;

    private final Function<K, V> generator;

    private final ConcurrentHashMap<K, V> cache = new ConcurrentHashMap<>();

    // 当前实现为队列尾部为最近访问的节点
    private final ConcurrentLinkedDeque<K> queue = new ConcurrentLinkedDeque<>();

    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    // 对 size 的读取并不都被锁保护，所以使用了 volatile 修饰保证可见性
    private volatile int size;


    /**
     * Create a new cache instance with the given limit and generator function.
     * @param sizeLimit the maximum number of entries in the cache
     * (0 indicates no caching, always generating a new value)
     * @param generator a function to generate a new value for a given key
     */
    public ConcurrentLruCache(int sizeLimit, Function<K, V> generator) {
        Assert.isTrue(sizeLimit >= 0, "Cache size limit must not be negative");
        Assert.notNull(generator, "Generator function must not be null");
        this.sizeLimit = sizeLimit;
        this.generator = generator;
    }


    /**
     * Retrieve an entry from the cache, potentially triggering generation
     * of the value.
     * @param key the key to retrieve the entry for
     * @return the cached or newly generated value
     */
    public V get(K key) {
        // 如果设置的 sizeLimit 为 0，说明不启用缓存，直接每次调用 generator 的 apply 函数生成值并返回
        if (this.sizeLimit == 0) {
            return this.generator.apply(key);
        }

        V cached = this.cache.get(key);
        if (cached != null) { // 如果存在 key 对应的缓存
            if (this.size < this.sizeLimit) { // 如果当前缓存区中缓存项个数不足 sizeLimit, 说明无需移动 queue 中的节点，直接返回即可
                return cached;
            }
            this.lock.readLock().lock(); // 执行到此处说明缓存区中元素个数已经大于等于 sizeLimit, 那么此时需要移动 queue 中的节点
            try {
                if (this.queue.removeLastOccurrence(key)) { // 从队列尾部向前找当前访问的 key 并移除
                    this.queue.offer(key); // 将当前访问的 key 加入至队列尾部，注意此操作在读锁中实现，即存在并发调用，所以 queue 采用了线程安全的实现：ConcurrentLinkedDeque
                }
                return cached;
            }
            finally {
                this.lock.readLock().unlock();
            }
        }

        this.lock.writeLock().lock(); // 执行到此处说明缓存区中不存在 key 对应的缓存
        try {
            // 进入了写锁的临界区，此处进行双重检查，避免多个线程并发调用 get 然后串行进入该临界区导致重复创建了缓存
            // Retrying in case of concurrent reads on the same key
            cached = this.cache.get(key);
            if (cached != null) {
                if (this.queue.removeLastOccurrence(key)) {
                    this.queue.offer(key);
                }
                return cached;
            }
            // 执行到此处，即将调用 generator 的 apply 函数生成缓存
            // Generate value first, to prevent size inconsistency
            V value = this.generator.apply(key);
            if (this.size == this.sizeLimit) { // 如果缓存区中的缓存项个数已经达到预设的个数限制，则移除队列头部元素
                K leastUsed = this.queue.poll();
                if (leastUsed != null) {
                    this.cache.remove(leastUsed);
                }
            }
            this.queue.offer(key); // 添加至队列尾部，即最近的元素在队尾
            this.cache.put(key, value);
            this.size = this.cache.size();
            return value;
        }
        finally {
            this.lock.writeLock().unlock();
        }
    }

}

最为核心的方法即为 get 方法，其实现思路在上方增加了注释。关键点在于读锁那部分代码是允许多线程执行的，而我们又需要维护 queue 中节点的顺序，所以选用了线程安全的队列实现：ConcurrentLinkedDeque。唯一不理解的就是对 cache 的修改操作都被写锁保护，在当前实现中 cache 由 ConcurrentHashMap 实现，是否可以更换为 HashMap 实现呢？

关于该实现，有用户提交 issue 反馈链表中的 O(n) 扫描效率低下，建议替换为 ConcurrentLinkedHashMap，详情可参考：Revisit ConcurrentLruCache implementation · Issue #26320。

Reference

spring-framework/ConcurrentLruCache.java at v5.3.14 · spring-projects/spring-framework · GitHub
Why does ConcurrentLruCache in Spring still use thread-safe maps and queues instead of ordinary maps and queues even when read-write lock are used? - Stack Overflow