java令牌桶算法

❶ 令牌桶算法的分类

基于令牌桶的典型标记器有多种算法实现方案，基本算法主要有IN/OUT公平标记器（FM）和三色标记器（TCM），扩展的算法主要有单速率三色标记器（srTCM）和双速率三色标记器（trTCM）。其中单速率标记器和双速率标记器已分别称为IETF的标准建议。
IN/OUT 公平标记器（FM）
FM是一种双色单令牌桶标记器，它的Tspec是系统的分组平均速录为R，允许的突发度为B，工作原理就是当IP分组到达时若桶中有足够的令牌，则将符合Tspec的分组标记为IN；若此时没有足够的令牌，则认为该到达分组不符合Tpsec，不符合Tpsec的分组将被标记为OUT，网络将可能对这些被标记为不同属性的分组依据相应的策略进行不同的处理。
单速率三色标记器（srTCM）
srTCM是一种三色双令牌桶标记器，它的Tpsec有三个参数：承诺信息速率，承诺突发尺寸和超额突发尺寸。CIR的单位是bps，CBS及EBS的单位是Byte。
srTCM由两个令牌桶C和E组成，它们的CIR相同，容量则分别为CBS和EBS，C桶内存放黄色令牌，开始时令牌桶C与E都是满的。进入的分组没有超过CBS就标记为绿色；超过了CBS而没有超过EBS就标记为黄色；否则标记为红色。在DiffServ中，红、黄、绿可映射为不同的DSCP值。
双速率标记器（trTCM）
trTCM也是一种三色双令牌桶标记器，它的Tpsec有4个参数：峰值信息速率（PIR）、峰值突发尺寸（PBS）、承诺信息速率（CIR）和承诺突发尺寸（CBS）。PIR和CIR的单位是bps，PBS和CBS的单位是Byte。

❷ 令牌桶（Token Bucket）

想象有一个木桶，系统按照固定速率，例如10ms每次，往桶里加入Token，如果桶已经满了就不再添加。新请求来临时，会各自拿走一个Token，如果没有Token 就拒绝服务。这里如果一段时间没有请求时，桶内就会积累一些token，下次一旦有突发流量，只要token足够，也能一次处理。

总结下令牌桶算法的特点，令牌桶即可以控制进入系统的请求请求量，同时允许突发流量。

在秒杀活动中，用户的请求速率是不固定的，这里我们假定为10r/s，令牌按照5个每秒的速率放入令牌桶，桶中最多存放20个令牌，那系统就只会允许持续的每秒处理5 个请求，或者每隔4 秒，等桶中20 个令牌攒满后，一次处理20个请求的突发情况，保证系统稳定性。

go简易版实现

❸ java限流原理

Google的guava包中已有相关的限流解决方案(令牌桶算法)
基于redis的限流算法可以去参考redis-cell

❹ 令牌桶算法的令牌桶工作参数

工作过程包括3个阶段：产生令牌、消耗令牌和判断数据包是否通过。其中涉及到2个参数：令牌产生的速率CIR（Committed Information Rate）/EIR（Excess Information Rate）和令牌桶的大小CBS（Committed Burst Size）/EBS（Excess Burst Size）。下面用图形简要概括一下这3个阶段与2个参数的关系。
产生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已到达CBS/EBS，则丢弃多余令牌。 消耗令牌：输入数据包会消耗桶中的令牌。在网络传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多。 判断是否通过：输入数据包经过令牌桶后的结果包括输出的数据包和丢弃的数据包。当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出，否则将其丢弃。

❺ 云南java课程分享分布式限流的运行原理

分布式编程架构技术我们在前几期的文章中已经给大家简单分析过很多次了，今天我们就一起来了解一下API网关分布式限流的运行原理都有哪些。

API网关中针对一个API、API分组、接入应用APPID,IP等进行限流。这些限流条件都将会产生一个限流使用的key，在后续的限流中都是对这个key进行限流。

限流算法通常在API网关中可以采用令牌桶算法实现。

必须说明一点的是分布式限流由于有网络的开销，TPS的支持隔本地限流是有差距的，因此在对于TPS要求很高的场景，建议采用本地限流进行处理。

下面讨论我们应该采用redis的哪一种分布式锁的方案：

由于redis事务要得到锁的效果需要在高TPS时会产生大量的无效的访问请求，所以不建议在这种场景下使用。

SETNX/EX的锁方案会产生在过期时间的问题，同时也有异步复制master数据到slave的问题。相比lua方案会产生更多的不稳定性。

我建议采用lua的方案来实施分布式锁，因为都是单进程单线程的执行，因此在TPS上和二种方案没有大的区别，而且由于只是一个lua脚本在执行，甚至是可能纯lua执行可能会有更高的TPS。当然是lua脚本中可能还是会去设置过期时间，但是应用server宕机并不会影响到redis中的锁。当然master异步复制的问题还是有，但是并不会造成问题，因为数据只会有1个lua脚本执行问题，下一个执行就正常了。

在实现方案的时候使用了Jedis库，云南java课程http://www.kmbdqn.com/认为有一些问题在方案的实现层面我已经去做过验证了，可能也会是读者的疑问。

❻ 超出esb吞吐量,启用流量控制是什么意思

流量控制是总线系统非常核心的模块，它能有效控制在高并发交易场景的流量情况，达到在业务突发状况下的业务系统以及平台的稳定和可靠性。
典型的流量控制算法采用令牌桶的算法控制网络流量，网络令牌桶算法如下：
令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。
————————————————
版权声明：本文为CSDN博主“smartesb”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/smartesb/article/details/39478981

❼ 限流算法之漏桶、令牌桶的区别

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

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。 在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。

如图所示，把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

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

Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。

漏桶算法与令牌桶算法在表面看起来类似，很容易将两者混淆。但事实上，这两者具有截然不同的特性，且为不同的目的而使用。

漏桶算法与令牌桶算法的区别在于，漏桶算法能够强行限制数据的传输速率，令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

需要注意的是，在某些情况下，漏桶算法不能够有效地使用网络资源，因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

查看原文可以戳这里
限流技术早期被应用于控制网络接口收发通信数据的速率，在互联网领域，也借鉴了这个概念，用于为服务控制请求的速率。

这段话怎么理解呢，比如说存在两个系统A、B，公用一个网络，网络带宽为2M, A、B各分得1M，此时通过漏桶算法控制两个系统使用网络的速率，A、B系统使用网络的速率固定最大值为1M,无论A、B系统接受多少流量，但流出的速率都限制在最大1M,当网络中没有发生拥塞，也就是可能出现B系统可能空闲没有使用网络，对应分给B系统的1M带宽是空闲的，而A系统这一时刻接收了5M的流量，由于漏桶限流的存在，A只能使用1M带宽，我们的带宽有2M,此刻我们只能使用1M,也就是达不到带宽的最大速率，另外1M带宽是浪费的，因此不能充分利用，缺乏效率；当然从另一方面来讲也带来了好处，就是隔离性，A系统无论收到多大的流量冲击，对于B系统的无感的，不会因为流量冲击A,而B受到影响.

这段又该怎么理解呢，比如我们的目标现在是每秒钟处理10个请求，使用漏桶法，我们设置桶的大小为10，流出的速率为0.1s流出一个请求，我们可以达成我们的目标；而使用令牌桶的话，我们会设置每1s向桶中放入10个令牌，请求如果是平稳的，每0.1s过来一个请求，来十个，同样能达到我们的目标，这里所说的某种程度的突发传输是指，比如在一秒内前0.5请求是平稳的，每0.1s来一个，但在0.6s的时候突发请求同时来个5个请求，此时令牌算法是可以承受这个突发流量的，并且让5个请求成功立刻同时通过，完成了所谓的某种程度的突发传输，而漏桶算法，也可以应对这种突发流量，但不同的是没有让5个请求同时立刻通过，而是缓冲在桶中，然后仍然以固定速率每0.1s通过一个。

这两种算法，都可以实现流速的控制，1s处理10个请求，多于10个的请求都会被拒绝，但由于漏桶算法流出速率是一定的，所以请求可能会被缓冲在桶中，不能马上得到处理，从而徒增了等待时间，而对于令牌桶算法，没有这种等待时间，有令牌则通过，无令牌则抛弃。

❽ RateLimiter令牌桶算法浅析

网络中的定义：
令牌桶算法是网络流量（Traffic Shaping）整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

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

传送到令牌桶的数据包需要消耗令牌。不同大小的数据包，消耗的令牌数量不一样。令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。

令牌桶算法的基本过程：
假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中；桶最多可以存发b个令牌。如果令牌到达时令牌桶已满，则这个令牌会被丢弃；
当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络；
如果令牌桶中少于n个令牌，则不会删除令牌，并且认为这个数据包在流量限制之外；
算法允许最长b个字节的突发，数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理：
1）被丢弃；
2）放在队列中当令牌桶中累积了足够多的令牌时再传输；
3）继续发送，但需要做特殊标记，网络过载时将这些特殊标记的包丢弃。

令牌桶算法与漏桶算法（Leaky Bucket）的主要区别：
1）漏桶算法能够强行限制数据的传输速率，而令牌桶算法在能够限制数据的平均传输速率外，还允许某种程度的突发传输。
2）令牌桶算法中，只要令牌桶中存在令牌，就允许突发地传输数据直到达到用户配置的上限，它适合于具有突发特性的流量。

RateLimiter是Guava中开源的一个令牌桶算法工具类，可以轻松实现限流工作。
RateLimiter有两个实现类：SmoothBursty和SmoothWarmingUp;
两者区别：
1）都是令牌桶算法的变种实现
2）SmoothBursty加令牌的速度是恒定的，SmoothWarmingUp会有个预热期，在预热期内加令牌的速度是慢慢增加的，直到达到固定速度为止。其适用场景是，对于有的系统而言刚启动时能承受的QPS较小，需要预热一段时间后才能达到最佳状态。

测试示例：

示例1：创建一个令牌桶，每秒生成一个令牌，申请失败立即返回。使用CountdownLatch计数器模拟多线程并发，调用await()方法阻塞当前线程，当计数完成后，唤醒所有线程并发执行。

示例2：创建一个令牌桶，每秒生成0.1个令牌，即每10s才会有一个令牌，超时时间设置成20s，20s内获取不到令牌返回失败，20s内可以生成2个令牌，加上创建时桶里会有一个令牌，超时前最终会有3条线程拿到令牌，并且每个令牌获取时间相隔10s。使用CountdownLatch计数器模拟多线程并发：调用await()方法阻塞当前线程，当计数完成后，唤醒所有线程并发执行。

参考文档：
https://ke..com/item/%E4%BB%A4%E7%89%8C%E6%A1%B6%E7%AE%97%E6%B3%95/6597000?fr=aladdin
https://blog.csdn.net/unclecoco/article/details/99583154

❾ 什么是漏桶算法和令牌桶算法

什么是令牌桶
在我们讨论突发数据量之前，我们首先要理解令牌桶的概念。令牌桶本身没有丢弃
和优先级策略，
令牌桶是这样工作的：
1． 令牌以一定的速率放入桶中。
2． 每个令牌允许源发送一定数量的比特。
3． 发送一个包，流量调节器就要从桶中删除与包大小相等的令牌数。
4． 如果没有足够的令牌发送包，这个包就会等待直到有足够的令牌（在整形
器的情况下）或者包被丢弃，也有可能被标记更低的DSCP（在策略者的情况下）。
5． 桶有特定的容量，如果桶已经满了，新加入的令牌就会被丢弃。因此，在
任何时候，源发送到网络上的最大突发数据量与桶的大小成比例。令牌桶允许突发，
但是不能超过限制。
Cisco IOS 流量策略（Traffic Policers）
IOS支持两种流量策略：
1． 传统的Cisco流量策略：CAR承诺接入速率，使用命令
Router(config-if)#rate-limit {input | output} CIR (bps)
Bc（burst-normal） Be(burst-max) conform-action action exceed-action action
2． 新型的Cisco流量策略：基于类的策略（Class-based policer），使用模
块化Qos CLI（MQC）语法。可以使用MQC命令建立流量策略并把策略应用到接口。
一个流量策略包括一个流量类（traffic class）和一个或多个Qos特性。Policy
命令用来执行流量策略特性，它指定了一个流量类所需要的最大速率，超过这个速
率Qos系统会立刻执行一个操作，标准的操作是丢弃或重置包头的DSCP字段。Policy
命令的语法是：
police cir<bps> Bc<bc> Be<be> conform<conform-action> exceed
<exceed-action> violate<violate-action>
理解Bc和Be
对于超额的数据包，流量策略并不会把它们缓存稍候转发，只有整形器（shaper）
会这样做。流量策略只执行一个发送或不发送的策略。因为不能缓存数据包，所以
在发生拥塞时，所能做的最好的方法就是通过配置适当的超额突发数据量Be来不那
么过分的丢弃数据包。这一点对理解流量策略使用Bc和Be来保证达到CIR是非常
重要的。
超额参数模仿路由器的通用缓存规则。The rule recommends configuring buffering
equal to the round-trip time bitrate to accommodate the outstanding TCP
windows of all connections in times of congestion.
突发参数 目的 推荐公式
普通突发 · 执行标准的令牌桶 · 设置最大数量的令牌(尽管如
果Be>Bc的话可以借到令牌). · 决定令牌桶有多大，因为如果桶已经满了那么令
牌将被丢弃而不会再加入到桶中。 CIR [bps] * (1 byte)/(8 bits) * 1.5
seconds Note: 1.5 seconds is the typical round trip time.
超额突发 · 为令牌桶提供超额突发能力 · 如果Bc = Be那么不
支持超额突发 · 当Bc = Be，流量调节器就不能借令牌，当令牌不够时只能丢弃数
据包 两倍的Bc
对TCP流量的测试表明，Bc 和Be的数值应该近似等于配置的平均速率在两秒钟内
的流量。如果你想限制流量在1Mb，应该把Bc 设置在1-2Mb，Be在2-4Mb。
举个例子，如果我们想把输出速率限制在1.5Mbps，我们可以做一下步骤：
1． 把承诺速率从比特转换成字节，因为突发数据量的单位为字节。
1500000 bits / 8 bits = 187500 bytes
2． 使用标准的1.5秒往返时间（round-trip time）计算Bc
187500 bytes * 1.5秒 = 281250 bytes
3． 两倍的Bc为Be
281250 bytes * 2 = 562500 bytes
使用命令
rate-limit input 1500000 281250 562500 conform-action {action}
exceed-action {action}
超额突发数据量
当数据包到达时可用的令牌数目小于包的大小，就可以使用超额突发数据量。包会
请求借用令牌。可以通过配置大于Bc的Be的数值来为令牌桶提供超额突发能力。
可以通过下面两个例子来理解Be。
第一个例子说明怎样配置CAR策略来允许所有的IP流量。管理员在T3线路上提供
了便宜的20Mbps的子速率服务。用户只花费子速率带宽的金额，也可以按需要增加
带宽。CAR限制了用户可用的流量速率，用户只能使用规定的速率加上承诺的突发
数据量。可以适当的设置Be=32000。
interface hssi 0/0/0
rate-limit output 20000000 24000 32000 conform-action transmit
exceed-action drop
下一个例子，用户只能发送24000字节的突发数据量，所有超过限制的数据包都要
被丢弃，因为设置Bc=Be，数据包流不能通过超额突发能力来借用令牌。
interface Hssi0/0/0
rate-limit output 20000000 24000 24000 conform-action transmit
exceed-action drop
正确设置突发数据量的重要性
策略以字节为单位指定了突发数据量，基于类的策略（class-based policer）支持
最小的突发数据量为1000字节，包括第二层包头。
突发数据量的目的是逐渐的丢弃数据包，就像RED那样，并且避免尾丢弃。设置足
够高的突发数据量对保证良好的吞吐量是非常重要的。
设置突发数据量时，考虑一下内容：
1． 如果突发数据量设置的过低，数据到达的速率将远远低于配置的速率。
2． 惩罚暂时突发对TCP流的吞吐量来说是相当不利的，具体情况请察看RFC
2001 and Random Early Detection (RED) gateways for Congestion Avoidance。
设置突发数据量来允许路由器容纳暂时突发。
3． 对离开接口的数据包的处理基于包的大小和桶中剩余的令牌数。
4． 在基于类的策略中，流量测量器不论接口是否拥塞都是激活的。每个包都
会经过令牌桶测量系统来决定是否符合配置的参数。
5． 如果数据突发量非常大而且非常突然，那么配置较高的超额突发数据量可
以保证超额令牌桶中存放较多的令牌。而且可以调整接口的MTU等于或大于突发数
据量大小。
允许的突发数据量数值
最初，包括IOS12.0，rate-limit命令支持承诺和超额的突发数据量的范围是：
Router1(config-if)#rate-limit input 18000000 ?
<8000-2000000> Normal burst bytes
Router1(config-if)#rate-limit input 18000000 2000000 ?
<8000-8000000> Maximum burst bytes
Router1(config-if)#rate-limit input 18000000 2000000
IOS12.1增加了突发数据量的最大值：
7500-107(config)#interface atm 1/0/0
7500-107(config-if)#rate-limit output ?
<8000-2000000000> Bits per second
access-group Match access list
qos-group Match qos-group ID<b

❿ 令牌桶算法的简介

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