您现在的位置是:首页 >技术交流 >时间轮的golang实践浅析网站首页技术交流

时间轮的golang实践浅析

New俊 2024-06-17 10:13:52
简介时间轮的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

参考

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。