简约而不简单：WorkQueue的轻量级高效之道 点击关注公众号，”技术干货”及时达！我是 LEE，老李，一个在 IT 行业摸爬滚打 17 年的技术老兵。 事件背景独立 WorkQueue 这个事情我犹豫了很久，一直没有真正的行动起来，直到有一天公司整个开发环境升级了，client-go 版本到了 1.28，而之前的我一直使用的 client-go 1.26，WorkQueue 包被迫升级了。你说这有什么关系呢？其实这个关系很大，因为 1.26 包含的的 WorkQueue 包基本停止更新快 1 年了，新版的 WorkQueue 多少有一些使用上的变化，而且我这边更多逻辑都是基于之前 WorkQueue 的版本来实现的，所以升级之后，我发现之前的项目基本都需要重弄一次。 之前一直希望有一个像 kubernetes 社区中 WorkQueue 项目出现，不要依赖其他第三方库。但是一直没有找到，所以我就想自己写一个。但是这次升级 client-go 版本之后，我发现我必须要做这个事情了，因为我不想重复的去修改之前的代码，而且我也想做一个开源项目，所以就有了这个项目。 接下来我会花一些时间向大家介绍一下这个项目设计思路。主要会从分几期文章来介绍： 聚焦项目的整体设计思路、目标和架构设计。针对 Queue 和 Simple Queue 模块的实现、使用示例和代码分析。介绍 Delaying Queue 和 Priority Queue 模块，包括使用实例和代码讲解。深入 RateLimiting Queue 模块的实现、使用案例和代码解析。项目简介WorkQueue https://github.com/shengyanli1982/workqueue workqueueWorkQueue 实际是一个 kubernetes 社区中 client-go 项目中 workqueue 包的复刻品，但是我并没有直接将 client-go 中的代码拿过来，而是重新实现了一遍。主要是因为 client-go 中的代码实现比较复杂，而且依赖了自身的第三方库，分离度不高。我希望能够做一个更加轻量级和干净的项目，有类似 client-go 项目中 workqueue 包的功能，但是不依赖其他第三方库，而且代码实现上也要更加简单易懂。 架构设计整体代码结构上也仿造了 kubernetes 社区中 client-go 项目中 workqueue 包的设计结构，采用分层设计。 基础 Queue 作为最底层的数据队列，提供了基本的队列操作，包括 Add, Get, Len, Stop 等接口。Delaying Queue 和 Priority Queue 从 Queue 派生，分别实现了延迟队列和优先级队列的功能。 RateLimiting Queue 从 Delaying Queue 派生，实现了一个速率限制队列，主要是为了控制队列的速率。 Simple Queue 功能类似 Queue，也可以作为最底层的数据队列，Simple Queue 与 Queue 的区别在于 Simple Queue 不会对存储在队列中的数据进行去重，而 Queue 会对存储在队列中的数据进行去重。所以 Simple Queue 的性能会比 Queue 要高一些。 「结构图如下：」 workqueue-1.png接口设计参考了 kubernetes 社区中 client-go 项目中 workqueue 包中接口设计，结合我日常工作中使用习惯，同时考虑到未来的通用性，少许做了一些修改。 「方法接口」 用于操作队列内的元素，所有的队列都需要实现这些方法接口。特殊的队列，比如 Delaying Queue 和 Priority Queue，除了需要实现这些方法接口之外，还需要实现其他接口，后续文章将跟大家分享。 //队列方法接口 //Queueinterface typeInterfaceinterface{ Add(elementany)error//添加元素到队列 Len()int//队列长度 Get()(elementany,errerror)//获取队列元素 GetWithBlock()(elementany,errerror)//阻塞获取队列元素 Done(elementany)//标记完成队列元素 Stop()//停止队列 IsClosed()bool//队列是否关闭 } 「回调接口」 用于队列中元素在不同操作阶段，需要额外触发的回调函数。比如元素添加到队列中时候，需要触发添加回调函数；元素从队列中获取出来时候，需要触发取回回调函数；元素从队列中标记完成时候，需要触发完成回调函数。 //队列的回调接口 //Callbackinterface typeCallbackinterface{ OnAdd(any)//添加元素到队列时候的回调函数 OnGet(any)//获取元素时候的回调函数 OnDone(any)//标记完成元素时候的回调函数 } 性能比对既然要做 kubernetes 社区中 client-go 项目中 workqueue 包的平替，那么当然就要看在实际情况下的性能表现了。所以我写了一个简单的 demo 程序，来对 client-go 和 WorkQueue 的差别。 「这次参赛选手如下：」 「client-go」: v1.26.12「WorkQueue」: v0.1.3「Go 版本」：go1.20.11 darwin/amd64 $gotest-benchmem-run=^$-bench^Benchmark*github.com/shengyanli1982/workqueue/bennchmark goos:darwin goarch:amd64 pkg:github.com/shengyanli1982/workqueue/bennchmark cpu:Intel(R)Xeon(R)CPUE5-4627v2@3.30GHz BenchmarkClientgoAdd-82363436466.3ns/op171B/op1allocs/op BenchmarkClientgoGet-84062987332.9ns/op7B/op0allocs/op BenchmarkClientgoAddAndGet-82547846468.0ns/op53B/op1allocs/op BenchmarkWorkqueueAdd-81600765670.0ns/op95B/op2allocs/op BenchmarkWorkqueueGet-83805994334.0ns/op25B/op0allocs/op BenchmarkWorkqueueAddAndGet-81633266793.1ns/op83B/op1allocs/op PASS okgithub.com/shengyanli1982/workqueue/bennchmark17.377s 眼光犀利的你一定发现了，WorkQueue 的性能比 client-go 的性能要差一些，这是为什么呢？主要是因为 WorkQueue 底层数据存储使用 DoubleLinkedList 实现，而 client-go 使用的是 slice 实现，所以 WorkQueue 的性能会比 client-go 的性能要差一些，实际已经通过优化将差距缩小到了几乎差不多，可以做到跟 client-go 一样的性能。 当然在代码开发之初也使用过 channel 和 slice，最后通过大量的复杂场景测试，发现 DoubleLinkedList 的综合能力要比 channel 和 slice 要好一些，所以最终选择了 DoubleLinkedList 作为底层数据存储。下面的章节就会对这部分的内容做一个详细的解析。 STL 解析如果写过 c++ 的小伙伴一定不陌生，STL 是 Standard Template Library 的缩写，中文名叫做标准模板库，是 c++ 标准模板库的一部分，是 c++ 标准模板库的核心，包括容器、算法和迭代器。STL 的设计思想是将数据结构和算法分离，使得算法独立于具体的数据结构，从而能够实现算法的复用。 当然 Go 语言中也有 STL，只不过 Go 语言中的 STL 只包含了部分的数据结构和算法，比如 container/list、container/heap、container/ring、container/stack、container/vector 等。Go 语言中的 STL 也是将数据结构和算法分离，使得算法独立于具体的数据结构，从而能够实现算法的复用。 类型对比由于 WorkQueue 底层数据存储需要使用 STL 中的部分算法，为了将性能最大化，不得不手动实现了 STL 中 DoubleLinkedList 和 QuadrupleHeap。 这里主要讲解下当初选用 DoubleLinkedList 作为底层数据存储的原因。 DoubleLinkedList (双向链表)「基于双向链表的队列复杂度」 动作平均复杂度最坏复杂度PushO(1)O(1)PopO(1)O(1)「优点」基于双向链表的队列 Push/Pop 操作为恒定时间，即复杂度为 「O(1)」。这是因为双向链表的 Push/Pop 操作只需要修改链最外部元素的指针，不需要移动任何元素。 「缺点」每个元素都需要开辟额外空间存储指向上一个、下一个结点的指针，且每次创建元素时，都需要分配内存，这会导致内存碎片化。 「注意因素」适用于长时间运行的程序，比如服务端程序，因为长时间运行的程序，内存的利用率比较重要，所以需要考虑内存的利用率。同时长时间运行的程序，内存碎片化的问题也比较严重，所以需要考虑内存碎片化的问题。 Slice (数组切片)「基于数组的队列复杂度」 动作平均复杂度最坏复杂度PushO(1)O(n)PopO(1)O(n)「优点」基于数组的队列 Pop 操作为恒定时间，即复杂度为 「O(1)」。这是因为数组的 Pop 操作只需要返回第一个元素，不需要移动任何元素。但是 Push 操作的复杂度也是 「O(1)」，因为每次 Push 操作都需要在 slice 的末尾添加元素，不需要移动任何元素。但是如果在第一个元素前插入元素，就需要移动所有元素，复杂度为 「O(n)」。 「缺点」数组填满时需扩容，扩容后占用很多空闲空间。扩容时需要重新分配内存，将数组原来元素复制过来，每次扩容时容量都会翻倍。即便扩容发生的频率并不高，但是随着时间推移，它占用空间可能越来越大。 「注意因素」需要考虑内存在长期使用下，扩容导致内存的浪费，以及大量对象需要复制和迁移导致的性能问题。 workqueue-6.png对比总结Slice 和 DoubleLinkedList 在做 FIFO 的 Queue 的时候，Push/Pop 的复杂度都是 「O(1)」，但是 Slice 在 数组填满时需扩容，扩容后占用很多空闲空间。扩容时需要重新分配内存，将数组原来元素复制过来，每次扩容时容量都会翻倍。而 DoubleLinkedList 且每次创建元素时，都需要分配内存，这会导致内存碎片化。 如何优化最终 WorkQueue 项目采用了 DoubleLinkedList 作为底层数据存储，主要是考虑到长时间运行的程序，内存的利用率比较重要，所以需要考虑内存的利用率。同时长时间运行的程序，内存碎片化的问题也比较严重，所以需要考虑内存碎片化的问题。 那么如何解决 DoubleLinkedList 的内存碎片化问题呢？主要是通过 sync.Pool 来解决的，sync.Pool 是 Go 语言提供的一个对象池，可以用来存储临时对象，以减少内存分配，降低 GC 压力。sync.Pool 会对对象的生命周期进行管理，不再使用的对象会被自动移除，而不会造成内存泄漏。 所以在 DoubleLinkedList 代码实现时候，我将 DoubleLinkedList 的元素对象放入到 sync.Pool 中，这样就可以解决 DoubleLinkedList 的内存碎片化问题。 「结构图如下：」 workqueue-7.png「参考代码：」 「https://github.com/shengyanli1982/workqueue/blob/main/internal/stl/deque/pool.go」 typeListNodePoolstruct{ bpsync.Pool//同步池(syncpool) } funcNewListNodePool()*ListNodePool{ return&ListNodePool{ bp:sync.Pool{ New:func()any{ returnNewNode(nil) }, }, } } func(p*ListNodePool)Get()*Node{ returnp.bp.Get().(*Node)//从池中获取ListNode对象(getListNodeobjectfromthepool) } func(p*ListNodePool)Put(b*Node){ ifb!=nil{ b.Reset() p.bp.Put(b)//将ListNode对象放回池中(putListNodeobjectbackintothepool) } } 「https://github.com/shengyanli1982/workqueue/blob/main/queue.go」 //添加元素到队列 //Addelementtoqueue func(q*Q)Add(elementany)error{ ... n:=q.nodepool.Get() n.SetData(element) ... } //从队列中获取一个元素,如果队列为空，不阻塞等待 //Getanelementfromthequeue. func(q*Q)Get()(elementany,errerror){ ... q.nodepool.Put(n) ... } 使用 Add 添加元素到队列时候，会从 sync.Pool 中获取 ListNode 对象，当使用 Get 获取元素时候，会将 ListNode 对象放回到 sync.Pool 中，当 Add 和 Get 速度达到平衡的时候，sync.Pool 中的 ListNode 对象数量会保持在一个比较稳定的状态，不会出现内存碎片化的问题。 最后感谢你能看到这里，本文章是 WorkQueue 项目的第一篇文章，主要是对项目的整体设计思路、目标和架构设计做了一个简单的介绍。 对于 WorkQueue 项目中的 STL 模块选择和对比做了一个详细的介绍，主要是为了让大家了解为什么会选择 DoubleLinkedList 作为底层数据存储，而不是 Slice。同时也介绍了如何通过 sync.Pool 来解决 DoubleLinkedList 的内存碎片化问题。 后续文章将会对项目中的 Queue 和 Simple Queue 模块的实现、使用示例和代码分析做一个详细的介绍。 点击关注公众号，”技术干货”及时达！ 阅读原文