摘要：在静态的频率分布下，性能也落后于因为其不再为不在缓存中的数据维护任何频率数据。可以详见的准入淘汰策略是新增一个新的元素时，判断使用该元素替换一个旧元素，是否可以提升缓存命中率。
1. Introduction
LFU的局限：
LFU实现需要维护大而复杂的元数据（频次统计数据等）
大多数实际工作负载中，访问频率随着时间的推移而发生根本变化（这是外卖业务不适合朴素LFU的根本原因）
针对LFU的问题，已经存在了一些LFU的替代或优化方案，例如WLFU（Window LFU）：
老化机制
限制采样为：最后W次访问的有限大小窗口
在绝大多数情况下，新访问的数据总是被直接插入到缓存中，缓存方案仅设计驱逐策略，即，决定应该驱逐哪个数据。这是因为维护当前不在缓存中的对象的元数据被认为是不切实际的。
由于维护所有访问的频率数据消耗过大，很多LFU的实现只维护了缓存中数据的频率数据。对于前者，我们称为Perfect LFU（PLFU），后者则称为In-Memory LFU。由于WLFU（Window-LFU）优于In-Memery LFU（以更大的元数据为代价），所以论文在第一节只讨论了WLFU和PLFU。
LRU是一个很常见的用来替代LFU的算法，LRU的淘汰最近最少使用的元素。相较于LFU，LRU可能会有更加高效的实现，可以并自动适应突发的访问请求；然而基于LRU的缓存，在较大的负载下，需要更多的空间来保持和LFU一样的缓存命中率。
本文的贡献：
阐明了一种近似LFU准入策略的缓存结构/算法的有效性
提出了一种缓存结构，只有在准入策略认为将其替换进入缓存会提高缓存命中率的情况下，才会被插入
提出了一种空间利用率很高的新的数据结构——TinyLFU，可以在较大访问量的场景下近似的替代LFU的数据统计部分（meta-data）。
通过形式化的证明和模拟，证明了TinyLFU获得的Freq排序与真实的访问频率排序是几乎近似的
以优化的形式将TinyLFU实现在了Caffeine项目中：W-TinyLFU
与其他几种缓存管理策略进行了比较，包括ARC、LIRC
对于较为静态的访问分布，各种的缓存管理策略的差异是微不足道的，而对于偏倚较大的负载场景，TinyLFU体现出了较大的优势。即便是使用了TinyLFU准入策略进行优化的LRU也获得了较大的提升（LRU原生没有准入策略）。
2. Related Work 2.1 Cache ReplacementPLFU更加适合相对静态的访问分布，但不能很好的适应动态的访问频率分布。
In-Memory LFU仅维护已存在于缓存中的数据项的访问频率，并始终将最近访问的项插入缓存中，如果需要，逐出缓存中最不频繁访问的项。通常In-Memory LFU使用堆来管理缓存，并且由Anirban优化到了O(1)。然而即便有了这样的改进，但In-Memory LFU仍然对频率分布的变化显得反应迟缓。在静态的频率分布下，性能也落后于PLFU（因为其不再为【不在缓存中的数据】维护任何频率数据）。
Aging
是对In-Memory LFU的优化，提高了其对变化的响应能力。
增加了一个【最大平均引用计数】，当缓存中的数据引用计数平均值超过了该值，则将所有的数据的频率技术都进行减少。但是如何减少（一般是存在一个衰减因子）是一个棘手且tricky的问题。
WLFU
只保存一个时间窗口内的访问数据来统计频次，这个机制要求按照时序对访问进行持续的采样。对变化的调整是优于PLFU的。
ARC
LIRS
SLRU
2Q
LRU-K
GDSF
2.2 近似统计结构（Approximate Counting Architectures）简单说就是对全流量采样，TinyLFU需要一种近似的流量统计结构来替代全量Hash，减少内存的占用，并且要尽可能高效，且尽量保持精度。可以详见3.2
3. TinyLFU Architecture 3.1 TinyLFU OverviewTinyLFU的准入&淘汰策略是：新增一个新的元素时，判断使用该元素替换一个旧元素，是否可以提升缓存命中率。
上图为TinyLFU的主要结构，但是在阐述前需要强调我们面临的两个主要的挑战：
维护一个新鲜度机制（freshness mechanism），来保持历史最近访问且可以移除旧事件（keep the history recent and remove the history old events）
如何减少内存的消耗
3.2 Approximate Counting Overview
Minimal Increment Counting Bloom Filter Counting Bloom Filter参考链接
Minimal Increment CBF 和CBF 使用一个合适大小的计数器来代替了Bloom Filter中的bit
Minimal Increment CBF支持以下两个方法（下面的阐述，假设我们的场景是来为key计算k=3个hash value，来定位）
Estimate
例如，获取到3个hash位置上的计数值：{2, 2, 5}，取所有值中的最小值返回
Add
在元素到达后，获取到已有的3个计数值{2, 2, 5}，Add操作仅增加两个较小的计数值，来避免针对最大值的不必要的增加
3.3 Freshness MechanismTinyLFU使用reset机制来保证sketch中的数据尽可能最新。每增加一个新的元素到approximation sketches，会增加一个计数值，一旦计数值达到了一个预设的采样尺寸（W），就会将频率采样（CBF）维护的所有计数值除以2（可以使用高效的寄存器位移来实现）；论文也花了较大的篇幅来证明了这种Reset机制的正确性，且评估了其存在的截断错误（3会被reset为1，而非1.5），并且得出了以下结论：
reset在固定的频率分布下完全正确，且可以应对流量频率的变化（数学归纳法证明，感兴趣的可以参考原文3.3.1）
采样数W越大，截断错误的带来的影响越小
3.4 Space Reduction
在两个维度减少了空间的占用：
减小了sketch中计数值的尺寸
对于我们的采样大小W，我们的计数值需要占用log(W) bit
减少了sketch分的计数器的数量
Doorkeeper
引入了Doorkeeper机制，来避免为长尾流量分配计数器
由一个常规的Bloom Filter拦截在CBF之前
如果一个元素，在Doorkeeper中，则直接插入TinyLFU的主结构，否则先插入Doorkeeper；对于数据查询，会将Doorkeeper中的那一个计数值也加到计数值上去
reset操作会清空Doorkeeper
这样对于每个W周期内，都会过滤仅有一次的访问的数据
尽管Doorkeeper需要一些额外的空间，但是相对于在主要结构中节约的空间来说，显得微不足道。
3.5 TingLFU vs a Strwman略
3.6 Connecting TinyLFU to Caches对于LRU和随机缓存而言，缓存存储本质上是个黑盒。而TinyLFU不同，由于reset机制的存在，需要在reset时，同步更新缓存中的item；
4. Winwod TinyLFU（W-TinyLFU）主要是优化了“sparse bursts（突发的稀疏流量）”，新的突发流量可能会因为无法构建足够的频率数据来保证自己驻留在缓存中。
前端是一个小的LRU（window cache）；window cache淘汰后，会送到DoorKeeper过滤；过滤通过后，元素存储到一个大的Segmented LRU缓存里。Window LRU，它的容量只占据1%的总空间，它的目的就是用来存放短期突发访问记录。存放主要元素的Segmented LRU(SLRU)是一种LRU的改进，主要把在一个时间窗口内命中至少2次的记录和命中1次的多带带存放，这样就可以把短期内较频繁的缓存元素区分开来。具体做法上，SLRU包含2个固定尺寸的LRU，一个叫Probation段A1，一个叫Protection段A2。新记录总是插入到A1中，当A1的记录被再次访问，就把它移到A2，当A2满了需要驱逐记录时，会把驱逐记录插入到A1中。W-TinyLFU中，SLRU有80%空间被分配给A2段。
5. 实验略
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/62009.html
摘要：在静态的频率分布下，性能也落后于因为其不再为不在缓存中的数据维护任何频率数据。可以详见的准入淘汰策略是新增一个新的元素时，判断使用该元素替换一个旧元素，是否可以提升缓存命中率。 1. Introduction LFU的局限： LFU实现需要维护大而复杂的元数据（频次统计数据等） 大多数实际工作负载中，访问频率随着时间的推移而发生根本变化（这是外卖业务不适合朴素LFU的根本原因） 针...
摘要：鉴于大多数场景里不同数据项使用的都是固定的过期时长，采用了统一过期时间的方式。缓存能复用驱逐策略下的队列以及下面将要介绍的并发机制，让过期的数据项在缓存的维护阶段被抛弃掉。的设计实现来自于大量的洞见和许多贡献者的共同努力。 本文来自阿里集团客户体验事业群 简直同学的投稿，简直基于工作场景对于缓存做了一些研究，并翻译了一篇文章供同道中人学习。 原文：http://highscalabi...
摘要：近几年，深度学习高速发展，出现了大量的新模型与架构，以至于我们无法理清网络类型之间的关系。是由深度学习先驱等人提出的新一代神经网络形式，旨在修正反向传播机制。当多个预测一致时本论文使用动态路由使预测一致，更高级别的将变得活跃。 近几年，深度学习高速发展，出现了大量的新模型与架构，以至于我们无法理清网络类型之间的关系。在这篇文章中，香港科技大学（HKUST）助理教授金成勳总结了深度网络类型之间...
阅读 2836·2021-07-30 15:30
阅读 537·2019-08-30 15:55
阅读 1603·2019-08-26 17:04
阅读 614·2019-08-26 11:36
阅读 2033·2019-08-26 10:58
阅读 3531·2019-08-23 14:34
阅读 1496·2019-08-22 18:48
阅读 2496·2019-08-21 17:51
