本文转载自微信公众号《肌肉码农》，作者肌肉码农。转载本文请联系肌农公众号。Caffeine使用一个ConcurrencyHashMap来保存所有的数据，那么它的过期淘汰策略是采用什么方法和数据结构呢？WriteOrderDeque是写expiration用的，比较简单不用多说，但是读expiration就比较复杂，用的是W-TinyLFU的结构加上算法。网上有很多文章介绍W-TinyLFU结构。你可以检查一下。这里主要从源码上分析。一般来说，它使用三个双端队列：accessOrderEdenDeque、accessOrderProbationDeque、accessOrderProbationDeque，使用双端队列的原因是支持LRU算法更方便。accessOrderEdenDeque属于eden区，缓存1%的数据，剩下的99%缓存在main区。accessOrderProbationDeque属于主区，缓存了主区20%的数据。这部分是冷数据，很快就会被淘汰。accessOrderProtectedDeque属于主区，缓存了主区80%的数据。这部分属于热点数据，是整个缓存的主要存储区域。先看一下淘汰方法的入口：voidevictEntries(){if(!evicts()){return;}//先从edn区淘汰int候选=evictFromEden();//淘汰后的数据eden的进入主区，然后从主区淘汰evictFromMain(candidates);}accessOrderEdenDeque对应W-TinyLFU的W(window)，里面保存了最新写入数据的引用，使用LRU淘汰，以及这里的数据主要是为了应对突发流量的问题。最终数据进入accessOrderProbationDeque。代码如下：sincereFromEden(){intcandidates=0;Nodenode=accessOrderEdenDeque().peek();while(edenWeightedSize()>edenMaximum()){//待处理的操作会调整thesize来反映正确的weightif(node==null){break;}Nodenext=node.getNextInAccessOrder();if(node.getWeight()!=0){node.makeMainProbation();//先从eden区移除accessOrderEdenDeque().remove(node);//移除的数据加入到主区的probation队列中}数据进入probation队列后，继续执行如下代码：candidate=accessOrderProbationDeque().peekLast();while(weightedSize()>maximum()){//Stoptryingtoevictcandidatesandalwayspreferthevictimif(candidates==0){candidate=null;}//尝试从受保护和登入队列中退出if((candidate==null)&&(victim==null)){if(victimQueue==PROBATION){victim=accessOrderProtectedDeque().peekFirst();victimQueue=PROTECTED;continue;}elseif(victimQueue==PROTECTED){victim=accessOrderEdenDeque().peekFirst();victimQueue=EDEN;continue;}//待处理的操作将调整thesizetoreflectthecorrectweightbreak;}//Skipoverentrieswithzerowightif((victim!=null)&&(victim.getPolicyWeight()==0)){victim=victim.getNextInAccessOrder();continue;}elseif((candidate!=null)&&(candidate.getPolicyWeight()==0)){candidate=candidate.getPreviousInAccessOrder();candidates--;continue;}//Evictimmediatelyifonlyoneoftheentriesispresentif(victim==null){candidates--;Nodeevict=candidate;candidate=candidate.getPreviousInAccessOrder();evictEntry(evict,RemovalCause.SIZE,0L);continue;}elseif(candidate==null){Nodeevict=victim;victim=victim.getNextInAccessOrder();evictEntry(evict,RemovalCause.SIZE,0L);continue;}//EvictimmediatelyifanentrywascollectedKvictimKey=victim.getKey();KcandidateKey=candidate.getKey();if(victimKey==null){Nodeevict=victim;victim=victim.getNextInAccessOrder();evictEntry(evict,RemovalCause.COLLECTED,0L);continue;}elseif(candidateKey==null){candidates--;Nodeevict=candidate;candidate=candidate.getPreviousInAccessOrder();evictEntry(evict,RemovalCause.COLLECTED,0L);continue;}//Evictimmediatelyifthecandidate'sweightexceedsthemaximumif(candidate.getPolicyWeight()>maximum()){candidates--;Nodeevict=candidate;candidate=candidate.getPreviousInAccessOrder();evictEntry(evict,RemovalCause.SIZE,0L);continue;}//Evicttheentrywiththelowestfrequencycandidates--;//最核心算法在这里：从probation的头尾取出两个节点进行比频率，频率更小者将被removeif(admit(candidateKey,victimKey)){Nodeevict=victim;victim=victim.getNextInAccessOrder();evictEntry(evict,RemovalCause.SIZE,0L);candidate=candidate.getPreviousInAccessOrder();}else{Nodeevict=candidate;candidate=candidate.getPreviousInAccessOrder();evictEntry(evict,RemovalCause.SIZE,0L);}}}上面的代码逻辑是从probation的头尾取出两个节点到比较frequency，frequency小的会被剔除，尾元素就是上一节从eden中剔除的元素。如果将两步逻辑结合起来，看起来是这样的：将eden队列中被lru淘汰的“候选人”和probation队列中通过lru淘汰的“被驱逐者”的频率进行比较，失败者会被实际移除缓存我们看一下它的比较逻辑将淘汰并开除Candidateif(candidateFreq>victimFreq){returntrue;//如果被驱逐者的频率高于候选人的频率，且候选人的频率小于或等于5，则候选人将被淘汰elseified}elseif(candidateFreq<=5){//最大频率为15减半后设置为7老化history.Anattack//exploitsthatahotcandidateisrejectedinfavorofahotvict.Thethresholdofawarm//candidatereducesthenumberofrandomacceptancestominimizetheimpactonthehitrate.returnfalse;}//随机淘汰intrarandom=ThreadLocalRandom.current().nextInt();return((random&127)==0);}从frequencySketch中取出candidates和deportees的频率，如果是candidate如果是candidate的频率高，驱逐者将被淘汰。如果被驱逐者的频率高于候选人的频率，而候选人的频率小于或等于5，则被驱逐者被淘汰。如果不满足前两个条件，被驱逐者将被随机淘汰。整个过程中有没有发现protectedDeque没有作用，那么它是如何作为主存储区保存大部分数据的呢？//onAccess方法触发此方法;}longmainProtectedWeightedSize=mainProtectedWeightedSize()+node.getPolicyWeightMovefrom();//先除accessOrderProbationDeque().remove(node);//加入受保护的accessOrderProtectedDeque().add(node);node.makeMainProtected();longmainProtectedMaximum=mainProtectedMaximum();//解除保护while(mainProtectedWeightedSize>mainProtectedMaximum){Nodedemoted=accessOrderProbationDeque().pollFirst();if(demoted==null){break;}demoted.makeMainProbation();//添加到probationaccessOrderProbationDeque().add(demoted);mainProtectedWeightedSize-=node.getPolicyWeight();}lazySetMainProtectedWeightedSize(mainProtectedWeightedSize);}当数据被访问且数据处于probation状态时，会将数据移至protected，并同时romp通过lru在protected淘汰一条数据，进入probation，这样数据流的逻辑就很清楚了：新数据进入eden，通过lru淘汰进入probation，probation中通过lru淘汰的数据使用频率pk，如果胜出继续留probation，如果失败，直接淘汰，当这块数据被访问的时候，会移到protected。当访问其他数据时，可能会通过lru将其从protected淘汰为probation。TinyLFUTraditionalLFU一般采用key-value的形式记录每个key出现的频率。优点是数据结构非常简单，可以和缓存本身的数据结构复用。添加一个属性来记录频率就足够了。它的缺点也很明显。frequency属性会占用很大的空间，但是如果使用压缩的方式存储频率呢？频率占用的空间肯定可以减少，但是会引出另一个问题：如何从压缩后的数据中得到key对应的频率？TinyLFU的解决方案是类似于位图的方法。取key的hash值得到它的位下标，然后用这个下标求频率，但是位图只有0和1两个值，所以频率显然可能很大。如何处理？另外，位图的使用需要占用非常大的空间。如何解决这个问题呢？TinyLFU根据最大数据量设置生成一个long数组，然后将频率值保存在四个long中的4位中（4位不会大于15），取频率值时，取其中最小的一个四个。Caffeine认为大于15的频率已经很高了，属于热数据，所以只需要4位来保存，而long有8字节64位，可以保存16个频率。取hash值后，向左移动两处，然后四次加hash，这样16个中的13个就可以用了，利用率还是挺高的。也许有更好的算法可以使用所有16个。publicvoidincrement(@NonnullEe){if(isNotInitialized()){return;}inthash=spread(e.hashCode());intstart=(hash&3)<<2;//Loopunrollingimprovethroughputby5mops/sintindex0=indexOf(hash,0);//indexOf也是hash方法，但是会通过tableMask限制范围intindex1=indexOf(hash,1);intindex2=indexOf(hash,2);intindex3=indexOf(hash,3);booleanadded=incrementAt(index0,start);added|=incrementAt(index1,start+1);added|=incrementAt(index2,start+2);added|=incrementAt(index3,start+3);//当数据写入次数达到datalength，会重启Setif(added&&(++size==sampleSize)){reset();}}对相应位置的位的四位Int值加1：booleanincrementAt(inti,intj){intoffset=j<<2;longmask=(0xfL<>>((start+i)<<2))&0xfL);//取最小值frequency=Math.min(frequency,count);}returnfrequency;}当数据写入次数达到数据长度时，数量减半，在此过程中部分冷数据会归0，减少hash冲突：voidreset(){intcount=0;for(inti=0;i>>1)&RESET_MASK;}size=(尺寸>>>1)-(计数>>>2);}
