去字节面试被面这题能答上来吗?谈谈你对时间轮的理解?
1.什么是时间轮
时间轮,简单理解就是一种=个用来存储定时任务的环状数组,它的工作原理和钟表的表盘类似。
它由两个部分组成, 一个是环状数组,另一个是遍历环状数组的指针。
首先,要定义一个固定长度的环状数组,然后数组的每一个元素代表一个时间刻度,假设每个刻度间隔是 1s,那么长度为 8 的数组,就代表 8 秒钟。
然后,就是有一个指针,这个指针按照顺时针无限地循环这个数组,每隔1个最小的时间单位就前进一个数组索引。
这个指针完整地转1圈,就代表 8 秒钟,转两圈表示 16 秒,假设从 0 点 0 分 0 秒开始,转
一圈以后就到了 0 点 0 分 9 秒钟。
2.工作原理
时间轮,环状数组里面的每个元素,都是用来存储定时任务的容器,当我们向时间轮里面添加一个定时任务的时候,我们会根据定时任务的执行时间计算它所存储的数组下标。当然,有可能在某个时间刻度上会存在多个定时任务,这个时候会采用双向链表的方式来存储。
当指针指向某个数组的时候,就会把这个数组中存储的任务取出来,然后遍历这个链表逐个运行里面的任务。
那如果某个定时任务的执行时间大于环形数组所表示的长度,一般可以使用一个圈数来表示该任务的延迟执行时间。比如,1个第 16 秒要执行的任务,那意味着这个任务应该是在第2圈的数组下标 为0 的位置执行。
3.优、缺点分析
使用时间轮的方式来管理多个定时任务的好处有很多,我认为有两个比较重要的优点:
(1)减少定时任务添加和删除的时间复杂度,提升性能。
(2)可以保证每次执行定时器任务都是 O(1)复杂度,在定时器任务密集的情况下,性能优势非常明显。
当然,时间轮也有缺点,对于执行时间非常严格的任务,时间轮不是很适合,因为时间轮算法的精度取决于最小时间单元的粒度。假设以 1s 为一个时间刻度,那小于 1s 的任务就无法被时间轮调度。
时间轮算法在很多框架中都有用到,比如 Dubbo、Netty、Kafka 等。
时间轮算法也是一个比较经典的设计。使用范围比较广,但是在实际应用中,大部分同学接触非常少。我认为这种设计思想或者这种数据结构,在我们实际应用中的某些特定场景也是可以借鉴和使用的。比如定时重试、衰减重试等等。
相关文章
- 基于Python的人脸识别考勤监控
- Python答题游戏
- Python调用百度API实现图像识别
- Python全栈疫情分析项目
- Python-基础-if语句快速入门
- Python-基础-循环语句快速入门
- Python-GUI签名
- 【2】VScode 搭建python和tensorflow环境
- python 简易时钟
- 【1】windows系统如何安装后缀是whl的python库
- 【2】超级详细Python-matplotlib画图,手把手教你画图!(线条颜色、大小、线形、标签)
- 【4】python读写文件操作---详细讲解!
- 【2】Anaconda下:ipython文件的打开方式,Jupyter Notebook中运行.py文件,快速打开ipython文件的方法!
- 【编写环境一】遇到常见python函数处理方式
- 【编写环境二】python库scipy.stats各种分布函数生成、以及随机数生成【泊松分布、正态分布等】
- Python xlwt数据保存到 Excel中以及xlrd读取excel文件画图
- 强化学习技巧三:Python多进程
- 强化学习技巧五:numba提速python程序
- 【7】python_matplotlib 输出(保存)矢量图方法;画图时图例说明(legend)放到图像外侧;Python_matplotlib图例放在外侧保存时显示不完整问题解决
- 【8】python_matplotlib改变横坐标和纵坐标上的刻度(ticks)、sagemath-list_plot()调整图例(legend)中点的数量、Matplotlib画各种论文图