抖音面试:说说延迟任务的调度算法?

简介: Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。## 1.延迟任务实现在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码:```javapublic class DelayTaskExample { public static void main(String[] args) { System.ou

Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。

1.延迟任务实现

在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码:

public class DelayTaskExample {
   
   
    public static void main(String[] args) {
   
   
        System.out.println("程序启动时间:" + LocalDateTime.now());
        NettyTask();
    }

    private static void NettyTask() {
   
   
        // 创建延迟任务实例
        HashedWheelTimer timer = new HashedWheelTimer(3, // 间隔时间
                TimeUnit.SECONDS, // 间隔时间单位
                100); // 时间轮中的槽数
        // 创建任务
        TimerTask task = new TimerTask() {
   
   
            @Override
            public void run(Timeout timeout) throws Exception {
   
   
                System.out.println("执行任务时间:" + LocalDateTime.now());
            }
        };
        // 将任务添加到延迟队列中
        timer.newTimeout(task, 0, TimeUnit.SECONDS);
    }
}

以上程序的执行结果如下:

程序启动时间:2024-06-04T10:16:23.033

执行任务时间:2024-06-04T10:16:26.118

从上述执行结果可以看出,我们使用 HashedWheelTimer 实现了延迟任务的执行。

2.时间轮调度算法

那么问题来了,HashedWheelTimer 是如何实现延迟任务的?什么是时间轮调度算法?

查看 HashedWheelTimer 类的源码会发现,其实它是底层是通过时间轮调度算法来实现的,以下是 HashedWheelTimer 核心实现源码(HashedWheelTimer 的创建源码)如下:

private static HashedWheelBucket[] createWheel(int 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;
}
private static final class HashedWheelBucket {
   
   
    private HashedWheelTimeout head;
    private HashedWheelTimeout tail;
    // 省略其他代码
}

在 HashedWheelTimer 中,使用了 HashedWheelBucket 数组实现时间轮的概念,每个 HashedWheelBucket 表示时间轮中一个 slot(时间槽),HashedWheelBucket 内部是一个双向链表结构,双向链表的每个节点持有一个 HashedWheelTimeout 对象,HashedWheelTimeout 代表一个定时任务,每个 HashedWheelBucket 都包含双向链表 head 和 tail 两个 HashedWheelTimeout 节点,这样就可以实现不同方向进行链表遍历,如下图所示:
image.png
时间轮算法的设计思想就来源于钟表,如上图所示,时间轮可以理解为一种环形结构,像钟表一样被分为多个 slot 槽位。每个 slot 代表一个时间段,每个 slot 中可以存放多个任务,使用的是链表结构保存该时间段到期的所有任务。时间轮通过一个时针随着时间一个个 slot 转动,并执行 slot 中的所有到期任务。

任务的添加是根据任务的到期时间进行取模,然后将任务分布到不同的 slot 中。如上图所示,时间轮被划分为 8 个 slot,每个 slot 代表 1s,当前时针指向 2 时,假如现在需要调度一个 3s 后执行的任务,应该加入 2+3=5 的 slot 中;如果需要调度一个 12s 以后的任务,需要等待时针完整走完一圈 round 零 4 个 slot,需要放入第 (2+12)%8=6 个 slot。

那么当时针走到第 6 个 slot 时,怎么区分每个任务是否需要立即执行,还是需要等待下一圈 round,甚至更久时间之后执行呢?所以我们需要把 round 信息保存在任务中。例如图中第 6 个 slot 的链表中包含 3 个任务,第一个任务 round=0,需要立即执行;第二个任务 round=1,需要等待 18=8s 后执行;第三个任务 round=2,需要等待 28=8s 后执行。所以当时针转动到对应 slot 时,只执行 round=0 的任务,slot 中其余任务的 round 应当减 1,等待下一个 round 之后执行。

可以看出时间轮有点类似 HashMap,如果多个任务如果对应同一个 slot,处理冲突的方法采用的是拉链法。在任务数量比较多的场景下,适当增加时间轮的 slot 数量,可以减少时针转动时遍历的任务个数。

时间轮定时器最大的优势就是,任务的新增和取消都是 O(1) 时间复杂度,而且只需要一个线程就可以驱动时间轮进行工作。

课后思考

Netty 中的时间轮调度算法有什么缺点?

参考 & 鸣谢

《Netty核心原理剖析与RPC实践》

本文已收录到我的面试小站 www.javacn.site,其中包含的内容有:Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、消息队列等模块。

相关文章
|
2天前
|
机器学习/深度学习 算法 物联网
深入剖析操作系统调度算法
【7月更文挑战第13天】本文旨在探讨和比较不同的操作系统调度算法,并分析其对系统性能的影响。文章首先概述了调度算法的基本概念及其重要性,随后详细阐述了常见的调度算法类型,包括先来先服务、短作业优先、优先级调度、时间片轮转以及多级反馈队列等。通过对比不同算法的优缺点,文章进一步探讨了现代操作系统中调度算法的应用与挑战,以及如何根据实际需求选择合适的调度策略。最后,文章展望了操作系统调度算法的未来发展方向,特别是在云计算和物联网时代下的适应性与创新。
9 1
|
5天前
|
设计模式 安全 Java
Java面试题:设计模式如单例模式、工厂模式、观察者模式等在多线程环境下线程安全问题,Java内存模型定义了线程如何与内存交互,包括原子性、可见性、有序性,并发框架提供了更高层次的并发任务处理能力
Java面试题:设计模式如单例模式、工厂模式、观察者模式等在多线程环境下线程安全问题,Java内存模型定义了线程如何与内存交互,包括原子性、可见性、有序性,并发框架提供了更高层次的并发任务处理能力
18 1
|
5天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
14 1
|
16天前
|
算法 调度 云计算
操作系统中的调度算法:从理论到实践
在计算机科学领域,操作系统的调度算法是决定任务执行顺序的关键。本文首先概述了调度算法的基本概念和重要性,随后深入探讨了几种主要的调度算法,包括先来先服务、短作业优先、轮转与优先级调度等。通过引用最新的科研数据和实验证据,文章揭示了不同调度算法的性能表现和适用场景。此外,本文还讨论了现代操作系统中调度算法面临的挑战和未来的发展方向,强调了在多核处理器和云计算环境下调度策略的复杂性。最后,通过案例分析,展示了如何在实际系统中应用这些理论知识,以及在设计高效调度系统时需要考虑的因素。
|
5天前
|
算法 Java 程序员
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
8 0
|
5天前
|
设计模式 安全 Java
Java面试题:如何实现一个线程安全的单例模式,并确保其在高并发环境下的内存管理效率?如何使用CyclicBarrier来实现一个多阶段的数据处理任务,确保所有阶段的数据一致性?
Java面试题:如何实现一个线程安全的单例模式,并确保其在高并发环境下的内存管理效率?如何使用CyclicBarrier来实现一个多阶段的数据处理任务,确保所有阶段的数据一致性?
10 0
|
5天前
|
设计模式 SQL 安全
Java面试题:设计一个线程安全的内存管理器,使用观察者模式来通知所有线程内存使用情况的变化。如何确保在添加和移除内存块时的线程安全?如何确保任务的顺序执行和调度器的线程安全?
Java面试题:设计一个线程安全的内存管理器,使用观察者模式来通知所有线程内存使用情况的变化。如何确保在添加和移除内存块时的线程安全?如何确保任务的顺序执行和调度器的线程安全?
11 0
|
5天前
|
设计模式 并行计算 安全
Java面试题:如何使用设计模式优化多线程环境下的资源管理?Java内存模型与并发工具类的协同工作,描述ForkJoinPool的工作机制,并解释其在并行计算中的优势。如何根据任务特性调整线程池参数
Java面试题:如何使用设计模式优化多线程环境下的资源管理?Java内存模型与并发工具类的协同工作,描述ForkJoinPool的工作机制,并解释其在并行计算中的优势。如何根据任务特性调整线程池参数
10 0
|
5天前
|
存储 安全 Java
Java面试题:如何在Java应用中实现有效的内存优化?在多线程环境下,如何确保数据的线程安全?如何设计并实现一个基于ExecutorService的任务处理流程?
Java面试题:如何在Java应用中实现有效的内存优化?在多线程环境下,如何确保数据的线程安全?如何设计并实现一个基于ExecutorService的任务处理流程?
10 0
|
5天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
8 0