Go語言實現(xiàn)lru淘汰策略和超時過期

更新時間：2024年02月11日 09:14:24 作者：洛語言

緩存的大小是有限的,當(dāng)添加數(shù)據(jù)發(fā)現(xiàn)剩余緩存不夠時,需要淘汰緩存中的部分?jǐn)?shù)據(jù),本文主要介紹了Go語言實現(xiàn)lru淘汰策略和超時過期,感興趣的可以了解一下

lru淘汰策略

緩存的大小是有限的，當(dāng)添加數(shù)據(jù)發(fā)現(xiàn)剩余緩存不夠時，需要淘汰緩存中的部分?jǐn)?shù)據(jù)。如何選擇性的淘汰緩存中的數(shù)據(jù)呢？常用方法有以下三種。

LRU: 全稱Least Recently Use，意為：最近最少使用的。當(dāng)緩存到達最大值時，就會淘汰最近最久未使用的數(shù)據(jù)。
LFU： 全稱Least Frequently User，意為：最少使用。注意與LRU的區(qū)別，LFU強調(diào)使用次數(shù)最少的。當(dāng)緩存到達最大值時，就會淘汰最近最少使用的。
FIFO： 全稱First In First Out，意為：最先進的最先出去。當(dāng)緩存到達最大值時，就會淘汰最先進入緩存的那個數(shù)據(jù)。

這里我們只實現(xiàn)LRU淘汰策略。

lru的實現(xiàn)需要用到兩個數(shù)據(jù)結(jié)構(gòu)：雙向循環(huán)鏈表和一個字典map，雙向循環(huán)鏈表是緩存內(nèi)容的主要存放位置，并且借助雙向循環(huán)鏈表 來實現(xiàn)數(shù)據(jù)淘汰。字典map存放的是指向鏈表節(jié)點的指針，便于在鏈表中查詢緩存。

每當(dāng)我們添加數(shù)據(jù)時，將數(shù)據(jù)插入鏈表頭部，同時將節(jié)點的指針存儲到map中。當(dāng)我們查詢數(shù)據(jù)時，通過key在map中獲取對應(yīng)節(jié)點的指針，然后將該節(jié)點放到鏈表的頭部，并返回數(shù)據(jù)。當(dāng)緩存淘汰數(shù)據(jù)時，只需要將鏈表尾部的數(shù)據(jù)剔除，并刪除map中對應(yīng)節(jié)點的指針。

通過以上方案可以實現(xiàn)lru淘汰策略。但是lru淘汰策略還存在很大問題，數(shù)據(jù)的剔除是由lru算法決定的，使用者并不能決定何時淘汰。如果舊數(shù)據(jù)一直不被剔除，就可能造成數(shù)據(jù)并不一致問題。所以接下來在lru的基礎(chǔ)上實現(xiàn)超時淘汰。

超時淘汰

實現(xiàn)超時淘汰我們需要增加一個字典map來維護，當(dāng)我們添加數(shù)據(jù)時需要指定數(shù)據(jù)的過期時間，設(shè)置為負(fù)數(shù)表示永不過期。設(shè)置了過期時間的數(shù)據(jù)(過期時間為非負(fù)數(shù))也要加入這個map。
接下來要考略的就是什么時候剔除過期數(shù)據(jù)，這里有三種方案：

定時剔除： 為設(shè)置了過期時間的值綁定定時事件，時間一到就觸發(fā)事件將數(shù)據(jù)刪除。
缺點： 當(dāng)很多數(shù)據(jù)同時過期時會占用大量cpu，使緩存的效率降低。
惰性刪除： 數(shù)據(jù)過期時并不會立刻刪除，當(dāng)過期的數(shù)據(jù)被獲取時，才會刪除。
缺點： 若數(shù)據(jù)一直未被獲取，會占用內(nèi)存。
定期刪除： 同樣也是數(shù)據(jù)過期不會被立刻刪除，緩存會每隔一段時間從map中抽取部分?jǐn)?shù)據(jù)，刪除其中過期的數(shù)據(jù)。
缺點： 時間間隔很難確定，若時間間隔太短，會跟定時刪除一樣，占用大量CPU資源。若時間間隔太長，緩存中的數(shù)據(jù)不能被及時刪除，浪費大量內(nèi)存資源。

這里為參考了Redis的超時淘汰策略，將惰性刪除和定期刪除結(jié)合使用。每當(dāng)獲取數(shù)據(jù)時會查看該數(shù)據(jù)是否過期，如果過期就將該數(shù)據(jù)刪除。與此同時，會另外開啟一個協(xié)程，定期的從緩存中抽取部分?jǐn)?shù)據(jù)，刪除過期數(shù)據(jù)。

代碼實現(xiàn)

my-cache2/evict/cache.go

type Value interface {
	Len() int
}

type entity struct {
	key string
	v   Value
	ddl int64
}

type Cache struct {
	maxBytes      uint64
	uBytes        uint64
	ll            *list.List
	allDataMap    map[string]*list.Element
	expireDataMap map[string]*list.Element
}

Value 是緩存存儲的數(shù)據(jù)類型接口。
entity 是將緩存數(shù)據(jù)、key，以及過期時間ddl封裝成的數(shù)據(jù)類型。key用于從兩個map中查找數(shù)據(jù)并刪除。
Cache 是實現(xiàn)lru和超時過期的核心數(shù)據(jù)結(jié)構(gòu)。
- maxBytes 是緩存的最大內(nèi)存。
- uBytes是已經(jīng)使用的緩存大小。
- ll 是雙向循環(huán)鏈表，是存儲緩存數(shù)據(jù)和實現(xiàn)lru的主要數(shù)據(jù)結(jié)構(gòu)。
- allDataMap 是緩存中所有數(shù)據(jù)的映射字典，可以通過key獲取該數(shù)據(jù)在ll中對應(yīng)節(jié)點的指針。
- expireDataMap 與allDataMap類似，它是緩存中所有設(shè)置了過期時間的數(shù)據(jù)的映射字典。

實例化緩存

func NewCache(maxBytes uint64) *Cache {
	return &Cache{
		maxBytes:   maxBytes,
		ll:         new(list.List),
		allDataMap: make(map[string]*list.Element),
	}
}

在實例化緩存時并沒有初始化expireDataMap，是因為這里會使用延遲加載，當(dāng)?shù)谝粋€設(shè)置了過期時間的數(shù)據(jù)被添加時，這個map才會被初始化。

添加數(shù)據(jù)

func (c *Cache) Add(key string, v Value, expire int64) error {
	if c.allDataMap[key] != nil{
		c.remove(key)
	}
	vBytes := uint64(v.Len()) + uint64(len([]byte(key)))
	if vBytes > c.maxBytes-c.uBytes {
		if vBytes > c.maxBytes {
			return fmt.Errorf("%s is not find in cache", key)
		}
		c.RemoveOldest()
		return c.Add(key, v, expire)
	}
	var ddl int64 = -1
	if expire > 0 {
		ddl = time.Now().Unix() + expire
	}
	e := c.ll.PushFront(&entity{key, v, ddl})
	c.uBytes += vBytes
	c.allDataMap[key] = e
	if expire > 0 {
		if c.expireDataMap == nil {
			c.expireDataMap = make(map[string]*list.Element)
		}
		c.expireDataMap[key] = e
	}
	return nil

}

添加的數(shù)據(jù)若已經(jīng)存在，需要先刪掉舊數(shù)據(jù)(實現(xiàn)更新)。
添加數(shù)據(jù)首先要檢查緩存的內(nèi)存大小是否足夠，不夠的話就需要剔除緩存中的一些舊數(shù)據(jù)。
添加數(shù)據(jù)時需要指定expire(數(shù)據(jù)多少秒后過期)。若expire小于0，表示永不過期；expire大于0會在指定秒數(shù)后過期然后Add函數(shù)會根據(jù)這個expire獲取數(shù)據(jù)的過期時間。

刪除緩存

func (c *Cache) RemoveOldest() {
	back := c.ll.Back()
	c.ll.Remove(back)
	e := back.Value.(*entity)
	delete(c.allDataMap, e.key)
	delete(c.expireDataMap, e.key)
	c.uBytes -= uint64(back.Value.(*entity).v.Len()) + uint64(len(e.key))
}
func (c *Cache) remove(key string) {
	element := c.allDataMap[key]
	c.ll.MoveToBack(element)
	c.RemoveOldest()
}

RemoveOldest() 函數(shù)用來移除最久未使用的緩存。
remove() 函數(shù)用來移除指定key對應(yīng)的緩存。

獲取緩存

func (c *Cache) Get(key string) (Value, error) {
	element := c.allDataMap[key]
	if element == nil {
		return nil, fmt.Errorf("%s is not find in cache", key)
	}
	entity := element.Value.(*entity)
	if entity.ddl > 0 && entity.ddl < time.Now().Unix() {
		c.remove(key)
		return nil, fmt.Errorf("%s is not find in cache", key)
	}
	c.ll.MoveToFront(element)
	return entity.v, nil
}

在獲取緩存時，若被獲取的緩存過期，就會將該緩存刪除，并返回nil和異常。若被獲取的數(shù)據(jù)未過期或未設(shè)置過期時間，就會將該數(shù)據(jù)放到鏈表首部。

定期刪除

func (c *Cache) DeleteExpired() {
	go func() {
		for true {
			if c.expireDataMap == nil {
				time.Sleep(1 * time.Second)
				continue
			}
			count := 20
			expired := 0
			for _, v := range c.expireDataMap {
				if count <= 0 {
					break
				}
				e := v.Value.(*entity)
				if e.ddl <= time.Now().Unix() {
					expired++
					c.remove(e.key)
				}
				count--
			}
			if expired < 5 {
				time.Sleep(1 * time.Second)
			}
		}
	}()
}

go語言中，range遍歷map每次的順序都是隨機的，我們可以借助range來隨機獲取map中的部分鍵。
調(diào)用該函數(shù)會啟動一個協(xié)程，該協(xié)程每秒會隨機獲取expiredDataMap中的二十個緩存數(shù)據(jù)，并檢查它們是否過期，若二十個數(shù)據(jù)中有五個以上的數(shù)據(jù)已經(jīng)過期，那么會立刻再次獲取二十個緩存數(shù)據(jù)重復(fù)該操作(不會進行等待)。

測試

func (c *Cache) Print() {
	fmt.Println("allDataMap:")
	for _, v := range c.allDataMap {
		fmt.Printf("%v  ", v.Value.(*entity).key)
	}
	fmt.Println("\nexpireDataMap")
	for _, v := range c.expireDataMap {
		fmt.Printf("%v  ", v.Value.(*entity).key)
	}
	fmt.Println()
}

func (c *Cache) Len() int {
	return len(c.allDataMap)
}

在cache.go中實現(xiàn)這兩個函數(shù)是為了更好的進行測試。

my-cache2/test/cache_test.go

type v struct {
	s string
}

func (v v) Len() int {
	return len(v.s)
}

// 測試對url剔除、對設(shè)置超時時間和未設(shè)置超時時間進行分組
func TestCache1(t *testing.T) {
	cache := evict.NewCache(20)
	cache.Add("12", v{"ab"}, 2)
	cache.Add("34", v{"ab"}, 2)
	cache.Add("56", v{"ab"}, 2)
	cache.Add("78", v{"ab"}, 2)
	cache.Add("90", v{"ab"}, 2)
	cache.Add("91", v{"ab"}, 2)
	cache.Add("92", v{"ab"}, 2)
	cache.Add("93", v{"ab"}, -1)
	cache.Add("94", v{"ab"}, -1)
	cache.Add("95", v{"ab"}, -1)
	cache.Print()
}

// 測式定時隨機剔除
func TestCache2(t *testing.T) {
	cache := evict.NewCache(20)
	cache.DeleteExpired()
	cache.Add("12", v{"ab"}, 2)
	cache.Add("34", v{"ab"}, 2)
	cache.Add("56", v{"ab"}, 2)
	cache.Add("78", v{"ab"}, 2)
	cache.Add("90", v{"ab"}, 2)
	cache.Add("95", v{"ab"}, -1)
	cache.Print()
	time.Sleep(4 * time.Second)
	cache.Print()
}
//測試Get不會刪除未過期數(shù)據(jù)，但是會刪除過期數(shù)據(jù)
func TestCache3(t *testing.T) {
	cache := evict.NewCache(20)
	cache.Add("12", v{"ab"}, 2)
	cache.Add("34", v{"ab"}, 2)
	cache.Add("56", v{"ab"}, 2)
	cache.Add("78", v{"ab"}, 2)
	cache.Add("90", v{"ab"}, 2)
	fmt.Println(cache.Get("12"))
	fmt.Println(cache.Get("34"))
	fmt.Println(cache.Get("56"))
	fmt.Println(cache.Get("78"))
	fmt.Println(cache.Get("90"))
	time.Sleep(4 * time.Second)
	fmt.Println(cache.Get("12"))
	fmt.Println(cache.Get("34"))
	fmt.Println(cache.Get("56"))
	fmt.Println(cache.Get("78"))
	fmt.Println(cache.Get("90"))
	cache.Print()
}

=== RUN TestCache1
allDataMap:
93 94 95 91 92
expireDataMap
91 92
--- PASS: TestCache1 (0.00s)
PASS

=== RUN TestCache2
allDataMap:
56 78 90 95 34
expireDataMap
34 56 78 90
allDataMap:
95
expireDataMap

--- PASS: TestCache2 (4.00s)
PASS

=== RUN TestCache3
{ab} <nil>
{ab} <nil>
{ab} <nil>
{ab} <nil>
{ab} <nil>
<nil> 12 is not find in cache
<nil> 34 is not find in cache
<nil> 56 is not find in cache
<nil> 78 is not find in cache
<nil> 90 is not find in cache
allDataMap:

expireDataMap

--- PASS: TestCache3 (4.01s)
PASS