常用缓存淘汰算法

java 缓存 算法
算法
发布日期:   2023-04-27

FIFO（First In First Out）

FIFO

FIFO算法的核心是更换最早进入内存的页面。数据结构上使用队列（Queue）来实现。新访问的数据插入队列尾部，数据从队列中属性移动淘汰队列头部的数据。

优点

实现简单。

缺点

无法根据使用频次、时间等维度进行优化，会导致缓存命中率降低。

LRU（Least Recently Used）

LRU是最近最少使用策略的缩写，根据历史访问记录来进行淘汰，其核心思想是如果数据最近被访问过，那么将来被访问的几率也更高。

LRU

每当缓存被使用的时候（C、B、A）,则将使用频率+1，当进行淘汰的时候，将使用频率最低的数据淘汰（E）。

优点

提高频繁使用数据的命中率。

缺点

当所有数据访问都很频繁的时候，将失去优点。

SLRU（Segmented LRU）

LRU有个问题，如果一个元素纸杯访问一次，那么它也会把其他元素给挤出去，这样会导致如果缓存空间不够长，遇到突发的稀疏流量（如：列表遍历）将会把大量元素给挤出去，留下一堆可能不会再次被访问的元素在缓存中，导致命中率下降。

SLRU是把缓存分成两段，一段是淘汰段，一段是保护段，两个段都是普通的LRU实现。第一次被访问的元素将进入淘汰段，只有处于淘汰段中的元素再次被访问才会进入保护段。保护段中的元素如果被淘汰，将会再次进入淘汰段，而淘汰段的元素被淘汰则会被移出缓存。

它能更好的抵御突发的稀疏流量，保护段的元素不会被只访问一次的元素给淘汰。

空间不足时只会从淘汰段淘汰，保护段的元素不会被直接淘汰。

SLRU

W-TinyLFU

对于需要缓存的场景，一个优秀的缓存淘汰策略可以提高缓存的命中率，最常用的淘汰策略是LFU和LRU。

对于LFU来说，它只需要维护每个元素的使用频率，为了准确，需要维护全局元素的频率，这会带来巨大的空间成本。而且一个元素前期使用频率高，后期不再使用也很难淘汰，但在实际场景中访问频率会随着实际发生变化。

LRU是一个很优秀的缓存淘汰策略，但它需要更大的空间来保证元素不会在下次访问之前被淘汰。

而W-TinyLFU则是一个非常优秀的缓存淘汰策略，它综合的考虑了现实场景中可能会遇到的各种问题，有如下优点：

  • 准入策略：进入缓存的元素必须是能够提高缓存命中率的。
  • 基于频率：它具有LFU的优点，但使用了一种低空间消耗的频率统计方式，避免LFU由于频率统计带来的巨大空间消耗。
  • 保鲜机制：前边有提到LFU访问超过一定频率后就难以被淘汰，但现实场景中访问频率会随着时间发生变化，因此W-TinyLFU加入了保鲜机制，来保证缓存中的元素是频繁被访问的，保鲜机制简单来讲就是让每个元素的频率随着时间降低，而不是一直保持不变。

SLRU

W-TinyLFU由多个部分组合而成，包括：窗口缓存、布隆过滤器、主缓存。

BloomFilter（布隆过滤器）

布隆过滤器是一种用于判断元素是否存在的方式，它的空间成本非常小，速度也非常快。

但由于它是基于概率的，所以也存在一定的误判率。规则：

  • 返回存在：元素可能存在
  • 返回不存在：元素一定不存在

适合场景：能够容忍一定误判，元素是否存在集合内的场景，例：缓存。

BloomFilter

判断元素是否存在，如上图流程，根据哈希函数映射的位置（一般会使用3个哈希函数），判断所有映射的位置是否都是1，如果是，元素可能存在，否则元素一定不存在。

由于不同的元素通过哈希函数计算后，可能映射到同一个位置，因此如果一个不存在的元素对应的位置都被其他元素设置为1，则查询时会误判。

CountMinSketch（近似计数器）

近似计数器用来统计一个元素被访问的次数，它能以非常小的空间统计大量元素的计数，同时保证高性能和准确性。

与布隆过滤器类似，它是基于概率的，因此计数有一定的误差，可能会比真实的数量大。因此适合能够容忍计数存在一定误差的场景，例：缓存元素被访问的频率。

近似计数器的数据结构是一个二维数组，每个元素都是一个计数器，可以使用一个数值类型表示，例：无符号int。

CountMinSketch

对于增加计数操作，每个元素会通过不同的哈希函数映射到每行的某个位置，并增加对应位置上的计数。

估算计数也是如上图的流程，根据哈希映射到每行对应的位置，然后读取所有行的计数，返回其中最小的一个。

返回最小值是因为，其他元素可能也会映射到相同的位置上边，导致计数比真实的大，因此返回的最小值最有可能是真实计数。

窗口缓存

前边提到，W-TinyLFU选择一个元素是否加入缓存，得看这个元素加入缓存是否能提高整体缓存命中率，而这个评估的依据是根据元素的访问频率。但是如果刚加入缓存的元素（表示元素刚刚才开始被访问），它的频率并不足以让它加入软床，那么它会直接被淘汰。

因此在W-TinyLFU中使用LRU来作为窗口缓存，主要是让元素能够有计划在窗口缓存中去积累它的频率，避免因为使用频率很低而直接被淘汰。

窗口缓存很小，只占整个W-TinyLFU的1%。

基于频率

在W-TinyLFU中主要是使用了LFU的访问频率的思想，根据访问的频率进行PK，决定元素的去留，不过W-TinyLFU使用了另外的方式来统计元素的访问频率，也就是前边提到的BloomFilter和CountMinSketch。

频率统计机制

W-TinyLFU中使用BloomFilter+CountMinSketch来统计元素的访问频率，BloomFilter作为一个前置计数器，而CountMinSketch则作为主计数器。

在W-TinyLFU中使用一个4bit大小的CountMinSketch计数器来统计每个元素的访问频率，它是主计数器，元素在第一个计数会记录在BloomFilter中，之后就会记录在CountMinSketch中。

需要BloomFilter的主要原因是CountMinSketch也是基于概率的，在计数的正确性一定的情况下，越多的元素进入CountMinSketch计数器，那么CountMinSketch就需要越大和越多的哈希函数，而BloomFilter可以抵挡部分技术支持还不需要那么么大的元素（也就是计数值只有1），这样我们就可以减小CountMinSketch计数器的大小。

FrequencyMechanism

估算元素计数值时需要把BloomFilter和CountMinSketch的计数进行求和。对于每个元素BloomFilter最大只能表示计数值1，而CountMinSketch计数器4bit可以表达最大计数值15，因此每个元素最大能表达的计数值是16。

保鲜机制

前边提到了LFU建立起一定频率后就难以被淘汰，现实场景中访问频率会随着时间变化，因此W-TinyLFU加入了保鲜机制，来保证缓存中的元素是频繁访问的。保鲜机制简单讲就是让每个元素的频率随着时间降低，而不是一直保持不变。

具体的做法是，我们在进行一定次数的操作后，把前边提到的BloomFilter和CountMinSketch计数器的值进行衰减。对于BloomFilter会直接清空（置0）。而CountMinSketch则会把每个元素的值除以2。

这样不仅可以让元素的频率随着时间降低，而且还避免BloomFilter和CountMinSketch长时间使用后被污染（这2个数据结构都是基于概率的，因此每个位置都可能映射多个元素，时间长了造成的污染会越来越大）。

主缓存

主缓存中的元素会被有效保护，除非主缓存中最有可能被淘汰的元素在过滤器PK时输给了从窗口缓存中淘汰的元素，才会有主缓存中的元素被淘汰。

Java中常用的缓存框架

Caffeine

Caffeine是一个基于java8+的高性能缓存库，是Guava Cache的升级版，相⽐于Guava Cache，它具有以下⼏个优势：

  • 更⾼的性能：Caffeine使⽤了更快的数据结构、更⾼效的缓存算法，以及更优化的内存管理策略，
    使得其在⼤多数场景下可以⽐Guava Cache更快地进⾏缓存访问和更新操作。
  • 更灵活的API：Caffeine提供了更丰富和灵活的API，可以⽅便地设置缓存参数、⾃定义缓存清理策
    略、异步加载数据等。此外，它还⽀持使⽤Java 8的lambda表达式等新特性来简化代码编写。
  • 更友好的内存管理：Caffeine允许⽤户通过配置最⼤缓存⼤⼩、最⼤权重、过期时间等参数来控制
    缓存的内存占⽤量，从⽽避免因缓存过多数据⽽导致内存溢出问题。
  • 更好的兼容性：Caffeine⽀持与Guava集成，并提供了⼀套向后兼容的API，可以轻松地升级现有
    的Guava Cache应⽤程序。

使用示例

package show.lmm;

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.RemovalCause;

import java.util.concurrent.TimeUnit;

public class CaffeineCache {
    public static void main(String[] args) throws InterruptedException {
        Cache<Integer, String> cache = Caffeine.newBuilder()
                //设置缓存的初始容量为10
                .initialCapacity(10)
                // 设置缓存最大容量为100，超过100之后就会按照LRU最近最少使用算法来移除缓存
                .maximumSize(100)
                //设置写缓存后8秒钟过期
                .expireAfterWrite(8, TimeUnit.SECONDS)
                //设置要统计的缓存命中率
                .recordStats()
                //设置缓存移除通知
                .removalListener((Integer key, String value, RemovalCause cause) -> {
                    System.out.println("缓存删除了！！！！");
                })
                //build方法可以指定CacheLoader，在缓存不存在时通过CacheLoader的实现自动加载缓存
                .build();

        //cache.put(1 , "value");
        for (int i = 0; i < 20; i++) {
            String str = cache.get(1, key -> key + "value");
            System.out.println(str);
            //休眠一秒
            TimeUnit.SECONDS.sleep(1);
            if (i == 10) {
                cache.put(1, "value");
                System.out.println("---------------------");
                System.out.println(cache.getIfPresent(1));
                //删除缓存
                cache.invalidate(1);
                System.out.println("---------------------");
            }
        }

    }
}

Guava Cache

Guava Cache是Google开源发布的⼀个类似ConcurrentHashMap和ConcurrentSkipListMap的本地缓
存库，可以⾃动回收过期元素。

  • 优点：与Guava集成，单机⾼性能，⽀持过期、LRU/Cleanup机制。

使用示例：

package show.lmm;

import com.google.common.cache.CacheBuilder;
import com.google.common.cache.CacheLoader;
import com.google.common.cache.LoadingCache;
import com.google.common.cache.RemovalListener;

import java.util.ArrayList;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.TimeUnit;

public class GuavaCache {

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        LoadingCache<Integer, String> cache = CacheBuilder.newBuilder()
                //设置并发级别为8，并发级别是指可以同时写缓存的线程数
                .concurrencyLevel(8)
                //设置缓存的初始容量为10
                .initialCapacity(10)
                // 设置缓存最大容量为100，超过100之后就会按照LRU最近最少使用算法来移除缓存
                .maximumSize(100)
                //设置写缓存后8秒钟过期
                .expireAfterWrite(8, TimeUnit.SECONDS)
                //设置要统计的缓存命中率
                .recordStats()
                //设置缓存移除通知
                .removalListener((RemovalListener<Integer, String>) notification ->
                        System.out.println("----" + notification.getKey() + ":" + notification.getValue()))
                //build方法可以指定CacheLoader，在缓存不存在时通过CacheLoader的实现自动加载缓存
                .build(new CacheLoader<>() {
                    @Override
                    public String load(Integer s) {
                        System.out.println("load data:" + s);
                        String str = s + ":cache-value";
                        return str;
                    }
                });

        for (int i = 0; i < 20; i++) {
            String str = cache.get(1);
            System.out.println(str);
            //休眠一秒
            TimeUnit.SECONDS.sleep(1);
            if (i == 10) {
                System.out.println("---------------------");
                cache.invalidate(1);
                System.out.println("---------------------");
            }
        }

        //将某个key的缓存直接删除
        cache.invalidate(1);
        //将一批key的缓存直接删除
        cache.invalidateAll(new ArrayList<>());
        //删除所有缓存数据
        cache.invalidateAll();

        //打印缓存的命中率情况
        System.out.println("cache stats:" + cache.stats());
    }
}

Ehcache

Ehcache是⼀种功能丰富的开源缓存管理器，拥有分布式和本地缓存的强⼤功能。

  • 优点：⽀持分布式情景，可以通过配置⽂件进⾏优化和扩展。
  • 缺点：在单个JVM实例上运⾏时，并发读写性能较差；与Ehcache相⽐较复杂。

示例

https://gitee.com/luoye/examples/tree/main/cacheDemo

文章作者: Ming Ming Liu
文章链接: https://www.lmm.show/32/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Ming Ming Liu !
java 缓存 算法
  目录