> ## Content Index
> Fetch the complete content index at: https://huizhou92.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 如何高效管理定时事件
- URL: https://huizhou92.com/e9-ab-98-e6-95-88-e7-ae-a1-e7-90-86-e5-ae-9a-e6-97-b6-e4-ba-8b-e4-bb-b6/
- Published: 2025-01-14T13:18:02.000Z
- Updated: 2026-09-06T11:40:47.000Z
- Description: 如何高效管理定时事件. 场景描述 假设有这么一个场景： 假设100w个Uber司机，司机客户端每隔10分钟上报一次数据，如果十分钟没有上报数据，服务端会将这个司机设置为离线状态，不给他派单。 我们应该如何实现这个功能？ 通常的情况下，我们会使用redis的zset等第三方组件来实现这个功能，但是如果不使用第三。
- Author: huizhou92
- Tags: tech, golang, #lang-zh-cn

## 场景描述

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

## 使用 Timer

1. 用一个Map<uid, last\_time>来记录每一个uid最近一次上报时间；
2. 当某个用户uid存活上报时，实时更新这个Map；
3. 启动一个timer，轮询扫描这个Map，看每个uid的last\_time是否超过30s，如果超过则进行超时处理；

```go

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来管理其心跳超时。

```go
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)，效率有待提升。  
前面铺垫了这么久，终于轮到我们的主角了，时间轮。

# 时间轮算法

![时间轮算法示意图](https://images.hxzhouh.com/blog-images/2025/01/3dd09d201f36757e8aa9b8280ee35476.webp)

时间轮是一个比较有趣的算法，他最早刊登在George Varghese和Tony Lauck的[论文](https://dl.acm.org/doi/pdf/10.1145/37499.37504?ref=huizhou92.com)里。 时间轮算法的核心逻辑是：

- 使用一个固定大小的数组表示时间轮，每个槽（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](https://gist.github.com/hxzhouh/5e2cedc633bae0a7cf27d9f5d47bef01?ref=huizhou92.com)

### 优势

- 时间轮算法添加任务只需要将任务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](https://www.confluent.io/blog/apache-kafka-purgatory-hierarchical-timing-wheels/?ref=huizhou92.com) 中的层级时间轮实现：

- 每一层时间轮的大小都固定为 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. 真实世界中的时间轮  
  - Netty4 的 [HashedWheelTimer](https://netty.io/4.0/api/io/netty/util/HashedWheelTimer.html?ref=huizhou92.com)。
  - Kafka 的 [Purgatory](https://www.confluent.io/blog/apache-kafka-purgatory-hierarchical-timing-wheels/?ref=huizhou92.com)。
  - go-zero 的[NewTimingWheel](https://github.com/zeromicro/go-zero/blob/12071d17b40f4b58ba541747cab9eda30955c18c/core/collection/timingwheel.go?ref=huizhou92.com#L66)
2. [Hashed and Hierarchical Timing Wheels](https://paulcavallaro.com/blog/hashed-and-hierarchical-timing-wheels/?ref=huizhou92.com)

---

- [本文长期连接](https://huizhou92.com/e9-ab-98-e6-95-88-e7-ae-a1-e7-90-86-e5-ae-9a-e6-97-b6-e4-ba-8b-e4-bb-b6)
- 如果您觉得我的博客对你有帮助，请通过 [RSS](https://huizhou92.com/sitemap.xml)订阅我。
- 或者在[X](https://x.com/@piaopiaopig?ref=huizhou92.com)上关注我。
- 如果您有[Medium](https://medium.huizhou92.com/?ref=huizhou92.com)账号，能给我个关注嘛？我的文章第一时间都会发布在Medium。