Go語言如何實現LRU算法的核心思想和實現過程

這篇文章主要介紹了Go語言如何實現LRU算法的核心思想和實現過程，具有一定借鑒價值，需要的朋友可以參考下。下面就和我一起來看看吧。

GO實現Redis的LRU例子

常見的三種緩存淘汰算法有三種:FIFO,LRU和LFU

實現LRU緩存淘汰算法

1.FIFO/LFU/LRU算法簡介

緩存全部存在內存中，內存是有限的，因此不可能無限制的添加數據，假定我們能夠最大使用的內存為Max,那么在一個時間點之后，添加了某一條緩存記錄之后，占用內存超過了N,這個時候就需要從緩存中移除一些數據，那么該移除或者淘汰誰呢？我們肯定希望去移除沒用的數據，將熱點數據留在緩存中,下面幾種就是對應的幾種策略！

FIFO （First in First Out）

先進先出，內存滿了時淘汰最老存在最久的key緩存，這種算法認為越早被添加的數據使用可能性會比新加入進來的小，但是這種也有弊端，在某些場景下比如查歷史支付記錄的賬單，就需要查詢之前的緩存記錄，這類記錄就不得不因為每天新的支付從而淘汰掉以前的支付記錄（當然這類記錄存庫是最好方式）

【實現方式】維護一個隊列先進先出就行了,新來的數據加到隊尾

LFU (Least Frequently Used)

最少使用，也就是淘汰緩存中訪問頻率最低的記錄。這個算法認為過去訪問次數最高的使用概率也最大，但是這樣就額外維護了一個訪問次數，對內存其實占用也挺多的，再者訪問次數最多的數據，突然不使用了，那么要淘汰它之前，需要內存其他區域的數據訪問次數全部超過它才有可能，所以淘汰的缺點也非常明顯。

【實現方式】LFU 的實現需要維護一個按照訪問次數排序的隊列，每次訪問，訪問次數加1，隊列重新排序，淘汰時選擇訪問次數最少的即可

LRU （Least Recently Used）

最近最少使用,相對于只考慮使用時間和使用次數來看，LRU會相對比較平均去淘汰數據，如果數據最近被使用過，那么將來被訪問的概率將提高

【實現方式】維護一個隊列，如果某條記錄被訪問了，則移動到隊尾，那么隊首則是最近最少訪問的數據，淘汰該條記錄即可。

2.LRU算法實現

2.1核心數據結構

這張圖很好地表示了 LRU 算法最核心的 2 個數據結構

• 綠色的是字典(map)，存儲鍵和值的映射關系。這樣根據某個鍵(key)查找對應的值(value)的復雜是O(1)，在字典中插入一條記錄的復雜度也是O(1)。

• 紅色的是雙向鏈表(double linked list)實現的隊列。將所有的值放到雙向鏈表中，這樣，當訪問到某個值時，將其移動到隊尾的復雜度是O(1)，在隊尾新增一條記錄以及刪除一條記錄的復雜度均為O(1)。

接下來我們創建一個包含字典和雙向鏈表的結構體類型 Cache，方便實現后續的增刪查改操作。

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

• 在這里我們直接使用 Go 語言標準庫實現的雙向鏈表list.List。

• 字典的定義是 map[string]*list.Element，鍵是字符串，值是雙向鏈表中對應節點的指針。

• maxBytes 是允許使用的最大內存，nbytes 是當前已使用的內存，OnEvicted 是某條記錄被移除時的回調函數，可以為 nil。

• 鍵值對 entry 是雙向鏈表節點的數據類型，在鏈表中仍保存每個值對應的 key 的好處在于，淘汰隊首節點時，需要用 key 從字典中刪除對應的映射。

• 為了通用性，我們允許值是實現了 Value 接口的任意類型，該接口只包含了一個方法 Len() int，用于返回值所占用的內存大小。

方便實例化 Cache，實現 New() 函數：

// 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 個步驟，第一步是從字典中找到對應的雙向鏈表的節點，第二步，將該節點移動到隊尾。

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

• 如果鍵對應的鏈表節點存在，則將對應節點移動到隊尾，并返回查找到的值。

• c.ll.MoveToBack(ele)，即將鏈表中的節點 ele 移動到隊尾

2.3刪除

這里的刪除，實際上是緩存淘汰。即移除最近最少訪問的節點（隊首）

// 移除最近最近，最少訪問的的節點
func (c *Cache)RemoveOldest(){
	ele:=c.ll.Front()  // 取到隊首節點，從鏈表中刪除
	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() 取到隊首節點，從鏈表中刪除。

• delete(c.cache, kv.key)，從字典中 c.cache 刪除該節點的映射關系。

• 更新當前所用的內存 c.nbytes。

• 如果回調函數 OnEvicted 不為 nil，則調用回調函數

2.4新增或修改

// 新增或修改
func (c *Cache)Add(key string ,value Value){
   if int64(value.Len())>c.maxBytes{
      log.Printf("超過最大容量%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())
   }
   // 如果當前使用的內存>允許使用的最大內存 使用淘汰策略
   for c.maxBytes !=0 && c.maxBytes < c.nbytes{
       c.RemoveOldest()
   }
}

• 如果鍵存在，則更新對應節點的值，并將該節點移到隊尾。

• 不存在則是新增場景，首先隊尾添加新節點 &entry{key, value}, 并字典中添加 key 和節點的映射關系。

• 更新 c.nbytes，如果超過了設定的最大值 c.maxBytes，則移除最少訪問的節點。

以上就是Go語言如何實現LRU算法的核心思想和實現過程的詳細內容了，看完之后是否有所收獲呢？如果想了解更多相關內容，歡迎來億速云行業資訊！