基于漏桶(Leaky bucket)与令牌桶(Token bucket)算法的流量控制
互联网服务赖以生存的根本是流量, 产品和运营会经常通过各种方式来为应用倒流,比如淘宝的双十一等,如何让系统在处理高并发的同时还是保证自身系统的稳定,通常在最短时间内提高并发的做法就是加机器,但是如果机器不够怎么办?那就需要做业务降级或系统限流,流量控制中用的比较多的两个算法就是漏桶和令牌桶.
漏桶算法(Leaky bucket)
漏桶算法强制一个常量的输出速率而不管输入数据流的突发性,当输入空闲时,该算法不执行任何动作.就像用一个底部开了个洞的漏桶接水一样,水进入到漏桶里,桶里的水通过下面的孔以固定的速率流出,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率.如下图所示:
令牌桶(Token bucket)
令牌桶算法的基本过程如下:
每秒会有 r 个令牌放入桶中,或者说,每过 1/r 秒桶中增加一个令牌
桶中最多存放 b 个令牌,如果桶满了,新放入的令牌会被丢弃
当一个 n 字节的数据包到达时,消耗 n 个令牌,然后发送该数据包
如果桶中可用令牌小于 n,则该数据包将被缓存或丢弃
漏桶和令牌桶比较
“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输数据外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的上限,因此它适合于具有突发特性的流量。
RateLimiter
我们可以使用 Guava 的 RateLimiter 来实现基于令牌桶的流量控制。RateLimiter 令牌桶算法的单桶实现,RateLimiter 对简单的令牌桶算法做了一些工程上的优化,具体的实现是 SmoothBursty。需要注意的是,RateLimiter 的另一个实现 SmoothWarmingUp,就不是令牌桶了,而是漏桶算法。
SmoothBursty 有一个可以放 N 个时间窗口产生的令牌的桶,系统空闲的时候令牌就一直攒着,最好情况下可以扛 N 倍于限流值的高峰而不影响后续请求,就像三峡大坝一样能扛千年一遇的洪水.
建议继续学习:
- 为什么算法这么难? (阅读:10744)
- 15道使用频率极高的基础算法题 (阅读:5631)
- 一些有意思的算法代码 (阅读:4004)
- Fastbit中的bitmap索引算法 (阅读:3785)
- 算法的意义 (阅读:3355)
- 研发面试最常用的10大算法 (阅读:3017)
- 生成特定分布随机数的方法 (阅读:2716)
- 算法收集 (阅读:2504)
- 机器学习算法之LightGBM (阅读:1633)
- 聚类算法之ISODATA (阅读:1470)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Eric 来源: JavaRanger - 专注JAVA高性能程序开发、JVM、Mysql优化、算法
- 标签: 令牌桶 漏桶 算法
- 发布时间:2015-11-08 22:00:18
- [41] 界面设计速成
- [36] Oracle MTS模式下 进程地址与会话信
- [33] IOS安全–浅谈关于IOS加固的几种方法
- [33] 如何拿下简短的域名
- [32] 视觉调整-设计师 vs. 逻辑
- [32] 程序员技术练级攻略
- [32] 图书馆的世界纪录
- [31] android 开发入门
- [31] 【社会化设计】自我(self)部分――欢迎区
- [28] 读书笔记-壹百度:百度十年千倍的29条法则