【51CTO.com原創(chuàng)稿件】2016年11月25日，由51CTO.com主辦的WOT2016大數(shù)據(jù)技術(shù)峰會(huì)在北京粵財(cái)JW萬豪酒店召開，50多位來自阿里、騰訊、百度、京東、小米等知名企業(yè)的大數(shù)據(jù)領(lǐng)域資深技術(shù)專家齊聚大會(huì)現(xiàn)場，將在兩天的時(shí)間里與逾千名一線IT技術(shù)人員直面交流，分享經(jīng)驗(yàn)。

在WOT2016大數(shù)據(jù)技術(shù)峰會(huì)的主會(huì)場，Hortonworks 高級技術(shù)成員、 HBase核心貢獻(xiàn)者 Ted Yu帶來了主題為《Tiny LFU ,a highly efficient cache admission policy》的演講。以下是他的演講實(shí)錄：

[[177099]]

數(shù)據(jù)的分布隨著時(shí)間的演變也是會(huì)變的，比如一個(gè)用戶走了，下周就不怎么熱了。所以考慮的問題是這樣兩個(gè)問題，當(dāng)Cache滿的時(shí)候，就要去除出去。很多對于Cache的管理方案，基本上忽略了Admission。Efficient Policy和新的數(shù)據(jù)進(jìn)行比較，看誰更適合在這上面。如果新的數(shù)據(jù)有更大的貢獻(xiàn)，再把它放回Cache里面。

如果最近它更被頻繁訪問，就希望把它放在Cache里面，增加Cache的尺寸，能不能達(dá)到類似的效果呢？它的橫軸單位是條目，就是Cache能放多少條目。越往后Cache越大，Y軸是看看有百分之多少能夠從Cache找到。大家發(fā)現(xiàn)當(dāng)Cache達(dá)到3700條的時(shí)候，它的***率才相當(dāng)于最下頭兩個(gè)紫色和藍(lán)色的。所以看出來Cache的大小不是Cache的決定因素。

我們今天討論的主要是基于訪問頻度的，上面這幾條線，TLFU和WLFU，對于一個(gè)條目，希望它的源數(shù)據(jù)占的空間越少越好?？匆幌卤容^單純的這個(gè)Window LFU。看一下這個(gè)滑動(dòng)窗口，這是基于活動(dòng)窗口的訪問頻度，來了一個(gè)紫色的框，代表著一個(gè)條目，如果它比這個(gè)WindowLFU更頻繁的的話，就把它放在Cache。 

能不能把這個(gè)滑動(dòng)窗口去掉？滑動(dòng)窗口在這里面它的期值是10，這里面第4個(gè)就是黃的那個(gè)，是多的一個(gè)。如果這個(gè)窗口沒有大10的時(shí)候，繼續(xù)把這條目繼續(xù)在Cache里面放。這時(shí)候來了不同的條目，好了，窗口這個(gè)實(shí)時(shí)條目已經(jīng)滿了。如果去找它的窗口的話，把對于每一個(gè)條目的Coueters除以，它3除以2變成1了，這就要丟失一些精度。

去掉滑動(dòng)窗口是***個(gè)，第二個(gè)就是這些統(tǒng)計(jì)值不用精確值，而是用近似值來表示。下面呈現(xiàn)結(jié)果大家會(huì)看到，效果還是非常不錯(cuò)的。在條目之中，這個(gè)Counter也可以共享，在下一列講到大家就會(huì)知道這個(gè)共享是什么意思。這樣的話，對源數(shù)據(jù)耗用的空間就非常少，代價(jià)就是損失了一部分精度。簡單來講，這個(gè)精度它每次都不停的做除以2除以2，但是***損失是1。

講最簡單的，怎么判斷有一個(gè)值，把它轉(zhuǎn)換成數(shù)值以后，看它是不是在一個(gè)集合里面。有一個(gè)選擇就是哈希，哈希以后就會(huì)得到一個(gè)值。所以為了減少Collisions，把這個(gè)表增大，可能和我們現(xiàn)在討論的減少源數(shù)據(jù)的占用空間是相反的。

所以Bloom fiters更抽象化，來看一下這個(gè)例子。假設(shè)我們這個(gè)數(shù)據(jù)有11位，然后有K，就是說H到K，從0到1的區(qū)間里面去進(jìn)行運(yùn)算。算Bloom fiters的時(shí)候，要聯(lián)系到Y(jié)，聯(lián)系到K，都去算一遍。 這個(gè)Bloom fiters它的功能還是比較有限的，因此就要引入一個(gè)Counting Bloom，這樣每一個(gè)上有不光是0和1了，可以更高。做增量的時(shí)候，把這些位相應(yīng)的都去做分面，這是一個(gè)增量操作。第二個(gè)，操作是做減量，比如第7位和第5位，相應(yīng)把它做一個(gè)增量。第三個(gè)，做一個(gè)相應(yīng)的估計(jì)值，因?yàn)槊總€(gè)位置上可以打一位。這個(gè)里面是4，因?yàn)?最小。

主要技巧之一，就是Counting Bloom。做增量的時(shí)候，不是把每一位***位和第五位都去做增1，因?yàn)?最小，所以把它做增1。但是這個(gè)時(shí)候不能做減量，因?yàn)橹挥幸晃?，不知道給誰做增量。第二改進(jìn)，是把這個(gè)Counter變得更小一點(diǎn)。假設(shè)給定一個(gè)W的話，我們大致要用到的LogW，這么多位的信息表示它，可不可以做得更好呢？如果一個(gè)條目要在Counter里面待下去的話，整個(gè)對于Counter出現(xiàn)了一個(gè)W/C。所以每一個(gè)Counter，出現(xiàn)13位就可以了，而不需要14位。

這個(gè)Counter還可以變得更小，還是回到基本假設(shè)，分布是非常不均衡的?？磧?yōu)酷或者土豆的視頻，有的沒有什么人看，比如是看了很少次，零次或者一次，有的很熱。所以呢，對于這些只出現(xiàn)一次的，就要先設(shè)一個(gè)，這里面寫的是SBF，這個(gè)和Counting Bloom是一樣的。先設(shè)一位的Counting Bloom，對于這些不太熱的數(shù)據(jù)，希望把它的增量限制在這里。

如果在做增量的時(shí)候，每一個(gè)位置上所對應(yīng)的都是1，到第二級的SBF里面怎么樣？所以這就是兩級的這樣一個(gè)結(jié)構(gòu)。還是看一個(gè)例子，這是根據(jù)經(jīng)驗(yàn)值推出來的，假設(shè)有一千個(gè)條目，Window  LFU是九千個(gè)，阿爾法是0.9這樣一個(gè)訪問頻率。實(shí)際上7239項(xiàng)都是出現(xiàn)在***項(xiàng)里面，只有416項(xiàng)能夠進(jìn)入到第二級的SBF。所以從整體上平均考量的話，每一個(gè)條目只需要1.22位，這只需要非常少的空間來表示源數(shù)據(jù)就可以了。 當(dāng)然實(shí)際上每個(gè)條目最需要布置一個(gè)Counter，所以源數(shù)據(jù)要更多一點(diǎn)。

剛才講了四點(diǎn)，主要是去除滑動(dòng)窗口，用Counting Bloom做一個(gè)近似。

這張圖剛才出現(xiàn)過，我再稍微多講一句。WLFU不用近似的。大家可以看到，這個(gè)紫色的線和大藍(lán)色的線它的***率是***的，***個(gè)是阿爾法等于0.9的時(shí)候，第二個(gè)阿爾法等于0.7的時(shí)候。這是維基百科的，因?yàn)樗南∈杩赡懿灰粯?，但是表示出來的含義是一樣的。所以我就快速過一下。

IBM的作品，這個(gè)T1是近期訪問的數(shù)據(jù)，綠色的區(qū)域T2就是更經(jīng)常訪問的，訪問兩次以上的條目所在的區(qū)域。所以T1+T2的大小是一定的，但是有一個(gè)指針在這個(gè)T2和T1之間滑動(dòng)，它是要?jiǎng)討B(tài)的在RU和RFU之間進(jìn)行調(diào)整。

規(guī)則是這樣的，首先在T1和T2中都沒有找到，然后就去B1，換了小的幽靈的樣子，就是要去B1或者B2里面去找一下。如果在B1里找到了，所以就要對這個(gè)RLU部分有一個(gè)傾斜，所以就往右移，如果在B2找到了，那么就往左移。

另外一個(gè)競爭的，叫做Low inter-reference Recency Set ，它有一個(gè)閾值。第二個(gè)For freguent items是近期訪問的。下面會(huì)看到一系列的曲線，紅色帶一個(gè)三角的，就是最上面的這個(gè)，就是理想值。大家可以看到它接近60%，橫軸還是以條目計(jì)的大。在紅線的相對聽的這條線是Lifs，大家看到這兩者是不相上下的。最上面一條***解，下面第二個(gè)就是Window Cache hit rate，這個(gè)都是不同的數(shù)據(jù)級。

這個(gè)圖表里看到綠線三角的是ARC，它是比Window LFU***率要差一些。這個(gè)圖要講一下，大家看到這個(gè)紅色代帶網(wǎng)子的是采樣，采樣就是我在這里和另一邊是掛鉤的。***個(gè)圖窗口寬度是一萬七千項(xiàng)，第二個(gè)是九千項(xiàng)。綠色在***張圖里面誤差基本上看不太出來了，綠色的是決斷誤差，決斷誤差是因?yàn)閯偛盘岬?.5變成1了，所以這有一個(gè)決斷誤差。這誤差是相對來講比穩(wěn)定，用了綠色空間來表示的。還有待藍(lán)色斜線是代表近似誤差，實(shí)際上是一個(gè)近似，這個(gè)近似本身就有一個(gè)誤差。這圖看不太出來，但是當(dāng)每一個(gè)條目用1.25位的時(shí)候，會(huì)出現(xiàn)近似誤差。所以大家看到藍(lán)的部分是在1.25的地方出現(xiàn)，如果用比1.25更多的數(shù)據(jù)表示的話，不會(huì)有這個(gè)數(shù)據(jù)。

所以就是告訴大家，當(dāng)每一個(gè)條目采用1.25字節(jié)的時(shí)候，綜合考慮第二個(gè)采樣誤差、決斷誤差和近似誤差的話，這個(gè)效果是非常理想的。好，看一下和HBase什么關(guān)系？LruBlockCache，它的訪問量是4766387，它的***率是85.67%。

【51CTO原創(chuàng)稿件，合作站點(diǎn)轉(zhuǎn)載請注明原文作者和出處為51CTO.com】