Golang 隨機淘汰演算法快取實現

• 2022 年 9 月 9 日
• 筆記
• Go

快取如果寫滿, 它必須淘汰舊值以容納新值, 最近最少使用淘汰演算法 (LRU) 是一個不錯的選擇, 因為你如果最近使用過某些值, 這些值更可能被保留. 你如果構造一個比快取限制還長的循環, 當循環最後的值可以命中快取時, LRU 就會是完美的, 但是當它無法命中快取時, 這個快取將失效. 快取的淘汰演算法也要降級為隨機淘汰演算法.

基於 sync.Map 和 map 的無序遍歷機制, 帶有 過期時間 的隨機淘汰快取可以非常輕鬆被實現.

實現

構造器

type Item struct {
	item   interface{}
	exired int64
}

type Cache struct {
	cache *sync.Map
	limit int64
	size  int64
}

func NewCache(limit int64) *Cache {
	if limit <= 0 {
		log.Panicf("cache.NewCache.limit:%+v <= 0", limit)
	}
	return &Cache{cache: &sync.Map{}, limit: limit}
}

介面以及實現

func (c *Cache) Get(key interface{}) (interface{}, bool) {
	if val, ok := c.cache.Load(key); !ok {
		return nil, false
	} else if item, _ := val.(*Item); item.exired <= 0 || time.Now().Unix() < item.exired {
		return item.item, true
	} else {
		c.cache.Delete(key)
		atomic.AddInt64(&c.size, -1)
		return nil, false
	}
}

func (c *Cache) Set(key, val interface{}, exired int64) {
	if _, ok := c.cache.Load(key); ok && val != nil {
		c.cache.Store(key, &Item{val, exired})
		return
	} else if ok && val == nil {
		c.cache.Delete(key)
		atomic.AddInt64(&c.size, -1)
		return
	} else if (c.limit <= c.size && c.deleteAnother(key)) || c.size < c.limit {
		c.cache.Store(key, &Item{val, exired})
		return
	}
}

func (c *Cache) Size() int64 {
	return c.size
}

Random淘汰演算法

基於 go 對 map 的無序遍歷機制

func (c *Cache) deleteAnother(key interface{}) (found bool) {
	c.cache.Range(func(other, value interface{}) bool {
		if key == other {
			return true
		}
		found = true
		c.cache.Delete(other)
		return false
	})
	return found
}

實例

1. aws-sdk-go快取 Endpoint 對象.

參考

[1] Caches: LRU v. random [EB/OL]. //danluu.com/2choices-eviction/.