一篇学会Caffeine W-TinyLFU源码分析

本文转载自微信公众号「肌肉码农」,作者肌肉码农。转载本文请联系肌肉码农公众号。

Caffeine使用一个ConcurrencyHashMap来保存所有数据,那它的过期淘汰策略采用什么方式与数据结构呢?其中写过期是使用writeOrderDeque,这个比较简单无需多说,而读过期相对复杂很多,使用W-TinyLFU的结构与算法。

网络上有很多文章介绍W-TinyLFU结构的,大家可以去查一下,这里主要是从源码来分析,总的来说它使用了三个双端队列:accessOrderEdenDeque,accessOrderProbationDeque,accessOrderProtectedDeque,使用双端队列的原因是支持LRU算法比较方便。

accessOrderEdenDeque属于eden区,缓存1%的数据,其余的99%缓存在main区。

accessOrderProbationDeque属于main区,缓存main内数据的20%,这部分是属于冷数据,即将补淘汰。

accessOrderProtectedDeque属于main区,缓存main内数据的80%,这部分是属于热数据,是整个缓存的主存区。

我们先看一下淘汰方法入口:

 
 
 
 
  1. void evictEntries() { 
  2.   if (!evicts()) { 
  3.     return; 
  4.   } 
  5.   //先从edn区淘汰 
  6.   int candidates = evictFromEden(); 
  7.   //eden淘汰后的数据进入main区,然后再从main区淘汰 
  8.   evictFromMain(candidates); 

accessOrderEdenDeque对应W-TinyLFU的W(window),这里保存的是最新写入数据的引用,它使用LRU淘汰,这里面的数据主要是应对突发流量的问题,淘汰后的数据进入accessOrderProbationDeque.代码如下:

 
 
 
 
  1. int evictFromEden() { 
  2.   int candidates = 0; 
  3.   Node node = accessOrderEdenDeque().peek(); 
  4.   while (edenWeightedSize() > edenMaximum()) { 
  5.     // The pending operations will adjust the size to reflect the correct weight 
  6.     if (node == null) { 
  7.       break; 
  8.     } 
  9.  
  10.     Node next = node.getNextInAccessOrder(); 
  11.     if (node.getWeight() != 0) { 
  12.       node.makeMainProbation(); 
  13.       //先从eden区移除 
  14.       accessOrderEdenDeque().remove(node); 
  15.       //移除的数据加入到main区的probation队列 
  16.       accessOrderProbationDeque().add(node); 
  17.       candidates++; 
  18.  
  19.       lazySetEdenWeightedSize(edenWeightedSize() - node.getPolicyWeight()); 
  20.     } 
  21.     node = next; 
  22.   } 
  23.  
  24.   return candidates; 

数据进入probation队列后,继续执行以下代码:

 
 
 
 
  1. void evictFromMain(int candidates) { 
  2.   int victimQueue = PROBATION; 
  3.   Node victim = accessOrderProbationDeque().peekFirst(); 
  4.   Node candidate = accessOrderProbationDeque().peekLast(); 
  5.   while (weightedSize() > maximum()) { 
  6.     // Stop trying to evict candidates and always prefer the victim 
  7.     if (candidates == 0) { 
  8.       candidate = null; 
  9.     } 
  10.  
  11.     // Try evicting from the protected and eden queues 
  12.     if ((candidate == null) && (victim == null)) { 
  13.       if (victimQueue == PROBATION) { 
  14.         victim = accessOrderProtectedDeque().peekFirst(); 
  15.         victimQueue = PROTECTED; 
  16.         continue; 
  17.       } else if (victimQueue == PROTECTED) { 
  18.         victim = accessOrderEdenDeque().peekFirst(); 
  19.         victimQueue = EDEN; 
  20.         continue; 
  21.       } 
  22.  
  23.       // The pending operations will adjust the size to reflect the correct weight 
  24.       break; 
  25.     } 
  26.  
  27.     // Skip over entries with zero weight 
  28.     if ((victim != null) && (victim.getPolicyWeight() == 0)) { 
  29.       victim = victim.getNextInAccessOrder(); 
  30.       continue; 
  31.     } else if ((candidate != null) && (candidate.getPolicyWeight() == 0)) { 
  32.       candidate = candidate.getPreviousInAccessOrder(); 
  33.       candidates--; 
  34.       continue; 
  35.     } 
  36.  
  37.     // Evict immediately if only one of the entries is present 
  38.     if (victim == null) { 
  39.       candidates--; 
  40.       Node evict = candidate; 
  41.       candidate = candidate.getPreviousInAccessOrder(); 
  42.       evictEntry(evict, RemovalCause.SIZE, 0L); 
  43.       continue; 
  44.     } else if (candidate == null) { 
  45.       Node evict = victim; 
  46.       victim = victim.getNextInAccessOrder(); 
  47.       evictEntry(evict, RemovalCause.SIZE, 0L); 
  48.       continue; 
  49.     } 
  50.  
  51.     // Evict immediately if an entry was collected 
  52.     K victimKey = victim.getKey(); 
  53.     K candidateKey = candidate.getKey(); 
  54.     if (victimKey == null) { 
  55.       Node evict = victim; 
  56.       victim = victim.getNextInAccessOrder(); 
  57.       evictEntry(evict, RemovalCause.COLLECTED, 0L); 
  58.       continue; 
  59.     } else if (candidateKey == null) { 
  60.       candidates--; 
  61.       Node evict = candidate; 
  62.       candidate = candidate.getPreviousInAccessOrder(); 
  63.       evictEntry(evict, RemovalCause.COLLECTED, 0L); 
  64.       continue; 
  65.     } 
  66.  
  67.     // Evict immediately if the candidate's weight exceeds the maximum 
  68.     if (candidate.getPolicyWeight() > maximum()) { 
  69.       candidates--; 
  70.       Node evict = candidate; 
  71.       candidate = candidate.getPreviousInAccessOrder(); 
  72.       evictEntry(evict, RemovalCause.SIZE, 0L); 
  73.       continue; 
  74.     } 
  75.  
  76.     // Evict the entry with the lowest frequency 
  77.     candidates--; 
  78.     //最核心算法在这里:从probation的头尾取出两个node进行比较频率,频率更小者将被remove 
  79.     if (admit(candidateKey, victimKey)) { 
  80.       Node evict = victim; 
  81.       victim = victim.getNextInAccessOrder(); 
  82.       evictEntry(evict, RemovalCause.SIZE, 0L); 
  83.       candidate = candidate.getPreviousInAccessOrder(); 
  84.     } else { 
  85.       Node evict = candidate; 
  86.       candidate = candidate.getPreviousInAccessOrder(); 
  87.       evictEntry(evict, RemovalCause.SIZE, 0L); 
  88.     } 
  89.   } 

上面的代码逻辑是从probation的头尾取出两个node进行比较频率,频率更小者将被remove,其中尾部元素就是上一部分从eden中淘汰出来的元素,如果将两步逻辑合并起来讲是这样的:在eden队列通过lru淘汰出来的”候选者“与probation队列通过lru淘汰出来的“被驱逐者“进行频率比较,失败者将被从cache中真正移除。下面看一下它的比较逻辑admit:

 
 
 
 
  1. boolean admit(K candidateKey, K victimKey) { 
  2.   int victimFreq = frequencySketch().frequency(victimKey); 
  3.   int candidateFreq = frequencySketch().frequency(candidateKey); 
  4.   //如果候选者的频率高就淘汰被驱逐者 
  5.   if (candidateFreq > victimFreq) { 
  6.     return true; 
  7.     //如果被驱逐者比候选者的频率高,并且候选者频率小于等于5则淘汰者 
  8.   } else if (candidateFreq <= 5) { 
  9.     // The maximum frequency is 15 and halved to 7 after a reset to age the history. An attack 
  10.     // exploits that a hot candidate is rejected in favor of a hot victim. The threshold of a warm 
  11.     // candidate reduces the number of random acceptances to minimize the impact on the hit rate. 
  12.     return false; 
  13.   } 
  14.   //随机淘汰 
  15.   int random = ThreadLocalRandom.current().nextInt(); 
  16.   return ((random & 127) == 0); 

从frequencySketch取出候选者与被驱逐者的频率,如果候选者的频率高就淘汰被驱逐者,如果被驱逐者比候选者的频率高,并且候选者频率小于等于5则淘汰者,如果前面两个条件都不满足则随机淘汰。

整个过程中你是不是发现protectedDeque并没有什么作用,那它是怎么作为主存区来保存大部分数据的呢?

 
 
 
 
  1. //onAccess方法触发该方法  
  2. void reorderProbation(Node node) { 
  3.   if (!accessOrderProbationDeque().contains(node)) { 
  4.     // Ignore stale accesses for an entry that is no longer present 
  5.     return; 
  6.   } else if (node.getPolicyWeight() > mainProtectedMaximum()) { 
  7.     return; 
  8.   } 
  9.  
  10.   long mainProtectedWeightedSize = mainProtectedWeightedSize() + node.getPolicyWeight(); 
  11.  //先从probation中移除 
  12.  accessOrderProbationDeque().remove(node); 
  13. //加入到protected中 
  14.   accessOrderProtectedDeque().add(node); 
  15.   node.makeMainProtected(); 
  16.  
  17.   long mainProtectedMaximum = mainProtectedMaximum(); 
  18. //从protected中移除 
  19.   while (mainProtectedWeightedSize > mainProtectedMaximum) { 
  20.     Node demoted = accessOrderProtectedDeque().pollFirst(); 
  21.     if (demoted == null) { 
  22.       break; 
  23.     } 
  24.     demoted.makeMainProbation(); 
  25.     //加入到probation中 
  26.     accessOrderProbationDeque().add(demoted); 
  27.     mainProtectedWeightedSize -= node.getPolicyWeight(); 
  28.   } 
  29.  
  30.   lazySetMainProtectedWeightedSize(mainProtectedWeightedSize); 

当数据被访问时并且该数据在probation中,这个数据就会移动到protected中去,同时通过lru从protected中淘汰一个数据进入到probation中。

这样数据流转的逻辑全部通了:新数据都会进入到eden中,通过lru淘汰到probation,并与probation中通过lru淘汰的数据进行使用频率pk,如果胜利了就继续留在probation中,如果失败了就会被直接淘汰,当这条数据被访问了,则移动到protected。当其它数据被访问了,则它可能会从protected中通过lru淘汰到probation中。

TinyLFU

传统LFU一般使用key-value形式来记录每个key的频率,优点是数据结构非常简单,并且能跟缓存本身的数据结构复用,增加一个属性记录频率就行了,它的缺点也比较明显就是频率这个属性会占用很大的空间,但如果改用压缩方式存储频率呢? 频率占用空间肯定可以减少,但会引出另外一个问题:怎么从压缩后的数据里获得对应key的频率呢?

TinyLFU的解决方案是类似位图的方法,将key取hash值获得它的位下标,然后用这个下标来找频率,但位图只有0、1两个值,那频率明显可能会非常大,这要怎么处理呢? 另外使用位图需要预占非常大的空间,这个问题怎么解决呢?

TinyLFU根据最大数据量设置生成一个long数组,然后将频率值保存在其中的四个long的4个bit位中(4个bit位不会大于15),取频率值时则取四个中的最小一个。

Caffeine认为频率大于15已经很高了,是属于热数据,所以它只需要4个bit位来保存,long有8个字节64位,这样可以保存16个频率。取hash值的后左移两位,然后加上hash四次,这样可以利用到16个中的13个,利用率挺高的,或许有更好的算法能将16个都利用到。

 
 
 
 
  1. public void increment(@Nonnull E e) { 
  2.     if (isNotInitialized()) { 
  3.       return; 
  4.     } 
  5.  
  6.     int hash = spread(e.hashCode()); 
  7.     int start = (hash & 3) << 2; 
  8.  
  9.     // Loop unrolling improves throughput by 5m ops/s 
  10.     int index0 = indexOf(hash, 0); //indexOf也是一种hash方法,不过会通过tableMask来限制范围 
  11.     int index1 = indexOf(hash, 1); 
  12.     int index2 = indexOf(hash, 2); 
  13.     int index3 = indexOf(hash, 3); 
  14.  
  15.     boolean added = incrementAt(index0, start); 
  16.     added |= incrementAt(index1, start + 1); 
  17.     added |= incrementAt(index2, start + 2); 
  18.     added |= incrementAt(index3, start + 3); 
  19.  
  20.     //当数据写入次数达到数据长度时就重置 
  21.     if (added && (++size == sampleSize)) { 
  22.       reset(); 
  23.     } 
  24.   } 

给对应位置的bit位四位的Int值加1:

 
 
 
 
  1. boolean incrementAt(int i, int j) { 
  2.   int offset = j << 2; 
  3.   long mask = (0xfL << offset); 
  4.   //当已达到15时,次数不再增加 
  5.   if ((table[i] & mask) != mask) { 
  6.     table[i] += (1L << offset); 
  7.     return true; 
  8.   } 
  9.   return false; 

获得值的方法也是通过四次hash来获得,然后取最小值:

 
 
 
 
  1. public int frequency(@Nonnull E e) { 
  2.   if (isNotInitialized()) { 
  3.     return 0; 
  4.   } 
  5.  
  6.   int hash = spread(e.hashCode()); 
  7.   int start = (hash & 3) << 2; 
  8.   int frequency = Integer.MAX_VALUE; 
  9.   //四次hash 
  10.   for (int i = 0; i < 4; i++) { 
  11.     int index = indexOf(hash, i); 
  12.     //获得bit位四位的Int值 
  13.     int count = (int) ((table[index] >>> ((start + i) << 2)) & 0xfL); 
  14.     //取最小值 
  15.     frequency = Math.min(frequency, count); 
  16.   } 
  17.   return frequency; 

当数据写入次数达到数据长度时就会将次数减半,一些冷数据在这个过程中将归0,这样会使hash冲突降低:

 
 
 
 
  1. void reset() { 
  2.   int count = 0; 
  3.   for (int i = 0; i < table.length; i++) { 
  4.     count += Long.bitCount(table[i] & ONE_MASK); 
  5.     table[i] = (table[i] >>> 1) & RESET_MASK; 
  6.   } 
  7.   size = (size >>> 1) - (count >>> 2); 

本文题目:一篇学会Caffeine W-TinyLFU源码分析
文章位置:http://www.shufengxianlan.com/qtweb/news42/446892.html

网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联