簡介

前置知識

知道什么是緩存

聽完本節(jié)公開課，你可以收獲

• 掌握樸素LRU、LFU算法的思想以及源碼
• 掌握一種流式計數(shù)的算法 Count-Min Sketch
• 手撕TinyLFU算法、分析Window-TinyLFU源碼

一、LRU和LFU算法

LRU算法

LRU Least Recently Used 最近最少使用算法

LRU 算法的思想是如果一個數(shù)據(jù)在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。所以，當(dāng)指定的空間已存滿數(shù)據(jù)時，應(yīng)當(dāng)把最久沒有被訪問到的數(shù)據(jù)淘汰。

也就是淘汰數(shù)據(jù)的時候，只看數(shù)據(jù)在緩存里面待的時間長短這個維度。

這樣子做有什么缺點呢？我們來看個例子

無法復(fù)制加載中的內(nèi)容

按照LRU算法進(jìn)行訪問和數(shù)據(jù)淘汰，10次訪問的結(jié)果如下圖所示

無法復(fù)制加載中的內(nèi)容

10次訪問結(jié)束后，緩存中剩下的數(shù)據(jù)是b、c、d三個元素，這個顯然不太合理。

直觀上講，為什么說他不合理，是因為明明a是被頻繁訪問的數(shù)據(jù)，最終卻被淘汰掉了。所以如果要改進(jìn)這個算法，我們希望的是能夠記錄每個元素的訪問頻率信息，訪問頻率最低的那個才是最應(yīng)該被淘汰的那個。

恭喜你，這就是LFU的規(guī)則。

在開始LFU之前，我們先來看一下LRU的代碼怎么寫。

有句古話講得好：緩存就是Map + 淘汰策略。Map的作用是提供快速訪問，淘汰策略是緩存算法的靈魂，決定了命中率的高低。根據(jù)對于LRU的描述，我們需要一個東西（術(shù)語叫做數(shù)據(jù)結(jié)構(gòu)）來記錄數(shù)據(jù)被訪問的先后順序，這里我們可以選擇鏈表。

打開IDE，迅速寫下第一行代碼：

type LRU struct {
   data map[string]*list.Element
   cap int
   list *list.List
}

解釋一下為什么需要這幾個變量， cap 是緩存中可以存放的數(shù)據(jù)個數(shù)，也就是緩存的容量上限。data就是Map。List我們用來記錄數(shù)據(jù)的先后訪問順序，每次訪問，都把本次訪問的節(jié)點移動到鏈表中的頭部。這樣子整個鏈表就會按照近期的訪問記錄來排序了。

func (lru *LRU) add(k, v string) {
   if Map中存有這條Key {
      替換Map中的Value值
      將鏈表中的對應(yīng)節(jié)點移到最前面
   } else {
      if 已經(jīng)達(dá)到緩存容量上限 {
         獲取鏈表尾部節(jié)點的Key，并從Map中刪除
         移除鏈表尾部的Node
      }
      創(chuàng)建要插入的新節(jié)點
      將新節(jié)點插入到鏈表頭部
      放入Map中
   }
}
func (lru *LRU) get(k string) string {
   if Map中存有這條Key {
      返回查詢到的Value
      將對應(yīng)節(jié)點移動到鏈表頭部
   } else {
      返回 空
   }
}

LFU算法

我們已經(jīng)成功的寫出了LRU算法（偽代碼），接下來嘗試自己寫一下LFU算法。首先我們知道LFU算法比LRU多了什么，LFU需要記錄每條數(shù)據(jù)的訪問次數(shù)信息，并且按照訪問次數(shù)從高到低排序，訪問次數(shù)用什么來記錄呢？

只需要在鏈表節(jié)點中增加一個訪問頻率Frequency，就可以了，這個Frequency可以使用int來存儲。同時排序的規(guī)則稍加變動，不是把最近訪問的放到最前面，而是按照訪問頻率插入到對應(yīng)位置即可。如果頻率相同，再按照LRU的規(guī)則，比較誰是最新訪問的。

暫時無法在文檔外展示此內(nèi)容

小結(jié)：

講完了LRU和LFU，我們來看一下他們有啥優(yōu)缺點。

LRU

優(yōu)點：實現(xiàn)簡單、可以很快的適應(yīng)訪問模式的改變

缺點：對于熱點數(shù)據(jù)的命中率可能不如LFU

LFU

優(yōu)點：對于熱點數(shù)據(jù)命中率更高

缺點：難以應(yīng)對突發(fā)的稀疏流量、可能存在舊數(shù)據(jù)長期不被淘汰，會影響某些場景下的命中率（如外賣），需要額外消耗來記錄和更新訪問頻率

二、TinyLFU

Count-Min Sketch 算法

剛才提到了LFU需要統(tǒng)計每個條數(shù)據(jù)的訪問頻率，這就需要一個int或者long類型來存儲次數(shù)，但是仔細(xì)一想，一條緩存數(shù)據(jù)的訪問次數(shù)真的需要int類型這么大的表示范圍來統(tǒng)計嗎？我們認(rèn)為一個緩存被訪問15次已經(jīng)算是很高的頻率了，那么我們只用4個Bit就可以保存這個數(shù)據(jù)。（2^4=16）

再來介紹一個cmSketch算法，看過硬核課堂BloomFilter視頻的都知道，BloomFilter利用位圖的思想來標(biāo)記一條數(shù)據(jù)是否存在，存在與否可以用某個Bit位的0 | 1來代替，那么我們能不能擴(kuò)展一下，利用這種思想來計數(shù)呢？

我們給要計數(shù)的值計算一個Hash，然后在位圖中給這個Hash值對應(yīng)的位置累加1就可以了，但是BloomFilter中的一個典型問題是假陽性，可以說只要是用Hash計算就有存在沖突的可能，那么cmSketch計數(shù)法如果出現(xiàn)沖突會怎么樣呢？會給同一個位置多計算訪問次數(shù)。這里cmSketch選擇了以最小的統(tǒng)計數(shù)據(jù)值作為結(jié)果。這是一個不那么精確地統(tǒng)計方法，但是可以大致的反應(yīng)訪問分布的規(guī)律。

因為這個算法也就有了一個名字，叫做Count-Min Sketch。

下面我們來手撕這個算法。

//根據(jù)BloomFilter來思考一下我們需要什么
//一個bit圖，n個Hash函數(shù)
//一個BitMap的實現(xiàn)
type cmRow []byte //byte = uint8 = 0000，0000 = COUNTER 4BIT = 2 counter
//64 counter
//1 uint8 =  2counter
//32 uint8 = 64 counter
func newCmRow(numCounters int64) cmRow {
   return make(cmRow, numCounters/2)
}
func (r cmRow) get(n uint64) byte {
   return byte(r[n/2]>>((n&1)*4)) & 0x0f
}
0000,0000|0000,0000| 0000,0000 make([]byte, 3) = 6 counter
func (r cmRow) increment(n uint64) {
   //定位到第i個Counter
   i := n / 2 //r[i]
   //右移距離，偶數(shù)為0，奇數(shù)為4
   s := (n & 1) * 4
   //取前4Bit還是后4Bit
   v := (r[i] >> s) & 0x0f //0000, 1111
   //沒有超出最大計數(shù)時，計數(shù)+1
   if v < 15 {
      r[i] += 1 << s
   }
}
//cmRow 100,
//保鮮
func (r cmRow) reset() {
   // 計數(shù)減半
   for i := range r {
      r[i] = (r[i] >> 1) & 0x77 //0111，0111
   }
}
func (r cmRow) clear() {
   // 清空計數(shù)
   for i := range r {
      r[i] = 0
   }
}
//快速計算最接近x的二次冪的算法
//比如x=5，返回8
//x = 110，返回128
//2^n
//1000000 (n個0）
//01111111（n個1） + 1
// x = 1001010 = 1111111 + 1 =10000000 
func next2Power(x int64) int64 {
   x--
   x |= x >> 1 
   x |= x >> 2
   x |= x >> 4
   x |= x >> 8
   x |= x >> 16
   x |= x >> 32
   x++
   return x
}

如果我們要給n個數(shù)據(jù)計數(shù)，那么每4Bit當(dāng)做一個計數(shù)器Counter，我們一共需要幾個uint8來計數(shù)呢？答案是n/2

//cmSketch封裝
const cmDepth = 4
type cmSketch struct {
   rows [cmDepth]cmRow
   seed [cmDepth]uint64
   mask uint64
}
//numCounter - 1 = next2Power() = 0111111(n個1）
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
//0000,0000|0000,0000|0000,0000
func newCmSketch(numCounters int64) *cmSketch {
   if numCounters == 0 {
      panic("cmSketch: bad numCounters")
   }
   numCounters = next2Power(numCounters)
   sketch := &cmSketch{mask: uint64(numCounters - 1)}
   // Initialize rows of counters and seeds.
   source := rand.New(rand.NewSource(time.Now().UnixNano()))
   for i := 0; i < cmDepth; i++ {
      sketch.seed[i] = source.Uint64()
      sketch.rows[i] = newCmRow(numCounters)
   }
   return sketch
}
func (s *cmSketch) Increment(hashed uint64) {
   for i := range s.rows {
      s.rows[i].increment((hashed ^ s.seed[i]) & s.mask)
   }
}
// 找到最小的計數(shù)值
func (s *cmSketch) Estimate(hashed uint64) int64 {
   min := byte(255)
   for i := range s.rows {
      val := s.rows[i].get((hashed ^ s.seed[i]) & s.mask)
      if val < min {
         min = val
      }
   }
   return int64(min)
}
// 讓所有計數(shù)器都減半，保鮮機(jī)制
func (s *cmSketch) Reset() {
   for _, r := range s.rows {
      r.reset()
   }
}
// 清空所有計數(shù)器
func (s *cmSketch) Clear() {
   for _, r := range s.rows {
      r.clear()
   }
}

TinyLFU解決了LFU統(tǒng)計的內(nèi)存消耗問題，和緩存保鮮的問題，但是TinyLFU是否還有缺點呢？

有，論文中是這么描述的，根據(jù)實測TinyLFU應(yīng)對突發(fā)的稀疏流量時表現(xiàn)不佳。大概思考一下也可以得知，這些稀疏流量的訪問頻次不足以讓他們在LFU緩存中占據(jù)位置，很快就又被淘汰了。

我們回顧之前講過的，LRU對于稀疏流量效果很好，那可以不可以把LRU和LFU結(jié)合一下呢？就出現(xiàn)了下面這種緩存策略。

三、Window-TinyLFU

Window-TinyLFU策略里包含LRU和LFU兩部分，前端的小LRU叫做Window LRU，它的容量只占據(jù)1%的總空間，它的目的就是用來存放短期的突發(fā)訪問數(shù)據(jù)。存放主要元素的Segmented LRU(SLRU)是一種LRU的改進(jìn)，主要把在一個時間窗口內(nèi)命中至少2次的記錄和命中1次的單獨(dú)存放，這樣就可以把短期內(nèi)較頻繁的緩存元素區(qū)分開來。具體做法上，SLRU包含2個固定尺寸的LRU，一個叫Probation段A1，一個叫Protection段A2。新記錄總是插入到A1中，當(dāng)A1的記錄被再次訪問，就把它移到A2，當(dāng)A2滿了需要驅(qū)逐記錄時，會把驅(qū)逐記錄插入到A1中。W-TinyLFU中，SLRU有80%空間被分配給A2段。

視頻講解

以上就是LRU LFU TinyLFU緩存算法實例詳解的詳細(xì)內(nèi)容，更多關(guān)于LRU LFU TinyLFU緩存算法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論