Netty源码阅读9——时间轮

Posted by 皮皮潘 on 12-06,2021

时间轮主要处理延时任务问题,jdk原生地提供了Timer和ScheduledExecuterService解决了该问题,前者采用了绝对时间+最小堆实现,后者采用了DelayQueue和多线程基于生产者消费者模式实现,它们在增加任务和取消任务上都需有O(logn)的时间复杂度,在面对大量任务时会出现性能问题i,因此Netty采用时间轮解决对应问题,其具体实现是HashedWheelTimer,时间轮的核心概念在于:环状数组,Tick以及Slot,其结构如下:
IMG_0005.PNG
时间轮可以理解为一种环形结构,像钟表一样被分为多个 slot 槽位。每个 slot 代表一个时间段,每个 slot 中可以存放多个任务,使用的是链表结构保存该时间段到期的所有任务。时间轮通过一个时针随着时间一个个 slot 转动,并执行 slot 中的所有到期任务。

在Netty具体实现中,使用单个worker线程按照Tick时间间隔sleep一小会儿,然后遍历下一个Tick,并执行所有在当前Tick应该执行的任务,其中每个Tick指向的Slot对应一个HashdWheelBucket,其中存储了所有在当前Tick应该执行的任务,并通过HashedWheelTimeout进行封装同时采用双向链表的方式进行链接,这里需要注意的是Slot中不仅仅存储当前Tick应该执行的任务,还存储了N轮后也会落在该Tick上的Task,因此HashedWheelTimeout还封装了对应任务的轮次round,(为了性能Tick使用&计算,轮次使用>>>计算),当round为0时执行任务,反之round减一,具体结构如下:
IMG_0004.PNG

除了上述实现之外,Netty会将错过时间了的任务放到当前Tick中处理来保证每个任务都会执行到。另外为了解决多线程增加任务的并发冲突问题,Netty使用了一个SCMQ队列来接受延时任务,并让worker线程在每次检查tick和执行任务之前将队列中的任务计算好deadline和tick次数并放入到TimeWheel中。最后为了解决绝对系统时间问题,Netty会在WheelTimer启动时记录当前的时间作为启动时间,之后所有的时间deadline计算都基于启动时间进行相对时间的计算HashedWheelTimer 并不是十全十美的,使用的时候需要清楚它存在的问题:

  • 如果长时间没有到期任务,那么会存在时间轮空推进的现象。

  • 只适用于处理耗时较短的任务,由于 Worker 是单线程的,如果一个任务执行的时间过长,会造成 Worker 线程阻塞。

  • 相比传统定时器的实现方式,内存占用较大。

  • 不同类型任务的延时粒度不同,为了满足小延时粒度,这会造成单个slot中存有个大延时粒度的任务需要很多轮才能执行到,从而使得链表很长,遍历时间无意义增加。

其中为了解决问题4,Kafka采用了多级时间轮,类似于时分秒,秒转了一圈分才会转一格
IMG_0006.PNG