什么是时间轮?

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云原生数据库 PolarDB MySQL 版,Serverless 5000PCU 100GB
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: 时间轮是一种用于任务调度和时间管理的数据结构,尤其适合处理大量定时任务的场景,如网络服务器或实时系统。它由一个圆形数组构成,每个槽代表固定时间间隔,任务根据执行时间添加到相应槽。时间推进时,指针移动并执行到期任务。时间轮具有高效性和简单性,插入和删除操作接近常数时间复杂度。层级时间轮可扩展处理更大时间范围和精度。在Spring Boot中,可以使用Netty的`HashedWheelTimer`实现高效定时任务管理。

时间轮(Timing Wheel)是计算机科学中用于任务调度和时间管理的一种数据结构,特别是在实现高效的定时器和调度策略时非常有用。它主要用于需要高效处理大量定时任务的场景,如网络服务器或实时系统中。

简单介绍

时间轮(Timing Wheel)是一种高效的数据结构,用于管理和调度时间依赖的任务。它尤其适用于那些需要处理大量定时事件的系统,例如操作系统的任务调度器或网络服务器。下面,我将简单解释时间轮的原理和工作机制。

基本结构

时间轮基本上是一个圆形的数组,每个数组元素称为一个“槽”或“桶”。每个槽代表一段固定的时间间隔,例如1毫秒。每个槽都可以链接到一个或多个定时任务。

工作原理

  1. 初始化: 时间轮初始化时,会设置一个固定大小的数组,每个槽代表一个时间间隔。同时,有一个指针表示当前时间槽。
  2. 添加任务: 当一个定时任务被添加到时间轮时,会计算该任务需要在未来多少时间后执行。根据这个时间间隔,将任务添加到对应的槽中。如果时间间隔超过了时间轮的总时间范围,任务会被添加到最后一个槽或根据具体实现可能进入一个备用的数据结构。
  3. 时间的推进: 时间轮有一个当前时间指针,随着时间的推进,这个指针会移动到下一个槽。每当指针移动到一个新槽,就会检查这个槽里是否有任务需要执行。如果有,就执行这些任务。
  4. 任务执行: 任务在其对应的时间槽到达时被执行。执行完毕后,任务可以选择从时间轮中删除,或者如果需要周期性执行,可以重新计算其下次执行的时间并再次添加到时间轮中。

时间轮的优点

  • 高效性:时间轮避免了使用最小堆或其他数据结构频繁地插入和删除操作,这些操作通常是对数时间复杂度。时间轮的插入和删除操作可以视为常数时间复杂度,因为它们只涉及到数组索引的操作。
  • 简单:时间轮的结构简单,使得时间的前进和任务的调度非常直接,只涉及数组的索引操作和链表操作。

层级时间轮

对于处理更长时间范围或更高精度的需求,可以使用多层时间轮。层级时间轮由多个时间轮组成,每个时间轮负责不同的时间粒度和范围。例如,第一层时间轮可能每个槽代表1毫秒,而第二层时间轮的每个槽可能代表1秒。这种结构可以有效地扩展时间轮处理的时间范围和精度。

总之,时间轮是一种高效、易于管理的数据结构,特别适合于那些需要高效处理大量定时任务的系统。通过调整槽数量和层数,时间轮可以灵活地适应不同的应用场景和性能要求。

简单实例

在Spring Boot项目中,使用时间轮来管理定时任务是一种比较少见的应用,因为Spring Boot本身提供了强大的定时任务支持(如使用@Scheduled注解)。不过,如果你确实需要利用时间轮来管理任务,通常的情况是你正在处理非常高频的任务或者需要特别定制的调度策略。

对于时间轮的实现,我们可以利用第三方库,如netty中的HashedWheelTimer,它是一个用于处理超时事件的高性能时间轮实现。下面是如何在一个Spring Boot项目中使用HashedWheelTimer来计划和执行周期性任务的示例。

添加依赖

首先,你需要在你的pom.xml文件中添加Netty的依赖,因为HashedWheelTimer是Netty提供的:

xml

复制代码

<dependencies>
    <!-- 添加Netty依赖 -->
    <dependency>
        <groupId>io.netty</groupId>
        <artifactId>netty-all</artifactId>
        <version>4.1.48.Final</version> <!-- 请使用最新的稳定版本 -->
    </dependency>
    <!-- Spring Boot起始依赖 -->
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter</artifactId>
    </dependency>
</dependencies>

实现时间轮的配置和任务

接下来,我们可以设置一个Spring Boot配置类来初始化HashedWheelTimer,并且创建一个简单的定时任务:

java

复制代码

package com.example.demo;

import io.netty.util.HashedWheelTimer;
import io.netty.util.Timeout;
import io.netty.util.TimerTask;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import java.util.concurrent.TimeUnit;

@Configuration
public class TimerConfig {

    @Bean
    public HashedWheelTimer hashedWheelTimer() {
        // 创建一个时间轮定时器,每个槽的时间间隔为100毫秒,槽数量为512
        HashedWheelTimer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);
        // 开始时间轮定时器
        timer.start();
        return timer;
    }
    
    @Bean
    public Timeout scheduleTask(HashedWheelTimer timer) {
        // 创建一个定时任务
        TimerTask task = new TimerTask() {
            @Override
            public void run(Timeout timeout) throws Exception {
                System.out.println("执行任务: " + System.currentTimeMillis());
                // 重新调度任务,实现周期性执行
                timer.newTimeout(this, 1, TimeUnit.SECONDS);
            }
        };

        // 调度任务,每秒执行一次
        return timer.newTimeout(task, 1, TimeUnit.SECONDS);
    }
}

运行Spring Boot应用

接下来,你需要创建你的SpringBootApplication主类来运行你的应用:

java

复制代码

package com.example.demo;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class DemoApplication {

    public static void main(String[] args) {
        SpringApplication.run(DemoApplication.class, args);
    }
}

这个示例中,我们使用了Netty的HashedWheelTimer来实现一个简单的周期性任务,每秒输出当前的时间戳。这种方式非常适合处理高频率的定时任务,并且由于HashedWheelTimer的高效性,它在高负载下表现更为优秀。

实际案例

当涉及到需要非常高效的调度或处理大量定时任务的场景,一个常见的应用例子是在高性能游戏服务器或实时通讯系统中。在这些场景中,可能需要精确地管理大量的短周期性事件,例如用户的位置更新、状态同步或心跳检测。使用时间轮可以有效地降低任务调度的开销,提高整体性能。

场景案例

假设我们正在开发一个在线游戏的后端服务,需要每隔一定时间更新玩家的状态,包括位置、健康值和游戏内的交互事件。如果游戏服务器需要同时处理成千上万的玩家,使用传统的定时器(如Java的ScheduledExecutorService)可能会因为大量的线程调度而导致性能瓶颈。这时,HashedWheelTimer可以作为一个高效的解决方案来处理这些周期性的事件。

实现代码

下面的Java代码示例展示了如何在Spring Boot应用中使用HashedWheelTimer来管理大量玩家的状态更新任务:

java

复制代码

package com.example.game;

import io.netty.util.HashedWheelTimer;
import io.netty.util.Timeout;
import io.netty.util.TimerTask;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.stereotype.Component;

import java.util.concurrent.TimeUnit;

@Configuration
public class GameServerConfig {

    @Bean
    public HashedWheelTimer hashedWheelTimer() {
        // 设定时间轮的参数,每个时间间隔为100毫秒,总槽数为1024
        HashedWheelTimer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 1024);
        timer.start();
        return timer;
    }
}

@Component
public class PlayerManager {

    private final HashedWheelTimer timer;

    public PlayerManager(HashedWheelTimer timer) {
        this.timer = timer;
    }

    public void schedulePlayerUpdates(String playerId) {
        TimerTask updateTask = timeout -> {
            updatePlayerState(playerId);
            // 重新调度任务,保持玩家状态定期更新
            timer.newTimeout(this::schedulePlayerUpdates, 100, TimeUnit.MILLISECONDS);
        };
        timer.newTimeout(updateTask, 100, TimeUnit.MILLISECONDS);
    }

    private void updatePlayerState(String playerId) {
        // 模拟更新玩家状态的逻辑
        System.out.println("Updating state for player: " + playerId + " at " + System.currentTimeMillis());
    }
}

如何使用

  1. PlayerManager 类管理玩家的状态更新。它使用HashedWheelTimer来调度每个玩家的更新任务。
  2. schedulePlayerUpdates 方法设置一个任务,每100毫秒调用一次updatePlayerState来更新玩家状态,并重新调度自身以维持周期性执行。
  3. 这种方法可以极大地减少调度的开销,因为HashedWheelTimer通过减少任务的检查和管理次数来优化性能。


转载来源:https://juejin.cn/post/7372469324982763570

相关文章
|
1月前
|
小程序
获取本月1号0时间 获取本周一的0点时间
获取本月1号0时间 获取本周一的0点时间
|
9月前
|
Unix Linux Android开发
时间问题
时间问题
99 0
别再用大小比较时间了
由于写代码习惯了基本数据类型(int/Integer、long等)大小的比较,很多人连Date的时间先后比较也用大小(>、<、>=、<=)了。
109 0
|
消息中间件 算法 Linux
什么是时间轮
什么是时间轮
328 0
建立时间与保持时间
建立时间(Set up time,简写为T s u T_{su}T su ​ )是指触发时钟沿(以上升沿为例)到达D触发器之前,要求输入信号必须已经达到稳定的时间。对应的,保持时间(Hold time,简写为T h T_hT h ​ )是指触发时钟沿到达D触发器之后,要求输入信号还需要保持必须稳定的时间。建立时间、保持时间相对于触发时钟沿的关系如图所示。输入信号在建立时间和保持时间不能发生变化,容易出现灾难。
202 0
建立时间与保持时间
|
Unix
strtotime应用(案例:给未来时间添加对应的时间)
strtotime应用(案例:给未来时间添加对应的时间)
191 0
strtotime应用(案例:给未来时间添加对应的时间)
如果时间可以倒流
今天同事问阿粉一个问题,觉得挺有意义的,在这里也问问各位读者们:如果时间可以倒流,你最想做什么呢?为什么呢? 这个问题阿粉也问了问身边的一些朋友们,下面是他们的答案,或许可以给你一些启发 朋友 A :如果时间可以倒流,我特别想要回到高中的时候,好好学习,踏踏实实的去努力,好好读书。不是那种死板教条的读书,是有计划有效率的读书,希望自己能够死不要脸一些,多向老师和同学请教问题,我可能天资不够聪慧,但是如果能够有效率一些,死不要脸一些,最起码会比现在要好得多吧
如果时间可以倒流
|
SQL JavaScript
时间问题,你会吗?
【本题考点】 1)涉及到多条件分组问题,要想到使用case when条件表达式。 2)时间问题,要想到常用的日期函数(datediff和timestampdiff)来解决。
时间问题,你会吗?
一些时间的处理
let BGT = $(o.beginT).val(); let EDT = $(o.endT).val(); spanAddCls(3); // 获取点击日期, let date = statis.
816 0