限流算法

前言

限流顾名思义是限制流量,目的是为了保障服务稳定运行,避免服务被流量冲垮。

为什么要限流?因为再厉害的系统总有所能承载的能力上限,一旦流量突破这个上限,就会引起实例宕机,进而发生系统雪崩,带来灾难性后果。限流是系统自我保护的最直接手段,当流量超出服务处理能力时,部分请求将会被限流组件拦截,根据具体业务场景选择丢失。

限流算法

计数器

计算器算法的思想很简单,每当一个请求到来时,就将计数器加一,当计数器数值超过阈值后,就拒绝接收到的请求。在指定周期内,计数器会重置,开始新一轮的计数。计数器算法简单粗暴,易于实现。但是缺点也是很大的,容易造成前一个时间段非常忙碌,下一时间段又非常空闲。

漏通算法

漏桶算法由流量容器、流量入口和流量出口组成。流量入口一般就是业务请求,流量容器用于暂存一定大小的业务流量,流量出口则是我们设定的限速值,比如 1000 QPS。漏桶算法如下图:

如上图,流入漏桶流量的流速是不可控的,但流出流量的速度是恒定的,而漏桶的容量是有限的,这就会导致一旦流入流量超出漏桶容量,这部分流量只能被丢弃了。

漏桶算法可以通过暂存一定的流量达到流量整形的目的,但是漏桶不能处理突发流量。

令牌桶算法

令牌桶和漏桶算法既有相似之处,又有很大的不同,不同之处也是令牌桶算法能够支持突发流量的原因。

令牌桶算法需要一个令牌工厂以一定周期向令牌桶中放入令牌,当令牌桶满了之后,多出的令牌会被丢弃。每当一个请求到来时都会先从令牌桶中取令牌,由于令牌桶中可能存放了很多令牌,因此允许多个请求同时取令牌,如果令牌够多就可以在一定程度上支持突发流量。当令牌桶中没有令牌后,无法获取到令牌的请求可以丢弃,或者重试。令牌桶算法如下图:

小结

本篇文章简单介绍了常见的三种限流算法,它们被落地到不同的实现中,如 Dubbo 中的 TpsLimitFilter 使用的就是计算器限流算法,Google 提供的 RateLimiter 开源包使用的是基于令牌桶算法。

总体来说,限流既可以是在客户端限流,也可以是在服务端限流。此外,限流的实现方式既可支持 URL 以及方法级别的限流,也可支持基于 QPS 和线程的限流。