基于优先级的淘汰的本地缓存实现

[flycash]

正常情况下，淘汰策略都是 LRU 或者 LFU。但是在一些业务场景下，这两种淘汰策略缺乏灵活性。例如在一些场景下，我需要考虑先淘汰了大对象，有些时候我会考虑先淘汰了小对象。

那么这一切就可以抽象为：按照优先级来淘汰，并且是优先淘汰优先级低的对象。

那么对于 LRU 和 LFU 来说，也可以通过将它们伪装成优先级。比如说最近最少使用的优先级就最低。

在这里，因为考虑到控制本地缓存的内存使用量，就直接控制整个键值对数量，以及最大的值的大小，都不能超过某个阈值（用户参数传入）

[XiaKuan]

是否可以这样，缓存结构中添加一个优先级队列用于管理淘汰；LRU和LFU缓存通过修改Get方法和Set方法实现

优先级缓存在设置的时候需要加上优先级

/**
优先级缓存
*/
type PriorityCache struct {
	lock sync.RWMutex

	Items     map[string]*CacheItem // 缓存项的映射
	PriorityQ PriorityQueue         // 优先级队列

	onEvicted func(key string, val any)
	Size      int
	Capacity  int
}

// Get 获取缓存项
func (c *PriorityCache) Get(key string) any {
	item, exists := c.Items[key]
	if !exists {
		return nil
	}
	return item.Value
}

func (c *PriorityCache) Set(key string, value any, priority int) {
       // todo: 设置缓存同时判断是否超过容量
}

type CacheItem struct {
	Key      string
	Value    any
	Priority int // 优先级，用于淘汰策略
}

// SetPriority 更新优先级
func (c *CacheItem) SetPriority(priority int) error {
	c.Priority = priority
	return nil
}

func main() {
	cache.Set("key1", "value1", 3)

	// 获取缓存项
	val, exists := cache.Get("key1")
}

其余的各种实现通过对于PriorityCache进行包装使用，例如优先淘汰大对象就是在Set的时候将对象大小作为优先级
例如LRU缓存可以这么实现

/**
LRU缓存
*/
type LRU struct {
	PriorityCache
}

func (l *LRU) Get(key string) any {
	res, ok := l.Items[K]
	if !ok {
		return nil
	}

         // 利用时间戳作为优先级
	err := res.SetPriority(-int(time.Now().UnixNano()))
	if err != nil {
		return nil
	}
	return res
}

func (l *LRU) Set(key string, value any) {
	l.PriorityCache.Set(key, value, -int(time.Now().UnixNano()))
}

func main() {
	cache.Set("key1", "value1")

	// 获取缓存项
	val, exists := cache.Get("key1")
}

[flycash]

就是这个思路。但是我们在实现的时候，遇到了一些小问题，核心还是在于优先级队列要支持动态删除和调整，不然比较难以达成目标。但是暂时我们还缺少这样的一个优先级队列，所以有一点棘手。

[flycash]

你可以关注 #20

[XiaKuan]

你可以关注 #20

这个pr 看起来已经被合并了；但是看上去有两个疑惑：

1. 没有实现Cache接口中的Delete和IncrByFloat方法，是否可以使用double-check的方式调用deleteNode方法实现Delete方法，或者还是有别的顾虑
2. 不支持直接对于节点优先级的动态调整；看起来是priorityData结构中ekit的queue.PriorityQueue中使用小根堆的数据结构导致的；如果想要实现优先级的调整，可以对于节点删除再添加节点触发实现一下吗

之后能不能继续这个issue的开发

[flycash]

可以继续这个开发。应该是合并分支顺序的问题。你可以继续支持已有的方法。

不支持优先级策略调整，这个是优先级队列的问题，我们首先需要一个支持调整优先级的优先级队列。

非常欢迎你继续开发。