面试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


目录
相关文章
|
1月前
|
算法 Java
50道java集合面试题
50道 java 集合面试题
|
4月前
|
缓存 Java 关系型数据库
2025 年最新华为 Java 面试题及答案,全方位打造面试宝典
Java面试高频考点与实践指南(150字摘要) 本文系统梳理了Java面试核心考点,包括Java基础(数据类型、面向对象特性、常用类使用)、并发编程(线程机制、锁原理、并发容器)、JVM(内存模型、GC算法、类加载机制)、Spring框架(IoC/AOP、Bean生命周期、事务管理)、数据库(MySQL引擎、事务隔离、索引优化)及分布式(CAP理论、ID生成、Redis缓存)。同时提供华为级实战代码,涵盖Spring Cloud Alibaba微服务、Sentinel限流、Seata分布式事务,以及完整的D
261 0
|
12天前
|
设计模式 缓存 安全
提供一些准备Java八股文面试的建议
准备Java八股文面试需系统梳理核心知识点,涵盖Java基础、集合、多线程、JVM、设计模式及主流框架。重在理解原理而非死记硬背,结合源码与实际场景深化认知。通过思维导图构建知识体系,分模块刷题并模拟面试表达,关联项目经验,体现应用能力。关注Java新特性与技术演进,避免知识过时。最终实现从“背答案”到“懂原理、能实战”的转变,提升综合竞争力。(238字)
114 7
|
3月前
|
缓存 Java API
Java 面试实操指南与最新技术结合的实战攻略
本指南涵盖Java 17+新特性、Spring Boot 3微服务、响应式编程、容器化部署与数据缓存实操,结合代码案例解析高频面试技术点,助你掌握最新Java技术栈,提升实战能力,轻松应对Java中高级岗位面试。
369 0
|
12天前
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
3月前
|
Java 数据库连接 数据库
Java 相关知识点总结含基础语法进阶技巧及面试重点知识
本文全面总结了Java核心知识点,涵盖基础语法、面向对象、集合框架、并发编程、网络编程及主流框架如Spring生态、MyBatis等,结合JVM原理与性能优化技巧,并通过一个学生信息管理系统的实战案例,帮助你快速掌握Java开发技能,适合Java学习与面试准备。
162 2
Java 相关知识点总结含基础语法进阶技巧及面试重点知识
|
1月前
|
算法 Java
50道java基础面试题
50道java基础面试题
|
4月前
|
算法 架构师 Java
Java 开发岗及 java 架构师百度校招历年经典面试题汇总
以下是百度校招Java岗位面试题精选摘要(150字): Java开发岗重点关注集合类、并发和系统设计。HashMap线程安全可通过Collections.synchronizedMap()或ConcurrentHashMap实现,后者采用分段锁提升并发性能。负载均衡算法包括轮询、加权轮询和最少连接数,一致性哈希可均匀分布请求。Redis持久化有RDB(快照恢复快)和AOF(日志更安全)两种方式。架构师岗涉及JMM内存模型、happens-before原则和无锁数据结构(基于CAS)。
136 5
|
4月前
|
安全 Java API
2025 年 Java 校招面试常见问题及详细答案汇总
本资料涵盖Java校招常见面试题,包括Java基础、并发编程、JVM、Spring框架、分布式与微服务等核心知识点,并提供详细解析与实操代码,助力2025校招备战。
236 1
|
3月前
|
缓存 Java 关系型数据库
Java 面试经验总结与最新 BAT 面试资料整理含核心考点的 Java 面试经验及最新 BAT 面试资料
本文汇总了Java面试经验与BAT等大厂常见面试考点,涵盖心态准备、简历优化、面试技巧及Java基础、多线程、JVM、数据库、框架等核心技术点,并附实际代码示例,助力高效备战Java面试。
121 0

热门文章

最新文章