对于优先级队列和时间轮的了解，是始于一个issue：Add expirable LRU implementation。

针对一个需要周期判断是否过期的List时，开发组给出的意见是，使用优先级队列。

1
2
3
sync.Mutex
items     map[interface{}]*list.Element
evictList *list.List

https://github.com/hashicorp/golang-lru/pull/68#discussion_r443223151

1
2
3
Rather than using a list where you have to keep scanning through, I think you'd be better off using a priority queue. See https://github.com/hashicorp/vault/tree/master/sdk/queue and the Golang doc it links to. That way you simply add items to the queue where the sorting is by expiration time and only have to keep track of the first item in the queue in terms of expiration. This would also let you get rid of Close; a simple one-off timer would be the only goroutine you need to keep checking the first element.

与其使用一个你必须不停遍历的List，我认为你最好使用一个优先级队列。查看https://github.com/hashicorp/vault/tree/master/sdk/queue及其链接到的Golang文档。这样你只需按到期时间的顺序添加到队列中，并且只需要监听队列中的第一项。`这也可以让你不用close`(不懂！！！); 开启一个goroutine，设置一个简单的计时器不断检查第一个item的到期时间。

priority_queue，优先级队列是借助的官方库实现的堆(container/heap)来实现的。

关于这个包，可以参考：Golang: 详解container/heap。

为什么使用优先级队列，issue中其实说的很清楚，因为在维护一个任务队列时，需要选择一定的时间间隔去轮询整个列表，任务是否到期，这个轮询时间也是一个开销，可能发生在你轮询时，任务到期时间已经过去了，就造成了任务时间不准的现象。

但优先级队列可以先按照时间先后，选出最接近当前时间的任务，再之后的操作中，我们只需要先关注这个任务的时间是否到期即可，这样就可以优化一下前面所提到的问题，提高执行效率。

另外，在https://github.com/robfig/cron项目中，看到很多开发者对作者提议修改list为优先级队列，或者是，时间轮，作者的意见是：

1
2
3
https://github.com/robfig/cron/issues/236#issuecomment-570744625

I don't believe that the extra complexity is necessary. It's hard to imagine a system with so many scheduled tasks that sorting them takes a measurable amount of time. Tasks can not be activated more often than once a second at the most, so I don't see any reason to optimize this case. Thanks for your interest

作者的意思是，基本上，不会出现巨大量的定时任务，而且任务一秒钟最多只能激活一次，没必要花费这个功夫把代码搞复杂。

我倒是理解作者的意思，这在他看来并不是性能瓶颈，没有必要做这些修改或过度的优化操作；

在我看的另一个博客中（技术分享之golang构建分布式任务系统），作者采用的是一种宽范围的定时器。

高性能定时器的实现，这里没有再使用时间轮，而是采用类似rocketmq定时器的实现。根据不同时间间隔的定时器放到不同的队列里。由于定时器的需求在于任务超时控制及数据清理，所以定时器的精度可粗化。

img