Featured image of post 高效管理定时事件

高效管理定时事件

高效管理定时任务可以使用时间轮算法。它通过固定槽位实现快速任务添加,适合大量任务处理。总结了多种算法的优缺点,助力选择合适的实施方案。

 

场景描述

假设有这么一个场景: 假设100w个Uber司机,司机客户端每隔10分钟上报一次数据,如果十分钟没有上报数据,服务端会将这个司机设置为离线状态,不给他派单。
我们应该如何实现这个功能?
通常的情况下,我们会使用redis的zset等第三方组件来实现这个功能,但是如果不使用第三方组件呢?只使用内存呢?大概有这么几种方案:

使用 Timer

  1. 用一个Map<uid, last_time>来记录每一个uid最近一次上报时间;
  2. 当某个用户uid存活上报时,实时更新这个Map;
  3. 启动一个timer,轮询扫描这个Map,看每个uid的last_time是否超过30s,如果超过则进行超时处理;
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

var (
	userMap sync.Map
	timeout = 10 * time.Minute
)
func checkTimeout() {
	now := time.Now().Unix()
	userMap.Range(func(key, value any) bool {
		uid := key.(string)
		lastTime := value.(int64)
		if now-lastTime > int64(timeout) {
			fmt.Printf("User %s timed out. Last reported at %d\n", uid, lastTime)
			userMap.Delete(uid) 
		}
		return true
	})
}

缺点:这种方式效率不高,因为需要定期轮询整个Map,时间复杂度较高。

使用gorutine 管理

另一种方案是为每个司机分配一个Goroutine来管理其心跳超时。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
timer := time.NewTimer(timeout * time.Second)
for {
	select {
	case <-heartbeat: // 收到心跳信号
		if !timer.Stop() {
			<-timer.C
		}
		timer.Reset(timeout * time.Second)
	case <-timer.C: // 超时
		fmt.Printf("Driver %s timed out.\n", uid)
		break
	}
}
userMap.Delete(uid)

缺点:虽然不需要轮询,但每个Goroutine都有栈空间,当司机数量非常多时,内存消耗会很大。此外,Timer的创建和删除时间复杂度为O(log n),效率有待提升。
前面铺垫了这么久,终于轮到我们的主角了,时间轮。

时间轮算法

时间轮算法示意图

时间轮是一个比较有趣的算法,他最早刊登在George Varghese和Tony Lauck的论文里。 时间轮算法的核心逻辑是:

  • 使用一个固定大小的数组表示时间轮,每个槽(slot)对应一个时间间隔。
  • 每个slot中保存一个slice,用于存储当前时间段到期的任务,同时有一个Map<uid,slot> 记录uid对应的solt。
  • 使用一个定时器定期(interval)推动时间轮向前走一格(position),处理当前solt(position)的所有任务.

所以我们可以使用时间轮算法来实现功能。我们可以将interval设置成1s, 时间轮的slots为600,司机上报数据的时候,将记录插入到position-1的slot里面。
一个简单的Demo:
https://gist.github.com/hxzhouh/5e2cedc633bae0a7cf27d9f5d47bef01

优势

  • 时间轮算法添加任务只需要将任务append 到对应的slot里面,所以时间复杂度是O(1)
  • 时间轮槽位固定,内存占用可控。
  • 适合处理大量定时任务

劣势

  • 时间轮的精度受限于interval 的大小。
  • 如果任务分配不均匀的话,Delete Task 可能退化到 O(n)

所以时间轮特别适合以下场景的任务:

  • 大量任务的快速插入
  • 对时间精度要求不是特别高的场景
  • 任务分布相对均匀的情况

时间轮的优化

简单时间轮

将所有任务的换算为多少秒或毫秒(Interval)后到期,维护一个最大过期值(Interval)长度的数组。比如有10个任务,分别是1s,3s,100s 后到期,就建一个100长度的数组,数组的index就是每个任务的过期值(Interval),当前时间作为第一个元素,那么第二个元素就是1s 后到期的任务,第三个是2s 后到期的任务,依次类推。当前时间随着时钟的前进(tick),逐步发现过期的任务。

  • 开始调度一个任务(start_timer): 来一个新的调度任务时,换算任务的到期时间为到期值(Interval),直接放入相应的数组元素内即可,时间复杂度是O(1)。
  • 时钟走一格,需要做的操作(per_tick_bookkeeping):时钟走一格直接拿出这一格内的任务执行即可,时间复杂度是O(1)。

Hash有序时间轮 (Demo中使用的就是这种方式的变种)

简单时间轮虽然很完美,所有的操作时间复杂度都是O(1),但是当任务最大到期时间值非常大时,比如100w,构建这样一个数组是非常耗费内存的。可以改进一下,仍然使用时间轮,但是是用hash的方式将所有任务放到一定大小的数组内。 这个数组长度可以想象为时间轮的格子数量,轮盘大小(W)。
hash的数值仍然是每个任务的到期值(Interval),最简单的是轮盘大小(W)取值为2的幂次方,Interval哈希W后取余,余数作为轮盘数组的index,数组每个元素可能会有多个任务,把这些任务按照过期的绝对时间排序,这样就形成了一个链表,或者叫做时间轮上的一个桶。
但是Hash有序时间轮 还是有一个问题:
因为只使用了一个时间轮,处理每一格的定时任务列表的时间复杂度是 O(n),如果定时任务数量很大,分摊到每一格的定时任务列表就会很长,这样的处理性能显然是让人无法接受的。

层级时间轮

层级时间轮通过使用多个时间轮,并且对每个时间轮采用不同的 u,可以有效地解决简单时间轮及其变体实现的问题。
参考 Kafka 的 Purgatory 中的层级时间轮实现:

  • 每一层时间轮的大小都固定为 n,第一层时间轮的时间单位为u,那么第二层时间轮(我们称之为第一层时间轮的溢出时间轮 Overflow Wheel)的时间单位就为 n*u,以此类推。
  • 除了第一层时间轮是固定创建的,其他层的时间轮(均为溢出时间轮)都是按需创建的。
  • 原先插入到高层时间轮(溢出时间轮)的定时任务,随着时间的流逝,会被降级重新插入到低层时间轮中。

总结

总结一下几种算法的性能。

算法 添加任务复杂度 删除任务复杂度 内存开销 适用场景
Single Timer O(1)O(1) O(1)O(1) 适用于任务数量少、精度要求高的场景。
Multi Timer O(log⁡n)O(\log n) O(log⁡n)O(\log n) 适用于任务数量中等、任务间相互独立的场景,但内存开销较高。
Simple Timing Wheel O(1)O(1) O(n)O(n) 高(大数组) 任务分布均匀、到期时间精度要求较低的场景。
Hash Timing Wheel O(1)O(1) O(n)O(n) 任务数量较多、分布不均匀但对精度容忍较高的场景。
Hierarchical Timing Wheel O(1)O(1) O(log⁡n)O(\log n) 低到中 适用于大规模任务、层级管理复杂任务、需要较长生命周期的任务调度场景(如 Kafka 和 Netty)。

参考资料

  1. 真实世界中的时间轮
  2. Hashed and Hierarchical Timing Wheels

  • 本文长期连接
  • 如果您觉得我的博客对你有帮助,请通过 RSS订阅我。
  • 或者在X上关注我。
  • 如果您有Medium账号,能给我个关注嘛?我的文章第一时间都会发布在Medium。
Licensed under CC BY-NC-SA 4.0
最后更新于 Jan 14, 2025 21:17 CST
使用 Hugo 构建
主题 StackJimmy 设计