一篇学会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.   
  
  
  
  2.   if (!evicts()) { 
    3.   
  
  
  
  3.     return; 
    4.   
  
  
  
  4.   } 
    5.   
  
  
  
  5.   //先从edn区淘汰 
    6.   
  
  
  
  6.   int candidates = evictFromEden(); 
    7.   
  
  
  
  7.   //eden淘汰后的数据进入main区，然后再从main区淘汰 
    8.   
  
  
  
  8.   evictFromMain(candidates); 
    9.   
  
  
  
  9. } 
    10.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

广告

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

猜你还喜欢下面的内容

网站设计公司知识

分类信息网

成都网站优化　　 　重庆电商网站建设　　 　网站维护报价　　 　成都网页制作　　 　重庆建站　　 　app开发公司　　 　成都400电话　　 　网站排名优化　　 　SSL证书　　 　网站改版　　 　化妆品企业网站建设方案　　 　成都定制网站建设　　 　成都电信服务器托管　　 　自贡服务器托管　　 　域名注册　　 　创新互联重庆　　 　成都光华电信机房　　 　做网站　　 　石膏隔墙　　 　绵阳机房托管