Last Updated on

前言

在如今的盛行的微服务架构中,处理高并发情况下,添加效率,保护系统的手段都是我们运维经常会接触,需要了解的东西,在高并发系统中,有很多手段来保护系统,如缓存、降级和限流等等。

今天我们就记录介绍一下高并发情况下,最常用的两种限流算法:漏桶算法和令牌桶算法的原理,方便更好的理解。比如nginx中的限制访问速率的算法就是漏桶算法。

正文

1. 漏桶算法(Leaky Bucket)

漏桶算法是网络世界中流量整形或速率限制时经常使用的一种算法,它的主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。漏桶算法提供了一种机制,通过它,突发流量可以被整形以便为网络提供一个稳定的流量。

漏桶可以看作是一个带有常量服务时间的单服务器队列,如果漏桶溢出,那么数据包会被丢弃。 在网络中,漏桶算法可以控制端口的流量速率,平滑网络上的突发流量,实现流量整形,从而为网络提供一个稳定的流量,以避免DDos等突发大量请求导致服务崩溃。

如上图所示:水龙头的水来源和速率不定,经过漏桶,以恒定的速率通过,超过漏桶容量的直接丢弃。此算法最大的特点为完全控制速率在恒定的范围内无法超出。

2.令牌桶(Token Bucket)

漏桶算法是网络世界中流量整形或速率限制时经常使用的另一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。从原理上看,令牌桶算法和漏桶算法是相反的,一个“进水”,一个是“漏水”。

如上图所示,令牌桶会按恒定速率生成令牌,请求消耗令牌,令牌不足则丢弃请求,此算法的特点是,在桶的容量范围内,允许突发情况。

3. 比较与选择

漏桶算法与令牌桶算法在表面看起来类似,很容易将两者混淆。但事实上,这两者具有截然不同的特性,且为不同的目的而使用。漏桶算法与令牌桶算法的区别在于,漏桶算法能够强行限制数据的传输速率,令牌桶算法能够在限制数据传输的平均速率的同时还允许一定程度的突发传输。

需要注意的是,因为漏桶算法不支持突发特性的流量,主要目的为平滑流入速率,而令牌痛可以支持一定的突发流量,其限制的实际上为平均速率。根据实际的流量特性,选择不同算法,通常,漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

结束

以上简单的记录结束了一下漏桶算法和令牌桶算法,方便我们在遇到相关的东西时更好的理解。

有任何问题,欢迎留言。