一位工作了 7 年的程序员,去字节面试,被问到时间轮的问题。他说这个问题超出了他的知识面,自己也在网上也找了一些文章学习,但还是理解得不是很深刻。他希望让我出一期关于时间轮的面试题解析。今天,就给这位粉丝安排。
另外,我把往期分享的视频全部整理成一份500页的PDF面试题解析配套文档,希望能够以此来提高各位粉丝的通过率,
如何获取? :
扫描文章底部名片领取!
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 等。
时间轮算法也是一个比较经典的设计。使用范围比较广,但是在实际应用中,大部分同学接触非常少。我认为这种设计思想或者这种数据结构,在我们实际应用中的某些特定场景也是可以借鉴和使用的。比如定时重试、衰减重试等等。
最后,我把往期分享的面试题全部整理成了1份10W字的文档,希望能够以此来提高各位粉丝的通过率