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

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

[[177099]]

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

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

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

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

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

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

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

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

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

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

剛才講了四點，主要是去除滑動窗口，用Counting Bloom做一個近似。

這張圖剛才出現過，我再稍微多講一句。WLFU不用近似的。大家可以看到，這個紫色的線和大藍色的線它的***率是***的，***個是阿爾法等于0.9的時候，第二個阿爾法等于0.7的時候。這是維基百科的，因為它的稀疏可能不一樣，但是表示出來的含義是一樣的。所以我就快速過一下。

IBM的作品，這個T1是近期訪問的數據，綠色的區域T2就是更經常訪問的，訪問兩次以上的條目所在的區域。所以T1+T2的大小是一定的，但是有一個指針在這個T2和T1之間滑動，它是要動態的在RU和RFU之間進行調整。

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

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

這個圖表里看到綠線三角的是ARC，它是比Window LFU***率要差一些。這個圖要講一下，大家看到這個紅色代帶網子的是采樣，采樣就是我在這里和另一邊是掛鉤的。***個圖窗口寬度是一萬七千項，第二個是九千項。綠色在***張圖里面誤差基本上看不太出來了，綠色的是決斷誤差，決斷誤差是因為剛才提到1.5變成1了，所以這有一個決斷誤差。這誤差是相對來講比穩定，用了綠色空間來表示的。還有待藍色斜線是代表近似誤差，實際上是一個近似，這個近似本身就有一個誤差。這圖看不太出來，但是當每一個條目用1.25位的時候，會出現近似誤差。所以大家看到藍的部分是在1.25的地方出現，如果用比1.25更多的數據表示的話，不會有這個數據。

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

【51CTO原創稿件，合作站點轉載請注明原文作者和出處為51CTO.com】