k8s expiring lru cache

LRUExpireCache 是一种支持数据过期的 LRU（最近最少使用）缓存策略。
当缓存达到最大大小（maxsize）后，在Add操作中最近最少使用的项目将会被移除，
在Get操作中如果项目过期将会被移除。
下面是k8s源码中LRUExpireCache的实现。

import (
	"container/list"
	"sync"
	"time"
)

// Clock defines an interface for obtaining the current time
type Clock interface {
	Now() time.Time
}

// realClock implements the Clock interface by calling time.Now()
type realClock struct{}

func (realClock) Now() time.Time { return time.Now() }

// LRUExpireCache is a cache that ensures the mostly recently accessed keys are returned with
// a ttl beyond which keys are forcibly expired.
// LRUExpireCache 实现一个带过期时间的LRU Cache
type LRUExpireCache struct {
	// clock is used to obtain the current time
	// 用于获取当前时间
	clock Clock

	lock sync.Mutex

	maxSize      int
    // 官方提供的列表实现(双向链表)
	evictionList list.List
	entries      map[interface{}]*list.Element
}

// NewLRUExpireCache creates an expiring cache with the given size
// NewLRUExpireCache 创建一个指定大小LRU Expire Cache
func NewLRUExpireCache(maxSize int) *LRUExpireCache {
	return NewLRUExpireCacheWithClock(maxSize, realClock{})
}

// NewLRUExpireCacheWithClock creates an expiring cache with the given size, using the specified clock to obtain the current time.
func NewLRUExpireCacheWithClock(maxSize int, clock Clock) *LRUExpireCache {
	if maxSize <= 0 {
		panic("maxSize must be > 0")
	}

	return &LRUExpireCache{
		clock:   clock,
		maxSize: maxSize,
		entries: map[interface{}]*list.Element{},
	}
}

// cacheEntry 包括key, value, expireTime
type cacheEntry struct {
	key        interface{}
	value      interface{}
	expireTime time.Time
}

// Add adds the value to the cache at key with the specified maximum duration.
func (c *LRUExpireCache) Add(key interface{}, value interface{}, ttl time.Duration) {
	c.lock.Lock()
	defer c.lock.Unlock()

	// Key already exists
	oldElement, ok := c.entries[key]
	// 如果key已经存在
	if ok {
		// 将元素移到列表头
		c.evictionList.MoveToFront(oldElement)
		// 更新值和过期时间
		oldElement.Value.(*cacheEntry).value = value
		oldElement.Value.(*cacheEntry).expireTime = c.clock.Now().Add(ttl)
		return
	}

	// Make space if necessary
	// 如果列表长度已经大于设置的最大值
	if c.evictionList.Len() >= c.maxSize {
		// 从列表和entries删除最旧的元素
		toEvict := c.evictionList.Back()
		c.evictionList.Remove(toEvict)
		delete(c.entries, toEvict.Value.(*cacheEntry).key)
	}

	// Add new entry
	// 插入最新的元素
	entry := &cacheEntry{
		key:        key,
		value:      value,
		expireTime: c.clock.Now().Add(ttl),
	}
	element := c.evictionList.PushFront(entry)
	c.entries[key] = element
}

// Get returns the value at the specified key from the cache if it exists and is not
// expired, or returns false.
func (c *LRUExpireCache) Get(key interface{}) (interface{}, bool) {
	c.lock.Lock()
	defer c.lock.Unlock()

	element, ok := c.entries[key]
	if !ok {
		return nil, false
	}

	// 如果这个元素已过期则移除
	if c.clock.Now().After(element.Value.(*cacheEntry).expireTime) {
		c.evictionList.Remove(element)
		delete(c.entries, key)
		return nil, false
	}

	// 将元素移到列表头
	c.evictionList.MoveToFront(element)

	return element.Value.(*cacheEntry).value, true
}

// Remove removes the specified key from the cache if it exists
// Remove 从Cache中移除指定的key
func (c *LRUExpireCache) Remove(key interface{}) {
	c.lock.Lock()
	defer c.lock.Unlock()

	element, ok := c.entries[key]
	if !ok {
		return
	}

	c.evictionList.Remove(element)
	delete(c.entries, key)
}

// Keys returns all unexpired keys in the cache.
//
// Keep in mind that subsequent calls to Get() for any of the returned keys
// might return "not found".
//
// Keys are returned ordered from least recently used to most recently used.
func (c *LRUExpireCache) Keys() []interface{} {
	c.lock.Lock()
	defer c.lock.Unlock()

	now := c.clock.Now()

	val := make([]interface{}, 0, c.evictionList.Len())
	for element := c.evictionList.Back(); element != nil; element = element.Prev() {
		// Only return unexpired keys
		if !now.After(element.Value.(*cacheEntry).expireTime) {
			val = append(val, element.Value.(*cacheEntry).key)
		}
	}

	return val
}

---

REF:

1. lruexpirecache.go