java令牌桶算法（java令牌机制）

本篇文章给大家谈谈java令牌桶算法，以及java令牌机制对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

微信号：cloud7591
如需了解更多，欢迎添加客服微信咨询。
复制微信号

本文目录一览：

• 1、令牌桶（Token Bucket）
• 2、令牌桶算法的分类
• 3、限流和常见的三种算法
• 4、什么是漏桶算法和令牌桶算法
• 5、令牌桶算法的令牌桶工作参数

令牌桶（Token Bucket）

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

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

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

go简易版实现

令牌桶算法的分类

基于令牌桶的典型标记器有多种算法实现方案，基本算法主要有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。

限流和常见的三种算法

限流的三种算法

限流要解决的问题

典型限流的应用场景：

如何限流？

一般网关都有这种功能。 gateway、nginx、zuul等

限流：一定时间内，只允许N次请求。

从计算机友好的角度出发，是希望能在单位时间内均摊掉请求，使用漏斗算法可以达到这种效果。

但是漏斗算法有个弊端，就是先快后慢的这种请求，那么峰值的请求也只能排队等待被消费。实际上计算机是具备一定的高并发处理能力的，只要不是一直处于高并发下即可。所以 计数器限流和 漏洞限流折中的算法，令牌限流成为现在最主流的算法。

（Redis 结合expire方案可以实现)

第一次请求开始计时，例如1s以内，达到100次请求就拒绝访问了，直到1s过后，重新开始计数。

优点：

缺点：短暂的峰值过高对服务器不友好。服务器希望能把请求尽量的均摊开来，这样可以充分利用计算机资源。

消费的速度是恒定的，对于服务器而言是最友好的。

在算法实现方面，可以准备一个队列，用来保存请求，另外通过一个线程池（ScheduledExecutorService）来定期从队列中获取请求并执行，可以一次性获取多个并发执行。

参数：消费速度、桶容量（超过就抛弃，可以避免内存过大，有过多的等待的任务)

优点：

缺点：

令牌桶算法是比较常见的限流算法之一，大概描述如下：

1）所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；

2）根据限流大小，设置按照一定的速率往桶里添加令牌；

3）桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃活着拒绝；

4）请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除；

5）令牌桶有最低限额，当桶中的令牌达到最低限额的时候，请求处理完之后将不会删除令牌，以此保证足够的限流；

这种算法，既可以保证系统由一定的高并发能力，比如当前令牌桶容量是100，一开始直接消费掉100个请求。有保证服务器不会因为短暂的爆发，而导致server端空闲，因为令牌桶还会持续的生产令牌。

既有一定的并发能力，又不至于完全失去控制，可控的兼具并发力和流量控制的限流算法.是计数器算法（一定的并发处理能力）和漏洞限流（高峰过后仍然会持续的产生令牌）的折中算法。

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

什么是令牌桶

在我们讨论突发数据量之前，我们首先要理解令牌桶的概念。令牌桶本身没有丢弃

和优先级策略，

令牌桶是这样工作的：

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 cirbps Bcbc Bebe conformconform-action exceed

exceed-action violateviolate-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.

突发参数 目的 推荐公式

普通突发 · 执行标准的令牌桶 · 设置最大数量的令牌(尽管如

果BeBc的话可以借到令牌). · 决定令牌桶有多大，因为如果桶已经满了那么令

牌将被丢弃而不会再加入到桶中。 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 IDb

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

工作过程包括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令牌桶算法和java令牌机制的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。