时间轮(Timing Wheel)案例和原理

article/2025/7/28 4:08:45

什么是时间轮(Timing Wheel)

时间轮(Timing Wheel)是George Varghese和Tony Lauck在1996年的论文'Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility'实现的，它在Linux内核中使用广泛，是Linux内核定时器的实现方法和基础之一。

时间轮(Timing Wheel)是一种环形的数据结构，就像一个时钟可以分成很多格子（Tick)，每个格子代表时间的间隔，它指向存储的具体任务（timerTask）的一个链表。

​

以上述在论文中的图片例子，这里一个轮子包含8个格子（Tick), 每个tick是一秒钟；

任务的添加：如果一个任务要在17秒后执行，那么它需要转2轮，最终加到Tick=1位置的链表中。

任务的执行：在时钟转2Round到Tick=1的位置，开始执行这个位置指向的链表中的这个任务。（# 这里表示剩余需要转几轮再执行这个任务）

Netty的HashedWheelTimer要解决什么问题

HashedWheelTimer是Netty根据时间轮(Timing Wheel)开发的工具类，它要解决什么问题呢？这里面有两个要点：延迟任务 + 低时效性。@pdai

在Netty中的一个典型应用场景是判断某个连接是否idle，如果idle（如客户端由于网络原因导致到服务器的心跳无法送达），则服务器会主动断开连接，释放资源。判断连接是否idle是通过定时任务完成的，但是Netty可能维持数百万级别的长连接，对每个连接去定义一个定时任务是不可行的，所以如何提升I/O超时调度的效率呢？

Netty根据时间轮(Timing Wheel)开发了HashedWheelTimer工具类，用来优化I/O超时调度(本质上是延迟任务）；之所以采用时间轮(Timing Wheel)的结构还有一个很重要的原因是I/O超时这种类型的任务对时效性不需要非常精准。

HashedWheelTimer的使用方式

在了解时间轮（Timing Wheel)和Netty的HashedWheelTimer要解决的问题后，我们看下HashedWheelTimer的使用方式

通过构造函数看主要参数

 

 

public HashedWheelTimer( ThreadFactory threadFactory, long tickDuration, TimeUnit unit, int ticksPerWheel, boolean leakDetection, long maxPendingTimeouts, Executor taskExecutor) { }
 

具体参数说明如下：
 

  •  
    threadFactory：线程工厂，用于创建工作线程， 默认是Executors.defaultThreadFactory()
     
  •  
    tickDuration：tick的周期，即多久tick一次
     
  •  
    unit: tick周期的单位
     
  •  
    ticksPerWheel：时间轮的长度，一圈下来有多少格
     
  •  
    leakDetection：是否开启内存泄漏检测，默认是true
     
  •  
    maxPendingTimeouts：最多执行的任务数，默认是-1，即不限制。在高并发量情况下才会设置这个参数。
     
 

 

实现案例
 

 
这里展示下HashedWheelTimer的基本使用案例。@pdai
 

 

 

Pom依赖
 

引入pom的依赖
 

 

 

<dependency> <groupId>io.netty</groupId> <artifactId>netty-all</artifactId> <version>4.1.77.Final</version> </dependency>
 

 

2个简单例子
 

例子1：5秒后执行TimerTask
 

 

 

@SneakyThrows public static void simpleHashedWheelTimer() { log.info("init task 1..."); HashedWheelTimer timer = new HashedWheelTimer(1, TimeUnit.SECONDS, 8); // add a new timeout timer.newTimeout(timeout -> { log.info("running task 1..."); }, 5, TimeUnit.SECONDS); }
 

执行结果如下：
 

 

 

23:32:21.364 [main] INFO tech.pdai.springboot.schedule.timer.netty.HashedWheelTimerTester - init task 1... ... 23:32:27.454 [pool-1-thread-1] INFO tech.pdai.springboot.schedule.timer.netty.HashedWheelTimerTester - running task 1...
 

例子2：任务失效后cancel并让它重新在3秒后执行。
 

 

 

@SneakyThrows public static void reScheduleHashedWheelTimer() { log.info("init task 2..."); HashedWheelTimer timer = new HashedWheelTimer(1, TimeUnit.SECONDS, 8); Thread.sleep(5000); // add a new timeout Timeout tm = timer.newTimeout(timeout -> { log.info("running task 2..."); }, 5, TimeUnit.SECONDS); // cancel if (!tm.isExpired()) { log.info("cancel task 2..."); tm.cancel(); } // reschedule timer.newTimeout(tm.task(), 3, TimeUnit.SECONDS); }
 

 

23:28:36.408 [main] INFO tech.pdai.springboot.schedule.timer.netty.HashedWheelTimerTester - init task 2... 23:28:41.412 [main] INFO tech.pdai.springboot.schedule.timer.netty.HashedWheelTimerTester - cancel task 2... 23:28:45.414 [pool-2-thread-1] INFO tech.pdai.springboot.schedule.timer.netty.HashedWheelTimerTester - running task 2...
 

 

进一步理解
 

 
我们通过如下问题进一步理解HashedWheelTimer。@pdai
 

 

 

HashedWheelTimer是如何实现的?
 

 
简单看下HashedWheelTimer是如何实现的
 

 

 

 

​
 

 

 

  •  
    Worker：worker工作线程主要负责任务调度触发，单线程运行。
     
  •  
    HashedWheelBucket： 时间轮上面的格子，内部持有HashedWheelTimeout组成的链表结构的头尾节点，多个格子组成的时间轮形成一圈又一圈的任务环
     
  •  
    HashedWheelTimeout： 往时间轮里面提交的任务会被封装成HashedWheelTimeout
     
 

构造函数
 

 

 

public HashedWheelTimer( ThreadFactory threadFactory, long tickDuration, TimeUnit unit, int ticksPerWheel, boolean leakDetection, long maxPendingTimeouts, Executor taskExecutor) { checkNotNull(threadFactory, "threadFactory"); checkNotNull(unit, "unit"); checkPositive(tickDuration, "tickDuration"); checkPositive(ticksPerWheel, "ticksPerWheel"); this.taskExecutor = checkNotNull(taskExecutor, "taskExecutor"); // Normalize ticksPerWheel to power of two and initialize the wheel. wheel = createWheel(ticksPerWheel); mask = wheel.length - 1; // Convert tickDuration to nanos. long duration = unit.toNanos(tickDuration); // Prevent overflow. if (duration >= Long.MAX_VALUE / wheel.length) { throw new IllegalArgumentException(String.format( "tickDuration: %d (expected: 0 < tickDuration in nanos < %d", tickDuration, Long.MAX_VALUE / wheel.length)); } if (duration < MILLISECOND_NANOS) { logger.warn("Configured tickDuration {} smaller than {}, using 1ms.", tickDuration, MILLISECOND_NANOS); this.tickDuration = MILLISECOND_NANOS; } else { this.tickDuration = duration; } workerThread = threadFactory.newThread(worker); leak = leakDetection || !workerThread.isDaemon() ? leakDetector.track(this) : null; this.maxPendingTimeouts = maxPendingTimeouts; if (INSTANCE_COUNTER.incrementAndGet() > INSTANCE_COUNT_LIMIT && WARNED_TOO_MANY_INSTANCES.compareAndSet(false, true)) { reportTooManyInstances(); } }
 

创建wheel
 

 

 

private static HashedWheelBucket[] createWheel(int ticksPerWheel) { //ticksPerWheel may not be greater than 2^30 checkInRange(ticksPerWheel, 1, 1073741824, "ticksPerWheel"); ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel); HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel]; for (int i = 0; i < wheel.length; i ++) { wheel[i] = new HashedWheelBucket(); } return wheel; } private static int normalizeTicksPerWheel(int ticksPerWheel) { int normalizedTicksPerWheel = 1; while (normalizedTicksPerWheel < ticksPerWheel) { normalizedTicksPerWheel <<= 1; } return normalizedTicksPerWheel; }
 

任务的添加
 

 

 

@Override public Timeout newTimeout(TimerTask task, long delay, TimeUnit unit) { checkNotNull(task, "task"); checkNotNull(unit, "unit"); long pendingTimeoutsCount = pendingTimeouts.incrementAndGet(); if (maxPendingTimeouts > 0 && pendingTimeoutsCount > maxPendingTimeouts) { pendingTimeouts.decrementAndGet(); throw new RejectedExecutionException("Number of pending timeouts (" + pendingTimeoutsCount + ") is greater than or equal to maximum allowed pending " + "timeouts (" + maxPendingTimeouts + ")"); } start(); // Add the timeout to the timeout queue which will be processed on the next tick. // During processing all the queued HashedWheelTimeouts will be added to the correct HashedWheelBucket. long deadline = System.nanoTime() + unit.toNanos(delay) - startTime; // Guard against overflow. if (delay > 0 && deadline < 0) { deadline = Long.MAX_VALUE; } HashedWheelTimeout timeout = new HashedWheelTimeout(this, task, deadline); timeouts.add(timeout); return timeout; }
 

执行方法
 

 

 

/** * Starts the background thread explicitly. The background thread will * start automatically on demand even if you did not call this method. * * @throws IllegalStateException if this timer has been * {@linkplain #stop() stopped} already */ public void start() { switch (WORKER_STATE_UPDATER.get(this)) { case WORKER_STATE_INIT: if (WORKER_STATE_UPDATER.compareAndSet(this, WORKER_STATE_INIT, WORKER_STATE_STARTED)) { workerThread.start(); } break; case WORKER_STATE_STARTED: break; case WORKER_STATE_SHUTDOWN: throw new IllegalStateException("cannot be started once stopped"); default: throw new Error("Invalid WorkerState"); } // Wait until the startTime is initialized by the worker. while (startTime == 0) { try { startTimeInitialized.await(); } catch (InterruptedException ignore) { // Ignore - it will be ready very soon. } } }
 

停止方法
 

 

 

@Override public Set<Timeout> stop() { if (Thread.currentThread() == workerThread) { throw new IllegalStateException( HashedWheelTimer.class.getSimpleName() + ".stop() cannot be called from " + TimerTask.class.getSimpleName()); } if (!WORKER_STATE_UPDATER.compareAndSet(this, WORKER_STATE_STARTED, WORKER_STATE_SHUTDOWN)) { // workerState can be 0 or 2 at this moment - let it always be 2. if (WORKER_STATE_UPDATER.getAndSet(this, WORKER_STATE_SHUTDOWN) != WORKER_STATE_SHUTDOWN) { INSTANCE_COUNTER.decrementAndGet(); if (leak != null) { boolean closed = leak.close(this); assert closed; } } return Collections.emptySet(); } try { boolean interrupted = false; while (workerThread.isAlive()) { workerThread.interrupt(); try { workerThread.join(100); } catch (InterruptedException ignored) { interrupted = true; } } if (interrupted) { Thread.currentThread().interrupt(); } } finally { INSTANCE_COUNTER.decrementAndGet(); if (leak != null) { boolean closed = leak.close(this); assert closed; } } return worker.unprocessedTimeouts(); }
 

 

什么是多级Timing Wheel?
 

多级的时间轮是比较好理解的，时钟是有小时，分钟，秒的，秒转一圈(Round)分钟就转一个格（Tick）, 分钟转一圈(Round)小时就转一格（Tick）











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












相关文章










时间轮(TimingWheel)








时间轮(TimingWheel)




一、什么是时间轮 时间轮其实就是一种环形的数据结构&#xff0c;可以想象成时钟&#xff0c;分成很多格子&#xff0c;一个格子代表一段时间&#xff08;这个时间越短&#xff0c;Timer的精度越高&#xff09;。并用一个双向链表存储放在该格子上的延时任务&#xff0c;同时一…




阅读更多...

















高性能定时器3——时间轮








高性能定时器3——时间轮




​ 在网络程序中我们通常要处理三种事件&#xff0c;网络I/O事件、信号以及定时事件&#xff0c;我们可以使用I/O复用系统调用&#xff08;select、poll、epoll&#xff09;将这三类事件进行统一处理。我们通常使用定时器来检测一个客户端的活动状态&#xff0c;服务器程序通常…




阅读更多...

















C#，斐波那契数列（Fibonacci Sequence）的八种算法与源代码








C#，斐波那契数列（Fibonacci Sequence）的八种算法与源代码




一、莱昂纳多斐波那契&#xff08;Leonardo Fibonacci&#xff09; 斐波那契公元1170年生于意大利比萨&#xff0c;卒于1250年&#xff0c;被人称作“比萨的莱昂纳多”&#xff0c;是一名闻名于欧洲的数学家&#xff0c;其主要的著作有《算盘书》、《实用几何》和《四艺经》等。…




阅读更多...

















matlab斐波那契数列画图,斐波拉契数列 斐波那契数列 matlab程序








matlab斐波那契数列画图,斐波拉契数列 斐波那契数列 matlab程序




斐波那契数列数列从第3项开始，每一项都等于前两项之和。 例子：数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368 应用： 生活斐波那契 斐波那契数列中的斐波脾气有点大，表面温和到别人误以为很好欺…




阅读更多...

















快速计算斐波那契数列（Fibonacci数列）








快速计算斐波那契数列（Fibonacci数列）




本文最后更新于 619 天前&#xff0c;其中的信息可能已经有所发展或是发生改变。 题目描述 输入一个正整数n&#xff0c;求Fibonacci数列的第n个数。Fibonacci数列的特点&#xff1a;第1,2个数为1,1。从第3个数开始&#xff0c;概述是前面两个数之和。即&#xff1a; 要求输入的…




阅读更多...

















递归求斐波那契数列








递归求斐波那契数列




斐波那契数列 题目描述&#xff1a;编写一个函数&#xff0c;求斐波那契数列的第n项的值。 首先&#xff0c;对于斐波那契数列&#xff0c;我们是非常熟悉了&#xff0c;对斐波那契定义为如下&#xff1a;f(0)0,f(1)0,f(2)1,……f(n)f(n-1)f(n-2)&#xff0c;其中n>1。对于这…




阅读更多...

















斐波那契数列（Fibonacci）








斐波那契数列（Fibonacci）




有一对兔子&#xff0c;出生后第3个月起每个月都生一对免子。小兔子长到第3个月后每个月又生一对兔子。假设所有兔子都不死&#xff0c;问40个月的免子总数为多少?解题思路&#xff1a; 这是一个有趣的古典数学问题。可以从表1看出兔子繁殖的规律。                          …




阅读更多...

















【递归  动态规划  备忘录法】Fibonacci数列（斐波那契数列）（C++）








【递归  动态规划  备忘录法】Fibonacci数列（斐波那契数列）（C++）




一、什么是Fibonacci数列 
斐波那契数列指的是这样一个数列&#xff1a;1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…用文字来说&#xff0c;就是从第3项开始&#xff0c;每一项都等于前两项之和。至于包不包括0&#xff0c;一番查阅后没有得到证实… 不过重要的是“第3项开始…




阅读更多...

















算法-斐波那契数列Fibonacci








算法-斐波那契数列Fibonacci




斐波那契数列 Fibonacci 
斐波那契数列是这样的数列： 
0、1、1、2、3、5, 8、13、21、34 …… 
下一项是上两项的和。 
2 是上两项的和（1+1） 3 是上两项的和（1+2）、 5 是（2+3）、 依此类推！ 更多有意思的介绍可以见参考链接； 
算法 
1. 直接递归 初步想法就是采用递归的…




阅读更多...

















回顾斐波那契数列








回顾斐波那契数列




一 概述 斐波那契数列&#xff08;Fibonacci sequence&#xff09;&#xff0c;又称黄金分割数列。该数列是指递归方法定义为&#xff1a; 
F(0)  0&#xff0c;F(0)  1&#xff0c;F(n)  F(n-1)  F(n-2) (n ≥ 2&#xff0c;n ∈ N*) 的数列。 具体表现形式为&#xff1a;0&am…




阅读更多...

















题：斐波那契数列（Fibonacci数列）——一个数最少几步变成斐波那契数列的数








题：斐波那契数列（Fibonacci数列）——一个数最少几步变成斐波那契数列的数




题目描述&#xff1a; 
Fibonacci数列就形如&#xff1a;0, 1, 1, 2, 3, 5, 8, 13, ...&#xff0c;在Fibonacci数列中的数我们称为Fibonacci数。给你一 个N&#xff0c;你想让其变为一个Fibonacci数&#xff0c;每一步你可以把当前数字X变为X-1或者X1&#xff0c;现在给你一个…




阅读更多...

















Fibonacci数列前20项(斐波那契数列)








Fibonacci数列前20项(斐波那契数列)




HZKs Blog 本文标题&#xff1a; Fibonacci数列前20项(斐波那契数列) 本文链接&#xff1a; https://blog.zekun.fun/2021/coding/cppfibonacci数列前20项斐波那契数列/ 题目描述 Fibonacci数列的特点&#xff1a;第1,2个数为1,1。从第3个数开始&#xff0c;概述是前面两个数之…




阅读更多...

















for_each函数用法








for_each函数用法




Introduction 學習過STL的container後&#xff0c;想要存取每一個iterator&#xff0c;你一定寫過以下的程式  #include  < vector > #include  < iostream > using namespace std;   int main()  {   int ia[]  {1, 2, 3};   vector<int> ivec(ia, ia  size…




阅读更多...

















each函数用法








each函数用法




<?php/*each()只是一个函数&#xff0c;参数就是一个数组&#xff0c;返回的值也是一个数组1.返回的值也是一个数组&#xff0c;数组固定有4个元素&#xff0c;而且下标也是固定的1(值) value(值) 0(下标) key(下标)2.each()只是处理当前的元素将当前的元素(默认当前元素是…




阅读更多...

















$.each的用法








$.each的用法




1、示例1&#xff1a; <script type"text/javascript">var arr["1","2","3"];<span style"white-space:pre">	</span>//定义arr数组$.each(arr, function() {alert(this);<span style"white-spac…




阅读更多...

















for_each用法示例








for_each用法示例




文章目录 前言示例demo 前言 
由于偶然间发现for_each能使得避免使用for循环&#xff0c;大大简化了代码。这里简单记录下for_each的一个简单示例demo,方便温习。 
示例demo 
#include <iostream>
#include "vector"
#include "algorithm"void myfun…




阅读更多...

















字长、字节、字、字位的区别








字长、字节、字、字位的区别




字长、字节、字、字位的区别&#xff1a; 
&#xff08;1&#xff09;概念不一样 
同一时间处理二进制数位数叫字长&#xff0c;字长是直接用二进制代码指令表达的计算机语言。 
字节&#xff08;Byte &#xff09;是计算机信息技术用于计量存储容量的一种计量单位&#xff0c;…




阅读更多...

















微型计算机一个汉字多少字节,一个汉字多少字节(Byte)?








微型计算机一个汉字多少字节,一个汉字多少字节(Byte)?




2006-01-07 一个汉字有几个字节&#xff1f; 依据编码形式&#xff1a; GB&#xff0d;231280 编码为 2个字节(Byte) 包含了 20902 个汉字&#xff0c;其编码范围是 0x8140-0xfefe。 GB18030-2000(GBK2K) 在 GBK 的基础上进一步扩展了汉字&#xff0c;增加了藏、蒙等少数民族的…




阅读更多...

















计算机中1kb等于多少字节,在计算机中1kb等于多少字节








计算机中1kb等于多少字节,在计算机中1kb等于多少字节




在计算机中1kb等于1024个字节。字节是计算机信息技术用于计量存储容量的一种计量单位&#xff0c;也表示一些计算机编程语言中的数据类型和语言字符。一个字节存储8位无符号数。 本文操作环境&#xff1a;windows10系统、thinkpad t480电脑。 (学习视频分享&#xff1a;编程视频…




阅读更多...

















使用Java8新特性对List进行排序








使用Java8新特性对List进行排序




前言&#xff1a; 
在项目开发中往往会遇到各种数据需要排序展示在页面上&#xff0c;常见的从数据库查使用数据库的排序&#xff0c;还有一种就是使用我们的开发语言进行排序&#xff0c;这里给大家演示使用java8的新特性进行排序&#xff0c;众所周知java8带来了函数式编程和…




阅读更多...





























推荐文章


















Copyright @ 2022~2023