C/C++教程

Caffeine学习

本文主要是介绍Caffeine学习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

概述

网上都说 Caffeine 比 guava 更好,具体原因是啥呢?接下来就进行详细阐述。
一般本地缓存由于内存有限,需要特别注意淘汰策略,那涉及到淘汰的话就需要非常关注GC问题,还有缓存污染问题,本地缓存非常容易导致数据不一致。

具体优化点

驱逐策略 - 超过缓存容量需要被淘汰

guava的淘汰策略主要是 LRU, LRU认为新数据一般都是访问频率最大的,这种淘汰机制非常容易误杀,把一些真正的热点数据淘汰掉。
因此现代缓存扩展了对历史数据的使用,结合就近程度(recency)和访问频次(frequency)来更好的预测数据。
其中一种保留历史信息的方式是使用popularity sketch(一种压缩、概率性的数据结构)来从一大堆访问事件中定位频繁的访问者。
可以参考CountMin Sketch算法,它由计数矩阵和多个哈希方法实现。发生一次读取时,矩阵中每行对应的计数器增加计数,估算频率时,取数据对应是所有行中计数的最小值。
这个方法让我们从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做权衡。

Window TinyLFU(W-TinyLFU)算法将sketch作为过滤器,当新来的数据比要驱逐的数据高频时,这个数据才会被缓存接纳。
这个许可窗口给予每个数据项积累热度的机会,而不是立即过滤掉。这避免了持续的未命中,特别是在突然流量暴涨的的场景中,一些短暂的重复流量就不会被长期保留。
为了刷新历史数据,一个时间衰减进程被周期性或增量的执行,给所有计数器减半。

对于长期保留的数据,W-TinyLFU使用了分段LRU(Segmented LRU,缩写SLRU)策略。
起初,一个数据项存储被存储在试用段(probationary segment)中,在后续被访问到时,它会被提升到保护段(protected segment)中(保护段占总容量的80%)。
保护段满后,有的数据会被淘汰回试用段,这也可能级联的触发试用段的淘汰。这套机制确保了访问间隔小的热数据被保存下来,而被重复访问少的冷数据则被回收。

过期策略 - KEY过期了

过期的实现里,往往每个数据项拥有不同的过期时间。
因为容量的限制,过期后数据需要被淘汰,否则这些已过期的脏数据会污染到整个缓存。
一般缓存中会启用专有的清扫线程周期性的遍历清理缓存。
这个策略相比在每次读写操作时按照过期时间排序的优先队列来清理过期缓存要好,因为后台线程隐藏了的过期数据清除的时间开销。

鉴于大多数场景里不同数据项使用的都是固定的过期时长,Caffien采用了统一过期时间的方式。
这个限制让用O(1)的有序队列组织数据成为可能。针对数据的写后过期,维护了一个写入顺序队列,针对读后过期,维护了一个读取顺序队列。
缓存能复用驱逐策略下的队列以及下面将要介绍的并发机制,让过期的数据项在缓存的维护阶段被抛弃掉。

并发

并发的缓存读取可以采取分段锁进行优化。但是热点数据所持有的的锁会更常持有。
另一种可行方案来自于数据库理论,通过提交日志的方式来扩展写的性能。
写入操作先记入日志中,随后异步的批量执行,而不是立即写入到数据结构中。
这种思想可以应用到缓存中,执行哈希表的操作,将操作记录到缓冲区,然后在合适的时机执行缓冲区中的内容。

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

写数据时,采用更传统的并发队列,每次变更会引起一次立即的执行。
虽然数据的损失是不可接受的,但我们仍然有很多方法可以来优化写缓冲区。
所有类型的缓冲区都被多个的线程写入,但却通过单个线程来执行。这种多生产者/单个消费者的模式允许了更简单、高效的算法来实现。
缓冲区和细粒度的写带来了单个数据项的操作乱序的竞态条件。
插入、读取、更新、删除都可能被各种顺序的重放,如果这个策略控制的不合适,则可能引起悬垂索引。解决方案是通过状态机来定义单个数据项的生命周期。

这篇关于Caffeine学习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!