文档章节

学习一下令牌桶算法

明瞐
 明瞐
发布于 2016/12/07 11:20
字数 1290
阅读 84
收藏 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

共有 人打赏支持
明瞐
粉丝 5
博文 91
码字总数 27190
作品 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 ---不过...

___大侠
07/10
0
0
接口限流算法总结

算法介绍 计数器法 计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定,对于A接口来说,我们1分钟的访问次数不能超过100个。那么我们可以这么做:在一开始的时候,我们可以...

有事没事
2016/11/07
71
0
【Guava】使用Guava的RateLimiter做限流

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

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

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

suyain
08/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

python生成HTML报告

# -*- coding=utf-8 -*-# author=zyqimport timeclass Template(object): '''html报告''' HTML_TEMP=''' <!DOCTYPE html> <html lang="en"> <head......

小白兔_球球
9分钟前
1
0
模型融合资料汇总

https://blog.csdn.net/u012526003/article/details/79109418https://blog.csdn.net/willduan1/article/details/73618677https://blog.csdn.net/wstcjf/article/details/77989963?utm_so......

KYO4321
11分钟前
1
0
热更步骤

根据官方文档: http://docs.cocos.com/creator/manual/zh/advanced-topics/hot-update.html version_generator.js文件放到项目根目录下 注意步骤的顺序: 1.构建 2.根据构建目录运行下面命令...

Valiancer
12分钟前
1
0
小程序重写CheckBox样式

CheckBox /* 重写 checkbox 样式 *//* 未选中的 背景样式 */checkbox .wx-checkbox-input{ border-radius: 50%; width: 40rpx; height: 40rpx;}/* 选中后的 背景样式...

originDu
16分钟前
1
0
mysql自动安装脚本

[root@localhost_04 ~]# cat mysql.sh #!/bin/bash# "################检查本机安装mysql的基本条件########################"echo "Checking  user :"d=`id -u`if [ $d ......

芬野de博客
29分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部