设计高并发场景下的线程安全LRU缓存，支持自定义条目过期时间

题目

设计高并发场景下的线程安全LRU缓存，支持自定义条目过期时间

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

并发编程,集合框架选型,LRU算法实现,缓存设计,过期策略

快速回答

实现线程安全的LRU缓存需要：

• 使用LinkedHashMap的访问顺序特性实现LRU核心逻辑
• 采用ReentrantReadWriteLock保证线程安全
• 为每个条目添加过期时间戳，结合懒检查和定期清理
• 重写removeEldestEntry实现容量控制
• 使用守护线程定时清理过期条目

核心设计原理

在Java集合框架中实现高性能LRU缓存需解决三个核心问题：

1. LRU淘汰机制：利用LinkedHashMap的访问顺序特性（构造参数accessOrder=true），重写removeEldestEntry方法实现淘汰策略
2. 线程安全：采用读写锁（ReentrantReadWriteLock）实现读写分离，读操作可并发，写操作互斥
3. 过期处理：每个缓存条目记录创建时间戳和TTL，通过访问时的懒检查+定时扫描双重机制清理

完整代码实现

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.*;

public class ConcurrentLRUCache<K, V> {
    private final LinkedHashMap<K, CacheEntry<V>> cache;
    private final int maxCapacity;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();
    private final long defaultExpireMillis;
    private final Thread cleanupThread;

    public ConcurrentLRUCache(int maxCapacity, long defaultExpire, TimeUnit unit) {
        this.maxCapacity = maxCapacity;
        this.defaultExpireMillis = unit.toMillis(defaultExpire);
        this.cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, CacheEntry<V>> eldest) {
                return size() > maxCapacity;
            }
        };

        // 启动守护线程定期清理
        cleanupThread = new Thread(() -> {
            while (!Thread.currentThread().isInterrupted()) {
                try {
                    TimeUnit.SECONDS.sleep(10);
                    evictExpiredEntries();
                } catch (InterruptedException ignored) {
                    Thread.currentThread().interrupt();
                }
            }
        });
        cleanupThread.setDaemon(true);
        cleanupThread.start();
    }

    public void put(K key, V value) {
        put(key, value, defaultExpireMillis);
    }

    public void put(K key, V value, long expireMillis) {
        long expireTime = System.currentTimeMillis() + expireMillis;
        writeLock.lock();
        try {
            cache.put(key, new CacheEntry<>(value, expireTime));
        } finally {
            writeLock.unlock();
        }
    }

    public V get(K key) {
        readLock.lock();
        CacheEntry<V> entry;
        try {
            entry = cache.get(key);
        } finally {
            readLock.unlock();
        }

        if (entry == null) return null;

        // 懒检查过期
        if (System.currentTimeMillis() > entry.expireTime) {
            evictEntry(key);
            return null;
        }
        return entry.value;
    }

    private void evictEntry(K key) {
        writeLock.lock();
        try {
            cache.remove(key);
        } finally {
            writeLock.unlock();
        }
    }

    private void evictExpiredEntries() {
        writeLock.lock();
        try {
            long now = System.currentTimeMillis();
            cache.entrySet().removeIf(entry -> 
                now > entry.getValue().expireTime
            );
        } finally {
            writeLock.unlock();
        }
    }

    public void shutdown() {
        cleanupThread.interrupt();
    }

    private static class CacheEntry<V> {
        final V value;
        final long expireTime;

        CacheEntry(V value, long expireTime) {
            this.value = value;
            this.expireTime = expireTime;
        }
    }
}

最佳实践

• 读写锁优化：读操作使用读锁（可重入），写操作使用写锁（互斥），避免synchronized的全表锁
• 双重过期检查：get()操作中先读锁快速检查，发现过期再升级为写锁移除，减少锁竞争
• 定期清理：守护线程每10秒扫描过期条目，避免内存泄漏（注意设置合理的扫描间隔）
• 资源释放：提供shutdown()方法停止清理线程，防止线程泄漏

常见错误

• 死锁风险：在get()方法中直接使用写锁移除条目，需先释放读锁再获取写锁
• 过期时间精度：使用System.currentTimeMillis()而非System.nanoTime()，后者不适用于绝对时间计算
• 缓存污染：未处理重入问题，当缓存满时新条目可能触发淘汰，但被淘汰条目可能正在被使用
• 线程中断处理：清理线程需正确响应中断，否则JVM无法正常关闭

扩展知识

• 性能对比：ConcurrentHashMap+ConcurrentLinkedDeque方案可实现更高并发度，但实现复杂度更高
• 替代方案：考虑Google Guava的CacheBuilder或Caffeine缓存库，内置并发控制和W-TinyLFU算法
• 过期策略优化：采用分层过期队列（如时间轮算法）提升清理效率
• 监控扩展：添加hit/miss统计、最大访问延迟等监控指标