LFU（Least Frequently Used）算法根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
缺陷：在短时间内高频访问某些缓存，这些缓存会立刻晋升为热点数据，且很久不会被淘汰，这样会驻留在系统内存里面。或者最新加入的数据很快被剔除。
核心逻辑：
- 假设LFU的每个数据块都有一个引用计数freq，所有数据块按照freq排序，具有相同freq的数据块则按照访问时间排序。
- 调用 get(key) 方法时，要返回该 key 对应的 val。
- 只要用 get 或者 put 方法访问一次某个 key，该 key 的 freq 就要加1。
- 如果在容量满了的时候进行插入，则需要将 freq 最小的 key 删除，如果最小的 freq 对应多个 key，则删除其中最旧的那一个。
我的实现思路：
- LinkedHashMap本身是实现了LRU的，accessOrder为true时，链表顺序是访问顺序，每当缓存命中，LinkedHashMap将数据移到链表尾部
- 那么我们在LinkedHashMap的每一个节点上增加一个freq，并且按照freq、访问时间进行排序
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
long freq;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
void hit(Node head) { //命中缓存
freq++; //freq加1
}
}
- 每次命中缓存，缓存freq加1，然后循环与after比较freq，插入到比较大的after之前的位置，见afterNodeAccess方法
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
e.hit(head);
//循环与after比较freq，插入到比较大的after之前的位置，或者尾部
//判断e是否是链表头部或尾部，并重置头尾指针
++modCount;
}
}
- 达到了最大容量时删除头节点即可，见LinkedHashMap的afterNodeInsertion方法
void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 需要实现removeEldestEntry方法
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > capacity;
}
- 上面的实现非常方便简单，但是最差情况会达到O(n)
怎么让时间变成O(1)呢？时间主要消耗在命中缓存后要对缓存重新进行排序。
相同freq是链表中一段连续的局部链表，这个局部链表尾部其实就是将要插入的位置。那么基于上面的方案再加入一个hashmap来记录每个freq对应局部链表尾部的位置就可以了
下面是伪代码，不是真的源码
//freqMap保存的是每一个freq对应的局部链表的尾部节点
HashMap<Long, LinkedHashMap.Entry> freqMap;
void afterNodeAccess(Node<K,V> e) {
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
e.hit(head);
//循环与after比较freq，插入到比较大的after之前的位置
//增加一步，更新freqMap，将e插入到freq对应Entry的后面
Entry p = freqMap.get(e.freq);
//如果e已经在原本的链，把e从链中拿出来
e.after = p.after;
e.before = p;
p.after = e;
//更新freqMap的尾部
freqMap.put(e.freq, e);
//判断e是否是链表头部或尾部，并重置头尾指针
++modCount;
}
}
上述实现的缺陷：
- 新加入的key放在链表头部，那么当缓存满了以后会频繁的淘汰和插入，旧的缓存也就一直不会淘汰
- 一个缓存原本很活跃，freq增长到一定程度，然后突然冷了，可能会经历较长的淘汰时间，也可能会永不淘汰
思考：
- 对于这些缺陷，肯定需要有额外的策略控制缓存的淘汰，redis是怎么做的呢？
我认为，应该给新缓存成长的时间，放在不会被很快淘汰的位置；freq不应该是一直增长的，应该设置一个最大值，或者有一个梯度的衰减，freq越大则减的越多。不同业务类型的缓存，访问情况是不同的，对应缓存淘汰策略也应该不一样。
- 这只是单线程的方案，应该怎样实现一个可以支持并发的高性能缓存呢？
由此想到redis，由于本地处理速度远比网络请求快，所以redis单线程处理网络请求也可以支持高并发。
网友评论