网站怎么做邮箱,忂州网站建设,一般做网站用什么字体,手机上如何写html网页引言
下列代码模仿一段RPC请求的执行过程#xff0c;执行后会有哪些问题#xff1a; RPC代码示例答案#xff1a;因为超时控制后未阻断后续请求#xff0c;导致并发读写产生Panic思考#xff1a;客户端发起 HTTP 请求后#xff0c;如果在指定时间内没有收到服务器的响应…引言
下列代码模仿一段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 : 0timingWheels : make([]interface{}, 10)for { // 循环消费任务time.Sleep(1 * time.Second)index index % len(timingWheels)task : timingWheels[index]fmt.Println(task) // exec taskindex}{ // 增加任务x : 2 // 2s 后执行task_i : 任务itimingWheels[(indexx)%len(timingWheels)] task_i}简单时间轮的缺陷
一旦选定 n就不能包含到期间隔超过 n*u 的定时任务 解决办法选择较大的n 引申问题如果定时任务的到期时间跨度较大就会选择较大的 n在定时任务较少时会造成很大的空间浪费 引申问题的解决办法在定时任务中增加记录 round 轮次信息可以有效弥补上述两个缺点。同样以上面 u 为 1ms、n 为 3 的简单时间轮为例初始时间指向第 1 格此时如果要创建到期时间为 4ms 的定时任务可以在该任务中设置 round 为 14/3 取整剩余到期时间用 4ms 减去 round*3ms 等于 1ms因此放到第 2 格等到当前时间指向第 2 格时判断任务中的 round 大于 0所以不会删除并执行该任务而是对其 round 减一于是 round 变为 0等到再过 3ms 后当前时间再次指向第 2 格判断任务中的 round 为 0进而删除并执行该任务 index : 0timingWheels : 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 inttask interface{}}再次引申问题每格轮子只能存放一个task如果在同一时间需要执行多个任务怎么办 再次引申问题的解决办法将timingWheelsTask结构体修改为 type timingWheelsTask struct {taskList []TaskList}type TaskList struct {round inttask 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 优先队列 PushPopPeekAndShift DelayQueue 延时队列 OfferPoll Timer 定时器 event getBucketsetBucket bucket 时间轮的桶 ExpirationSetExpirationAddRemoveFlush TimingWheel 时间轮本轮 addaddOrRunadvanceClockStartAfterFunc Scheduler 调度时间轮 ScheduleFunc
参考
层级时间轮的 Golang 实现
