go语言循环队列的实现

Python015

go语言循环队列的实现,第1张

队列的概念在 顺序队列 中,而使用循环队列的目的主要是规避假溢出造成的空间浪费,在使用循环队列处理假溢出时,主要有三种解决方案

本文提供后两种解决方案。

顺序队和循环队列是一种特殊的线性表,与顺序栈类似,都是使用一组地址连续的存储单元依次存放自队头到队尾的数据元素,同时附设队头(front)和队尾(rear)两个指针,但我们要明白一点,这个指针并不是指针变量,而是用来表示数组当中元素下标的位置。

本文使用切片来完成的循环队列,由于一开始使用三个参数的make关键字创建切片,在输出的结果中不包含nil值(看起来很舒服),而且在验证的过程中发现使用append()函数时切片内置的cap会发生变化,在消除了种种障碍后得到了一个四不像的循环队列,即设置的指针是顺序队列的指针,但实际上进行的操作是顺序队列的操作。最后是对make()函数和append()函数的一些使用体验和小结,队列的应用放在链队好了。

官方描述(片段)

即切片是一个抽象层,底层是对数组的引用。

当我们使用

构建出来的切片的每个位置的值都被赋为interface类型的初始值nil,但是nil值也是有大小的。

而使用

来进行初始化时,虽然生成的切片中不包含nil值,但是无法通过设置的指针变量来完成入队和出队的操作,只能使用append()函数来进行操作

在go语言中,切片是一片连续的内存空间加上长度与容量的标识,比数组更为常用。使用 append 关键字向切片中追加元素也是常见的切片操作

正是基于此,在使用go语言完成循环队列时,首先想到的就是使用make(type, len, cap)关键字方式完成切片初始化,然后使用append()函数来操作该切片,但这一方式出现了很多问题。在使用append()函数时,切片的cap可能会发生变化,用不好就会发生扩容或收缩。最终造成的结果是一个四不像的结果,入队和出队操作变得与指针变量无关,失去了作为循环队列的意义,用在顺序队列还算合适。

参考博客:

Go语言中的Nil

Golang之nil

Go 语言设计与实现

有个服务会大量使用延迟消息,进行事件处理。随着业务量不断上涨。在晚间、节假日等流量高峰期消息延迟消息队列限流会导致事件丢失,影响业务。与下游沟通后给上调到了最大限流值,问题依然存在,于是决定自己搞一套降级方案。

下游服务触发限流时,能降级部分流量到本地延迟队列,把业务损失降到最低。

本地延迟队列承接部分mq流量

流程如下:

1. 使用zset 存储延迟消息,其中:score为执行时间,value为消息体

2. 启动协程轮询zset,获取score最小的10条数据,协程执行间隔时间xs

        如果最小分值小于等于当前时间戳,则发送消息

        若最小分值大于当前时间戳,sleep等待执行

需要对key进行hash,打散到多个分片中,避免大key和热key问题,官方大key定义

因此,需保证每个key中value数量n<5000,单个value大小不超过 10240/n kb

假设承接10w qps,如何处理?

10w qps延迟120s时,最开始消息队列会积累100000*120=12000000条消息

假如每条消息大小500b,需占用存储6000000kb = 6000Mb = 6GB

为避免大key问题,每个zset存放4000个元素,需要哈希到3000(3000是key的数量,可配置)个zset中。

整个集群假设500台实例,每个处理qps平均在200左右。

单实例消费能力计算:

遍历每个zset,针对每个zset起goroutine处理,此示例中需要 起3000个

但是每秒能处理成功的只有200个,其他都在空跑

综上:

将redis key分片数n和每次处理的消息数m进行动态配置,便于调整

当流量上涨时,调大分片数n和单实例单分片并发数m即可,假如消费间隔200ms,集群处理能力为n*m*5 qps

n = (qps * 120) / 4000

若qps=q,则计算公式如下

zadd = q

zRange = 500 * 5 * n / 500

zRemove = q

setNx = 500 * 5 * n

若10w qps,则

读qps = 15000 + 500*3000*5 =7515000,写 20w

pros

redis 读写性能好,可支持较大并发量,zrange可直接取出到达执行时间的消息

cons

redis 大key问题导致对数据量有一定的限制

分片数量扩缩容会漏消费,会导致事件丢失,业务有损

key分片数量过多时,redis读写压力较大

机器资源浪费,3000个协程,单实例同一秒只有200个针对处理,其他都在空跑

流程如下:

使用带缓冲的channel来实现延迟队列,channel中存放的数据为消息体(包括执行时间),channel能保证先进先出

从channel中取出数据后,判断是否到达执行时间

到达,同步发送mq

未到达,sleep 剩余执行时间,然后再次执行

从channel读出的数据如果未到达执行时间,无法再次放入channel中,需要协程sleep(执行时间-当前时间)

10w qps延迟120s时,最开始消息队列会积累100000*120=12000000条消息,假设每条消息大小500b,需要6G存储空间

channel 大小 = (qps*120)/ c , c=集群实例数,c=500 =>channel大小为24000,占用12M内存

要处理10w qps,分摊到每个机器的处理速度为 100000/500 = 200,假设单协程处理10qps,开20个即可。

pros:

本地存储,相比redis,读写速度更快;协程数量少,开销低;资源利用率较方案一高

cons:

稳定性不如redis,实例故障可能导致数据丢失;worker池和channel扩缩容依赖服务重启,成本高速度慢

综上,我们以10w qps为例,对比两种方案在以下指标差异,选择方案二。

附上demo