设计一个线程安全的LRU缓存，支持高并发读写和容量淘汰

题目

设计一个线程安全的LRU缓存，支持高并发读写和容量淘汰

信息

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

考点

并发编程,Java集合框架,LRU算法,锁粒度控制

快速回答

实现线程安全LRU缓存的核心要点：

• 使用 LinkedHashMap 的访问顺序特性实现LRU逻辑
• 通过读写锁（ReentrantReadWriteLock）分离读写操作
• 重写 removeEldestEntry 方法实现淘汰策略
• 使用双重检查锁定处理初始化竞态条件
• 对 computeIfAbsent 等复合操作进行同步控制

1. 核心设计原理

LRU（Least Recently Used）缓存需要满足：当容量达到上限时，自动淘汰最久未使用的数据。Java中可通过继承 LinkedHashMap 并设置访问顺序（accessOrder=true）实现：

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCapacity;

    public LRUCache(int maxCapacity) {
        super(16, 0.75f, true);  // 访问顺序模式
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }
}

2. 线程安全实现方案

2.1 读写锁优化

直接使用 Collections.synchronizedMap 会导致全局锁性能瓶颈。应采用读写锁分离：

public class ConcurrentLRUCache<K, V> {
    private final LinkedHashMap<K, V> cache;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();

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

    public V get(K key) {
        readLock.lock();
        try {
            return cache.get(key);
        } finally {
            readLock.unlock();
        }
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }
}

2.2 复合操作处理

computeIfAbsent 等操作需要原子性执行：

public V computeIfAbsent(K key, Function<K, V> loader) {
    // 先尝试读锁快速路径
    readLock.lock();
    try {
        V value = cache.get(key);
        if (value != null) return value;
    } finally {
        readLock.unlock();
    }

    // 未命中时升级为写锁
    writeLock.lock();
    try {
        // 双重检查避免重复加载
        V value = cache.get(key);
        if (value == null) {
            value = loader.apply(key);
            cache.put(key, value);
        }
        return value;
    } finally {
        writeLock.unlock();
    }
}

3. 常见错误与陷阱

• 死锁风险：在同步块内调用用户回调函数（如loader）可能导致死锁
• 锁升级问题：读写锁不支持锁升级，需释放读锁后再获取写锁
• 可见性问题：未正确同步导致缓存状态不一致
• 淘汰策略失效：未正确处理 LinkedHashMap 的结构性修改

4. 最佳实践

• 容量限制：设置合理的初始容量和负载因子避免频繁扩容
• 性能监控：记录缓存命中率和锁竞争情况
• 淘汰策略扩展：通过 AccessOrderDeque 实现自定义淘汰逻辑
• 替代方案：考虑 Caffeine 或 Guava Cache 等成熟库

5. 扩展知识

• 锁分段技术：当缓存极大时，可将数据分到多个Segment中降低锁竞争
• 无锁方案：使用 ConcurrentHashMap + ConcurrentLinkedDeque 实现无锁LRU（需处理原子更新问题）
• WeakReference：结合软/弱引用实现内存敏感型缓存
• 过期机制：添加TTL（Time-To-Live）支持自动过期