【.com原稿】2016年11月25日，由.com主办的WOT2016大数据技术峰会在北京JW万豪酒店举行。来自阿里巴巴、腾讯、百度、京东、小米等知名企业的50多位大数据领域资深技术专家齐聚大会现场，将与千余名一线人员交流分享经验IT技术人员在两天内。在WOT2016大数据技术峰会主会场，Hortonworks高级技术成员、HBase核心贡献者TedYu以《Tiny LFU ,a highly efficient cache admission policy》为主题进行了演讲。以下是他的演讲实录：数据的分布也会随着时间的演变而变化。比如一个用户走了，下周就不会很热了。所以要考虑的问题就是下面两个问题。当缓存已满时，必须将其删除。很多Cache的管理方案基本忽略了Admission。将EfficientPolicy与新数据进行比较，看看谁更适合它。如果新数据有较大的贡献，则将其放回Cache。如果最近访问比较频繁，希望放到缓存中，增加缓存的大小。能达到类似的效果吗？它的横轴单位是entry，也就是Cache能容纳多少个entry。Cache越大，Y轴就是看能从Cache中找到多少百分比。大家发现当Cache达到3700时，它的缓存率相当于最下面的两个紫色和蓝色。所以可见Cache的大小并不是Cache的决定因素。我们今天讨论的主要是基于访问频率。对于上面的几行TLFU和WLFU，对于一个entry来说，希望它的源数据占用的空间越小越好。看一下比较简单的WindowLFU。看这个滑动窗口，它是根据活动窗口的访问频率。有一个紫色框，代表一个条目。如果比这个WindowLFU更频繁，就会放到Cache中。这个滑动窗口可以去掉吗？这里的滑动窗口的期望值是10，第四个是黄色的，也就是多出来的那个。如果window不大于10，则继续将这个条目放入Cache中。这时候，不同的条目来了，嗯，窗口的实时条目已经满了。如果你找它的窗口，对每一个entry除以Coueters，3除以2就变成1，这样会损失一些精度。去掉滑动窗口是第一，其次是这些统计值不是用精确值，而是近似值。下面给出结果，大家会看到效果还是很不错的。在词条中，这个Counter也是可以共享的，这个共享是什么意思大家在下一篇专栏说的时候就知道了。在这种情况下，源数据占用的空间非常少，但会损失一些精度。简单的说就是这个精度每次一直除2除2，但是最大损失1。说最简单的，怎么判断有一个值，转化成一个值之后，看是不是在一个集合中。一种选择是散列，然后产生一个值。因此，为了减少Collisions，增加表的大小可能与我们讨论的减少源数据占用的空间相反。所以Bloomfitrs比较抽象，我们来看这个例子。假设我们的数据有11位，然后有K，也就是说H到K，在0到1的区间进行计算，在统计Bloomfitters的时候，就得联系Y和K来统计全部。这个Bloomfitter的功能比较有限，所以引入了一个CountingBloom，让每一个不只有0和1，可以更高。在做增量的时候，这些位对应的是分面的，也就是增量操作。第二个，操作就是做一个减量，比如第7个和第5个，对应的让它做一个自增。第三，做相应的估算，因为每个位置都可以打一个bit。这个是4，因为4是最小的。其中一项主要技术是CountingBloom。做自增的时候，不需要每隔第一位和第五位都加1，因为3是最小的，所以加1。但是这时候不能做减，因为只有一个人，而且我不知道该增加谁。第二个改进是让Counter变小一点。假设给一个W，我们粗略的用这个LogW，那么多比特的信息代表它，能不能做得更好？如果条目要留在柜台内，则整个柜台将有一个W/C。因此，对于每个计数器，13位数字就足够了，而不是14位数字。这个Counter也可以做得小一点，或者回到分布很不平衡的基本假设。在优酷或土豆上看视频，有的人看的人不多，比如看过几次、零次或一次，还有一些很火。所以对于那些只出现一次的，你必须先设置一个，SBF，和CountingBloom是一样的。先设置一个countingbloom，对于这些不太热的数据，希望在这里限制它的增量。如果在做增量的时候，每个位置对应1，那去二级SBF怎么样？所以这是这样一个两层结构。让我们看一个基于经验值的例子。假设有1000个entry，WindowLFU为9000，Alpha是0.9这样的访问频率。事实上，7239个项目全部出现在第一个项目中，只有416个项目可以进入SBF的第二层。所以平均而言，每个条目只需要1.22位，这需要非常少的空间来表示源数据。当然，其实每个入口最需要安排一个Counter，所以源数据需要多一点。刚才讲了四点，主要是去掉滑动窗口，用CountingBloom做一个近似。这张图是刚才出现的，所以我再说一点。WLFU不使用近似值。如您所见，紫色线和蓝色大线的效率最高。第一个是alpha等于0.9时，第二个是alpha等于0.7时。这个来自维基百科，因为可能疏疏不一样，但是表达的意思是一样的。所以我会快速回顾一下。对于IBM的工作来说，这个T1是最近访问的数据，绿色区域T2是访问比较频繁的区域，定位访问次数超过2次的item。所以T1+T2的大小是固定的，但是有一个指针在T2和T1之间滑动，需要在RU和RFU之间动态调整。规则是这样的，先在T1或T2找不到，再去B1，换个小鬼的样子，去B1或B2找就行了。如果在B1找到，那么RLU部分有倾斜，所以向右移动，如果在B2找到，那么就向左移动。另一个竞赛，叫做Lowinter-referenceRecencySet，它有一个门槛。第二个Forfreguentitems是最近的访问。下面你会看到一系列曲线，上面有红色三角形的是最上面的，这是理想值。可以看到已经接近60%了，横轴在item方面还是很大的。相对于红线听到的线是Lifs，可以看出两者具有可比性。上面的解是解法，下面第二个是WindowCachehitrate，都是不同的数据级别。在这张图中，绿线三角形是ARC，低于WindowLFU渗透率。我想谈谈这张照片。可以看到带网的红色带子正在采样。采样是我连接到另一边的地方。第一个图形窗口宽度为17,000项，第二个为9,000项。绿色的错误在第一张图中基本看不出来。绿色的是决策错误。判定错误是因为前面说的1.5变成了1，所以出现了判定错误。这个错误比较稳定，用绿色空间表示。还有待观察，蓝色斜杠代表的是近似误差，其实就是一种近似，而这种近似本身就存在误差。在这张图上看起来不太好，但是当使用1.25bitsperentry时，会出现近似误差。所以你可以看到蓝色部分出现在1.25。如果用大于1.25的数据表示，就没有这个数据。所以我想告诉大家，当每个entry使用1.25字节的时候，如果综合考虑二次采样误差、决策误差和逼近误差，效果是非常理想的。好，我们看看和HBase有什么关系？LruBlockCache，其访问量为4766387，攻击率为85.67%。【原创稿件，合作网站转载请注明原作者和出处为.com】
