欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 四种经典限流算法,确保不溢出!

程序员文章站 2022-03-23 19:04:07
**本文原创首发于我的公众号【程序员大帝】,希望大家可以关注我,一起码动人生,成为Coding King!!!**前言文字开篇先放一段经典对白尔康:紫薇,我想就这样拥着你一直追到天边去。紫薇:我现在觉得又刺激又害怕又兴奋又快乐又幸福,只是担心……尔康:你不要担心,我们还是好好享受这一刻,这可是千金难买的好机会啊。紫薇:只是,上次这样被你拥着,已经好久好久。尔康:喜欢你,太多太多。紫薇:我也是。尔康:你说什么,我没听清楚!紫薇:我也是、我也是、我也是。你有多少,我就有多少!不、不,我...

**

本文原创首发于我的公众号【程序员大帝】,希望大家可以关注我,一起码动人生,成为Coding King!!!

**

荐
                                                        四种经典限流算法,确保不溢出!

前言

文字开篇先放一段经典对白

尔康:紫薇,我想就这样拥着你一直追到天边去。

紫薇:我现在觉得又刺激又害怕又兴奋又快乐又幸福,只是担心……

尔康:你不要担心,我们还是好好享受这一刻,这可是千金难买的好机会啊。

紫薇:只是,上次这样被你拥着,已经好久好久。

尔康:喜欢你,太多太多。

紫薇:我也是。

尔康:你说什么,我没听清楚!

紫薇:我也是、我也是、我也是。你有多少,我就有多少!不、不,我比你还要多。

尔康:你不可能比我还多,因为我已经满了!

紫薇:你满了,那我就漫出来了!

荐
                                                        四种经典限流算法,确保不溢出!

在没有速率限制的情况下,如果每个用户都可以随心所欲地发送请求,这可能会导致“峰值”的到来,那对我们的系统来说,真的是「又刺激,又害怕」

限流(Rate Limiting,即速率限制)是指通过一些列算法,限制每个用户调用 API 的频率,防止 API 被过度使用。本文将介绍几种经典的限流算法,相信大家耐心看了之后肯定有收获,码字不易,别忘了「在看」,「转发」哦。

  • 计数器算法

  • 滑动时间窗口算法

  • 漏桶算法

  • 令牌桶算法

正文

01 计数器算法

计数器算法的实现,比较简单粗暴。

我们可以直接通过一个计数器,限制每一秒钟能够接收的请求数。比如说 qps定为 1000,那么实现思路就是从第一个请求进来开始计时,在接下去的 1s 内,每来一个请求,就把计数加 1,如果累加的数字达到了 1000,那么后续的请求就会被全部拒绝。等到 1s 结束后,把计数恢复成 0 ,重新开始计数。

Java 语言中实现计数器非常简单,由于并发请求的原因,所以要考虑线程安全。所以可以采用 AtomicLong 这样的原子类,它自身的 incrementAndGet 方法通过 CAS ( Compare And Swap )保证了线程安全。每次有请求过来,就把计数器加 1 ,然后和阈值进行比较。

计数器的实现方式为什么说简单粗暴?

如果1s 内的前半秒,已经通过了 1000 个请求,那后面的半秒,只能眼巴巴的把请求拒绝,我们把这种现象称为“突刺现象”。

02 滑动时间窗口算法

针对上面出现的这种,由于瞬间达到的大流量导致的突刺现象,滑动时间窗口算法应运而生。

这个算法会把时间划分为一个个小的时间片段,有点类似于 CPU 的时间分片设计。每过一个时间片段,我们的时间窗口就会往右滑动一格,每个时间片段都有独立的计数器。

我们在计算整个时间窗口内的请求总数时会累加所有的时间片段内的计数器。时间窗口划分的越细,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。

滑动时间窗口算法在 TCP 协议中也被经常使用,相关内容在介绍网络的部分时候再给大家讲讲。

03 漏桶算法

漏桶算法顾名思义,我们想象有一个漏桶,也可以是漏斗。

当请求进来时,相当于有水倒入漏斗,上面开头大,但是小面开头小。水流到了会在漏斗里先堆积,然后从下面的小口慢慢地流出。不管上面流量多大,下面流出的速度始终保持不变。

漏桶算法使得服务器可以完全不考虑调用方的情况,反正接收的速度都是恒定的,比如每 10 毫秒处理一次请求。

但漏桶算法也有一定的缺陷,因为一个漏桶的容量总归是有限的。如果请求太多,那就真的又呼应文章前的那段话「我要漫出来了」!。如果桶满,新进来的请求就只能丢弃了。

算法的具体实现方式有很多种,比如 Java 中可以使用队列这样的数据结构来作为漏桶,请求到达就放入队列中。然后再通过一个线程池定期从队列中获取请求并执行,当然也可以一次性获取多个任务并发执行。

04 令牌桶算法

令牌桶算法可以说是对漏桶算法的一种升级,漏桶算法通过出口的大小控制了接收请求的速率。令牌桶算法在此基础之上,还进一步提升了对突发流量的处理。

令牌桶算法中也有一个桶,用来存放一定数量的令牌,然后按照设定好的速率生成令牌并放到桶中。

每次请求到达时,它需要先获取令牌。拿到令牌后才能够对服务器进行调用,如果没拿到要么等待,要么被拒绝。

荐
                                                        四种经典限流算法,确保不溢出!

生成令牌并放在桶中的是持续不断的,如果请求比较少,令牌消耗的速度比生成的速度慢,那么桶中的令牌会越来越多。如果桶中一直有大量的可用令牌,这时进来的请求就可以直接拿到令牌执行。

令牌桶算法的实现思路:可以使用一个队列用来保存令牌,通过一个线程池定期生成令牌放到队列中,每来一个请求,就从队列中获取一个令牌,并继续执行。

05 总结

通过这篇文章,为大家介绍几种经典的限流算法。但是本文的讨论范围只局限于单机的范畴。如果是在集群分布式的环境下,算法的实现思想和设计模式都会有些变化,以后有机会再给大家介绍。

不过我的观念是,这几种算法并没有优劣之分,找到适合自己场景的最重要。
**

最后希望大家关注公众号「程序员大帝」,我们下次见

**

公众号后台回复“加群”可以加技术交流群,里面各个都是人才,说话又好听

荐
                                                        四种经典限流算法,确保不溢出!
公众号内还整理 《Java核心知识点整理.pdf》面试突击全都靠它了,好东西还是要分享出来给大家一起学习呀~

内容覆盖很广:Java 核心基础、Java 多线程、高并发、Spring、微服务、Netty 与 RPC、Zookeeper、Kafka、RabbitMQ、HBase、设计模式、负载均衡、分布式缓存、Hadoop、Spark、Storm、云计算等。
荐
                                                        四种经典限流算法,确保不溢出!
荐
                                                        四种经典限流算法,确保不溢出!
荐
                                                        四种经典限流算法,确保不溢出!

本文地址:https://blog.csdn.net/kingcoding/article/details/107306138