设计一个线程安全的LRU缓存并优化高并发性能

题目

设计一个线程安全的LRU缓存并优化高并发性能

信息

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

考点

并发编程,集合框架选型,LRU算法实现,性能优化

快速回答

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

• 使用LinkedHashMap的访问顺序特性实现基础LRU逻辑
• 通过ReentrantReadWriteLock或ConcurrentHashMap+ConcurrentLinkedDeque保证线程安全
• 针对写操作采用分段锁优化并发性能
• 实现动态容量调整和过期策略
• 处理缓存穿透和雪崩问题

核心需求分析

LRU（Least Recently Used）缓存需要满足：1) 快速访问 2) 自动淘汰最久未使用的数据 3) 线程安全 4) 高并发下的性能稳定。Java集合框架中LinkedHashMap可通过覆写removeEldestEntry实现基础LRU，但需额外处理线程安全问题。

基础实现方案

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

    public SimpleLRUCache(int maxCapacity) {
        super(maxCapacity, 0.75f, true); // 开启访问顺序
        this.maxCapacity = maxCapacity;
    }

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

此实现非线程安全，且LinkedHashMap在并发场景下会产生数据不一致问题。

线程安全优化方案

方案1：读写锁控制

public class ReadWriteLockLRUCache<K, V> {
    private final LinkedHashMap<K, V> cache;
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();

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

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

缺陷：写操作完全互斥，高并发下成为性能瓶颈。

方案2：分段锁+并发队列（推荐）

public class ConcurrentLRUCache<K, V> {
    private final ConcurrentHashMap<K, V> cacheMap;
    private final ConcurrentLinkedDeque<K> accessQueue;
    private final ReentrantLock[] segmentLocks;
    private final int concurrencyLevel;

    public V get(K key) {
        V value = cacheMap.get(key);
        if (value != null) {
            ReentrantLock lock = getSegmentLock(key);
            lock.lock();
            try {
                accessQueue.remove(key);   // O(n)操作
                accessQueue.addLast(key);
            } finally {
                lock.unlock();
            }
        }
        return value;
    }

    public void put(K key, V value) {
        ReentrantLock lock = getSegmentLock(key);
        lock.lock();
        try {
            if (cacheMap.size() >= MAX_CAPACITY) {
                K eldest = accessQueue.pollFirst();
                if (eldest != null) cacheMap.remove(eldest);
            }
            cacheMap.put(key, value);
            accessQueue.addLast(key);
        } finally {
            lock.unlock();
        }
    }

    private ReentrantLock getSegmentLock(K key) {
        return segmentLocks[Math.abs(key.hashCode() % concurrencyLevel)];
    }
}

关键优化点

• 分段锁设计： 根据key哈希分散锁竞争，默认16段
• 数据结构分离： ConcurrentHashMap负责数据存储，并发队列维护访问顺序
• 惰性删除： 在put操作时触发淘汰，避免单独清理线程
• 容量预警： 当size达到90%容量时启动后台线程预清理

性能对比

生产环境建议

1. 直接使用Caffeine或Guava Cache（支持权重、过期时间等）
2. 自定义实现时：
   • 添加软引用/弱引用防止内存泄漏
   • 实现cleanUp方法定时清理过期数据
   • 使用StampedLock优化读多写少场景
3. 防御性编程：
   • 限制单个Key的大小防止DoS攻击
   • 添加熔断机制当缓存失败时降级

常见陷阱

• 并发修改异常： 未同步的LinkedHashMap在迭代时修改
• 死锁风险： 嵌套调用缓存方法导致锁重入
• 性能悬崖： ConcurrentLinkedDeque.remove()的O(n)复杂度
• 内存泄漏： 未正确清理关联资源（如数据库连接）

扩展知识

• 变种算法： LRU-K（考虑历史访问频率）、SLRU（分段LRU）
• JVM优化： 使用-XX:+UseCompressedOops减少内存占用
• 监控指标： 命中率、平均加载时间、淘汰计数
• TinyLFU： Caffeine采用的频率统计算法，空间效率比LRU高10倍