文档章节

学习一下令牌桶算法

明瞐
 明瞐
发布于 2016/12/07 11:20
字数 1290
阅读 92
收藏 2

今天观看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 的设计者选择的是后者,先把眼前的活干了,后面的事后面再说。

本文转载自:http://blog.csdn.net/sunnyyoona/article/details/51228456

共有 人打赏支持
明瞐
粉丝 7
博文 99
码字总数 35381
作品 0
海淀
程序员
私信 提问
老板让你抗住千万级流量,如何做架构设计?

随着互联网的发展,各项软件的客户量日益增多,当客户量达到一定峰值时,当数以万计的流量来临时,程序的顺利运行以及即时响应则显得尤为重要,就像双11那天的淘宝一样。那么,如何设计架构才...

技术小能手
2018/11/23
0
0
过载保护算法浅析

过载保护算法浅析 ShareCore2014-06-21538 阅读 算法 何为过载保护?所谓“过载”,即需求超过了负载能力;而“保护”则是指当“过载”发生了,采取必要的措施保护自己不受“伤害”。在计算机...

ShareCore
2014/06/21
0
0
SpringCloud 微服务 (十四) 服务网关 Zuul 过滤器(Pre&Post)

壹 上篇学习了zuul路由,这边继续学习,粗糙的记录zuul过滤器的用法 贰 现在对请求url做个约定,在请求url上没有带参数key=123的url全部过滤掉 ①localhost:7000/product/list?key=1234 ---不过...

___大侠
2018/07/10
0
0
【Guava】使用Guava的RateLimiter做限流

一、常见的限流算法 目前常用的限流算法有两个:漏桶算法和令牌桶算法。 1.漏桶算法 漏桶算法的原理比较简单,请求进入到漏桶中,漏桶以一定的速率漏水。当请求过多时,水直接溢出。可以看出...

大海201506
2018/09/19
0
0
面试宝典系列-缓存、降级(熔断)和限流

高并发系统三大利器:缓存、降级(熔断)和限流。 缓存: 很好理解,在高并发系统中,没有缓存,数据库分分钟就被玩跪了。使用缓存不单单能够提升系统访问速度、提高并发访问量,也是保护数据...

suyain
2018/08/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

大数据教程(11.9)hive操作基础知识

上一篇博客分享了hive的简介和初体验,本节博主将继续分享一些hive的操作的基础知识。 DDL操作 (1)创建表 #建表语法CREATE [EXTERNAL] TABLE [IF NOT EXISTS] table_name [(col_name ...

em_aaron
今天
2
0
OSChina 周四乱弹 —— 我家猫真会后空翻

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @我没有抓狂 :#今天听这个# 我艇牛逼,百听不厌,太好听辣 分享 Led Zeppelin 的歌曲《Stairway To Heaven》 《Stairway To Heaven》- Led Z...

小小编辑
今天
2
0
node调用dll

先安装python2.7 安装node-gyp cnpm install node-gyp -g 新建一个Electron-vue项目(案例用Electron-vue) vue init simulatedgreg/electron-vue my-project 安装electron-rebuild cnpm ins......

Chason-洪
今天
3
0
scala学习(一)

学习Spark之前需要学习Scala。 参考学习的书籍:快学Scala

柠檬果过
今天
3
0
通俗易懂解释网络工程中的技术,如STP,HSRP等

导读 在面试时,比如被问到HSRP的主备切换时间时多久,STP几个状态的停留时间,自己知道有这些东西,但在工作中不会经常用到,就老是记不住,觉得可能还是自己基础不够牢固,知识掌握不够全面...

问题终结者
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部