乐趣区

关于redis:java-从零开始手写-redis十缓存淘汰算法-LFU-最少使用频次

jiezi

前言

java 从零手写实现 redis（一）如何实现固定大小的缓存？

java 从零手写实现 redis（三）redis expire 过期原理

java 从零手写实现 redis（三）内存数据如何重启不失落？

java 从零手写实现 redis（四）增加监听器

java 从零手写实现 redis（五）过期策略的另一种实现思路

java 从零手写实现 redis（六）AOF 长久化原理详解及实现

java 从零手写实现 redis（七）LRU 缓存淘汰策略详解

从零开始手写 redis（八）奢侈 LRU 淘汰算法性能优化

本节一起来学习下另一个罕用的缓存淘汰算法，LFU 起码应用频次算法。

LFU 基础知识

概念

LFU(Least Frequently Used) 即最近最不罕用. 看名字就晓得是个基于拜访频次的一种算法。

LRU 是基于工夫的, 会将工夫上最不常拜访的数据给淘汰，在算法体现上是放到列表的顶部;LFU 为将频率上最不常拜访的数据淘汰.

既然是基于频率的, 就须要有存储每个数据拜访的次数.

从存储空间上, 较 LRU 会多出一些持有计数的空间.

核心思想

如果一个数据在最近一段时间内应用次数很少，那么在未来一段时间内被应用的可能性也很小。

实现思路

O(N) 的删除

为了可能淘汰起码应用的数据，集体第一直觉就是间接一个 HashMap<String, Interger>, String 对应 key 信息，Integer 对应次数。

每次拜访到就去 +1，设置和读取的工夫复杂度都是 O(1)；不过删除就比拟麻烦了，须要全副遍历比照，工夫复杂度为 O(n);

O(logn) 的删除

另外还有一种实现思路就是利用小顶堆 +hashmap，小顶堆插入、删除操作都能达到 O(logn) 工夫复杂度，因而效率相比第一种实现办法更加高效。比方 TreeMap。

O(1) 的删除

是否可能更进一步优化呢？

其实 O(1) 的算法是有的，参见这篇 paper:

An O(1) algorithm for implementing the LFU cache eviction scheme

简略说下集体的想法：

咱们要想实现 O(1) 的操作，必定离不开 Hash 的操作，咱们 O(N) 的删除中就实现了 O(1) 的 put/get。

然而删除性能比拟差，因为须要寻找次数起码的比拟耗时。

private Map<K, Node> map; // key 和数据的映射
private Map<Integer, LinkedHashSet<Node>> freqMap; // 数据频率和对应数据组成的链表

class Node {
    K key;
    V value;
    int frequency = 1;
}

咱们应用双 Hash 基本上就能够解决这个问题了。

map 中寄存 key 和节点之间的映射关系。put/get 必定都是 O(1) 的。

key 映射的 node 中，有对应的频率 frequency 信息；雷同的频率都会通过 freqMap 进行关联，能够疾速通过频率获取对应的链表。

删除也变得非常简单了，根本能够确定须要删除的最低频次是 1，如果不是最多从 1…n 开始循环，最小 freq 抉择链表的第一个元素开始删除即可。

至于链表自身的优先级，那么能够依据 FIFO，或者其余你喜爱的形式。

paper 的核心内容介绍

他山之石，可以攻玉。

咱们在实现代码之前，先来读一读这篇 O(1) 的 paper。

介绍

本文的构造如下。

对 LFU 用例的形容，它能够证实优于其余缓存逐出算法

LFU 缓存实现应反对的字典操作。这些是确定策略运行时复杂度的操作

以后最驰名的 LFU 算法及其运行时复杂度的形容

提出的 LFU 算法的阐明；每个操作的运行时复杂度为 O（1）

LFU 的用处

思考用于 HTTP 协定的缓存网络代理应用程序。

该代理通常位于 Internet 与用户或一组用户之间。

它确保所有用户都可能拜访 Internet，并实现所有可共享资源的共享，以实现最佳的网络利用率和响应速度。

这样的缓存代理应该尝试在可摆布的无限数量的存储或内存中最大化其能够缓存的数据量。

通常，在将动态资源（例如图像，CSS 样式表和 javascript 代码）替换为较新版本之前，能够很容易地将它们缓存很长时间。

这些动态资源或程序员所谓的“资产”简直蕴含在每个页面中，因而缓存它们是最无益的，因为简直每个申请都将须要它们。

此外，因为要求网络代理每秒解决数千个申请，因而应将这样做所需的开销放弃在最低水平。

为此，它应该仅驱赶那些不常常应用的资源。

因而，应该将常常应用的资源放弃在不那么频繁应用的资源上，因为前者曾经证实本人在一段时间内是有用的。

当然，有一个说法与之相同，它说未来可能不须要大量应用的资源，然而咱们发现在大多数状况下状况并非如此。

例如，频繁应用页面的动态资源始终由该页面的每个用户申请。

因而，当内存不足时，这些缓存代理能够应用 LFU 缓存替换策略来驱赶其缓存中应用起码的我的项目。

LRU 在这里也可能是实用的策略， 然而当申请模式使得所有申请的我的项目都没有进入缓存并且以循环形式申请这些我的项目时，LRU 将会失败。

ps: 数据的循环申请，会导致 LRU 刚好不适应这个场景。

在应用 LRU 的状况下，我的项目将一直进入和来到缓存，而没有用户申请拜访缓存。

然而，在雷同条件下，LFU 算法的性能会更好，大多数缓存项会导致缓存命中。

LFU 算法的病理行为并非没有可能。

咱们不是在这里提出 LFU 的案例，而是试图证实如果 LFU 是实用的策略，那么比以前公布的办法有更好的实现办法。

LFU 缓存反对的字典操作

当咱们谈到缓存逐出算法时，咱们次要须要对缓存数据进行 3 种不同的操作。

  1. 在缓存中设置（或插入）我的项目
  2. 检索（或查找）缓存中的我的项目；同时减少其应用计数（对于 LFU）
  3. 从缓存中逐出（或删除）起码应用（或作为逐出算法的策略）

LFU 算法的以后最驰名的复杂性

在撰写本文时，针对 LFU 缓存逐出策略的上述每个操作的最驰名的运行时如下：

插入：O（log n）

查找：O（log n）

删除：O（log n）

这些复杂度值间接从二项式堆实现和规范无抵触哈希表中取得。

应用最小堆数据结构和哈企图能够轻松无效地施行 LFU 缓存策略。

最小堆是基于（我的项目的）应用计数创立的，并且通过元素的键为哈希表建设索引。

无抵触哈希表上的所有操作的程序均为 O（1），因而 LFU 缓存的运行工夫由最小堆上的操作的运行工夫管制。

将元素插入高速缓存时，它将以 1 的应用计数进入，因为插入最小堆的开销为 O（log n），因而将其插入 LFU 高速缓存须要 O（log n）工夫。

在查找元素时，能够通过哈希函数找到该元素，该哈希函数将键哈希到理论元素。同时，应用计数（最大堆中的计数）加 1，这导致最小堆的重组，并且元素从根移开。

因为元素在任何阶段都能够向下挪动至 log(n) 电平，因而此操作也须要工夫 O（log n）。

当抉择一个元素将其逐出并最终从堆中删除时，它可能导致堆数据结构的重大重组。

应用计数起码的元素位于最小堆的根。

删除最小堆的根包含将根节点替换为堆中的最初一个叶节点，并将该节点起泡到正确的地位。

此操作的运行时复杂度也为 O（log n）。

提出的 LFU 算法

对于能够在 LFU 缓存上执行的每个字典操作（插入，查找和删除），提出的 LFU 算法的运行时复杂度为 O（1）。

这是通过保护 2 个链接列表来实现的。一个用于拜访频率，另一个用于具备雷同拜访频率的所有元素。

哈希表用于按键拜访元素（为分明起见，下图中未显示）。

双链表用于将代表一组具备雷同拜访频率的节点的节点链接在一起（在下图中显示为矩形块）。

咱们将此双重链接列表称为频率列表。具备雷同拜访频率的这组节点实际上是此类节点的双向链接列表（在下图中显示为圆形节点）。

咱们将此双向链接列表（在特定频率本地）称为节点列表。

节点列表中的每个节点都有一个指向其父节点的指针。

频率列表（为分明起见，未在图中显示）。因而，节点 x 和您将有一个指向节点 1 的指针，节点 z 和 a 将有一个指向节点 2 的指针，依此类推 …

上面的伪代码显示了如何初始化 LFU 缓存。

用于按键定位元素的哈希表由按键变量示意。

为了简化实现，咱们应用 SET 代替链表来存储具备雷同拜访频率的元素。

变量项是规范的 SET 数据结构，其中蕴含具备雷同拜访频率的此类元素的键。

它的插入，查找和删除运行时复杂度为 O（1）。

伪代码

前面的都是一些伪代码了，咱们条国内。

了解其最外围的思维就行了，上面咱们上真代码。

感触

这个 O(1) 的算法最外围的中央实际上不多，放在 leetcode 应该算是一个中等难度的题目。

不过很奇怪，这篇论文是在 2010 年提出的，预计以前都认为 O(logn) 是极限了？

java 代码实现

根本属性 

public class CacheEvictLfu<K,V> extends AbstractCacheEvict<K,V> {private static final Log log = LogFactory.getLog(CacheEvictLfu.class);

    /**
     * key 映射信息
     * @since 0.0.14
     */
    private final Map<K, FreqNode<K,V>> keyMap;

    /**
     * 频率 map
     * @since 0.0.14
     */
    private final Map<Integer, LinkedHashSet<FreqNode<K,V>>> freqMap;

    /**
     *
     * 最小频率
     * @since 0.0.14
     */
    private int minFreq;

    public CacheEvictLfu() {this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.minFreq = 1;
    }

}

节点定义

  • FreqNode.java
public class FreqNode<K,V> {

    /**
     * 键
     * @since 0.0.14
     */
    private K key;

    /**
     * 值
     * @since 0.0.14
     */
    private V value = null;

    /**
     * 频率
     * @since 0.0.14
     */
    private int frequency = 1;

    public FreqNode(K key) {this.key = key;}

    //fluent getter & setter
    // toString() equals() hashCode()}

移除元素 

/**
 * 移除元素
 *
 * 1. 从 freqMap 中移除
 * 2. 从 keyMap 中移除
 * 3. 更新 minFreq 信息
 *
 * @param key 元素
 * @since 0.0.14
 */
@Override
public void removeKey(final K key) {FreqNode<K,V> freqNode = this.keyMap.remove(key);
    //1. 依据 key 获取频率
    int freq = freqNode.frequency();
    LinkedHashSet<FreqNode<K,V>> set = this.freqMap.get(freq);
    //2. 移除频率中对应的节点
    set.remove(freqNode);
    log.debug("freq={} 移除元素节点：{}", freq, freqNode);
    //3. 更新 minFreq
    if(CollectionUtil.isEmpty(set) && minFreq == freq) {
        minFreq--;
        log.debug("minFreq 升高为：{}", minFreq);
    }
}

更新元素 

/**
 * 更新元素，更新 minFreq 信息
 * @param key 元素
 * @since 0.0.14
 */
@Override
public void updateKey(final K key) {FreqNode<K,V> freqNode = keyMap.get(key);
    //1. 曾经存在
    if(ObjectUtil.isNotNull(freqNode)) {
        //1.1 移除原始的节点信息
        int frequency = freqNode.frequency();
        LinkedHashSet<FreqNode<K,V>> oldSet = freqMap.get(frequency);
        oldSet.remove(freqNode);
        //1.2 更新最小数据频率
        if (minFreq == frequency && oldSet.isEmpty()) {
            minFreq++;
            log.debug("minFreq 减少为：{}", minFreq);
        }
        //1.3 更新频率信息
        frequency++;
        freqNode.frequency(frequency);
        //1.4 放入新的汇合
        this.addToFreqMap(frequency, freqNode);
    } else {
        //2. 不存在
        //2.1 构建新的元素
        FreqNode<K,V> newNode = new FreqNode<>(key);
        //2.2 固定放入到频率为 1 的列表中
        this.addToFreqMap(1, newNode);
        //2.3 更新 minFreq 信息
        this.minFreq = 1;
        //2.4 增加到 keyMap
        this.keyMap.put(key, newNode);
    }
}

/**
 * 退出到频率 MAP
 * @param frequency 频率
 * @param freqNode 节点
 */
private void addToFreqMap(final int frequency, FreqNode<K,V> freqNode) {LinkedHashSet<FreqNode<K,V>> set = freqMap.get(frequency);
    if (set == null) {set = new LinkedHashSet<>();
    }
    set.add(freqNode);
    freqMap.put(frequency, set);
    log.debug("freq={} 增加元素节点：{}", frequency, freqNode);
}

数据淘汰 

@Override
protected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {
    ICacheEntry<K, V> result = null;
    final ICache<K,V> cache = context.cache();
    // 超过限度，移除频次最低的元素
    if(cache.size() >= context.size()) {FreqNode<K,V> evictNode = this.getMinFreqNode();
        K evictKey = evictNode.key();
        V evictValue = cache.remove(evictKey);
        log.debug("淘汰最小频率信息, key: {}, value: {}, freq: {}",
                evictKey, evictValue, evictNode.frequency());
        result = new CacheEntry<>(evictKey, evictValue);
    }
    return result;
}

/**
 * 获取最小频率的节点
 *
 * @return 后果
 * @since 0.0.14
 */
private FreqNode<K, V> getMinFreqNode() {LinkedHashSet<FreqNode<K,V>> set = freqMap.get(minFreq);
    if(CollectionUtil.isNotEmpty(set)) {return set.iterator().next();}
    throw new CacheRuntimeException("未发现最小频率的 Key");
}

测试

代码 

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .evict(CacheEvicts.<String, String>lfu())
        .build();
cache.put("A", "hello");
cache.put("B", "world");
cache.put("C", "FIFO");
// 拜访一次 A
cache.get("A");
cache.put("D", "LRU");

Assert.assertEquals(3, cache.size());
System.out.println(cache.keySet());

日志 

[DEBUG] [2020-10-03 21:23:43.722] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 增加元素节点：FreqNode{key=A, value=null, frequency=1}
[DEBUG] [2020-10-03 21:23:43.723] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 增加元素节点：FreqNode{key=B, value=null, frequency=1}
[DEBUG] [2020-10-03 21:23:43.725] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 增加元素节点：FreqNode{key=C, value=null, frequency=1}
[DEBUG] [2020-10-03 21:23:43.727] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=2 增加元素节点：FreqNode{key=A, value=null, frequency=2}
[DEBUG] [2020-10-03 21:23:43.728] [main] [c.g.h.c.c.s.e.CacheEvictLfu.doEvict] - 淘汰最小频率信息, key: B, value: world, freq: 1
[DEBUG] [2020-10-03 21:23:43.731] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict
[DEBUG] [2020-10-03 21:23:43.732] [main] [c.g.h.c.c.s.e.CacheEvictLfu.addToFreqMap] - freq=1 增加元素节点：FreqNode{key=D, value=null, frequency=1}
[D, A, C]

LFU vs LRU

区别

LFU 是基于拜访频次的模式，而 LRU 是基于拜访工夫的模式。

劣势

在数据拜访合乎正态分布时，相比于 LRU 算法，LFU 算法的缓存命中率会高一些。

劣势

  • LFU 的复杂度要比 LRU 更高一些。
  • 须要保护数据的拜访频次，每次拜访都须要更新。
  • 晚期的数据相比于前期的数据更容易被缓存下来，导致前期的数据很难被缓存。
  • 新退出缓存的数据很容易被剔除，像是缓存的末端产生“抖动”。

小结

不过理论实际中，LFU 的利用场景理论并没有那么宽泛。

因为实在的数据都是有歪斜的，热点数据才是常态，所以 LRU 的性能个别状况下优于 LFU。

开源地址：https://github.com/houbb/cache

感觉本文对你有帮忙的话，欢送点赞评论珍藏关注一波，你的激励，是我最大的能源~

目前咱们实现了性能比拟优异的 LRU 和 LFU 算法，然而操作系统理论采纳的却不是这两种算法，咱们下一节将一起学习下操作系统青眼的 clock 淘汰算法。

不晓得你有哪些播种呢？或者有其余更多的想法，欢送留言区和我一起探讨，期待与你的思考相遇。

退出移动版