面试Java后端却问我时间轮算法,面试官没想到我看过Dubbo源码!(下)

简介: 面试Java后端却问我时间轮算法,面试官没想到我看过Dubbo源码!(下)

HashedWheelTimer

Timer 接口的实现,通过时间轮算法实现了一个定时器。

职能

根据当前时间轮指针选定对应 HashedWheelBucket 槽,从链表头部开始迭代,计算每个 HashedWheelTimeout 定时任务:

  • 属于当前时钟周期则取出运行
  • 不属于则将其剩余的时钟周期数减一

核心域

workerState

时间轮当前所处状态,三个可选值,由 AtomicIntegerFieldUpdater 实现其原子地修改。

image.pngstartTime

当前时间轮的启动时间,提交到该时间轮的定时任务的 deadline 字段值均以该时间戳为起点进行计算。

image.png

wheel

时间轮环形队列,每个元素都是一个槽。当指定时间轮槽数为 n 时,会向上取最靠近 n 的 2 次幂值

image.png

timeouts、cancelledTimeouts

HashedWheelTimer 会在处理 HashedWheelBucket 的双向链表前,先处理这俩队列的数据:


timeouts 队列

缓冲外部提交时间轮中的定时任务

cancelledTimeouts 队列

暂存取消的定时任务

image.png

tick

位于 HashedWheelTimer$Worker ,时间轮的指针,步长为 1 的单调递增计数器

image.png

mask

掩码, mask = wheel.length - 1,执行 ticks & mask 便能定位到对应的时钟槽

image.png

ticksDuration

时间指针每次加 1 所代表的实际时间,单位为纳秒。

image.png

pendingTimeouts

当前时间轮剩余的定时任务总数。

image.png

workerThread

时间轮内部真正执行定时任务的线程。

image.png

worker

真正执行定时任务的逻辑封装这个 Runnable 对象中。

image.png

newTimeout()

提交定时任务,在定时任务进入到 timeouts 队列之前会先调用 start() 方法启动时间轮,其中会完成下面两个关键步骤:

  1. 确定时间轮的 startTime 字段
  2. 启动 workerThread 线程,开始执行 worker 任务。

之后根据 startTime 计算该定时任务的 deadline,最后才能将定时任务封装成 HashedWheelTimeout 并添加到 timeouts 队列。

4 时间轮指针一次转动的执行流程

HashedWheelTimer$Worker.run()

  1. 时间轮指针转动,时间轮周期开始
  2. 清理用户主动取消的定时任务,这些定时任务在用户取消时,记录到 cancelledTimeouts 队列中。在每次指针转动的时候,时间轮都会清理该队列
  3. 将缓存在 timeouts 队列中的定时任务转移到时间轮中对应的槽中
  4. 根据当前指针定位对应槽,处理该槽位的双向链表中的定时任务
  5. 检测时间轮的状态。如果时间轮处于运行状态,则循环执行上述步骤,不断执行定时任务。如果时间轮处于停止状态,则执行下面的步骤获取到未被执行的定时任务并加入 unprocessedTimeouts 队列:遍历时间轮中每个槽位,并调用 clearTimeouts() 方法;对timeouts 队列中未被加入槽中循环调用 poll()
  1. 最后再次清理 cancelledTimeouts 队列中用户主动取消的定时任务。

5 定时任务应用

并不直接用于周期性操作,而是只向时间轮提交执行单次的定时任务,在上一次任务执行完成的时候,调用 newTimeout() 方法再次提交当前任务,这样就会在下个周期执行该任务。即使在任务执行过程中出现了 GC、I/O 阻塞等情况,导致任务延迟或卡住,也不会有同样的任务源源不断地提交进来,导致任务堆积。


Dubbo 时间轮应用主要在如下方面:

失败重试, 例如,Provider 向注册中心进行注册失败时的重试操作,或是 Consumer 向注册中心订阅时的失败重试等

周期性定时任务, 例如,定期发送心跳请求,请求超时的处理,或是网络连接断开后的重连机制


参考

https://zhuanlan.zhihu.com/p/32906730


目录
打赏
0
0
0
0
1888
分享
相关文章
Java大厂面试高频:Collection 和 Collections 到底咋回答?
Java中的`Collection`和`Collections`是两个容易混淆的概念。`Collection`是集合框架的根接口,定义了集合的基本操作方法,如添加、删除等;而`Collections`是一个工具类,提供了操作集合的静态方法,如排序、查找、同步化等。简单来说,`Collection`关注数据结构,`Collections`则提供功能增强。通过小王的面试经历,我们可以更好地理解这两者的区别及其在实际开发中的应用。希望这篇文章能帮助你掌握这个经典面试题。
30 4
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
114 2
Java社招面试中的高频考点:Callable、Future与FutureTask详解
大家好,我是小米。本文主要讲解Java多线程编程中的三个重要概念:Callable、Future和FutureTask。它们在实际开发中帮助我们更灵活、高效地处理多线程任务,尤其适合社招面试场景。通过 Callable 可以定义有返回值且可能抛出异常的任务;Future 用于获取任务结果并提供取消和检查状态的功能;FutureTask 则结合了两者的优势,既可执行任务又可获取结果。掌握这些知识不仅能提升你的编程能力,还能让你在面试中脱颖而出。文中结合实例详细介绍了这三个概念的使用方法及其区别与联系。希望对大家有所帮助!
85 60
Java线程调度揭秘:从算法到策略,让你面试稳赢!
在社招面试中,关于线程调度和同步的相关问题常常让人感到棘手。今天,我们将深入解析Java中的线程调度算法、调度策略,探讨线程调度器、时间分片的工作原理,并带你了解常见的线程同步方法。让我们一起破解这些面试难题,提升你的Java并发编程技能!
39 16
Java面试必问!run() 和 start() 方法到底有啥区别?
在多线程编程中,run和 start方法常常让开发者感到困惑。为什么调用 start 才能启动线程,而直接调用 run只是普通方法调用?这篇文章将通过一个简单的例子,详细解析这两者的区别,帮助你在面试中脱颖而出,理解多线程背后的机制和原理。
35 12
Java后端开发-使用springboot进行Mybatis连接数据库步骤
本文介绍了使用Java和IDEA进行数据库操作的详细步骤,涵盖从数据库准备到测试类编写及运行的全过程。主要内容包括: 1. **数据库准备**:创建数据库和表。 2. **查询数据库**:验证数据库是否可用。 3. **IDEA代码配置**:构建实体类并配置数据库连接。 4. **测试类编写**:编写并运行测试类以确保一切正常。
15 2
【Java若依框架】RuoYi-Vue的前端和后端配置步骤和启动步骤
本文介绍了如何配置和启动基于Java的若依(RuoYi)项目,涵盖后端和前端的详细步骤。首先,准备Redis、MySQL以及IDE(如Idea和VS)。接着,通过GitHub获取代码并导入到IDE中,执行必要的SQL文件和配置数据库密码。然后,启动Redis并进行相关配置。最后,按照前端配置步骤克隆前端代码库,打开终端执行命令完成前端配置。整个过程详细记录了每一步的操作,帮助开发者顺利部署若依项目。 如果你觉得有帮助,请点赞、关注和收藏,这将是我持续分享的动力!
66 1
Java Dubbo 面试题
Java Dubbo相关基础面试题
Java MyBatis 面试题
Java MyBatis相关基础面试题
Java JVM 面试题
Java JVM(虚拟机)相关基础面试题

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等