GO實(shí)現(xiàn)Redis的LRU例子

常見(jiàn)的三種緩存淘汰算法有三種:FIFO,LRU和LFU

實(shí)現(xiàn)LRU緩存淘汰算法

1.FIFO/LFU/LRU算法簡(jiǎn)介

緩存全部存在內(nèi)存中，內(nèi)存是有限的，因此不可能無(wú)限制的添加數(shù)據(jù)，假定我們能夠最大使用的內(nèi)存為Max,那么在一個(gè)時(shí)間點(diǎn)之后，添加了某一條緩存記錄之后，占用內(nèi)存超過(guò)了N,這個(gè)時(shí)候就需要從緩存中移除一些數(shù)據(jù)，那么該移除或者淘汰誰(shuí)呢？我們肯定希望去移除沒(méi)用的數(shù)據(jù)，將熱點(diǎn)數(shù)據(jù)留在緩存中,下面幾種就是對(duì)應(yīng)的幾種策略！

FIFO （First in First Out）

先進(jìn)先出，內(nèi)存滿(mǎn)了時(shí)淘汰最老存在最久的key緩存，這種算法認(rèn)為越早被添加的數(shù)據(jù)使用可能性會(huì)比新加入進(jìn)來(lái)的小，但是這種也有弊端，在某些場(chǎng)景下比如查歷史支付記錄的賬單，就需要查詢(xún)之前的緩存記錄，這類(lèi)記錄就不得不因?yàn)槊刻煨碌闹Ц稄亩蕴粢郧暗闹Ц队涗洠ó?dāng)然這類(lèi)記錄存庫(kù)是最好方式）

【實(shí)現(xiàn)方式】維護(hù)一個(gè)隊(duì)列先進(jìn)先出就行了,新來(lái)的數(shù)據(jù)加到隊(duì)尾

LFU (Least Frequently Used)

最少使用，也就是淘汰緩存中訪問(wèn)頻率最低的記錄。這個(gè)算法認(rèn)為過(guò)去訪問(wèn)次數(shù)最高的使用概率也最大，但是這樣就額外維護(hù)了一個(gè)訪問(wèn)次數(shù)，對(duì)內(nèi)存其實(shí)占用也挺多的，再者訪問(wèn)次數(shù)最多的數(shù)據(jù)，突然不使用了，那么要淘汰它之前，需要內(nèi)存其他區(qū)域的數(shù)據(jù)訪問(wèn)次數(shù)全部超過(guò)它才有可能，所以淘汰的缺點(diǎn)也非常明顯。

【實(shí)現(xiàn)方式】LFU 的實(shí)現(xiàn)需要維護(hù)一個(gè)按照訪問(wèn)次數(shù)排序的隊(duì)列，每次訪問(wèn)，訪問(wèn)次數(shù)加1，隊(duì)列重新排序，淘汰時(shí)選擇訪問(wèn)次數(shù)最少的即可

LRU （Least Recently Used）

最近最少使用,相對(duì)于只考慮使用時(shí)間和使用次數(shù)來(lái)看，LRU會(huì)相對(duì)比較平均去淘汰數(shù)據(jù)，如果數(shù)據(jù)最近被使用過(guò)，那么將來(lái)被訪問(wèn)的概率將提高

【實(shí)現(xiàn)方式】維護(hù)一個(gè)隊(duì)列，如果某條記錄被訪問(wèn)了，則移動(dòng)到隊(duì)尾，那么隊(duì)首則是最近最少訪問(wèn)的數(shù)據(jù)，淘汰該條記錄即可。

2.LRU算法實(shí)現(xiàn)

2.1核心數(shù)據(jù)結(jié)構(gòu)

這張圖很好地表示了 LRU 算法最核心的 2 個(gè)數(shù)據(jù)結(jié)構(gòu)

• 綠色的是字典(map)，存儲(chǔ)鍵和值的映射關(guān)系。這樣根據(jù)某個(gè)鍵(key)查找對(duì)應(yīng)的值(value)的復(fù)雜是O(1)，在字典中插入一條記錄的復(fù)雜度也是O(1)。
• 紅色的是雙向鏈表(double linked list)實(shí)現(xiàn)的隊(duì)列。將所有的值放到雙向鏈表中，這樣，當(dāng)訪問(wèn)到某個(gè)值時(shí)，將其移動(dòng)到隊(duì)尾的復(fù)雜度是O(1)，在隊(duì)尾新增一條記錄以及刪除一條記錄的復(fù)雜度均為O(1)。

接下來(lái)我們創(chuàng)建一個(gè)包含字典和雙向鏈表的結(jié)構(gòu)體類(lèi)型 Cache，方便實(shí)現(xiàn)后續(xù)的增刪查改操作。

package lru
import (
	"container/list"
	"log"
)
// Cache is a LRU cache. It is not safe for concurrent access.
type Cache struct {
	maxBytes int64 // 允許使用的最大內(nèi)存
	nbytes   int64 // 當(dāng)前已使用的內(nèi)存
	ll       *list.List
	cache    map[string]*list.Element
	// optional and executed when an entry is purged.
	OnEvicted func(key string, value Value) // 某條記錄被移除時(shí)的回調(diào)函數(shù)
}
type entry struct {
	key   string
	value Value
}
// Value use Len to count how many bytes it takes
type Value interface {
	Len() int
}

• 在這里我們直接使用 Go 語(yǔ)言標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)的雙向鏈表list.List。
• 字典的定義是 map[string]*list.Element，鍵是字符串，值是雙向鏈表中對(duì)應(yīng)節(jié)點(diǎn)的指針。
• maxBytes 是允許使用的最大內(nèi)存，nbytes 是當(dāng)前已使用的內(nèi)存，OnEvicted 是某條記錄被移除時(shí)的回調(diào)函數(shù)，可以為 nil。
• 鍵值對(duì) entry 是雙向鏈表節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型，在鏈表中仍保存每個(gè)值對(duì)應(yīng)的 key 的好處在于，淘汰隊(duì)首節(jié)點(diǎn)時(shí)，需要用 key 從字典中刪除對(duì)應(yīng)的映射。
• 為了通用性，我們?cè)试S值是實(shí)現(xiàn)了 Value 接口的任意類(lèi)型，該接口只包含了一個(gè)方法 Len() int，用于返回值所占用的內(nèi)存大小。

方便實(shí)例化 Cache，實(shí)現(xiàn) New() 函數(shù)：

// New is the Constructor of Cache
func New(maxBytes int64, onEvicted func(string, Value)) *Cache {
	return &Cache{
		maxBytes:  maxBytes,
		ll:        list.New(),
		cache:     make(map[string]*list.Element),
		OnEvicted: onEvicted,
	}
}

2.2查找功能

查找主要有 2 個(gè)步驟，第一步是從字典中找到對(duì)應(yīng)的雙向鏈表的節(jié)點(diǎn)，第二步，將該節(jié)點(diǎn)移動(dòng)到隊(duì)尾。

func (c *Cache)Get(key string)(val Value,ok bool){
	// 如果找到了節(jié)點(diǎn)，就將緩存移動(dòng)到隊(duì)尾
	if ele,ok:=c.cache[key];ok{
		c.ll.MoveToBack(ele)
		kv:=ele.Value.(*entry)
		return kv.value,true
	}
	return
}

• 如果鍵對(duì)應(yīng)的鏈表節(jié)點(diǎn)存在，則將對(duì)應(yīng)節(jié)點(diǎn)移動(dòng)到隊(duì)尾，并返回查找到的值。
• c.ll.MoveToBack(ele)，即將鏈表中的節(jié)點(diǎn) ele 移動(dòng)到隊(duì)尾

2.3刪除

這里的刪除，實(shí)際上是緩存淘汰。即移除最近最少訪問(wèn)的節(jié)點(diǎn)（隊(duì)首）

// 移除最近最近，最少訪問(wèn)的的節(jié)點(diǎn)
func (c *Cache)RemoveOldest(){
	ele:=c.ll.Front()  // 取到隊(duì)首節(jié)點(diǎn)，從鏈表中刪除
	if ele!=nil{
		c.ll.Remove(ele)
	    kv:=ele.Value.(*entry)
	    delete(c.cache,kv.key)
	    c.nbytes-=int64(len(kv.key))+int64(kv.value.Len())
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

• c.ll.Front() 取到隊(duì)首節(jié)點(diǎn)，從鏈表中刪除。
• delete(c.cache, kv.key)，從字典中 c.cache 刪除該節(jié)點(diǎn)的映射關(guān)系。
• 更新當(dāng)前所用的內(nèi)存 c.nbytes。
• 如果回調(diào)函數(shù) OnEvicted 不為 nil，則調(diào)用回調(diào)函數(shù)

2.4新增或修改

// 新增或修改
func (c *Cache)Add(key string ,value Value){
   if int64(value.Len())>c.maxBytes{
      log.Printf("超過(guò)最大容量%d,插入緩存容量為%d",c.maxBytes,int64(value.Len()))
      return
   }
   if ele,ok:=c.cache[key];ok{
          c.ll.MoveToBack(ele)
          kv:=ele.Value.(*entry)
       c.nbytes += int64(value.Len()) - int64(kv.value.Len())
   }else{
      ele:=c.ll.PushFront(&entry{key: key,value: value})
      c.cache[key]=ele
      c.nbytes=int64(len(key))+int64(value.Len())
   }
   // 如果當(dāng)前使用的內(nèi)存>允許使用的最大內(nèi)存 使用淘汰策略
   for c.maxBytes !=0 && c.maxBytes < c.nbytes{
       c.RemoveOldest()
   }
}

• 如果鍵存在，則更新對(duì)應(yīng)節(jié)點(diǎn)的值，并將該節(jié)點(diǎn)移到隊(duì)尾。
• 不存在則是新增場(chǎng)景，首先隊(duì)尾添加新節(jié)點(diǎn) &entry{key, value}, 并字典中添加 key 和節(jié)點(diǎn)的映射關(guān)系。
• 更新 c.nbytes，如果超過(guò)了設(shè)定的最大值 c.maxBytes，則移除最少訪問(wèn)的節(jié)點(diǎn)。

到此這篇關(guān)于Go語(yǔ)言實(shí)現(xiàn)LRU算法的核心思想和實(shí)現(xiàn)過(guò)程的文章就介紹到這了,更多相關(guān)Go LRU算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論