基于Golang实现延迟队列(DelayQueue)
在Golang实战开发的过程中,我们经常会遇到一些这样那样的问题,然后要卡好半天,等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《基于Golang实现延迟队列(DelayQueue)》,聊聊延迟、队列,希望可以帮助到正在努力赚钱的你。
背景
延迟队列是一种特殊的队列,元素入队时需要指定到期时间(或延迟时间),从队头出队的元素必须是已经到期的,而且最先到期的元素最先出队,也就是队列里面的元素是按照到期时间排序的,添加元素和从队头出队的时间复杂度是O(log(n))。
由于以上性质,延迟队列一般可以用于以下场景(定时任务、延迟任务):
- 缓存:用户淘汰过期元素
- 通知:在指定时间通知用户,比如会议开始前30分钟
- 订单:30分钟未支付取消订单
- 超时:服务器自动断开太长时间没有心跳的连接
其实在Golang中是自带定时器的,也就是time.After()
、time.AfterFunc()
等函数,它们的性能也是非常好的,随着Golang版本升级还会优化。但是对于某些场景来说确实不够方便,比如缓存场景我们需要能够支持随机删除定时器,随机重置过期时间,更加灵活的删除一小批过期元素。而且像Kafka的时间轮算法(TimeWheel)里面也用到了延迟队列,因此还是有必要了解下如何实现延迟队列。
原理
堆
延迟队列每次出队的是最小到期时间的元素,而堆就是用来获取最值的数据结构。使用堆我们可以实现O(log(n))时间复杂度添加元素和移除最小到期时间元素。
随机删除
有时候延迟队列还需要具有随机删除元素的能力,可以通过以下方式实现:
- 元素添加删除标记字段:堆中每个元素都添加一个删除标记字段,并把这个元素的地址返回给用户,用户就可以标记元素的这个字段为true,这样元素到达堆顶时如果判断到这个字段为true就会被清除,而延迟队列里的元素逻辑上是一定会到达堆顶的(因为时间会流逝)。这是一种懒删除的方式。
- 元素添加堆中下标字段(或用map记录下标):堆中每个元素都添加一个堆中下标字段,并把这个元素的地址返回给用户,这样我们就可以通过这个元素里面记录的下标快速定位元素在堆中的位置,从而删除元素。详细可以看文章如何实现一个支持O(log(n))随机删除元素的堆。
重置元素到期时间
如果需要重置延迟队列里面元素的到期时间,则必须知道元素在堆中的下标,因为重置到期时间之后必须对堆进行调整,因此只能是元素添加堆中下标字段
。
Golang实现
这里我们实现一个最简单的延迟队列,也就是不支持随机删除元素和重置元素的到期时间,因为有些场景只需要添加元素和获取到期元素这两个功能,比如Kafka中的时间轮,而且这种简单实现性能会高一点。
数据结构
主要的结构可以看到就是一个heap,Entry是每个元素在堆中的表示,Value是具体的元素值,Expired是为了堆中元素根据到期时间排序。
mutex是一个互斥锁,主要是保证操作并发安全。
wakeup是一个缓冲区长度为1的通道,通过它实现添加元素的时候唤醒等待队列不为空或者有更小到期时间元素加入的协程。(重点)
type Entry[T any] struct { Value T Expired time.Time // 到期时间 } // 延迟队列 type DelayQueue[T any] struct { h *heap.Heap[*Entry[T]] mutex sync.Mutex // 保证并发安全 wakeup chan struct{} // 唤醒通道 } // 创建延迟队列 func New[T any]() *DelayQueue[T] { return &DelayQueue[T]{ h: heap.New(nil, func(e1, e2 *Entry[T]) bool { return e1.Expired.Before(e2.Expired) }), wakeup: make(chan struct{}, 1), } }
实现原理
阻塞获取元素的时候如果队列已经没有元素,或者没有元素到期,那么协程就需要挂起等待。而被唤醒的条件是元素到期、队列不为空或者有更小到期时间元素加入。
其中元素到期协程在阻塞获取元素时发现堆顶元素还没到期,因此这个条件可以自己构造并等待。但是条件队列不为空和有更小到期时间元素加入则需要另外一个协程在添加元素时才能满足,因此必须通过一个中间结构来进行协程间通信,一般Golang里面会使用Channel来实现。
添加元素
一开始加了一个互斥锁,避免并发冲突,然后把元素加到堆里。
因为我们Take()操作,既阻塞获取元素操作,在不满足条件时会去等待wakeup通道,但是等待通道前必须释放锁,否则Push()无法写入新元素去满足条件队列不为空和有更小到期时间元素加入。而从释放锁后到开始读取wakeup通道这段时间是没有锁保护的,如果Push()在这期间插入新元素,为了保证通道不阻塞同时又能通知到Take()协程,我们的通道的长度需要是1,同时使用select+default保证在通道里面已经有元素的时候不阻塞Push()协程。
// 添加延迟元素到队列 func (q *DelayQueue[T]) Push(value T, delay time.Duration) { q.mutex.Lock() defer q.mutex.Unlock() entry := &Entry[T]{ Value: value, Expired: time.Now().Add(delay), } q.h.Push(entry) // 唤醒等待的协程 // 这里表示新添加的元素到期时间是最早的,或者原来队列为空 // 因此必须唤醒等待的协程,因为可以拿到更早到期的元素 if q.h.Peek() == entry { select { case q.wakeup <h3>阻塞获取元素</h3> <p>这里先判断堆是否有元素,如果有获取堆顶元素,然后判断是否已经到期,如果到期则直接出堆并返回。否则等待直到超时或者元素到期或者有新的元素到达。</p> <p>这里在解锁之前会清空wakeup通道,这样可以保证下面读取的wakeup通道里的元素肯定是新加入的。</p> <pre class="brush:go;">// 等待直到有元素到期 // 或者ctx被关闭 func (q *DelayQueue[T]) Take(ctx context.Context) (T, bool) { for { var expired *time.Timer q.mutex.Lock() // 有元素 if !q.h.Empty() { // 获取元素 entry := q.h.Peek() if time.Now().After(entry.Expired) { q.h.Pop() q.mutex.Unlock() return entry.Value, true } // 到期时间,使用time.NewTimer()才能够调用Stop(),从而释放定时器 expired = time.NewTimer(time.Until(entry.Expired)) } // 避免被之前的元素假唤醒 select { case <h3>Channel方式阻塞读取</h3> <p>Golang里面可以使用Channel进行流式消费,因此简单包装一个Channel形式的阻塞读取接口,给通道一点缓冲区大小可以带来更好的性能。</p> <pre class="brush:go;">// 返回一个通道,输出到期元素 // size是通道缓存大小 func (q *DelayQueue[T]) Channel(ctx context.Context, size int) <p>使用方式</p> <pre class="brush:go;">for entry := range q.Channel(context.Background(), 10) { // do something }
性能测试
这里进行一个简单的性能测试,也就是先添加元素,然后等待到期后全部拿出来。
func BenchmarkPushAndTake(b *testing.B) { q := New[int]() b.ResetTimer() // 添加元素 for i := 0; i <p>测试结果:</p> <blockquote><p>Benchmark-8 2331534 476.8 ns/op 76 B/op 1 allocs/op</p></blockquote> <h2>总结</h2> <p>堆实现的延迟队列是一种实现起来比较简单的定时器(当然阻塞读取Take()是比较复杂的),由于时间复杂度是O(log(n)),因此可以满足定时任务数量不是特别多的场景。堆实现的延迟队列也是可以随机删除元素的,可以根据具体任务选择是否实现。如果对定时器性能要求比较敏感的话可以选择使用时间轮实现定时器,它可以在O(1)的时间复杂度添加和删除一个定时器,不过实现起来比较复杂(挖个坑,下篇文章实现)。</p> <p>终于介绍完啦!小伙伴们,这篇关于《基于Golang实现延迟队列(DelayQueue)》的介绍应该让你收获多多了吧!欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识,快来关注吧!</p>

- 上一篇
- GO将mysql 中 decimal 数据类型映射到 protobuf的操作方法

- 下一篇
- go pprof 的使用操作代码
-
- 靓丽的小蘑菇
- 真优秀,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,帮助很大,总算是懂了,感谢up主分享博文!
- 2023-03-10 20:25:45
-
- 虚心的手套
- 这篇文章内容真是及时雨啊,太详细了,真优秀,码住,关注up主了!希望up主能多写Golang相关的文章。
- 2023-03-04 07:11:54
-
- 粗暴的小懒猪
- 这篇博文真是及时雨啊,太细致了,太给力了,已加入收藏夹了,关注up主了!希望up主能多写Golang相关的文章。
- 2023-03-03 04:44:29
-
- Golang · Go教程 | 24分钟前 |
- Go语言os.File同步与持久化详解
- 247浏览 收藏
-
- Golang · Go教程 | 30分钟前 |
- Golang实现轻量级Service Mesh,Linkerd数据平面开发详解
- 412浏览 收藏
-
- Golang · Go教程 | 38分钟前 |
- Golang深拷贝实现与指针值类型对比
- 417浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- Golang时间处理性能优化技巧分享
- 392浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- 用Golang集成TerraformSDK管理基础设施
- 494浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- GolangWebAPI异常处理与优化技巧
- 426浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- Golang命令行工具依赖管理:cobra与urfave集成解析
- 127浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- Go调用WindowsDLL未定义错误解决办法
- 230浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- Golang容器化环境搭建教程
- 464浏览 收藏
-
- Golang · Go教程 | 1小时前 | Goroutine Goroutine泄露 pprof delve 堆栈分析
- Golang协程调试与堆栈分析技巧
- 446浏览 收藏
-
- Golang · Go教程 | 1小时前 |
- Golang异步IO优化技巧分享
- 236浏览 收藏
-
- Golang · Go教程 | 2小时前 |
- Golang缓存与内存管理技巧解析
- 198浏览 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 543次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 514次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 499次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 484次学习
-
- AI Mermaid流程图
- SEO AI Mermaid 流程图工具:基于 Mermaid 语法,AI 辅助,自然语言生成流程图,提升可视化创作效率,适用于开发者、产品经理、教育工作者。
- 539次使用
-
- 搜获客【笔记生成器】
- 搜获客笔记生成器,国内首个聚焦小红书医美垂类的AI文案工具。1500万爆款文案库,行业专属算法,助您高效创作合规、引流的医美笔记,提升运营效率,引爆小红书流量!
- 537次使用
-
- iTerms
- iTerms是一款专业的一站式法律AI工作台,提供AI合同审查、AI合同起草及AI法律问答服务。通过智能问答、深度思考与联网检索,助您高效检索法律法规与司法判例,告别传统模板,实现合同一键起草与在线编辑,大幅提升法律事务处理效率。
- 560次使用
-
- TokenPony
- TokenPony是讯盟科技旗下的AI大模型聚合API平台。通过统一接口接入DeepSeek、Kimi、Qwen等主流模型,支持1024K超长上下文,实现零配置、免部署、极速响应与高性价比的AI应用开发,助力专业用户轻松构建智能服务。
- 620次使用
-
- 迅捷AIPPT
- 迅捷AIPPT是一款高效AI智能PPT生成软件,一键智能生成精美演示文稿。内置海量专业模板、多样风格,支持自定义大纲,助您轻松制作高质量PPT,大幅节省时间。
- 526次使用
-
- Go+Redis实现延迟队列实操
- 2023-02-23 426浏览
-
- Go 实战单队列到优先级队列实现图文示例
- 2022-12-31 468浏览
-
- Go语言函数的延迟调用(DeferredCode)详解
- 2023-01-07 326浏览
-
- goFrame的队列gqueue对比channel使用详解
- 2022-12-26 311浏览
-
- 使用golang编写一个并发工作队列
- 2023-01-07 497浏览