簡(jiǎn)介

前置知識(shí)

知道什么是緩存

聽(tīng)完本節(jié)公開(kāi)課，你可以收獲

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

一、LRU和LFU算法

LRU算法

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

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

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

這樣子做有什么缺點(diǎn)呢？我們來(lái)看個(gè)例子

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

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

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

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

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

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

在開(kāi)始LFU之前，我們先來(lái)看一下LRU的代碼怎么寫。

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

打開(kāi)IDE，迅速寫下第一行代碼：

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

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

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

LFU算法

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

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

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

小結(jié)：

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

LRU

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

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

LFU

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

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

二、TinyLFU

Count-Min Sketch 算法

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

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

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

因?yàn)檫@個(gè)算法也就有了一個(gè)名字，叫做Count-Min Sketch。

下面我們來(lái)手撕這個(gè)算法。

//根據(jù)BloomFilter來(lái)思考一下我們需要什么
//一個(gè)bit圖，n個(gè)Hash函數(shù)
//一個(gè)BitMap的實(shí)現(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個(gè)Counter
   i := n / 2 //r[i]
   //右移距離，偶數(shù)為0，奇數(shù)為4
   s := (n & 1) * 4
   //取前4Bit還是后4Bit
   v := (r[i] >> s) & 0x0f //0000, 1111
   //沒(méi)有超出最大計(jì)數(shù)時(shí)，計(jì)數(shù)+1
   if v < 15 {
      r[i] += 1 << s
   }
}
//cmRow 100,
//保鮮
func (r cmRow) reset() {
   // 計(jì)數(shù)減半
   for i := range r {
      r[i] = (r[i] >> 1) & 0x77 //0111，0111
   }
}
func (r cmRow) clear() {
   // 清空計(jì)數(shù)
   for i := range r {
      r[i] = 0
   }
}
//快速計(jì)算最接近x的二次冪的算法
//比如x=5，返回8
//x = 110，返回128
//2^n
//1000000 (n個(gè)0）
//01111111（n個(gè)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個(gè)數(shù)據(jù)計(jì)數(shù)，那么每4Bit當(dāng)做一個(gè)計(jì)數(shù)器Counter，我們一共需要幾個(gè)uint8來(lái)計(jì)數(shù)呢？答案是n/2

//cmSketch封裝
const cmDepth = 4
type cmSketch struct {
   rows [cmDepth]cmRow
   seed [cmDepth]uint64
   mask uint64
}
//numCounter - 1 = next2Power() = 0111111(n個(gè)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)
   }
}
// 找到最小的計(jì)數(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)
}
// 讓所有計(jì)數(shù)器都減半，保鮮機(jī)制
func (s *cmSketch) Reset() {
   for _, r := range s.rows {
      r.reset()
   }
}
// 清空所有計(jì)數(shù)器
func (s *cmSketch) Clear() {
   for _, r := range s.rows {
      r.clear()
   }
}

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

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

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

三、Window-TinyLFU

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

視頻講解

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

最新評(píng)論