【高并发】不得不说的几种限流算法

2022-06-15 16:54:36 浏览数 (1)

持之以恒,贵在坚持,每天进步一点点!

作者个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,具有精准的定时任务和延迟队列处理功能。自开源半年多以来,已成功为十几家中小型企业提供了精准定时调度方案,经受住了生产环境的考验。为使更多童鞋受益,现给出开源框架地址:

https://github.com/sunshinelyz/mykit-delay

PS: 欢迎各位Star源码,也可以pr你牛逼哄哄的代码。

常见的限流算法有:令牌桶、漏桶,计数器也可以用来进行粗暴限流实现。

一、令牌桶算法

令牌桶算法,是一个存放固定容量令牌的桶,按照固定速率网桶里添加令牌。令牌桶算法描述如下:

  • 假设限制2r/s,则按照500毫秒的固定速率往桶中添加令牌。
  • 桶中最多存放b个令牌,当桶满时,新添加的令牌被丢弃或拒绝。
  • 当一个n个字节大小的数据包到达,将从桶中删除n个令牌,接着数据包被发送到网络上。
  • 如果桶中的令牌不足n个,则不会删除令牌,且该数据包将被限流(要么丢弃,要么在缓冲区等待)。

二、漏桶算法

漏桶作为计量工具时,可以用于流量整形和流量控制,漏桶算法的描述如下。

  • 一个固定容量的漏桶,按照常量固定速率流出水滴。
  • 如果桶是空的,则不需要流出水滴。
  • 可以以任意速率流入水滴到漏桶。
  • 如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。

三、令牌桶和漏桶算法对比

  • 令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减为零时,则拒绝新的请求。 漏桶则是按照常量固定速率流出请求,流入请求速率任意,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝。
  • 令牌桶限制的是平均流入速率(允许突发请求,只要有令牌就可以处理,支持一次拿3个令牌,或4个令牌),并允许一定程度的突发流量。
  • 漏桶限制的是常量流出速率(即流出速率是一个固定常量值,比如都是1的速率流出,而不能一次是1,下次又是2),从而平滑突发流入速率。
  • 令牌桶允许一定程度的突发,而漏桶主要目的是平滑流入速率。
  • 两个算法实现可以一样,但是方向是相反的,对于相同的参数得到的限流效果是一样。

四、计数器

使用计数器进行限流,主要限制总并发数,比如数据库连接池大小、线程池大小、秒杀并发数都是计数器的用法。只要全局总请求数或者一定时间段的总请求数达到设定的阈值,则进行限流。这种方式是简单粗暴的总数量限流,而不是平均速率限流。

——参考涛哥的《亿级流量网站架构核心技术》

冰河从一名普通程序员,短短几年时间,一路进阶成长为大厂高级技术专家,一直致力于分布式系统架构、微服务、分布式数据库、分布式事务与大数据技术的研究。在高并发、高可用、高可扩展性、高可维护性和大数据等领域拥有丰富的架构经验。对Hadoop,Storm,Spark,Flink等大数据框架源码进行过深度分析,并具有丰富的实战经验。

出版过两本畅销书《海量数据处理与大数据技术实战》、《MySQL技术大全:开发、优化与运维实战》。写了一本《深入理解高并发编程》电子书全网累计下载45W ,发布了一本全网首个开源的以实战案例为背景的《冰河的渗透实战笔记》电子书,全网五星好评。写的文章多次被微信公众号官方推荐。

0 人点赞