漏桶限流算法和令牌桶限流算法

2022-04-11
2622

令牌桶限流算法

漏桶限流算法

一、流量控制算法简介
流量控制在计算机领域称为过载保护。何为过载保护?所谓“过载”,即需求超过了负载能力;而“保护”则是指当“过载”发生了,采取必要的措施保护自己不受“伤害”。在计算机领域,尤其是分布式系统领域,“过载保护”是一个重要的概念。一个不具备“过载保护”功能的系统,是非常危险和脆弱的,很可能由于瞬间的压力激增,引起“雪崩效应”,导致系统的各个部分都同时崩溃,停止服务。这就好像在没有保险丝的保护下,电压突然变高,导致所有的电器都会被损坏一样,“过载保护”功能是系统的“保险丝”。

二、限流
限流是对某一时间窗口内的请求数进行限制,保持系统的可用性和稳定性,防止因流量暴增而导致的系统运行缓慢或宕机。常用的限流算法有令牌桶和和漏桶

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流
缓存:缓存的目的是提升系统访问速度和增大系统处理容量
降级:降级是当服务器压力剧增的情况下,根据当前业务情况及流量对一些服务和页面有策略的降级,以此释放服务器资源以保证核心任务的正常运行
限流:限流的目的是通过对并发访问/请求进行限速,或者对一个时间窗口内的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

三、漏桶算法
漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:




从上图可见,一个漏桶(Leaky Bucket)可以承受很多的水(请求),然后以一定的速度出水,进行路由下一级服务请求,但每个接口也有相应的速率,当水流过大,请求突然剧增,那么漏桶会在短时间内迅速装满,然后就会拒绝其他的请求,漏桶算法可以强行限制请求的访问以及数据的传输速率

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)

因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率。对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。

四、令牌通算法
令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务



令牌通算法以一定恒定的速度往桶里面放入令牌,就好比漏桶的水(请求),比如放入1000个令牌,每来一次请求,就从令牌通里面拿一个令牌,当令牌被拿完之后,其他服务就拒绝或者等待服务。

大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗,或者被消耗的速度小于产生的速度,令牌就会不断地增多,直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量。

相对比,漏桶算法强制限制一定的传输速率,而令牌通可以限制船速速率之外,还可以应对一些突发情况。