提供优先级缓存支持动态调整优先级功能

[XiaKuan]

仅限中文

使用场景

对于一些业务场景中，希望考虑先淘汰了大对象，有些时候考虑先淘汰了小对象。
但是实际中对象可能是会进行更新的，如果重复设置了k-v对，希望能够重新计算k-v对的优先级并设置优先级。

同时为了降低调用者的心智负担，不希望调用者手动调用一个类似于update的方法，而是在set（包括其他更新操作）的时候检查是否已经存在现有的k-v对并根据情况更新优先级

现在对于优先级队列缓存使用了ekit的PriorityQueue作为优先级数据的存储，底层的实现使用了小跟堆的实现，暂时不支持对于优先级的修改

想法来源于PR #28 #20

行业分析

如果你知道有框架提供了类似功能，可以在这里描述，并且给出文档或者例子

redis的有序集合类型提供了类似的功能，通过zadd添加和修改key的优先级，时间复杂度为O(log(n))，修改的方式如下
有序集合类型主要使用了哈希表结合跳表的数据结构，还有一定条件下使用类似压缩列表的类型
https://redis.io/docs/data-types/sorted-sets/
实现上使用了删除元素后重复插入的方案（3.0版本）

官方的heap包提供了一个在堆元素修改之后重新堆化的API，只需要指定某个元素在堆中的索引，就可以使得元素在堆中的位置正确
实现与插入和删除元素类似，尝试向下堆化（对应插入）之后再尝试向上堆化（对应删除），但是执行路径相比删除后重新插入更短

https://github.com/golang/go/blob/master/src/container/heap/heap.go

可行方案

如果你有设计思路或者解决方案，请在这里提供。你可以提供多个方案，并且给出自己的选择

方案一：
红黑树+跳表
红黑树用于键值对的查找，插入删除查找时间复杂度均为O(log(n))
跳表用于键值对的查找，插入删除查找时间复杂度平均为O(log(n))，最差为O(n)
之后的更新方法就是

func (r *RBTreePriorityCache) Set(_ context.Context, key string, val any, expiration time.Duration) error {
        // 红黑树查找key 平均时间复杂度O(log(n))
        // if 找不到 创建节点并插入 平均时间复杂度 O(log(n)) + O(log(n))
        // if 找到更新删除节点并重新插入 平均时间复杂度 rbTree插入+skipList删除+skipList插入 O(log(n)) + O(log(n)) + O(log(n))
}

方案二：
红黑树 + 堆 + 哈希表
红黑树用于键值对的查找，插入删除查找时间复杂度均为O(log(n))
堆用于存储优先级队列，插入删除时间复杂度均为O(log(n))，重新堆化复杂度最坏O(log(n))，弹出复杂度为O(1)
哈希表用于存储key对应的元素在堆中的索引，用于定位堆中元素并重新堆化，插入删除查找时间复杂度O(1)

func (r *RBTreePriorityCache) Set(_ context.Context, key string, val any, expiration time.Duration) error {
        // 红黑树查找key 平均时间复杂度O(log(n))
        // if 找不到 创建节点并插入 平均时间复杂度 O(log(n)) + O(log(n)) + O(1)
        // if 找到节点更新重新堆化 平均时间复杂度 堆化+哈希表查找 O(log(n)) + O(1)

方案三：
红黑树 + 优先级队列
沿用现在的数据结构，更新优先级采用优先级队列删除节点再添加节点

func (r *RBTreePriorityCache) Set(_ context.Context, key string, val any, expiration time.Duration) error {
        // 红黑树查找key 平均时间复杂度O(log(n))
        // if 找不到 创建节点并插入 平均时间复杂度 O(log(n)) + O(log(n)) 
        // if 找到节点删除节点重新插入节点 平均时间复杂度 rbTree插入+queue删除(延迟)+queue插入   O(log(n)) + O(log(n))  + O(log(n)) 

目前暂时倾向方案二，不过实现上感觉比较难复用ekit的PriorityQueue，原因是哈希表和堆耦合性比较强，堆中元素在堆化过程中交换索引需要更新到哈希表中，需要斟酌一下怎么实现

其它

任何你觉得有利于解决问题的补充说明

两个讨论的帖子
https://www.reddit.com/r/computerscience/comments/x3f8zo/dynamic_priority_queue/?onetap_auto=true
https://stackoverflow.com/questions/2288241/priority-queue-with-dynamic-item-priorities

一篇论文
https://ceur-ws.org/Vol-1525/paper-13.pdf

你使用的是 ecache 哪个版本?

你设置的的 Go 环境?

上传 go env 的结果

[flycash]

我个人倾向于方案一，因为它可以让我们少维护一个数据结构。

而且我们在删除的时候。可以通过树形结构（其实这个部分也可以是哈希结构）找到节点，这个节点本身也处于一个跳表中。如果这个跳表是利用链表来实现的，那么调整优先级，就是把这个节点从跳表里面摘掉，然后再找一个合适的位置。

我感觉，我们可以先考虑提供一个跳表的优先级队列。

堆结构的优先级队列，对删除实在太不友好。