设计一个线程安全的 LRU 缓存系统，支持异步数据加载和缓存淘汰

题目

设计一个线程安全的 LRU 缓存系统，支持异步数据加载和缓存淘汰

信息

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

考点

并发编程,内存管理,缓存策略,异步编程,Swift高级特性

快速回答

实现线程安全的 LRU 缓存需要综合运用：

• 使用DispatchQueue的barrier保证线程安全
• 双向链表 + 哈希表实现 O(1) 的 LRU 操作
• NSLock或os_unfair_lock保护关键区域
• 异步加载使用OperationQueue管理依赖
• 弱引用避免循环引用，结合autoreleasepool管理内存
• 响应内存警告实现主动清理

核心设计原理

LRU（Least Recently Used）缓存需要：

1. 双向链表：记录访问顺序（头节点最新，尾节点最旧）
2. 哈希表：实现 O(1) 的键值查询（[Key: ListNode]）
3. 线程安全：读写锁机制处理并发访问
4. 异步加载：避免重复请求，支持回调闭包

代码实现示例

final class LRUCache<Key: Hashable, Value> {
    private class ListNode {
        var key: Key?
        var value: Value?
        var next: ListNode?
        weak var prev: ListNode?
    }

    private let capacity: Int
    private var nodesDict = [Key: ListNode]()
    private let lock = os_unfair_lock()
    private let queue = DispatchQueue(label: "com.cache.queue", attributes: .concurrent)

    // 哑节点简化边界处理
    private let head = ListNode()
    private let tail = ListNode()

    init(capacity: Int) {
        self.capacity = max(1, capacity)
        head.next = tail
        tail.prev = head
    }

    func getValue(forKey key: Key, loader: @escaping (Key) -> Value?) -> Value? {
        // 1. 检查缓存是否存在
        os_unfair_lock_lock(&lock)
        defer { os_unfair_lock_unlock(&lock) }

        if let node = nodesDict[key] {
            moveToHead(node)
            return node.value
        }

        // 2. 异步加载数据
        queue.async(flags: .barrier) { [weak self] in
            guard let self = self else { return }
            if let value = loader(key) {
                self.setValue(value, forKey: key)
            }
        }
        return nil
    }

    private func setValue(_ value: Value, forKey key: Key) {
        os_unfair_lock_lock(&lock)
        defer { os_unfair_lock_unlock(&lock) }

        let node: ListNode
        if let existing = nodesDict[key] {
            // 更新现有值
            existing.value = value
            node = existing
        } else {
            // 创建新节点
            node = ListNode()
            node.key = key
            node.value = value
            nodesDict[key] = node

            // 检查容量限制
            if nodesDict.count > capacity, let last = popTail() {
                nodesDict.removeValue(forKey: last.key!)
            }
        }
        moveToHead(node)
    }

    private func moveToHead(_ node: ListNode) {
        // 从链表移除
        node.prev?.next = node.next
        node.next?.prev = node.prev

        // 插入头部
        node.next = head.next
        head.next?.prev = node
        head.next = node
        node.prev = head
    }

    private func popTail() -> ListNode? {
        guard let last = tail.prev, last !== head else { return nil }
        last.prev?.next = tail
        tail.prev = last.prev
        return last
    }

    func clearOnMemoryWarning() {
        queue.async(flags: .barrier) { [weak self] in
            autoreleasepool {
                self?.nodesDict.removeAll()
                self?.head.next = self?.tail
                self?.tail.prev = self?.head
            }
        }
    }
}

最佳实践

• 线程安全策略：
  • 使用os_unfair_lock保护关键操作（比NSLock快 50%）
  • DispatchQueue.barrier确保写入时独占访问
• 内存优化：
  • 弱引用打破循环引用（weak var prev）
  • autoreleasepool包裹批量清理操作
  • 响应UIApplication.didReceiveMemoryWarningNotification
• 性能优化：
  • 哑节点消除头尾判空逻辑
  • 哈希表 O(1) 访问 + 链表 O(1) 移动节点

常见错误

• 线程死锁：在锁内调用异步加载导致相互等待
• 循环引用：未使用[weak self]导致内存泄漏
• 优先级反转：高优先级线程等待低优先级线程的锁
• 缓存穿透：未处理异步加载失败导致重复请求

扩展知识

• 缓存策略对比：
  • LFU（最不经常使用）：适合访问模式稳定的场景
  • ARC（自适应替换缓存）：结合 LRU/LFU 优点
• Swift 特性进阶：
  • 使用actor（Swift 5.5+）简化并发代码
  • 用NSCache替代自定义实现（但失去 LRU 控制）
• 性能指标：
  • 监控缓存命中率（Hit Ratio）优化容量
  • 使用os_signpost测量关键操作耗时