Redis之时间轮机制(五)

article/2025/7/28 0:54:26

🚀 优质资源分享 🚀

学习路线指引(点击解锁)知识定位人群定位
🧡 Python实战微信订餐小程序 🧡进阶级本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。
💛Python量化交易实战💛入门级手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

一、什么是时间轮

时间轮这个技术其实出来很久了,在kafka、zookeeper等技术中都有时间轮使用的方式。 时间轮是一种高效利用线程资源进行批量化调度的一种调度模型。把大批量的调度任务全部绑定到同一个调度器上,使用这一个调度器来进行所有任务的管理、触发、以及运行。所以时间轮的模型能够高效管理各种延时任务、周期任务、通知任务。 以后大家在工作中遇到类似的功能,可以采用时间轮机制。如下图所示,时间轮,从图片上来看,就和手表的表圈是一样,所以称为时间轮,是因为它是以时间作为刻度组成的一个环形队列,这个环形队列采用数组来实现,数组的每个元素称为槽,每个槽可以放一个定时任务列表,叫HashedWheelBucket,它是一个双向链表,量表的每一项表示一个定时任务项(HashedWhellTimeout),其中封装了真正的定时任务TimerTask。时间轮是由多个时间格组成,下图中有8个时间格,每个时间格代表当前时间轮的基本时间跨度(tickDuration),其中时间轮的时间格的个数是固定的。在下图中,有8个时间格(槽),假设每个时间格的单位为1s,那么整个时间轮走完一圈需要8s钟。每秒钟指针会沿着顺时针方向移动一个,这个单位可以设置,比如以秒为单位,可以以一小时为单位,这个单位可以代表时间精度。通过指针移动,来获得每个时间格中的任务列表,然后遍历这一个时间格中的双向链表来执行任务,以此循环。

二、时间轮案例使用

这里使用的时间轮是Netty这个包中提供的,使用方法比较简单。

  • 先构建一个HashedWheelTimer时间轮。
    • tickDuration: 100 ,表示每个时间格代表当前时间轮的基本时间跨度,这里是100ms,也就是指针100ms跳动一次,每次跳动一个窗格
    • ticksPerWheel:1024,表示时间轮上一共有多少个窗格,分配的窗格越多,占用内存空间就越大
    • leakDetection:是否开启内存泄漏检测。
    • maxPendingTimeouts[可选参数],最大允许等待的任务数,默认没有限制。
  • 通过newTimeout()把需要延迟执行的任务添加到时间轮中
@RestController
@RequestMapping("/timer")
public class HashedWheelController {//时间轮的定义HashedWheelTimer hashedWheelTimer=new HashedWheelTimer(new DefaultThreadFactory("demo-timer"),100, TimeUnit.MILLISECONDS,1024,false);@GetMapping("/{delay}")public void tick(@PathVariable("delay")Long delay){//SCHEDULED(定时执行的线程)//Timer(Java原生定时任务执行)System.out.println("CurrentTime:"+new Date());hashedWheelTimer.newTimeout(timeout -> {System.out.println("多少秒后执行这任务:"+new Date());},delay,TimeUnit.SECONDS);}
}

三、时间轮的原理解析

时间轮的整体原理,分为几个部分。

创建时间轮

时间轮本质上是一个环状数组,比如我们初始化时间轮时:ticksPerWheel=8,那么意味着这个环状数组的长度是8,如图3-12所示。

HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];

添加任务

  • 当通过newTimeout()方法添加一个延迟任务时,该任务首先会加入到一个阻塞队列中中。然后会有一个定时任务从该队列获取任务,添加到时间轮的指定位置,计算方法如下。
//当前任务的开始执行时间除以每个窗口的时间间隔,得到一个calculated值(表示需要经过多少tick,指针没跳动一个窗格,tick会递增),单位
为nanos(微毫秒)
long calculated = timeout.deadline / tickDuration;
//计算当前任务需要在时间轮中经历的圈数,因为当前任务执行时间有可能大于完整一圈的时间,所以需要计算经过几圈之后才能执行该任务。
timeout.remainingRounds = (calculated - tick) / wheel.length;
//取最大的一个tick,有可能当前任务在队列中已经过了执行时间,这种情况下直接用calculated这个值就没意义了。
final long ticks = Math.max(calculated, tick); // Ensure we don't schedule for past.
int stopIndex = (int) (ticks & mask); //通过ticks取模mask,得到一个下标
HashedWheelBucket bucket = wheel[stopIndex]; //把任务添加到指定数组下标位置

任务执行

  • Worker线程按照每次间隔时间转动后,得到该时间窗格中的任务链表,然后从链表的head开始逐个取出任务,有两个判断条件
  • 当前任务需要转动的圈数为0,表示任务是当前圈开始执行
  • 当前任务达到了delay时间,也就是timeout.deadline <= deadline
  • 最终调用timeout.expire()方法执行任务。
        public void expireTimeouts(long deadline) {HashedWheelTimeout timeout = head;// process all timeoutswhile (timeout != null) {HashedWheelTimeout next = timeout.next;if (timeout.remainingRounds <= 0) {next = remove(timeout);if (timeout.deadline <= deadline) {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));}} else if (timeout.isCancelled()) {next = remove(timeout);} else {timeout.remainingRounds --;}timeout = next;}}

四、时间轮的源码分析

HashedWheelTimer的构造

  • 调用 createWheel 创建一个时间轮,时间轮数组一定是 2 的幂次方,比如传入的 ticksPerWheel=6,那么初始化的 wheel 长度一定是 8,这样是便于时间格的计算。
  • tickDuration,表示时间轮的跨度,代表每个时间格的时间精度,以纳秒的方式来表现。
  • 把工作线程 Worker 封装成 WorkerThread,从名字可以知道,它就是最终那个负责干活的线程。
public HashedWheelTimer(ThreadFactory threadFactory,long tickDuration, TimeUnit unit, int ticksPerWheel,long maxPendingTimeouts) {// 创建时间轮基本的数据结构,一个数组。长度为不小于ticksPerWheel的最小2的n次方wheel = createWheel(ticksPerWheel);// 这是一个标示符,用来快速计算任务应该呆的格子。// 我们知道,给定一个deadline的定时任务,其应该呆的格子=deadline%wheel.length.但是%操作是个相对耗时的操作,所以使用一种变通的位运算代替:// 因为一圈的长度为2的n次方,mask = 2^n-1后低位将全部是1,然后deadline&mast == deadline%wheel.length// java中的HashMap在进行hash之后,进行index的hash寻址寻址的算法也是和这个一样的mask = wheel.length - 1;//时间轮的基本时间跨度,(tickDuration传入是1的话,这里会转换成1000000)this.tickDuration = unit.toNanos(tickDuration);// 校验是否存在溢出。即指针转动的时间间隔不能太长而导致tickDuration*wheel.length>Long.MAX\_VALUEif (this.tickDuration >= Long.MAX\_VALUE / wheel.length) {throw new IllegalArgumentException(String.format("tickDuration: %d (expected: 0 < tickDuration in nanos < %d",tickDuration, Long.MAX\_VALUE / wheel.length));}//把worker包装成threadworkerThread = threadFactory.newThread(worker);this.maxPendingTimeouts = maxPendingTimeouts;//如果HashedWheelTimer实例太多,那么就会打印一个error日志if (INSTANCE\_COUNTER.incrementAndGet() > INSTANCE\_COUNT\_LIMIT &&WARNED\_TOO\_MANY\_INSTANCES.compareAndSet(false, true)) {reportTooManyInstances();}
}
  • 对传入的 ticksPerWheel 进行整形
  • 初始化固定长度的 HashedWheelBucket
private static HashedWheelBucket[] createWheel(int ticksPerWheel) {if (ticksPerWheel <= 0) {throw new IllegalArgumentException("ticksPerWheel must be greater than 0: " + ticksPerWheel);}if (ticksPerWheel > 1073741824) {throw new IllegalArgumentException("ticksPerWheel may not be greater than 2^30: " + ticksPerWheel);}//对传入的时间轮大小进行整形,整形成2的幂次方ticksPerWheel = normalizeTicksPerWheel(ticksPerWheel);//初始化一个固定长度的Bucket数组HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];for (int i = 0; i < wheel.length; i++) {wheel[i] = new HashedWheelBucket();}return wheel;
}

添加任务到时间轮

调用 newTimeout 方法,把任务添加进来。

public Timeout newTimeout(TimerTask task, long delay, TimeUnit unit) {if (task == null) {throw new NullPointerException("task");}if (unit == null) {throw new NullPointerException("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方法进行启动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;//在delay为正数的情况下,deadline是不可能为负数//如果为负数,那么说明超过了long的最大值if (delay > 0 && deadline < 0) {deadline = Long.MAX\_VALUE;}//创建一个Timeout任务,理论上来说,这个任务应该要加入到时间轮的时间格子中,但是这里并不是先添加到时间格,而是先//加入到一个阻塞队列,然后等到时间轮执行到下一个格子时,再从队列中取出最多100000个任务添加到指定的时间格(槽)中。HashedWheelTimeout timeout = new HashedWheelTimeout(this, task, deadline);timeouts.add(timeout);return timeout;
}

start

任务添加到阻塞队列之后,我们再来看启动方法。

start 方法会根据当前的 workerState 状态来启动时间轮。并且用了 startTimeInitialized 来控制线程的运行,如果 workerThread 没有启动起来,那么 newTimeout 方法会一直阻塞在运行 start 方法中。如果不阻塞,newTimeout 方法会获取不到 startTime。

public void start() {//workerState一开始的时候是0(WORKER\_STATE\_INIT),然后才会设置为1(WORKER\_STATE\_STARTED)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");}// 等待worker线程初始化时间轮的启动时间while (startTime == 0) {try {//这里使用countDownLauch来确保调度的线程已经被启动startTimeInitialized.await();} catch (InterruptedException ignore) {// Ignore - it will be ready very soon.}}
}

启动时间轮

调用 start()方法, 会调用 workerThread.start(); 来启动一个工作线程,这个工作线程是在构造方法中初始化的,包装的是一个 Worker 内部线程类。

所以直接进入到 Worker 这个类的 run 方法,了解下它的设计逻辑:

public void run() {// 初始化startTime,表示时间轮的启动时间startTime = System.nanoTime();if (startTime == 0) {// We use 0 as an indicator for the uninitialized value here, so make sure it's not 0 when initialized.startTime = 1;} // 唤醒被阻塞的start()方法。startTimeInitialized.countDown();do {//返回每tick一次的时间间隔final long deadline = waitForNextTick();if (deadline > 0) {//计算时间轮的槽位int idx = (int) (tick & mask);//移除掉CancelledTaskprocessCancelledTasks();//得到当前指针位置的时间槽HashedWheelBucket bucket =wheel[idx];//将newTimeout()方法中加入到待处理定时任务队列中的任务加入到指定的格子中transferTimeoutsToBuckets();//运行目前指针指向的槽中的bucket链表中的任务bucket.expireTimeouts(deadline);tick++;}} while (WORKER\_STATE\_UPDATER.get(HashedWheelTimer.this) == WORKER\_STATE\_STARTED);//如果Worker\_State一只是started状态,就一直循环// Fill the unprocessedTimeouts so we can return them from stop() method.for (HashedWheelBucket bucket : wheel) {bucket.clearTimeouts(unprocessedTimeouts); //清除时间轮中不需要处理的任务}for (; ; ) {//遍历任务队列,发现如果有任务被取消,则添加到unprocessedTimeouts,也就是不需要处理的队列中。HashedWheelTimeout timeout = timeouts.poll();if (timeout == null) {break;}if (!timeout.isCancelled()) {unprocessedTimeouts.add(timeout);}}//处理被取消的任务.processCancelledTasks();
}

时间轮指针跳动

这个方法的主要作用就是返回下一个指针指向的时间间隔,然后进行 sleep 操作。

大家可以想象一下,一个钟表上秒与秒之间是有时间间隔的,那么 waitForNextTick 就是根据当前时间计算出跳动到下个时间的时间间隔,然后进行 sleep,然后再返回当前时间距离时间轮启动时间的时间间隔。

说得再直白一点:,假设当前的 tickDuration 的间隔是 1s,tick 默认 = 0, 此时第一次进来,得到的 deadline=1,也就是下一次跳动的时间间隔是 1s。假设当前处于:

private long waitForNextTick() {//tick表示总的tick数//tickDuration表示每个时间格的跨度,所以deadline返回的是下一次时间轮指针跳动的时间long deadline = tickDuration * (tick + 1);for (; ; ) {//计算当前时间距离启动时间的时间间隔final long currentTime = System.nanoTime() - startTime;//通过下一次指针跳动的延迟时间距离当前时间的差额,这个作为sleep时间使用。// 其实线程是以睡眠一定的时候再来执行下一个ticket的任务的long sleepTimeMs = (deadline - currentTime + 999999) / 1000000;//sleepTimeMs小于零表示走到了下一个时间槽位置if (sleepTimeMs <= 0) {if (currentTime == Long.MIN\_VALUE) {return -Long.MAX\_VALUE;} else {return currentTime;}}if (isWindows()) {sleepTimeMs = sleepTimeMs / 10 * 10;}//进入到这里进行sleep,表示当前时间距离下一次tick时间还有一段距离,需要sleep。try {Thread.sleep(sleepTimeMs);} catch (InterruptedException ignored) {if (WORKER\_STATE\_UPDATER.get(HashedWheelTimer.this) == WORKER\_STATE\_SHUTDOWN) {return Long.MIN\_VALUE;}}}
}

transferTimeoutsToBuckets

转移任务到时间轮中,前面我们讲过,任务添加进来时,是先放入到阻塞队列。

而在现在这个方法中,就是把阻塞队列中的数据转移到时间轮的指定位置。

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

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

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

private void transferTimeoutsToBuckets() {// 循环100000次,也就是每次转移10w个任务for (int i = 0; i < 100000; i++) {//从阻塞队列中获得具体的任务HashedWheelTimeout timeout = timeouts.poll();if (timeout == null) {// all processedbreak;}if (timeout.state() == HashedWheelTimeout.ST\_CANCELLED) {// Was cancelled in the meantime.continue;}//计算tick次数,deadline表示当前任务的延迟时间,tickDuration表示时间槽的间隔,两者相除就可以计算当前任务需要tick几次才能被执行long calculated = timeout.deadline / tickDuration;// 计算剩余的轮数, 只有 timer 走够轮数, 并且到达了 task 所在的 slot, task 才会过期.(被执行)timeout.remainingRounds = (calculated - tick) / wheel.length;//如果任务在timeouts队列里面放久了, 以至于已经过了执行时间, 这个时候就使用当前tick, 也就是放到当前bucket, 此方法调用完后就会被执行final long ticks = Math.max(calculated, tick);// 算出任务应该插入的 wheel 的 slot, stopIndex = tick 次数 & mask, mask = wheel.length - 1int stopIndex = (int) (ticks & mask);//把timeout任务插入到指定的bucket链中。HashedWheelBucket bucket = wheel[stopIndex];bucket.addTimeout(timeout);}
}

运行时间轮中的任务

当指针跳动到某一个时间槽中时,会就触发这个槽中的任务的执行。该功能是通过 expireTimeouts 来实现

这个方法的主要作用是: 过期并执行格子中到期的任务。也就是当 tick 进入到指定格子时,worker 线程会调用这个方法

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

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

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

void expireTimeouts(long deadline) {HashedWheelTimeout timeout = head;// 遍历当前时间槽中的所有任务while (timeout != null) {HashedWheelTimeout next = timeout.next;//如果当前任务要被执行,那么remainingRounds应该小于或者等于0if (timeout.remainingRounds <= 0) {//从bucket链表中移除当前timeout,并返回链表中下一个timeoutnext = remove(timeout);//如果timeout的时间小于当前的时间,那么就调用expire执行taskif (timeout.deadline <= deadline) {timeout.expire();} else {//不可能发生的情况,就是说round已经为0了,deadline却>当前槽的deadline// 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));}} else if (timeout.isCancelled()) {next = remove(timeout);} else {//因为当前的槽位已经过了,说明已经走了一圈了,把轮数减一timeout.remainingRounds--;}//把指针放置到下一个timeouttimeout = next;}
}


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

相关文章

C++定时器和时间轮

文章目录 定时器最小堆实现定时器 时间轮单层级时间轮多层级时间轮 定时器 有些时候我们需要延迟执行一些功能&#xff0c;比如每10s进行一次数据采集。或者告知用户技能冷却有多少时间&#xff0c;如果我们将执行这些功能的任务交给主线程&#xff0c;就会造成主线程的阻塞。…

简单描述时间轮

时间轮 作用 也是用来作定时器触发任务&#xff0c;只是他更高效&#xff0c;时间复杂度为O(1)。 运行原理 为了方便理解我们参考钟表&#xff0c;它分为3个层次&#xff1a;时、分、秒&#xff0c;只有秒针在运动&#xff0c;走动一格时间为1秒&#xff0c;走一圈为1分钟&…

再谈时间轮

时间轮很早前就很流行了&#xff0c;在很多优秀开源框架中都有用到&#xff0c;像kafka、netty。也算是现在工程师基本都了解的一个知识储备了。有幸在工作中造过两次轮子&#xff0c;所以今天聊聊时间轮。 时间轮是一种高性能定时器。 时间轮&#xff0c;顾名思义&#xff0c…

时间轮原理及其在框架中的应用

一、时间轮简介 1.1 为什么要使用时间轮 在平时开发中&#xff0c;经常会与定时任务打交道。下面举几个定时任务处理的例子。 1&#xff09;心跳检测。在Dubbo中&#xff0c;需要有心跳机制来维持Consumer与Provider的长连接&#xff0c;默认的心跳间隔是60s。当Provider在3…

时间轮分析

背景 在需要完成重试机制或者心跳机制一类的业务&#xff0c;除了使用excutors做定时任务。还可以使用时间轮完成这类需求 分析 使用dubbo中的心跳重试作为案例分析时间轮的使用 源码分析 在HeaderExchangeClient启动的时候调用startHeartBeatTask()开启心跳任务&#xff0…

Netty时间轮

概述 时间轮是一个高性能&#xff0c;低消耗的数据结构&#xff0c;它适合用非准实时&#xff0c;延迟的短平快任务&#xff0c;例如心跳检测。在netty和kafka中都有使用。 比如Netty动辄管理100w的连接&#xff0c;每一个连接都会有很多超时任务。比如发送超时、心跳检测间隔等…

高性能定时器时间轮的实现

时间轮的概念 关于定时器有很多种&#xff0c;有基于升序的定时器时间链表&#xff0c;但是这种链表存在效率的不足&#xff0c;就是当插入定时器的时候时间复杂度是O(n).今天&#xff0c;我们来认识一下高性能定时器时间轮。 如上图所示&#xff0c;就是一个时间轮的基本轮廓…

深度剖析 -- 时间轮算法(TimingWheel)是如何实现的?

前言 时间轮的应用场景很多&#xff0c;在 Netty、Akka、Quartz、ZooKeeper 、Kafka等组件中都存在时间轮的踪影。我们下面讲解的时间轮的实现以JRaft中的为例子进行讲解&#xff0c;因为JRaft这部分的代码是参考Netty的&#xff0c;所以大家也可以去Netty中去寻找源码实现。 …

Kafka原理--时间轮(延时操作)

原文网址&#xff1a;Kafka原理--时间轮(延时操作)_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍Kafka的时间轮的原理。 Kafka没有延迟队列功能供用户使用&#xff0c;本文介绍的延时操作仅仅是Kafka内部的使用&#xff0c;用户无法使用。 Kafka延时操作 Kafka中存在大量的…

时间轮算法HashedWheelTimer

文章目录 一.HashedWheelTimer是什么?二.能干什么?为什么需要这个东西?优点适用场景 三.怎么用?使用步骤1.引入pom2.使用举例 四.时间轮原理五.使用注意点1.一个HashedWheelTimer对象只有一个worker线程2.每次添加的任务只会执行一次3.时间轮的参数非常重要4.所有的任务都是…

时间轮-理论篇

1. 引言 定时任务再开发过程中无处不在&#xff0c;定时发送消息&#xff0c;定时更新数据库表的状态&#xff0c;Linux系统定时执行脚本等等。这些操作都离不开定时任务&#xff0c;那么这些定时任务是怎么实现的是否又去想过。如果让开发者自己去实现一个定时任务又该怎么实…

定时任务的实现原理:时间轮算法

文章目录 前言时间轮定时使用方式时间轮定时内部原理时间轮定时源码剖析构造方法添加任务工作线程启动工作线程run方法指针跳动将队列任务放入时间轮中链表任务遍历定时任务执行 前言 最近在思考实现定时任务的几种方式&#xff0c;比如 quartz&#xff0c;delay queue&#xf…

时间轮-Java实现篇

在前面的文章《时间轮-理论篇》讲了时间轮的一些理论知识&#xff0c;然后根据理论知识。我们自己来实现一个简单的时间轮。 1. 理论抽象 将时间轮的理论进行抽象&#xff0c;主要有两个方面&#xff1a; 时间轮的转动每一个时间间隔任务的处理&#xff0c;从时间间隔的Buke…

时间轮timewheel算法

时间轮是个不太常见&#xff0c;但在部分场景有较高使用价值的工具。 时间轮常用于延时任务&#xff0c;在Netty、akka、Quartz、Zookeeper等高性能组件中都存在时间轮定时器的踪影。 从定时任务说起 自然界中定时任务无处不在&#xff0c;太阳每天东升西落&#xff0c;候鸟的…

定时器实现原理——时间轮

时间轮 时间轮算法是通过一个时间轮去维护定时任务&#xff0c;按照一定的时间单位对时间轮进行划分刻度。然后根据任务延时计算任务落在该时间轮的第几个刻度上&#xff0c;如果任务时长超出了刻度数量&#xff0c;则需要增加一个参数记录时间轮需要转动的圈数。 简单时间轮…

时间轮算法

一、时间轮算法 1. 时间轮的基本概念 Kafka中存在大量的延时操作&#xff0c;如延时生产、延时消费等&#xff1b;而JDK中自带的 Timer 和 DelayQueue 的插入和删除操作的平均复杂度为 O&#xff08;nlogn&#xff09;&#xff0c;无法满足 Kafka 的高性能要求&#xff0c;因…

时间轮算法(TimingWheel)

时间轮算法的应用非常广泛&#xff0c;在 Dubbo、Netty、Kafka、ZooKeeper、Quartz 的组件中都有时间轮思想的应用&#xff0c;甚至在 Linux 内核中都有用到。 其思想理论基础可以参考论文&#xff1a;http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pd…

那些惊艳的算法们(三)—— 时间轮

从定时任务说起 自然界中定时任务无处不在&#xff0c;太阳每天东升西落&#xff0c;候鸟的迁徙&#xff0c;树木的年轮&#xff0c;人们每天按时上班&#xff0c;每个月按时发工资、交房租&#xff0c;四季轮换&#xff0c;潮涨潮落&#xff0c;等等&#xff0c;从某种意义上…

1、时间轮

一、什么是时间轮&#xff1f; 作为一个粗人&#xff0c;咱不扯什么高级的词汇&#xff0c;直接上图&#xff1a; 上面是一张时间轮的示意图&#xff0c;可以看到&#xff0c;这个时间轮就像一个钟表一样&#xff0c;它有刻度&#xff0c;图中画了9个格子&#xff0c;每个格子…

浅谈时间轮算法

浅谈时间轮算法 基于队列的定时任务执行模型缺陷 在计算机世界中&#xff0c;只有待解决的问题变得大规模后&#xff0c;算法的价值才能够最大化的体现。时间轮算法可以将插入和删除操作的时间复杂度都降为 O(1)&#xff0c;在大规模问题下还能够达到非常好的运行效果。 如果…