LRU

Least Recently Used —— 最近最少使用的数据, 踢走 (

感觉可以看成一个在缓存容量达到上限的情况下, 先剔除什么旧数据来对新数据进行存储的一种策略.

那么它的思想就是淘汰最长时间没有被访问的那个元素.

我们假设 Cache 的容量是 3 个元素, 然后有一条访问链(箭头指向更新访问的) A -> B -> C 在这个访问链中, A 是最老, 最古早的没有使用到的数据, 同时 C 是最新被使用过的数据.

此时 Cache 已经抵达上限, 如果我们再调用 D 的话, 根据上述策略, 就踢掉 A, 然后缓存 D

它可以“成立”, 是基于假设 —— 「Temporal Locality」, 即 ”最近访问的数据, 很可能马上还会再次被访问“

存储数据结构推导

假设我们有实现这样的策略, 那么有1️以下几个操作 ——

让它们的时间复杂度越低越好, 甚至是 O(1)

那么首先遇到了 O(1) 的查找 Key 操作, 第一反应或许是哈希表(不考虑缓存局部性). 不赖, 那么实际上我们针对 Key 还需要另一个数据结构进行维护 —— 因为假设我们仅仅记录时间戳, 那么在达到缓存上限的时候需要遍历整个表进行查找最旧元素, 这是一个 O(N) 的很贵的操作.

那么也就是说, 我们最好的处理方式是在每一次修改的时候维护一个数据结构, 可以保证每次 O(1) 的时间复杂度能够知道最旧的数据.

现在模拟一下, 假设还是上面的例子,有 A -> B -> C , 那么此时假设在每一次操作的时候我们维护了一个序列, 最左侧是 A, 表示最旧访问. 最右侧是 C, 表示最新访问.

那么此时又访问了数据 A —— 因为 A 是已经在缓存中的数据, 所以那个哈希表没必要动, 但是我们要更新 A -> B -> C 的访问时间顺序存储链条, 变成 B -> C -> A

也就是做了一个「把中间某个已经缓存过的元素, 调到序列最右侧」, 那么这样做比较便宜的数据结构大概率是链表, 因为涉及到处移动元素. 不过此时又会遇到一个问题 —— 我们从中间查找到 A 这个位置, 在链表的使用中又是一个 O(N) 的操作. 那本质上其实没什么变化.

所以我们不妨设计一个 Hash key -> Iter 的结构, 这样我们可以以 O(1) 的速度得到链表的位置, 然后再以 O(1) 的操作删除原先位置并且插入到链表最右侧.

最后一个小总结 —— 其实我们考虑了两件事情

那么看上去我们需要维护两个哈希表? —— 不, 直接把 value 存在链表元素中即可

这样就推导出了最基础的 LRU Cache 存储数据结构

Key -> List Iterator -> List Node -> Value

不赖