# timewheel

**Repository Path**: bossDuy/timewheel

## Basic Information

- **Project Name**: timewheel
- **Description**: 时间轮算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-08-06
- **Last Updated**: 2025-08-06

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

延迟任务的实现：

1. 优先队列存储任务，时间精度比较好   ，但是插入元素的时间是O(log(N))，元素多的时候比较慢，也就是无法满足大吞吐量的要求
2. 时间轮，牺牲了时间精度，插入的时间复杂度是O(1)；需要高吞吐的组件维持大量延迟任务，并且对及时性要求不高，比如IO事件处理

# 时间轮

## 原理

核心组成：

- 时间轮盘（数组）：整个环形数据结构
- 基准时间：数组中表示时间都是按照这个基准来表示的，第一个0-99ms就是 基准时间+0-99ms
- 槽位(slot)：时间轮上的分隔，每个槽位表示一段时间间隔
- 指针：指示当前时间，随时间推移顺时针移动
- 任务链表：挂载在每个槽位上的待执行任务集合

![输入图片说明](img/img1.pngimage.png)

比如，我们设定一个slot为100ms，那么具体队对应的任务应该放到哪一个时间槽如下

因为每一个槽都是100ms，所以对于时间轮来讲 10ms和99ms 都是应该同时执行的，正如前面所说，时间轮牺牲了时间的精准度换得取任务时间复杂度为O(1)

> 对于超过数组长度所表示的时间，使用 目标时间对数组最大表示时间取余


![输入图片说明](img/img2.pngimage.png)

实现的话可以通过数组和链表表示延时任务，时间轮通过定时的取扫描当前槽的任务是否需要执行

- 扫描的时候是需要扫描整个链表（存储任务的）的，还是O(N)，但是不需要扫描所有的延迟任务，被数组切割开了
- 插入任务的时候，只需要把任务计算到对应的位置然后插入，时间复杂度是O(1)