`

令牌桶算法(token bucket algorithm) 限流

 
阅读更多

http://blog.csdn.net/sunnyyoona/article/details/51228456

 今天观看QCon大会讲述了阿里线上管控体系,其中主要使用了令牌桶算法来实现限流的目的。表示非常好奇,故此学习一下什么是令牌桶算法。

1. 简介

令牌桶算法最初来源于计算机网络。在网络传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。

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

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

传送到令牌桶的数据包需要消耗令牌。不同大小的数据包,消耗的令牌数量不一样。

令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌,则允许发送流量;而如果令牌桶中不存在令牌,则不允许发送流量。因此,如果突发门限被合理地配置并且令牌桶中有足够的令牌,那么流量就可以以峰值速率发送。

2.算法过程

算法描述:

  • 假如用户配置的平均发送速率为r,则每隔1/r秒一个令牌被加入到桶中(每秒会有r个令牌放入桶中);

  • 假设桶中最多可以存放b个令牌。如果令牌到达时令牌桶已经满了,那么这个令牌会被丢弃;

  • 当一个n个字节的数据包到达时,就从令牌桶中删除n个令牌(不同大小的数据包,消耗的令牌数量不一样),并且数据包被发送到网络;

  • 如果令牌桶中少于n个令牌,那么不会删除令牌,并且认为这个数据包在流量限制之外(n个字节,需要n个令牌。该数据包将被缓存或丢弃);

  • 算法允许最长b个字节的突发,但从长期运行结果看,数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理:(1)它们可以被丢弃;(2)它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输;(3)它们可以继续发送,但需要做特殊标记,网络过载的时候将这些特殊标记的包丢弃。

注意:

令牌桶算法不能与另外一种常见算法漏桶算法相混淆。这两种算法的主要区别在于漏桶算法能够强行限制数据的传输速率,而令牌桶算法在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在令牌桶算法中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。

3.Java实现

我们可以使用Guava 的 RateLimiter 来实现基于令牌桶的流控,RateLimiter 令牌桶算法是单桶实现。RateLimiter 对简单的令牌桶算法做了一些工程上的优化,具体的实现是 SmoothBursty。需要注意的是,RateLimiter 的另一个实现SmoothWarmingUp,就不是令牌桶了,而是漏桶算法。也许是出于简单起见,RateLimiter 中的时间窗口能且仅能为 1s。

SmoothBursty 有一个可以放 N 个时间窗口产生的令牌的桶,系统空闲的时候令牌就一直攒着,最好情况下可以扛 N 倍于限流值的高峰而不影响后续请求。RateLimite允许某次请求拿走超出剩余令牌数的令牌,但是下一次请求将为此付出代价,一直等到令牌亏空补上,并且桶中有足够本次请求使用的令牌为止。当某次请求不能得到所需要的令牌时,这时涉及到一个权衡,是让前一次请求干等到令牌够用才走掉呢,还是让它先走掉后面的请求等一等呢?Guava 的设计者选择的是后者,先把眼前的活干了,后面的事后面再说。

 

分享到:
评论

相关推荐

    令牌桶算法(token bucket algorithm)

    **令牌桶算法**(Token Bucket Algorithm)是一种流量控制算法,在网络通信领域被广泛应用于实现服务质量(QoS)策略中的流量监管和整形功能。其核心思想是通过一个虚拟的“令牌桶”来监控和管理数据包的发送速度,以...

    令牌桶算法c实现

    This project involved emulation of the Token Bucket algorithm using POSIX threads in C. The aim was to simulate a traffic shaper that receives and transmits packets to a server, while being controlled...

    bucket4j-基于令牌桶算法的Java速率限制库

    Bucket4j是一个强大的Java速率限制库,它基于令牌桶算法(Token Bucket Algorithm)来实现流量控制和资源调度。令牌桶算法是一种在网络流量管理和流量整形中广泛使用的策略,它允许系统在限定的速率内发送数据,并能...

    基于令牌桶算法在抵御Flood攻击系统中的实现

    在抵御网络洪水攻击(Flood Attack)的研究中,令牌桶算法(Token Bucket Algorithm)是一种用于控制网络流量,防止恶意流量泛滥的重要技术。令牌桶算法是一种网络流量整形和速率限制机制,它的基本原理是通过一种...

    sch_tbf.rar_token bucket_token bucket filter

    1. **令牌桶算法(Token Bucket Algorithm)**: 令牌桶算法是一种流量整形和流量控制算法,主要用于网络通信中对数据传输速率的控制。它允许突发数据在一段时间内高速发送,但整体上不超过预设的平均速率。桶内有...

    Algorithm-TokenBucket.zip

    - `TokenBucket.h`: 定义了令牌桶类的接口,包括构造函数、添加令牌、消费令牌等方法。 - `TokenBucket.cpp`: 实现了令牌桶类的接口,包括无锁版本的令牌管理逻辑。 - `main.cpp`: 示例程序,展示了如何使用无锁令牌...

    SnowJena:Distributed lock-free current limiting framework based on token bucket algorithm.基于令牌桶算法实现的分布式无锁限流框架

    基于令牌桶算法实现的分布式无锁限流框架,支持动态配置规则,支持可视化监控,开箱即用。 Document 使用文档:| 功能概要 限流 降级 授权 注解 监控 黑名单 白名单 控制台 分布式 高可用 设计模式 单例模式 观察者...

    计算机网络网络学院要点PPT课件.pptx

    9. 令牌桶算法(Token Bucket Algorithm):令牌桶算法是一种流量整形算法,用于限制网络中的流量。令牌桶算法的基本思想是将用户发出的不平滑的数据包流转变成网络中平滑的数据包流,并且加入令牌机制来控制流量。 ...

    CCIE4.0之QoS详解教程文档分享

    令牌桶算法(token bucket algorithm) 单速双色 单速三色 双速三色 分类和标记(Classification and Marking) 流(Flow) 管制和整形(Policing and Shaping) 配置管制 配置整形 接口直接开启整形 ...

    研究论文-基于智能网业务控制点过载算法研究

    在过载控制算法的研究中,令牌桶算法(Token Bucket Algorithm)是研究的一个重点。该算法是一种针对流量控制的速率限制算法,与漏桶算法相似,但它允许在桶内积累一定数量的令牌,这使得它可以应对突发的流量请求,...

    Go如何实现HTTP请求限流示例

    Go语言实现限流的原理主要依赖于令牌桶算法(Token bucket algorithm)。令牌桶是一种流量整形(in traffic shaping)工具,用来控制网络流量或者数据传输速率,限制数据的发送速度,并允许在短时间内有突发流量的产生。...

    VPP研究及使用 --- Qos策略

    VPP的QoS功能利用了令牌桶算法(Token Bucket Algorithm),这是一种有效的流量平滑和速率限制算法。在令牌桶算法中,系统以固定速率向桶中投放令牌,数据包只有在获得令牌后才能被发送。令牌桶算法的参数包括桶容量...

    nginx 如何实现读写限流的方法

    `limit_req` 模块基于令牌桶算法(Token Bucket Algorithm)来限制请求速率。它会在特定速率内允许请求通过,超过设定速率的请求则会被延迟或拒绝。`burst` 参数允许在短时间内突发一定数量的请求,超出这个值后,新...

    Android代码-bucket4j

    Bucket4j - is Java rate-limiting library based on token-bucket algorithm. Advantages of Bucket4j Implemented on top of ideas of well known algorithm, which are by de-facto standard for rate ...

    对QOS的介绍

    2. **令牌桶算法(Token Bucket Algorithm)**:这是一种流量控制机制,用于限制发送速率,防止拥塞。它包含两个桶,一个存储令牌,另一个处理数据包。只有当令牌桶中有足够的令牌时,才能发送数据包。 3. **单速...

    Python库 | quart_rate_limiter-0.6.0-py3-none-any.whl

    该库的核心功能是通过令牌桶算法(Token Bucket Algorithm)来实现速率限制。这个算法是一种流量整形和拥塞控制算法,它会以恒定的速度添加令牌到桶中,而请求则会消耗这些令牌。当桶中的令牌不足以满足请求时,请求...

    在网络中实施Quality of Service,即QOS技术

    **令牌桶算法(Token Bucket Algorithm)** 令牌桶算法是QoS中用于流量整形的一种方法。它使用一个装满令牌的桶,只有当令牌存在时才能发送数据包。桶的容量限制了突发流量的大小,令牌的生成速率决定了平均发送...

    cisco qos配置

    - **令牌桶算法(Token Bucket Algorithm)**:一种流量控制算法,通过分配令牌来控制数据流的速度和突发性。 - **单速双色**:使用单一速度阈值进行流量监控,超过阈值的数据包会被标记为红色,表示超出了允许的...

    C++标准库(第二版)英文版.pdf

    The C++ Standard Library A Tutorial and Reference (2nd Edition)+cppstdlib-code.zip C++标准库(第二版)英文版.pdf 非扫描版+源代码 Prefaceto the SecondEdition xxiii Acknowledgments for the Second...

Global site tag (gtag.js) - Google Analytics