队列常见的使用场景:异步处理、系统解耦、数据同步、流量削峰,常见的种类有任务队列、消息队列、请求队列。
现在考虑这样一个问题:某某服务,用户需要在48小时之内评分;否则会自动评价为5星。
预备知识:某某服务必有订单,这些订单会存储到数据库里。
一个常见的做法是开启定时任务,每隔一段时间去轮询,发现订单超过48小时而没有评分,那么会自动评分。
这种做法有一些问题:
1)轮询间隔不好控制。如果太频繁,对CPU不友好;如果不及,则时效性太差。
2)订单可能有很多,全部查询出来效率很低(即使通过分页查询优化,也需要一个循环)
先提供两种思路:
1)java.util.concurrent.DelayQueue
缺点是这个队列是基于内存的,容量有限,而且重启之后会丢失消息;
2)redis 有序集合
zadd key 1513674550287 member,其中score是时间戳。有序集合按照score逆序排序。这个需要一个线程去轮询,但是成本很低,因为只需要查询集合第一个元素即可,况且redis 响应神速。
现在介绍的第三种方案:环形的任务队列,由数组实现,数组中元素是Set<Task>,数组长度是3600。
Task结构中有两个核心属性:
- Cycle-Num:当Current Index第几圈扫描到这个Slot时,执行任务
- Task-Function:需要执行的任务指针
启动一个Timer,每个一秒钟在移动一个slot,那转一圈正好需要一个小时。
如图,当前Current Index指向第一格,当有延时消息到达之后,例如希望3610秒之后,触发一个延时消息任务,只需:
- 计算这个Task应该放在哪一个slot,现在指向1,3610秒之后,应该是第11格,所以这个Task应该放在第11个slot的Set<Task>中
- 计算这个Task的Cycle-Num,由于环形队列是3600格,这个任务是3610秒后执行,所以应该绕3610/3600=1圈之后再执行,于是Cycle-Num=1
Current Index不停的移动,每秒移动到一个新slot,遍历slot中对应的Set<Task>,每个Task看Cycle-Num是不是0:
- 如果不是0,说明还需要多移动几圈,将Cycle-Num减1
- 如果是0,说明马上要执行这个Task了,取出Task-Funciton执行(可以用单独的线程来执行Task),并把这个Task从Set<Task>中删除。
Netty中的工具类HashedWheelTimer的原理与这种环形的延迟队列相似。
参考资料:1分钟实现“延迟消息”功能