分类
用最赚钱的方式去赚钱

漏桶算法和令牌桶算法的区别

漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率

对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务

并不能说明令牌桶一定比漏洞好,她们使用场景不一样。令牌桶可以用来保护自己,主要用来对调用者频率进行限流,为的是让自己不被打垮。所以如果自己本身有处理能力的时候,如果流量突发(实际消费能力强于配置的流量限制),那么实际处理速率可以超过配置的限制。而漏桶算法,这是用来保护他人,也就是保护他所调用的系统。主要场景是,当调用的第三方系统本身没有保护机制,或者有流量限制的时候,我们的调用速度不能超过他的限制,由于我们不能更改第三方系统,所以只有在主调方控制。这个时候,即使流量突发,也必须舍弃。因为消费能力是第三方决定的。

令牌桶算法(Token Bucket)

在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。
令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。
大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗,或者被消耗的速度小于产生的速度,令牌就会不断地增多,直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。
传送到令牌桶的数据包需要消耗令牌。不同大小的数据包,消耗的令牌数量不一样。
令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌,则允许发送流量;而如果令牌桶中不存在令牌,则不允许发送流量。因此,如果突发门限被合理地配置并且令牌桶中有足够的令牌,那么流量就可以以峰值速率发送。
令牌桶算法的基本过程如下:
假如用户配置的平均发送速率为r,则每隔1/r秒一个令牌被加入到桶中;
假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了,那么这个令牌会被丢弃;
当一个n个字节的数据包到达时,就从令牌桶中删除n个令牌,并且数据包被发送到网络;
如果令牌桶中少于n个令牌,那么不会删除令牌,并且认为这个数据包在流量限制之外;
算法允许最长b个字节的突发,但从长期运行结果看,数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理:
它们可以被丢弃;
它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输;
它们可以继续发送,但需要做特殊标记,网络过载的时候将这些特殊标记的包丢弃。
注意:令牌桶算法不能与另外一种常见算法“漏桶算法(Leaky Bucket)”相混淆。这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。

一种解法是,开启一个定时任务,由定时任务持续生成令牌。这样的问题在于会极大的消耗系统资源,如,某接口需要分别对每个用户做访问频率限制,假设系统中存在6W用户,则至多需要开启6W个定时任务来维持每个桶中的令牌数,这样的开销是巨大的。
另一种解法则是延迟计算,如上resync函数。该函数会在每次获取令牌之前调用,其实现思路为,若当前时间晚于nextFreeTicketMicros,则计算该段时间内可以生成多少令牌,将生成的令牌加入令牌桶中并更新数据。这样一来,只需要在获取令牌时计算一次即可

漏桶算法(Leaky Bucket)

接下来,详细分解一下漏桶算法在数据包传送过程中的实现原理。
1、队列接收到准备转发的数据包。
2、队列被调度,得到转发机会。由于队列配置了流量整形,队列中的数据包首先进入漏桶中。
3、根据数据包到达漏桶的速率与漏桶的输出速率关系,确定数据包是否被转发。
如果到达速率≤输出速率,则漏桶不起作用。
如果到达速率>输出速率,则需考虑漏桶是否能承担这个瞬间的流量。
1) 漏桶算法和令牌桶算法的区别 若数据包到达的速率-漏桶流出的速率≤配置的漏桶突发速率,则数据包可被不延时的送出。
2) 若数据包到达的速率-漏桶流出的速率>配置的漏桶突发速率,则多余的数据包被存储到漏桶中。暂存在漏桶中的数据包在不超过漏桶容量的情况下延时发出。
3) 若数据包到达的速率-漏桶流出的速率>配置的漏桶突发速率,且数据包的数量已经超过漏桶的容量,则这些数据包将被丢弃。

版权声明: 本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

Louis军

漏桶算法与令牌桶算法在表面看起来类似,很容易将两者混淆。但事实上,这两者具有截然不同的特性,且为不同的目的而使用。漏桶算法与令牌桶算法的区别在于:漏桶算法能够强行限制数据的传输速率。令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。需要说明的是:在某些情况下,漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的,所以即使网络中没有发生拥塞,漏桶算法也不能使某一个单独的数据流达到端口速率。因此,漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常,漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制

1 | 0 漏桶限流算法的原理

2 | 0 令牌桶算法(Token)

1 .传统的方式整合RateLimiter 有很大的缺点:代码重复量特别大,而且本身不支持注解方式。 2 .如果限流代码可以放在网关中,相当于针对所有的服务接口都实现限流(可以使用排除法进行排除不进行限流的方法),维护性不是很强。 3 .正常的互联网公司项目,不是所有的服务接口都需要实现限流方法的,一般只真针对于大流量接口。比如:秒杀抢购、12306抢票等。 4 .可以手动封装一个RateLimiter类 注解来解决这个方法


以规定的速率往令牌桶中放入 token,用户请求必须获取到令牌桶中的 token才可以访问我们的业务逻辑方法,如果没有从令牌桶中获取到 token ,拒绝访问。
在高并发情况下,如果我们的请求过多 超出了令牌桶生成令牌的速度,这时候请求就会被驳回,提示请稍后重试!
优势:能够控制请求的速率。

3| 0 使用RateLimiter实现令牌桶限流

4| 0 总结

漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率

对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务

并不能说明令牌桶一定比漏洞好,她们使用场景不一样。令牌桶可以用来保护自己,主要用来对调用者频率进行限流,为的是让自己不被打垮。所以如果自己本身有处理能力的时候,如果流量突发(实际消费能力强于配置的流量限制),那么实际处理速率可以超过配置的限制。而漏桶算法,这是用来保护他人,也就是保护他所调用的系统。主要场景是,当调用的第三方系统本身没有保护机制,或者有流量限制的时候,我们的调用速度不能超过他的限制,由于我们不能更改第三方系统,所以只有在主调方控制。这个时候,即使流量突发,也必须舍弃。因为消费能力是第三方决定的。

漏桶算法和令牌桶算法的区别

暮色里de白雪檐 于 2020-07-15 14:44:00 发布 370 收藏 1

漏桶算法与令牌桶算法在表面看起来类似,很容易将两者混淆。但事实上,这两者具有截然不同的特性,且为不同的目的而使用。漏桶算法与令牌桶算法的区别在于:漏桶算法能够强行限制数据的传输速率。令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。需要说明的是:在某些情况下,漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的,所以即使网络中没有发生拥塞,漏桶算法也不能使某一个单独的数据流达到端口速率。因此,漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常,漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制

漏桶限流算法的原理

令牌桶算法(Token)


以规定的速率往令牌桶中放入 token,用户请求必须获取到令牌桶中的 token才可以访问我们的业务逻辑方法,如果没有从令牌桶中获取到 token ,拒绝访问。
在高并发情况下,如果我们的请求过多 超出了令牌桶生成令牌的速度,这时候请求就会被驳回,提示请稍后重试!
优势:能够控制请求的速率。

漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率

对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务

并不能说明令牌桶一定比漏洞好,她们使用场景不一样。令牌桶可以用来保护自己,主要用来对调用者频率进行限流,为的是让自己不被打垮。所以如果自己本身有处理能力的时候,如果流量突发(实际消费能力强于配置的流量限制),那么实际处理速率可以超过配置的限制。而漏桶算法,这是用来保护他人,也就是保护他所调用的系统。主要场景是,当调用的第三方系统本身没有保护机制,或者有流量限制的时候,我们的调用速度不能超过他的限制,由于我们不能更改第三方系统,所以只有在主调方控制。这个时候,即使流量突发,也必须舍弃。因为消费能力是第三方决定的。

漏桶算法和令牌桶算法,区别到底在哪里?

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

首先,漏桶和令牌桶的区别是保护自己还是保护别人吗?

其实就是我在课件上写的:漏桶的本质是总量控制,令牌桶的本质是速率控制。至于这个控制,你可以用来保护自己,也可以用来保护别人。

有的技术人员对于“保护别人”可能不太理解,这个主要应用于访问第三方,最典型的例子就是双十一的支付宝,支付的时候要访问银行的接口,银行的接口实际上处理高并发的能力并不强(例如澳门某银行对外提供的移动支付接口,峰值 TPS 是 30 次/s),这个时候支付宝自己处理性能再高都没用,而且越高越容易把下游的银行给压垮,所以支付宝不得不针对下游接口请求做限流。

网上的文章都说令牌桶更适合“突发流量”,为何你这里说漏桶更适合“瞬时(业务)高并发”?

其实,令牌桶的“突发流量”跟我们通常理解的“业务高并发”并不一样。令牌桶的算法原本是用于网络设备控制传输速度的,而且它控制的目的是保证一段时间内的平均速率控制,之所以说令牌桶适合突发流量,是指在网络传输的时候,可以允许某段时间内(一般就几秒)超过平均传输速率,这在网络环境下常见的情况就是“网络抖动”,但这个短时间的突发流量是不会导致雪崩效应,网络设备也能够处理得过来。对应到令牌桶应用到业务处理的场景,就要求即使有突发流量来了,系统自己或者下游系统要真的能够处理的过来,否则令牌桶允许突发流量进来,结果系统或者下游处理不了,那还是会被压垮。

The leaky bucket as a queue is therefore applicable only to traffic shaping, and does not, in general, allow the output packet stream to be bursty, i.e. it is jitter free. It is therefore significantly different from the token bucket algorithm.

排队方案的架构示意图