← 返回目录

小结一下

第 69 / 73 卷

图 93-1
图 93-1

小结一下

也是利用优先队列实现的,元素通过实现 Delayed 接口来返回延迟的时间。不过延迟队列就是个容器,需要其他线程来获取和执行任务。

这下是搞明白了 Timer、ScheduledThreadPool 和 DelayQueue,总结的说下它们都是通过优先队列来获取最早需要执行的任务,因此插入和删除任务的时间复杂度都为O(logn),并且 Timer、

ScheduledThreadPool 的周期性任务是通过重置任务的下一次执行时间来完成的。

问题就出在时间复杂度上,插入删除时间复杂度是O(logn),那么假设频繁插入删除次数为 m,总的时间复杂度就是O(mlogn),这种时间复杂度满足不了 Kafka 这类中间件对性能的要求,而时间轮算法的

插入删除时间复杂度是O(1)。我们来看看时间轮算法是如何实现的。

时间轮算法

俗话说艺术源于生活,技术也能从日常生活中找到灵感。咱们先来看块表,嗯金色的表。

图 94-1
图 94-1

都看清楚了吧,时间轮就是和手表时钟很相似的存在。时间轮用环形数组实现,数组的每个元素可以称为槽,和 HashMap一样称呼。

槽的内部用双向链表存着待执行的任务,添加和删除的链表操作时间复杂度都是 O(1),槽位本身也指代时间精度,比如一秒扫一个槽,那么这个时间轮的最高精度就是 1 秒。

也就是说延迟 1.2 秒的任务和 1.5 秒的任务会被加入到同一个槽中,然后在 1 秒的时候遍历这个槽中的链表执行任务。

图 95-1
图 95-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. 1什么是消息队列
  2. 2服务解耦
  3. 3注意
  4. 4小结一下
  5. 5如何保证消息不丢失
  6. 6存储消息
  7. 7如果处理重复消息
  8. 8如何保证消息的有序性
  9. 9最后
  10. 10正确的回答姿势
  11. 11小结一下面试技巧
  12. 12面试官想问的是什么
  13. 13消息队列设计成推消息还是拉消息?RocketMQ和Kafka是怎么做的?
  14. 14拉模式
  15. 15长轮询
  16. 16Kafka 中的长轮询
  17. 17小结一下
  18. 18消息队列之事务消息?RocketMQ和Kafka是怎么做的?
  19. 19分布式事务
  20. 20RocketMQ 事务消息
  21. 21RocketMQ 事务消息源码分析
  22. 22Kafka 事务消息
  23. 23最后
  24. 24那 qmq 怎么做的呢?
  25. 25再来看 RocketMQ 和 QMQ
  26. 26最后
  27. 27Kafka 系列
  28. 28entrySize
  29. 29从Kafka的索引冷热分区到MySQL InnoDB的缓冲池管理
  30. 30Kafka日志段如何读写解析?
  31. 31以下为日志的定义
  32. 32日志段的读取
  33. 33情景剧
  34. 34简单说下ZooKeeper
  35. 35Controller 底层事件模型
  36. 36LeaderAndIsrRequest
  37. 37Controller选举流程源码分析
  38. 38ControllerEventManager:事件处理器
  39. 39KafkaController#process
  40. 40ControllerContext:元数据
  41. 41最后
  42. 42Reactor模式
  43. 43Kafka Broker 网络通信模型
  44. 44源码级别剖析网络通信模型
  45. 45请求处理优先级
  46. 46Kafka为什么要抛弃Zookeeper?
  47. 47那为什么要抛弃 ZooKeeper
  48. 48所以没了 Zookeeper 之后的 Kafka 的怎样的?
  49. 49最后
  50. 50RocketMQ 整体架构设计
  51. 51NameServer
  52. 52Producer 发消息流程
  53. 53自动创建主题的弊端
  54. 54Broker 的存储
  55. 55消息刷盘机制
  56. 56文件预分配和文件预热
  57. 57Consumer
  58. 58一些注意点
  59. 59Linux内核参数
  60. 60Kafka和RocketMQ底层存储揭秘,为什么能这么快?
  61. 61sendfile-零拷贝
  62. 62RocketMQ 和 Kafka 的应用
  63. 63文件预分配
  64. 64RocketMQ 小结
  65. 65RocketMQ & Kafka 对比
  66. 66番外篇:定时任务的终极实现--时间轮,在Netty和Kafka中如何应用的?为什么不用Timer、延时线程池?
  67. 67小结一下
  68. 68小结一下
  69. 69小结一下
  70. 70Netty中的时间轮
  71. 71小结一下
  72. 72小结一下
  73. 73总结