Jvm内部缓存选型？一篇文章为你解答疑惑

另一种可行方案来自于数据库理论，通过提交日志的方式来扩展写的性能。写入操作先记入日志中，随后异步的批量执行，而不是立即写入到数据结构中。这种思想可以应用到缓存中，执行哈希表的操作，将操作记录到缓冲区，然后在合适的时机执行缓冲区中的内容。这个策略依然需要同步锁或者tryLock，不同的是把对锁的竞争转移到对缓冲区的追加写上。

在Caffeine中，有一组缓冲区被用来记录读写。一次访问首先会被因线程而异的哈希到stripped ring buffer上，当检测到竞争时，缓冲区会自动扩容。一个ring buffer容量满载后，会触发异步的执行操作，而后续的对该ring buffer的写入会被丢弃，直到这个ring buffer可被使用。虽然因为ring buffer容量满而无法被记录该访问，但缓存值依然会返回给调用方。这种策略信息的丢失不会带来大的影响，因为W-TinyLFU能识别出我们希望保存的热点数据。通过使用因线程而异的哈希算法替代在数据项的键上做哈希，缓存避免了瞬时的热点key的竞争问题。

写数据时，采用更传统的并发队列，每次变更会引起一次立即的执行。虽然数据的损失是不可接受的，但我们仍然有很多方法可以来优化写缓冲区。所有类型的缓冲区都被多个的线程写入，但却通过单个线程来执行。这种多生产者/单个消费者的模式允许了更简单、高效的算法来实现。

缓冲区和细粒度的写带来了单个数据项的操作乱序的竞态条件。插入、读取、更新、删除都可能被各种顺序的重放，如果这个策略控制的不合适，则可能引起悬垂索引。解决方案是通过状态机来定义单个数据项的生命周期。

在基准测试中，缓冲区随着哈希表的增长而增长，它的的使用相对更节省资源。读的性能随着CPU的核数线性增长，是哈希表吞吐量的33%。写入有10%的性能损耗，这是因为更新哈希表时的竞争是最主要的开销。

Caffeine

举个例子

Mysql的缓存池，内部实现是一个LRU，但是其内部有个中间点,指向倒数3/8，一半是old区，另一半是young区，新数据插入是直接插入young区，这样就保护了真正的老数据不会被冲刷掉。

多级队列的形式

LFU结合频率这一属性给予更好的预测缓存数据是否在未来被使用。

但是传统LFU有其局限性：

LFU实现需要维护大而复杂的元数据(频次统计数据等)

大多数实际工作负载中，访问频率随着时间的推移而发生根本变化，而传统LFU无法周期衰减频率

传统LFU的实现通过外接一个HashMap统计频率，但是HashMap存在Hash冲突，这会导致频率统计的不准确。

为了解决这些问题，Caffeine提出一种新的算法W-TinyLFU，它可以解决频率统计不准确以及访问频率衰减问题。这个方法让我们从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。

传统Hash存在Hash冲突的问题，使用LFU算法时候记录频率的话一旦发生hash冲突可能造成频率的统计错误。

W-TinyLFU算法使用一种Count-Min Sketch解决维护空间大的问题，类似布隆过滤器，降低冲突可能性，原理是多次hash分散开来，取最小值作为频率，一次Hash冲突的几率是1%的话，4次Hash的几率就是1%的4次方，大大降低的冲突可能性。

在Caffeine中为了实现Count-Min Sketch它在其中村政府，存放四个算法

其中randomSeed是一个随机数，sampleSize=开始设置的缓存最大树*10;table= 最大缓存数最接近的2的次方数(100的话是128，50是64);tableMask = table.length-1;size=0

在向缓存put数据的时候会调用

这个AddTask是一个Runnable，其中run方法会调用increment方法。

Caffeine比guava好在哪

W-TinyLFU

传统的LFU受时间周期的影响比较大。所以各种LFU的变种出现了，基于时间周期进行衰减，或者在最近某个时间段内的频率。同样的LFU也会使用额外空间记录每一个数据访问的频率，即使数据没有在缓存中也需要记录，所以需要维护的额外空间很大。

可以试想我们对这个维护空间建立一个hashMap，每个数据项都会存在这个hashMap中，当数据量特别大的时候，这个hashMap也会特别大。

再回到LRU，我们的LRU也不是那么一无是处，LRU可以很好的应对突发流量的情况，因为他不需要累计数据频率。

所以W-TinyLFU结合了LRU和LFU，以及其他的算法的一些特点。

频率记录

首先要说到的就是频率记录的问题，我们要实现的目标是利用有限的空间可以记录随时间变化的访问频率。在W-TinyLFU中使用Count-Min Sketch记录我们的访问频率，而这个也是布隆过滤器的一种变种。

如果需要记录一个值，那我们需要通过多种Hash算法对其进行处理hash，然后在对应的hash算法的记录中+1，为什么需要多种hash算法呢?由于这是一个压缩算法必定会出现冲突，比如我们建立一个Long的数组，通过计算出每个数据的hash的位置。比如张三和李四，他们两有可能hash值都是相同，比如都是1那Long[1]这个位置就会增加相应的频率，张三访问1万次，李四访问1次那Long[1]这个位置就是1万零1，如果取李四的访问评率的时候就会取出是1万零1，但是李四命名只访问了1次啊，为了解决这个问题，所以用了多个hash算法可以理解为long[][]二维数组的一个概念，比如在第一个算法张三和李四冲突了，但是在第二个，第三个中很大的概率不冲突，比如一个算法大概有1%的概率冲突，那四个算法一起冲突的概率是1%的四次方。通过这个模式我们取李四的访问率的时候取所有算法中，李四访问最低频率的次数。所以他的名字叫Count-Min Sketch。

这里和以前的做个对比，简单的举个例子:如果一个hashMap来记录这个频率，如果我有100个数据，那这个HashMap就得存储100个这个数据的访问频率。哪怕我这个缓存的容量是1，因为Lfu的规则我必须全部记录这个100个数据的访问频率。如果有更多的数据我就有记录更多的。

在Count-Min Sketch中，我这里直接说caffeine中的实现吧(在FrequencySketch这个类中),如果你的缓存大小是100，他会生成一个long数组大小是和100最接近的2的幂的数，也就是128。而这个数组将会记录我们的访问频率。在caffeine中规定频率最大为15，15的二进制位1111，总共是4位，而Long型是64位。所以每个Long型可以放16种算法，但是caffeine并没有这么做，只用了四种hash算法，每个Long型被分为四段，每段里面保存的是四个算法的频率。这样做的好处是可以进一步减少Hash冲突，原先128大小的hash，就变成了128X4。

一个Long的结构如下:

（编辑：南平站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!