caffeine源码分析——淘汰策略tinylfu
2018-09-20 本文已影响0人
黄云斌huangyunbin
guava的loading cache是使用lru的淘汰策略， 但是很多场景最近的数据不一定热，反而容易把稍旧的热数据挤出去，所以最好还是能统计访问次数得到数据的热度。
但是一般的统计方式都会比较耗性能，caffeine采取的tinylfu是做的非常好的，对性能影响很低，而且占用内存也很低。
让我们来看看具体的实现方式吧：
基本原理：对一个key我们会取他的hash值，找到对应位置，然后累加得到访问次数。
问题1：hash会冲突
解决：如果用hashmap的方式，相同的下标变成链表，这种方式会占用很大的内存，而且速度也不是很快。
其实一个hash函数会冲突是比较低的，我多搞4个hash函数，4个都冲突的概率就微乎其微了。取这4个hash函数对应值的最小的那个，基本就是访问次数了。
问题2：用4个hash函数会存访问次数，那空间就是4倍了。怎么优化呢
解决：访问次数超过15次其实是很热的数据了，没必要存太大的数字。所以我们用4位就可以存到15了。一个long有64位，可以存16个4位。
而且hash冲突的概念和数组的大小也正相关，一个long 是64位，除以4个hash，在除以4位，一个long对应的数组大小其实是容量的4倍了。进一步降低了冲突的概率。
image.png
增加访问次数的代码：4次hash都增加
image.png
image.png
得到访问次数的代码：4次hash中取最小的结果
image.png
