文章总结（9）— 时间轮算法

作者: 小胖学编程 | 来源:发表于2023-04-22 11:47 被阅读0次

一张图理解Kafka时间轮(TimingWheel),看不懂算我
延时任务-基于netty时间轮算法实现
Kafka时间轮算法
一文搞定十大经典排序算法（Java实现）
优雅的时间轮算法
正则化dropout
2019-03-07 关键词：新的周期开始
day09-冒泡排序+优化
算法：二分查找
数据挖掘之---AprioriAll算法

【方案思索】如果一台机器上有10w个定时任务，如何做到高效触发？

最简单的方案：

用户线程：负责定时任务的注册；
定时任务队列轮询线程：负责扫描任务队列上符合要求的任务，如果任务的时间戳达到规定的时刻，首先从队列中取走此任务，然后将其交给异步线程池来处理；
异步线程池：负责定时任务的执行；

缺点：如果有 1k 个任务，那么定时任务队列轮询线程每次都需要扫描 1k 个任务来确定哪一个任务达到规定时刻，这种轮询效率非常差，尤其是在大部分任务并没有达到规定执行时刻的情况下。

改进措施1：使用有序的队列（例如最小堆）这样可以显著提升遍历效率。插入一个定时任务的事件复杂度为 O(nlogn)，普通任务队列的插入仅仅是 O(1)。

改进措施2：任务分类+多队列+并发线程，这种方式主要是试图利用现代 CPU 的多核并发性来解决遍历效率低的问题。例如我们将 10w 大小的任务队列分为 10 个任务队列，此时每一个任务队列的大小仅仅是 1w。在线程完全并发执行的情况下，将 10w 规模的问题简化为 1w 规模的问题。多并发线程轮询的副作用非常大：线程是一种宝贵资源，如果一个系统有大量的定时调度任务，那么CPU 会因为多条并发轮询线程而有着非常低的执行效率。

【时间轮算法】如果一台机器上有10w个定时任务，如何做到高效触发？

对于海量数据的处理，核心的处理方式是对问题分治：按照时间刻度对任务进行划分。

时间轮算法的核心是：轮询线程不再负责遍历所有任务，而是仅仅遍历时间刻度。时间轮算法好比指针不断在时钟上旋转、遍历，如果一个发现某一时刻上有任务（任务队列），那么就会将任务队列上的所有任务都执行一遍。

优点：时间轮算法可以解决遍历效率低的问题。时间轮算法中，轮询线程遍历到某一个时间刻度后，总是执行对应刻度上任务队列中的所有任务（通常是将任务扔给异步线程池来处理），而不再需要遍历检查所有任务的时间戳是否达到要求。

【时间刻度增多】任务有毫秒、分钟、小时、天等等时，单纯增加时间刻度会导致轮询效率低，如何去处理？

带有round的时间轮算法：时间轮的精度设置为秒，时间刻度个数固定为 60。每一个任务拥有一个 round 字段。

轮询线程的执行逻辑是：每隔一秒处理一个时间刻度上任务队列中的所有任务，任务的 round 字段减 1，接着判断如果 round 字段的值变为 0，那么将任务移出任务队列，交给异步线程池来执行对应任务。如果是重复执行任务，那么再将任务添加到任务队列中。

缺点：这种方式虽然简化了时间轮的刻度个数，但是并没有简化轮询线程运行效率不高的问题。时间轮每次处理一个时间刻度，就需要处理其上任务队列的所有任务。其运行效率甚至与基于普通任务队列实现的定时任务框架没有区别。

分层时间轮算法：类似现实的钟表，由多个环形数组组成，将任务散列到多个环形数组中。（例如：每个环形数组包含20个时间单位，表示一个时间维度（一轮），如：第一层时间轮，数组中的每个元素代表1ms，一圈就是20ms，当延迟时间大于20ms时，就“进位”到第二层时间轮，第二层中，每“一格”表示20ms，依此类推…）

分层时间轮的降级方式？

当时间“推进”到某个bucket时，说明该bucket中的任务在当前时间轮中的时间已经走完，需要进行“降级”，即进入更小粒度的时间轮中。

如何减少空推进（时间是如何推进的）？

一种直观的想法是，像现实中的钟表一样，“一格一格”地走，这样就需要有一个线程一直不停的执行，而大多数情况下，时间轮中的bucket（桶）大部分是空的，指针的“推进”就没有实质作用，因此，为了减少这种“空推进”，Kafka引入了DelayQueue，以bucket为单位入队，每当有bucket到期，即queue.poll能拿到结果时，才进行时间的“推进”，减少了 ExpiredOperationReaper 线程空转的开销。

有一个APP实时消息通道系统，对每个用户会维护一个APP到服务器的TCP连接，用来实时收发消息，对这个TCP连接，有这样一个需求：“如果连续30s没有请求包（例如登录，消息，keepalive包），服务端就要将这个用户的状态置为离线”。其中，单机TCP同时在线量约在10w级别，keepalive请求包较分散大概30s一次，吞吐量约在3000qps。