小结一下

小结一下
也是利用优先队列实现的,元素通过实现 Delayed 接口来返回延迟的时间。不过延迟队列就是个容器,需要其他线程来获取和执行任务。
这下是搞明白了 Timer、ScheduledThreadPool 和 DelayQueue,总结的说下它们都是通过优先队列来获取最早需要执行的任务,因此插入和删除任务的时间复杂度都为O(logn),并且 Timer、
ScheduledThreadPool 的周期性任务是通过重置任务的下一次执行时间来完成的。
问题就出在时间复杂度上,插入删除时间复杂度是O(logn),那么假设频繁插入删除次数为 m,总的时间复杂度就是O(mlogn),这种时间复杂度满足不了 Kafka 这类中间件对性能的要求,而时间轮算法的
插入删除时间复杂度是O(1)。我们来看看时间轮算法是如何实现的。
时间轮算法
俗话说艺术源于生活,技术也能从日常生活中找到灵感。咱们先来看块表,嗯金色的表。

都看清楚了吧,时间轮就是和手表时钟很相似的存在。时间轮用环形数组实现,数组的每个元素可以称为槽,和 HashMap一样称呼。
槽的内部用双向链表存着待执行的任务,添加和删除的链表操作时间复杂度都是 O(1),槽位本身也指代时间精度,比如一秒扫一个槽,那么这个时间轮的最高精度就是 1 秒。
也就是说延迟 1.2 秒的任务和 1.5 秒的任务会被加入到同一个槽中,然后在 1 秒的时候遍历这个槽中的链表执行任务。

从图中可以看到此时指针指向的是第一个槽,一共有八个槽0~7,假设槽的时间单位为 1 秒,现在要加入一个延时 5 秒的任务,计算方式就是 5 % 8 + 1 = 6,即放在槽位为 6,下标为 5 的那个槽中。更具体
的就是拼到槽的双向链表的尾部。
然后每秒指针顺时针移动一格,这样就扫到了下一格,遍历这格中的双向链表执行任务。然后再循环继续。
可以看到插入任务从计算槽位到插入链表,时间复杂度都是O(1)。那假设现在要加入一个50秒后执行的任务怎么办?这槽好像不够啊?难道要加槽嘛?和HashMap一样扩容?
不是的,常见有两种方式,一种是通过增加轮次的概念。50 % 8 + 1 = 3,即应该放在槽位是 3,下标是 2 的位置。然后 (50 - 1) / 8 = 6,即轮数记为 6。也就是说当循环 6 轮之后扫到下标的 2 的这个槽位会
触发这个任务。Netty 中的 HashedWheelTimer 使用的就是这种方式。
还有一种是通过多层次的时间轮,这个和我们的手表就更像了,像我们秒针走一圈,分针走一格,分针走一圈,时针走一格。
多层次时间轮就是这样实现的。假设上图就是第一层,那么第一层走了一圈,第二层就走一格,可以得知第二层的一格就是8秒,假设第二层也是 8 个槽,那么第二层走一圈,第三层走一格,可以得知第三
层一格就是 64 秒。那么一格三层,每层8个槽,一共 24 个槽时间轮就可以处理最多延迟 512 秒的任务。
全站分卷索引 · 73 卷
- 1什么是消息队列
- 2服务解耦
- 3注意
- 4小结一下
- 5如何保证消息不丢失
- 6存储消息
- 7如果处理重复消息
- 8如何保证消息的有序性
- 9最后
- 10正确的回答姿势
- 11小结一下面试技巧
- 12面试官想问的是什么
- 13消息队列设计成推消息还是拉消息?RocketMQ和Kafka是怎么做的?
- 14拉模式
- 15长轮询
- 16Kafka 中的长轮询
- 17小结一下
- 18消息队列之事务消息?RocketMQ和Kafka是怎么做的?
- 19分布式事务
- 20RocketMQ 事务消息
- 21RocketMQ 事务消息源码分析
- 22Kafka 事务消息
- 23最后
- 24那 qmq 怎么做的呢?
- 25再来看 RocketMQ 和 QMQ
- 26最后
- 27Kafka 系列
- 28entrySize
- 29从Kafka的索引冷热分区到MySQL InnoDB的缓冲池管理
- 30Kafka日志段如何读写解析?
- 31以下为日志的定义
- 32日志段的读取
- 33情景剧
- 34简单说下ZooKeeper
- 35Controller 底层事件模型
- 36LeaderAndIsrRequest
- 37Controller选举流程源码分析
- 38ControllerEventManager:事件处理器
- 39KafkaController#process
- 40ControllerContext:元数据
- 41最后
- 42Reactor模式
- 43Kafka Broker 网络通信模型
- 44源码级别剖析网络通信模型
- 45请求处理优先级
- 46Kafka为什么要抛弃Zookeeper?
- 47那为什么要抛弃 ZooKeeper
- 48所以没了 Zookeeper 之后的 Kafka 的怎样的?
- 49最后
- 50RocketMQ 整体架构设计
- 51NameServer
- 52Producer 发消息流程
- 53自动创建主题的弊端
- 54Broker 的存储
- 55消息刷盘机制
- 56文件预分配和文件预热
- 57Consumer
- 58一些注意点
- 59Linux内核参数
- 60Kafka和RocketMQ底层存储揭秘,为什么能这么快?
- 61sendfile-零拷贝
- 62RocketMQ 和 Kafka 的应用
- 63文件预分配
- 64RocketMQ 小结
- 65RocketMQ & Kafka 对比
- 66番外篇:定时任务的终极实现--时间轮,在Netty和Kafka中如何应用的?为什么不用Timer、延时线程池?
- 67小结一下
- 68小结一下
- 69小结一下
- 70Netty中的时间轮
- 71小结一下
- 72小结一下
- 73总结