您现在的位置是:首页 >技术交流 >时间轮的golang实践浅析网站首页技术交流
时间轮的golang实践浅析
简介时间轮的golang实践浅析
引言
- 下列代码模仿一段RPC请求的执行过程,执行后会有哪些问题:
RPC代码示例 - 答案:因为超时控制后未阻断后续请求,导致并发读写产生Panic
- 思考:客户端发起 HTTP 请求后,如果在指定时间内没有收到服务器的响应,则自动断开连接,超时控制是如何工作的?
什么是时间轮
- 思考:一定有一个类似于定时器的工具在执行,到时间后,中断任务。那么这个定时器是什么样的数据结构?又是如何实现这个定时功能的?
- 理论上
- 客户端发起请求后,立即创建(启动)一个 Timer:到期间隔为 d,到期后执行 “断开连接” 的操作。
- 如果到期间隔 d 以内收到了服务器的响应,客户端就删除(停止)这个 Timer。
- 如果一直没有收到响应,则 Timer 最终会到期,然后执行 “断开连接” 的操作。
- 实际上
- 现代的 Web 服务动辄管理 100w+ 的连接,每个连接都会有很多超时任务(比如发送超时、心跳检测等),如果每个超时任务都对应一个 Timer,性能会比较低下
- 破解之法:采用时间轮实现的 Timer来管理连接任务,使得创建和删除连接任务的时间复杂度为 O(1)
时间轮种类和设计思路
- 常见的时间轮实现有两种:
- 简单时间轮(Simple Timing Wheel)—— 比如 Netty4 的 HashedWheelTimer
- 层级时间轮(Hierarchical Timing Wheels)—— 比如 Kafka 的 Purgatory
简单时间轮
简单时间轮的设计思路
- 一个 简单时间轮就是一个循环列表,列表中的每一格包含一个定时任务列表(双向链表)。一个时间单位为 u、大小为 n 的简单时间轮,可以包含的定时任务的最大到期间隔为 n*u。
- 以 u 为 1ms、n 为 3 的简单时间轮为例,可以包含的定时任务的最大到期间隔为 3ms
简单时间轮示例
简单时间轮的实现
index := 0
timingWheels := make([]interface{}, 10)
for { // 循环消费任务
time.Sleep(1 * time.Second)
index = index % len(timingWheels)
task := timingWheels[index]
fmt.Println(task) // exec task
index++
}
{ // 增加任务
x := 2 // 2s 后执行
task_i := "任务i"
timingWheels[(index+x)%len(timingWheels)] = task_i
}
简单时间轮的缺陷
- 一旦选定 n,就不能包含到期间隔超过 n*u 的定时任务
- 解决办法:选择较大的n
- 引申问题:如果定时任务的到期时间跨度较大,就会选择较大的 n,在定时任务较少时会造成很大的空间浪费
- 引申问题的解决办法:在定时任务中增加记录 round 轮次信息,可以有效弥补上述两个缺点。同样以上面 u 为 1ms、n 为 3 的简单时间轮为例,初始时间指向第 1 格;此时如果要创建到期时间为 4ms 的定时任务,可以在该任务中设置 round 为 1(4/3 取整),剩余到期时间用 4ms 减去 round*3ms 等于 1ms,因此放到第 2 格;等到当前时间指向第 2 格时,判断任务中的 round 大于 0,所以不会删除并执行该任务,而是对其 round 减一(于是 round 变为 0);等到再过 3ms 后,当前时间再次指向第 2 格,判断任务中的 round 为 0,进而删除并执行该任务
index := 0
timingWheels := make([]timingWheelsTask, 10)
for { // 循环消费任务
time.Sleep(1 * time.Second)
index = index % len(timingWheels)
cur := timingWheels[index]
if cur.round != 0 {
cur.round--
} else {
fmt.Println(cur.task) // exec task
}
index++
}
{ // 增加任务
x := 20 // 2s 后执行
round_i := x / len(timingWheels)
index_i := x % len(timingWheels)
task_i := timingWheelsTask{
round: round_i,
task: "任务i",
}
timingWheels[index_i] = task_i
}
type timingWheelsTask struct {
round int
task interface{}
}
- 再次引申问题:每格轮子只能存放一个task,如果在同一时间,需要执行多个任务,怎么办?
- 再次引申问题的解决办法:将timingWheelsTask结构体修改为:
type timingWheelsTask struct {
taskList []TaskList
}
type TaskList struct {
round int
task interface{}
}
- 再一次引申问题:TaskList的处理时间是O(n),如果定时任务数量很大,分摊到每一格的定时任务列表就会很长,这样的处理性能显然是让人无法接受的,特别是对于时间精度要求比较高的任务,另外就是由于list过长,导致for循环完list后,当前index的时间已经过了,长此以往,会导致整体时间轮的精度不准确,延误后面的task执行。
- 问题到此看似无解
层级时间轮
层级时间轮的设计思路
- 层级时间轮 通过使用多个时间轮,并且对每个时间轮采用不同的 u,可以有效地解决简单时间轮及其变体实现的问题
- 理论上
- 每一层时间轮的大小都固定为 n,第一层时间轮的时间单位为 u,那么第二层时间轮(我们称之为第一层时间轮的溢出时间轮 Overflow Wheel)的时间单位就为 n*u,以此类推。
- 除了第一层时间轮是固定创建的,其他层的时间轮(均为溢出时间轮)都是按需创建的。
- 原先插入到高层时间轮(溢出时间轮)的定时任务,随着时间的流逝,会被降级重新插入到低层时间轮中
层级时间轮实例
- 以 u 为 1ms、n 为 3 的层级时间轮为例,第一层时间轮的时间单位为 1ms、大小为 3,第二层时间轮的时间单位为 3ms、大小为 3,以此类推
- 运行原理
- 初始时,只有第一层(Level 1)时间轮,假设当前时间(蓝色箭头)指向第 1 格(此时:到期间隔为 [0ms, 1ms) 的定时任务放第 1 格,[1ms, 2ms) 的放第 2 格,[2ms, 3ms) 的放第 3 格)。
- 此时我们创建一个到期间隔为 2ms 的定时任务 task1,按规则该任务会被插入到第一层时间轮的第 3 格。
- 同一时刻,我们再次创建一个到期间隔为 4ms 的定时任务 task2,因为到期间隔超过了第一层时间轮的间隔范围,所以会创建第二层(Level 2)时间轮;第二层时间轮中的当前时间(蓝色箭头)也指向第 1 格,按规则该任务会被插入到第二层时间轮的第 2 格。
- 随着时间的流逝,过了 2ms 后,第一层时间轮中的当前时间指向第 3 格,这一格包含的任务 task1 会被删除并执行;此时,第二层时间轮的当前时间没有变化,依然指向第 1 格。
- 随着时间的流逝,又过了 1ms 后,第一层时间轮中的当期时间指向第 1 格,这一格中没有任务;此时,第二层当前时间指向第 2 格,这一格包含的任务 task2 会被删除并重新插入时间轮,因为剩余到期时间为 1ms,所以 task2 会被插入到第一层时间轮的第 2 格。
- 随着时间的流逝,又过了 1ms 后,第一层时间轮中的当前时间指向第 2 格,这一格包含的定时任务 task2 会被删除并执行;此时,第二层时间轮的当前时间没有变化,依然指向第 2 格。
层级时间轮的实现
- timingwheel源码
- Kafka 的变体实现【指针不动,桶往前走】
- 使用大小为 wheelSize 的数组来表示一层时间轮,其中每一格是一个 bucket,每个 bucket 的时间单位为 tick。
- 这个时间轮数组并没有模拟循环列表的行为(如图左所示),而是模拟了哈希表的行为。具体而言(如图右所示),这个时间轮数组会随着 currentTime 的流逝而移动,也就是说 currentTime 永远是指向第一个 bucket 的,每个落到该时间轮的定时任务,都会根据哈希函数 (expiration/tick)%wheelSize 散列到对应的 bucket 中。
- Kafka Timer 实现源码
- 时钟驱动方式
- 常规的时间轮实现中,会在一个线程中每隔一个时间单位 tick 就醒来一次,并驱动时钟走向下一格,然后检查这一格中是否包含定时任务。如果时间单位 tick 很小(比如 Kafka 中 tick 为 1ms)并且(在最低层时间轮的)定时任务很少,那么这种驱动方式将会非常低效
- Kafka 的层级时间轮实现中,利用了 Java 内置的 DelayQueue 结构,将每一层时间轮中所有 “包含有定时任务的 bucket” 都加入到同一个 DelayQueue 中,然后 等到有 bucket 到期后再驱动时钟往前走,并逐个处理该 bucket 中的定时任务。
- 图解
- 往层级时间轮中添加一个定时任务 task1 后,会将该任务所属的 bucket2 的到期时间设置为 task1 的到期时间 expiration(= 当前时间 currentTime + 定时任务到期间隔 duration),并将这个 bucket2 添加(Offer)到 DelayQueue 中。
- DelayQueue(内部有一个线程)会等待 “到期时间最早(earliest)的 bucket” 到期,图中等到的是排在队首的 bucket2,于是经由 poll 返回并删除这个 bucket2;随后,时间轮会将当前时间 currentTime 往前移动到 bucket2 的 expiration 所指向的时间(图中是 1ms 所在的位置);最后,bucket2 中包含的 task1 会被删除并执行。
- 上述 Kafka 层级时间轮的驱动方式是非常高效的。虽然 DelayQueue 中 offer(添加)和 poll(获取并删除)操作的时间复杂度为 O(log n),但是相比定时任务的个数而言,bucket 的个数其实是非常小的(也就是 O(log n) 中的 n 很小),因此性能也是没有问题的
时间轮源码分析
- PriorityQueue 优先队列
- Push
- Pop
- PeekAndShift
- DelayQueue 延时队列
- Offer
- Poll
- Timer 定时器 event
- getBucket
- setBucket
- bucket 时间轮的桶
- Expiration
- SetExpiration
- Add
- Remove
- Flush
- TimingWheel 时间轮本轮
- add
- addOrRun
- advanceClock
- Start
- AfterFunc
- Scheduler 调度时间轮
- ScheduleFunc
参考
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。