HashedWheelTimer时间轮定时任务原理分析

article/2025/9/5 0:40:03

一、示例代码

 

HashedWheelTimer时间轮是一个高性能，低消耗的数据结构，它适合用非准实时，延迟的短平快任务，例如心跳检测。

时间轮是一种非常惊艳的数据结构。其在Linux内核中使用广泛，是Linux内核定时器的实现方法和基础之一。Netty内部基于时间轮实现了一个HashedWheelTimer来优化I/O超时的检测，

由于Netty动辄管理100w+的连接，每一个连接都会有很多超时任务。比如发送超时、心跳检测间隔等，如果每一个定时任务都启动一个Timer，不仅低效，而且会消耗大量的资源。
在Netty中的一个典型应用场景是判断某个连接是否idle，如果idle（如客户端由于网络原因导致到服务器的心跳无法送达），则服务器会主动断开连接，释放资源。得益于Netty NIO的优异性能，基于Netty开发的服务器可以维持大量的长连接，单台8核16G的云主机可以同时维持几十万长连接，及时掐掉不活跃的连接就显得尤其重要。

HashedWheelTimer本质是一种类似延迟任务队列的实现，那么它的特点就是上述所说的，适用于对时效性不高的，可快速执行的，大量这样的“小”任务，能够做到高性能，低消耗。
例如：

  • 心跳检测
  • session、请求是否timeout
    业务场景则有：
  • 用户下单后发短信
  • 下单之后15分钟，如果用户不付款就自动取消订单
@Slf4j
public class HashWheelTimerTest {int nIndex = 0;public void testHashWheelTimer(){log.debug(" hash wheel time--> start." );HashedWheelTimer hashedWheelTimer = new HashedWheelTimer();for (int i = 0; i < 10; i++) {hashedWheelTimer.newTimeout(new TimerTask() {@Overridepublic void run(Timeout timeout) throws Exception {log.debug(" wheel timer run nIndex:{},timeout:{}",nIndex++,timeout.isExpired() );}},i + 1  ,TimeUnit.SECONDS);}log.debug(" hash wheel  time--> end." );}public static void main(String[] args) {HashWheelTimerTest hashWheelTimerTest = new HashWheelTimerTest();hashWheelTimerTest.testHashWheelTimer();try {System.in.read();} catch (IOException e) {e.printStackTrace();}}
}

二、创建时间轮定时器对象

1.类成员变量分析

tick，时刻即轮上的指针，指向某一个格子
ticksPerWheel，轮盘一圈包含的格子数，也就是轮盘总刻度数
tickDuration，时刻间距，也就是指针走完一个格子的时长，值越小，精度越高。
roundDuration，计时周期，轮盘指针走完一圈耗时，roundDuration=ticksPerWheel∗tickDuration。当任务的延期时长delay超出计时周期时，任务放入对应桶中的同时保存剩余圈数：roundsRemaining=delay / roundDuration
bucket，相邻刻度之间为桶，桶中以链表或其他形式存放延时任务。当指针走过该桶时，桶中超时的延时任务开始启动
 

public class HashedWheelTimer implements Timer {private final Worker worker = new Worker();  //任务执行工作线程，实现runnableprivate final Thread workerThread; //工作线程对象。private final long tickDuration; //每个时钟小格子的时间长度。private final HashedWheelBucket[] wheel; //时间轮子数组，如果时钟有512个格子，则这个值的长度为512private final int mask;  //时间轮数组长度-1，用于计算任务位于哪个格子，进行掩码。private final CountDownLatch startTimeInitialized = new CountDownLatch(1);private final Queue<HashedWheelTimeout> timeouts = PlatformDependent.newMpscQueue();
// 待执行的延时任务。private final long maxPendingTimeouts;private volatile long startTime; //工作线程开始时间。public HashedWheelTimer(ThreadFactory threadFactory,long tickDuration, TimeUnit unit, int ticksPerWheel, boolean leakDetection,long maxPendingTimeouts) {// Normalize ticksPerWheel to power of two and initialize the wheel.wheel = createWheel(ticksPerWheel);mask = wheel.length - 1;long duration = unit.toNanos(tickDuration);this.tickDuration = duration;workerThread = threadFactory.newThread(worker);this.maxPendingTimeouts = maxPendingTimeouts;}

2.添加任务分析， 这里就是把task加入到Queue<HashedWheelTimeout> timeouts这个待执行的延迟任务队列中。

  public Timeout newTimeout(TimerTask task, long delay, TimeUnit unit) {long pendingTimeoutsCount = pendingTimeouts.incrementAndGet();start();long deadline = System.nanoTime() + unit.toNanos(delay) - startTime;HashedWheelTimeout timeout = new HashedWheelTimeout(this, task, deadline);timeouts.add(timeout);return timeout;}

 三、定时执行任务。

    1.由workThread中的worker这个对象来负责执行。

  1. 时间轮运行的时候首先会记录一下启动时间（startTime），然后调用startTimeInitialized释放外层的等待线程；
  2. 进入dowhile循环，调用waitForNextTick睡眠等待到下一次的tick指针的跳动，并返回当前时间减去startTime作为deadline
  3. 由于mask= wheel.length -1 ，wheel是2的次方数，所以可以直接用tick & mask 计算出此次在wheel中的槽位
  4. 调用processCancelledTasks将cancelledTimeouts队列中的任务取出来，并将当前的任务从时间轮中移除
  5. 调用transferTimeoutsToBuckets方法将timeouts队列中缓存的数据取出加入到时间轮中
  6. 运行目前指针指向的槽位中的bucket链表数据
  private final class Worker implements Runnable {private final Set<Timeout> unprocessedTimeouts = new HashSet<Timeout>();private long tick;@Overridepublic void run() {// Initialize the startTime.startTime = System.nanoTime();startTimeInitialized.countDown();do {final long deadline = waitForNextTick();if (deadline > 0) {int idx = (int) (tick & mask);processCancelledTasks();HashedWheelBucket bucket =wheel[idx];transferTimeoutsToBuckets();bucket.expireTimeouts(deadline);tick++;}} while (WORKER_STATE_UPDATER.get(HashedWheelTimer.this) == WORKER_STATE_STARTED);}

2.时间轮指针跳动

 private long waitForNextTick() {//计算下一个tick的时间，long deadline = tickDuration * (tick + 1);for (;;) {final long currentTime = System.nanoTime() - startTime;//根据当前计算需要sleep的时间。这里加了999999是因为向上取整了1毫秒，假如距离下一个tick的时间为2000010纳秒，那如果sleep 2毫秒是不够的，所以需要多sleep 1毫秒。long sleepTimeMs = (deadline - currentTime + 999999) / 1000000;//sleepTimeMs <=0 说明下一个tick的时间到了，说明上一个tick执行的时间“太久”了，所以直接返回就好了，不需要sleepif (sleepTimeMs <= 0) {//currentTime == Long.MIN_VALUE 这个判断不是很理解if (currentTime == Long.MIN_VALUE) {return -Long.MAX_VALUE;} else {return currentTime;}}//直接sleep等待try {Thread.sleep(sleepTimeMs);} catch (InterruptedException ignored) {//Worker被中断，如果是关闭了则返回负数，表示不会执行下一个tickif (WORKER_STATE_UPDATER.get(HashedWheelTimer.this) == WORKER_STATE_SHUTDOWN) {return Long.MIN_VALUE;}}}}

3.转移任务到时间轮中

在调用时间轮的方法加入任务的时候并没有直接加入到时间轮中，而是缓存到了timeouts队列中，所以在运行的时候需要将timeouts队列中的任务转移到时间轮数据的链表中

private void transferTimeoutsToBuckets() {//最多取队列的100000的元素出来for (int i = 0; i < 100000; i++) {HashedWheelTimeout timeout = timeouts.poll();if (timeout == null) {// all processedbreak;}//如果timeout被取消了则不做处理if (timeout.state() == HashedWheelTimeout.ST_CANCELLED) {// Was cancelled in the meantime.continue;}//计算位于实践论的层数long calculated = timeout.deadline / tickDuration;timeout.remainingRounds = (calculated - tick) / wheel.length;//就是timeout已经到期了，也不能放到之前的tick中final long ticks = Math.max(calculated, tick); // Ensure we don't schedule for past.//计算所在bucket下标，并放进去int stopIndex = (int) (ticks & mask);HashedWheelBucket bucket = wheel[stopIndex];//又是类似链表插入节点的操作bucket.addTimeout(timeout);}}

在这个转移方法中，写死了一个循环，每次都只转移10万个任务。

然后根据HashedWheelTimeout的deadline延迟时间计算出时间轮需要运行多少次才能运行当前的任务，如果当前的任务延迟时间大于时间轮跑一圈所需要的时间，那么就计算需要跑几圈才能到这个任务运行。

最后计算出该任务在时间轮中的槽位，添加到时间轮的链表中。

4.运行时间轮中的任务

当指针跳到时间轮的槽位的时间，会将槽位的HashedWheelBucket取出来，然后遍历链表，运行其中到期的任务。

public void expireTimeouts(long deadline) {HashedWheelTimeout timeout = head;//把bucket的所有timeout取出来执行while (timeout != null) {HashedWheelTimeout next = timeout.next;if (timeout.remainingRounds <= 0) {next = remove(timeout);if (timeout.deadline <= deadline) {//timeout的真正执行timeout.expire();} else {// The timeout was placed into a wrong slot. This should never happen.throw new IllegalStateException(String.format("timeout.deadline (%d) > deadline (%d)", timeout.deadline, deadline));}//该timeout被取消了则移除掉    } else if (timeout.isCancelled()) {next = remove(timeout);//否则层数减一，等待下一轮的到来} else {timeout.remainingRounds --;}timeout = next;}}

HashedWheelBucket是一个链表，所以我们需要从head节点往下进行遍历。如果链表没有遍历到链表尾部那么就继续往下遍历。

获取的timeout节点节点，如果剩余轮数remainingRounds大于0，那么就说明要到下一圈才能运行，所以将剩余轮数减一；

如果当前剩余轮数小于等于零了，那么就将当前节点从bucket链表中移除，并判断一下当前的时间是否大于timeout的延迟时间，如果是则调用timeout的expire执行任务。


http://chatgpt.dhexx.cn/article/nMIfdEFl.shtml

相关文章

SpringMVC中定时任务配置

SpringMVC中定时任务配置

在项目中使用定时任务是常有的事&#xff0c;比如每天定时进行数据同步或者备份等等。 以前在从事C语言开发的时候&#xff0c;定时任务都是通过写个shell脚本&#xff0c;然后添加到linux定时任务中进行调度的。 现在使用SpringMVC之后&#xff0c;一起都变得简单了o(∩_∩)…
阅读更多...
c语言1.5秒定时程序,C语言实现简单的定时器

c语言1.5秒定时程序,C语言实现简单的定时器

本文实例为大家分享了C语言实现简单的定时器的具体代码&#xff0c;供大家参考&#xff0c;具体内容如下 1.代码分析 2.代码 #include #include #include #ifndef CLOCKS_PER_SEC #define CLOCKS_PER_SEC 1000 #endif int main( void ) { clock_t start; long count 1; sta…
阅读更多...
c语言自动执行一分钟,C语言操作时间函数，实现定时执行某个任务的小例子

c语言自动执行一分钟,C语言操作时间函数，实现定时执行某个任务的小例子

https://m.toutiao.com/is/JcccKk6/ 时间操作函数在实际项目开发中会经常用到&#xff0c;最近做项目也正好用到就正好顺便整理一下。 时间概述 由上图可知&#xff1a;通过系统调用函数time()可以从内核获得一个类型为time_t的1个值&#xff0c;该值叫calendar时间&#xff0c…
阅读更多...
C语言实现任务调度与定时器

C语言实现任务调度与定时器

代码实现是在xl2tpd的源码中get到的&#xff0c;感觉很有意思的一段代码。基本功能就是实现定时器&#xff0c;时间到后从定时队列中取出&#xff0c;然后完成指定的任务。 1. schedule.c代码(自己添加了main函数&#xff0c;用来调试) /** Layer Two Tunnelling Protocol Da…
阅读更多...
c语言 精确定时程序,微调定时精确时间

c语言 精确定时程序,微调定时精确时间

1.定时器&蜂鸣器 一般定时器中断函数里的内容最好是能够快速地去执行完，比如只执行几条简单的语句，这样与主函数配合才会使程序更加高效。前期教学里，我们只使用定时器中断负责某个IO引脚间隔跳变或者使一个变量间隔自加1的简单语句。 比如我们现在要实现间隔50ms左右的…
阅读更多...
c语言实现任务调度器

c语言实现任务调度器

一、介绍 调度器是常用的一种编程框架&#xff0c;也是操作系统的拆分多任务的核心&#xff0c;比如单片机的裸机程序框架&#xff0c;网络协议栈的框架如can网关、485网关等等&#xff0c;使用场合比较多&#xff0c;是做稳定产品比较常用的编程技术 二、原理 1、超级循环 v…
阅读更多...
C语言定时1分钟程序,C语言操作时间函数，实现定时执行某个任务小程序

C语言定时1分钟程序,C语言操作时间函数，实现定时执行某个任务小程序

时间操作函数在实际项目开发中会经常用到，最近做项目也正好用到就正好顺便整理一下。 时间概述 由上图可知：通过系统调用函数time()可以从内核获得一个类型为time_t的1个值，该值叫calendar时间，即从1970年1月1日的UTC时间从0时0分0妙算起到现在所经过的秒数。而该时间也用于…
阅读更多...
vivado 2018.2官方下载

vivado 2018.2官方下载

前几天想装vivado&#xff0c;奈何学长给的文件安装出了点问题&#xff0c;百度网盘下载20g又太慢&#xff0c;去官网看了一下&#xff0c;发现官网的安装器挺小的。 下载地址&#xff1a;https://china.xilinx.com/support/download.html 需要再注册一下就好。 之后的安装步骤…
阅读更多...
vivado2021.1安装

vivado2021.1安装

首先需要在官网注册一个账号&#xff0c;安装软件时需要使用。 账号注册连接&#xff1a;xilink账号注册 vivado下载链接 xilink官网下载(使用官网下载需要注册账号&#xff0c;下载免费&#xff09; vivado阿里云盘下载 vivado licence阿里云盘下载 官网下载选择此项 下载完成…
阅读更多...
Vivado 2020.1 开放下载，中文资料随贴奉送

Vivado 2020.1 开放下载，中文资料随贴奉送

Vivado 2020.1 开放下载了&#xff01;&#xff01; 以下都是重点&#xff01; 新 功能 Vivado 2020.1 新增以下功能&#xff1a; 能够将完整的图像或选定的产品作为 Web 安装程序的一部分增强的地址映射&#xff0c;用于实时错误高亮显示和交叉探测Report QoR Suggestions 功能…
阅读更多...
vivado/vitis2020.2安装下载教程（适用于2019后版本）

vivado/vitis2020.2安装下载教程（适用于2019后版本）

1.解压安装包到当前文件夹。 2.右击以管理员身份运行。 3.提示下载最新的版本&#xff0c;不要下载&#xff0c;点击【Continue】&#xff0c;如果没弹出来这个就不管&#xff0c;然后点击【next】。 4.选择安装工具&#xff0c;选择安装完全体【vitis】&#xff0c;继续…
阅读更多...
FPGA开发软件（vivado + modelsim）环境搭建（附详细安装步骤+软件下载）

FPGA开发软件（vivado + modelsim）环境搭建（附详细安装步骤+软件下载）

本文详细介绍了vivado软件和modelsim软件的安装&#xff0c;以及vivado中配置modelsim仿真设置&#xff0c;每一步都加文字说明和图片。 一、软件安装包下载 1、vivado vivado版本很多&#xff0c;目前最新的已更新到vivado2022.2&#xff0c;版本越高&#xff0c;安装包越大&…
阅读更多...
基于Vivado的程序下载

基于Vivado的程序下载

Vivado下bit文件下载步骤 将电源、下载器与板卡连接&#xff0c;打开Vivado工程&#xff0c;参考《基于TcL脚本生成Vivado工程及编译》文档编译工程&#xff0c;生成对应的bit文件。 打开板卡电源开关&#xff0c;找到右下角的”Open Hardware Manager”展开&#xff0c;右击…
阅读更多...
Vivado® ML Editions 2022.2 最新更新（附下载链接）

Vivado® ML Editions 2022.2 最新更新（附下载链接）

本文由 AMD Vivado ML Editions 产品营销经理 Snehal Ullagaddi 撰写 AMD XILINX 近期全新推出了 Vivado ML Editions 2022.2 版给工具集带来了多项重大改进与增强功能。 主要亮点 推出电源设计管理器&#xff1a; 电源设计管理器 (PDM) 是全新的下一代功耗评估平台&#xff…
阅读更多...
Vivado全版本下载分享

Vivado全版本下载分享

Vivado是由Xilinx公司开发的一款用于FPGA设计和开发的综合设计环境。它包括了高层次综合&#xff08;HLS&#xff09;、逻辑设计、约束管理、IP核管理、仿真、综合、实现和调试等功能&#xff0c;支持面向最新FPGA器件的设计。 这里分享一下Vivado的电脑安装配置推荐&#xff…
阅读更多...
Vivado2019.2下载（官网百度云）与安装（手把手）

Vivado2019.2下载（官网百度云）与安装（手把手）

龙芯杯对于vivado版本的要求&#xff1a; Vivado Design Suite HL WebPACK™ 版是革命性设计套件的免费版本。我们用它&#xff0c;能满足龙芯杯的需要&#xff0c;而且不用license 区别如下&#xff1a; 下载地址 记得创建xilinx账号或者登陆&#xff01;&#xff01;&#…
阅读更多...
Vivado2018.3的下载安装

Vivado2018.3的下载安装

文章目录 一、下载二、安装过程三、参考资料 一、下载 Vivado 官网下载地址&#xff1a;https://www.xilinx.com/support/download.html百度网盘地址&#xff1a;https://pan.baidu.com/s/1j1lkZJrTDNJB-2dCI0et_g &#xff08;提取码&#xff1a;s2lg &#xff09; 说明&…
阅读更多...
XILINX VIVADO2018.2官方下载全教程记录.

XILINX VIVADO2018.2官方下载全教程记录.

毕设涉及FPGA&#xff0c;准备记录一下准备过程。 首先是Vivado的下载过程。 1.进入赛灵思下载官网。(https://www.xilinx.com/support/download/index.html/content/xilinx/en/downloadNav/vivado-design-tools/archive.html) 2.注册用户&#xff08;已有账号跳过&#xff09;…
阅读更多...
官网下载 Vivado

官网下载 Vivado

1、使用 谷歌浏览器 点击如下链接进入下载界面 https://www.xilinx.com/support/download/index.html/content/xilinx/en/downloadNav/vivado-design-tools/archive.html 2、下一步&#xff0c;登陆你的XILINX账号&#xff0c;然后就可以下载了
阅读更多...
Vivado官网下载

Vivado官网下载

https://www.xilinx.com/support/download.html &#xff08;需要注册一个AMD账号&#xff0c;之后即可免费下载&#xff09; 下载成功后开始安装&#xff1a; 默认配置即可&#xff0c;50多G
阅读更多...
推荐文章

Copyright @ 2022~2023