LRULFU是两种经典的缓存策略,实现复杂度也适中,非常适合用来面试考察中级以上的开发者,日常练手也是非常有益的。

说明和应用

LRU

LRU(Least Recently Used)策略是淘汰最旧的缓存,典型的应用场景就是手机上的App使用列表历史。
当一个已经打开过的App被用户再次使用时,此App会提升到最新的缓存,不会被缓存策略淘汰掉。
而太久没有使用的App,则会在需要清除缓存释放资源时被首先淘汰。

LFU

LFU(Least Frequently Used)策略是淘汰使用频率最低的缓存,典型的应用场景是代理的缓存系统。Cache优先缓存高频请求的资源,而将低频内容淘汰掉,这样缓存就可以很好的提升代理速度效果。

原理

LRU策略比较直观和简单,本质上需要解决的问题是两点:
* 缓存查找性能
* 缓存的增、删、改性能,而且要求缓存有序

最快的查找必然是哈希表,增、删、改性能最好的是双向链表,所以LRUCache的底层数据结构就是哈希表和双链表,结合这两个数据结构的优点解决两个问题。

所以实现LRU的数据结构如下:
1. 通过哈希表解决查找性能
2. 通过双链表解决缓存管理性能

LFU策略和LRU相比,在淘汰缓存时,多了一个查找维度:频率。
所以查找时,依旧要处理查找频率的问题。缓存的增、删、改性能以及优秀,和LRU相同,所以依旧通过双链表来解决。

LFU策略中,会出现同一频率下的缓存淘汰。淘汰策略可以根据具体应用场景来设计,但是最朴素的就是进行LRU淘汰。

所以实现LRU的数据结构如下:
1. 通过哈希表解决查找性能
2. 增加频率维度的哈希表解决频率维度的查找性能
2. 通过双链表解决缓存管理性能

实现

LRU

  • 通过valueMap保存key-Cache,Cache则包装到链表的Node中
  • 通过一个双链表管理Cache的有序问题(Recently Used)

以下是LRU的实现,不包含相关的protocol和泛型以及层次设计。完整实现在这里

class NaiveLRUCache<NaiveLRUCacheKey: Hashable, NaiveLRUCacheValue>: BaseCache {

    typealias ValueNodeType = CacheListNode<NaiveLRUCacheKey, NaiveLRUCacheValue>

    private var valueMap: [NaiveLRUCacheKey: ValueNodeType] = [:]
    private var list: DLinkedList<ValueNodeType>

    init() {

        let default_capacity: Int = 5
        list = DLinkedList<ValueNodeType>()

        super.init(default_capacity)
    }

    init(capacity: Int) {

        list = DLinkedList<ValueNodeType>()
        super.init(capacity)
    }

    var count: Int {
        return valueMap.count
    }

    public func setValue(_ value: NaiveLRUCacheValue, forKey key: NaiveLRUCacheKey) {

        if cache_size <= 0 {
            return
        }

        lock.lock()

        if let node = valueMap[key] {
            //有缓存,更新value
            node.val = value

            //移除旧缓存,放到最新
            list.removeNode(node)
            list.appendNode(node)

        } else {
            //无缓存,增加node
            let n = CacheListNode<NaiveLRUCacheKey, NaiveLRUCacheValue>(key, value)
            valueMap[key] = n
            list.appendNode(n)
        }

        lock.unlock()

        //检查是否超出容量,则移除最旧的缓存
        clean()
    }

    public func value(forKey key: NaiveLRUCacheKey) -> NaiveLRUCacheValue? {

        lock.lock()
        defer { lock.unlock() }

        if let v:CacheListNode = valueMap[key] {

            //移除缓存然后再放到最新
            list.removeNode(v)
            list.appendNode(v)

            return v.val
        }

        return nil
    }

    @discardableResult
    public func removeValue(forKey key: NaiveLRUCacheKey) -> Bool {
        lock.lock()
        defer { lock.unlock() }

        guard let v:CacheListNode = valueMap.removeValue(forKey: key) else {

            return false
        }

        list.removeNode(v)

        return true
    }

    private func clean() {

        lock.lock()
        defer { lock.unlock() }

        while count > cache_size, let h = list.head {
            //删除最旧缓存
            list.removeNode(h)
            valueMap.removeValue(forKey: h.key)
        }
    }
}

LFU

  • 和LRU一样,通过valueMap保存key-Cache,Cache则包装到链表的Node中
  • 在节点中增加freq字段管理缓存频率
  • 通过freqMap保存freq-CacheList,即同一频率的缓存node都收纳到一个链表中,这个链表通过freqMap来索引
  • LFU比LRU多的操作有几点:
    • 当缓存的频率变更时,需要处理缓存node换到新链表的问题
    • 淘汰缓存的时候,需要处理该频率对应的链表为空的问题。这个问题展开又可以说很多:)
    1. 如果不删除,则会一直占用内存,最坏情况下,freqMap的内存开销和cache数量一致(每个cache的频率都不一致);
    2. 如果频繁删除,则会有大量的内存分配动作带来的开销。
      所以光是freqMap的清洁操作都可以有很多种处理方式,要结合具体的Cache应用场景,Cache的内容来设计。

    这里的实现是当链表为空的时候,删掉freqMap中的freq-List对。
    以下是LFU的实现,不包含相关的protocol和泛型以及层次设计。完整实现在这里

extension NaiveLFUCache {

    class NaiveLFUCacheValueNode: CacheListNode<NaiveLFUCacheKey, NaiveLFUCacheValue> {

        var freq: Int = 0

        override init(_ k: NaiveLFUCacheKey, _ v: NaiveLFUCacheValue) {
            super.init(k, v)
        }

        public func useCount() {
            freq += 1
        }
    }
}

class NaiveLFUCache<NaiveLFUCacheKey: Hashable, NaiveLFUCacheValue>: BaseCache {

    typealias ValueNodeType = NaiveLFUCacheValueNode
    typealias ValueListType = DLinkedList<ValueNodeType>

    private var valueMap: [NaiveLFUCacheKey: ValueNodeType] = [:]       // <key, value wrap in Node with freq>
    private var freqMap: [Int: ValueListType] = [:]                     // <freq, List>
    private var minFreq = 1

    init() {
        let default_capacity: Int = 5
        super.init(default_capacity)
    }

    init(capacity: Int) {
        super.init(capacity)
    }

    var count: Int {
        return valueMap.count
    }

    private func resettleNode(_ node: ValueNodeType) {

        node.useCount()

        if node.freq <= minFreq {
            minFreq = node.freq
        }

        if let freqList = freqMap[node.freq] {
            freqList.appendNode(node)
        } else {
            //出现了新的频率
            let newlist = ValueListType()
            newlist.appendNode(node)
            freqMap[node.freq] = newlist
        }
    }

    public func setValue(_ value: NaiveLFUCacheValue, forKey key: NaiveLFUCacheKey) {

        if cache_size <= 0 {
            return
        }

        lock.lock()

        if let node = valueMap[key] {
            //有缓存,更新value
            node.val = value

            if let freqList = freqMap[node.freq] {
                freqList.removeNode(node)

                if freqList.isEmpty {
                    freqMap.removeValue(forKey: node.freq)
                }
            }

            resettleNode(node)

        } else {
            //无缓存,新增
            //新增之前检查容量,检查是否超出容量,否则移除最旧的缓存
            tryToRetireTheLeastUsedNode()

            let node = NaiveLFUCacheValueNode(key, value)
            valueMap[key] = node

            resettleNode(node)
        }

        lock.unlock()
    }

    public func value(forKey key: NaiveLFUCacheKey) -> NaiveLFUCacheValue? {

        lock.lock()
        defer { lock.unlock() }

        if let node = valueMap[key] {
            //存在
            //从旧频率表中移除
            if let oldFreqList = freqMap[node.freq] {
                oldFreqList.removeNode(node)
                if oldFreqList.isEmpty {
                    freqMap.removeValue(forKey: node.freq)
                }
            }

            resettleNode(node)

            return node.val
        }

        return nil
    }

    private func tryToRetireTheLeastUsedNode() {

        while count >= cache_size {
            //删除最少使用(频率最低)且最旧缓存
            if let list = freqMap[minFreq], !list.isEmpty, let h = list.head {
                list.removeNode(h)
                valueMap.removeValue(forKey: h.key)

                if list.isEmpty {
                    freqMap.removeValue(forKey: minFreq)
                }

            } else {
                freqMap.removeValue(forKey: minFreq)
                minFreq += 1
            }
        }
    }
}

总结

LRU和LFU缓存策略的实现,是很好的数据结构应用学习。
将常用的重要的两个基础数据结构都覆盖到了,在LFU中还可以进一步探讨内存管理的sense和理解。而且,除了考察数据结构的掌握情况,还可以展开去考察多线程问题。

关于线程安全,有两个解决思路
1、直接用锁,这个是最容易想到的办法。但是一不小心会搞出死锁来,要小心。
2、用串行队列再封一层,把所有需要上锁的行为,都通过队列串行化
但可能需要调整代码,以确保一些行为进队列后依旧可以保证是紧挨着直行的,而不会被其他线程插入的任务打断

我面试的话,如果候选人可以把LRU和LFU理解和实现都搞清楚,基本上可以认为数据结构基础是没有问题的。

Refer

Leetcode: 146. LRU Cache
Leetcode: 460. LFU Cache


发表评论

您的电子邮箱地址不会被公开。

我不是机器人*