高并发系统限流中的漏桶算法和令牌桶算法,通过流量整形和速率限制提升稳定性

转自互联网金融小站(internet-sky) 已获作者授权,拒绝二次转载

在大数据量高并发访问时,经常会出现服务或接口面对暴涨的请求而不可用的情况,甚至引发连锁反映导致整个系统崩溃。此时你需要使用的技术手段之一就是限流,当请求达到一定的并发数或速率,就进行等待、排队、降级、拒绝服务等。在限流时,常见的两种算法是漏桶和令牌桶算法算法,本文即对相关内容进行重点介绍。

一、漏桶和令牌桶算法的概念

漏桶算法(Leaky Bucket):主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。漏桶算法提供了一种机制,通过它,突发流量可以被整形以便为网络提供一个稳定的流量。漏桶算法的示意图如下:

请求先进入到漏桶里,漏桶以一定的速度出水,当水请求过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。

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

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

二、两种算法的区别

两者主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,所以它适合于具有突发特性的流量。

三、使用Guava的RateLimiter进行限流控制

Guava是google提供的java扩展类库,其中的限流工具类RateLimiter采用的就是令牌桶算法。RateLimiter 从概念上来讲,速率限制器会在可配置的速率下分配许可证,如果必要的话,每个acquire() 会阻塞当前线程直到许可证可用后获取该许可证,一旦获取到许可证,不需要再释放许可证。通俗的讲RateLimiter会按照一定的频率往桶里扔令牌,线程拿到令牌才能执行,比如你希望自己的应用程序QPS不要超过1000,那么RateLimiter设置1000的速率后,就会每秒往桶里扔1000个令牌。例如我们需要处理一个任务列表,但我们不希望每秒的任务提交超过两个,此时可以采用如下方式:

有一点很重要,那就是请求的许可数从来不会影响到请求本身的限制(调用acquire(1) 和调用acquire(1000) 将得到相同的限制效果,如果存在这样的调用的话),但会影响下一次请求的限制,也就是说,如果一个高开销的任务抵达一个空闲的RateLimiter,它会被马上许可,但是下一个请求会经历额外的限制,从而来偿付高开销任务。注意:RateLimiter 并不提供公平性的保证。

四、使用Semphore进行并发流控

Java 并发库的Semaphore 可以很轻松完成信号量控制,Semaphore可以控制某个资源可被同时访问的个数,通过 acquire() 获取一个许可,如果没有就等待,而 release() 释放一个许可。单个信号量的Semaphore对象可以实现互斥锁的功能,并且可以是由一个线程获得了“锁”,再由另一个线程释放“锁”,这可应用于死锁恢复的一些场合。下面的Demo中申明了一个只有5个许可的Semaphore,而有20个线程要访问这个资源,通过acquire()和release()获取和释放访问许可:

最后:进行限流控制还可以有很多种方法,针对不同的场景各有优劣,例如通过AtomicLong计数器控制、使用MQ消息队列进行流量消峰等等。

—————END—————

看完本文有意思?请分享给更多人

原文发布于微信公众号 - 顶级程序员(TopCoding)

原文发表时间:2017-03-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

知乎美女挖掘指南--Python实现自动化图片抓取、颜值评分

声明:文中所有文字、图片以及相关外链中直接或间接、明示或暗示涉及性别、颜值分数等信息全部由相关人脸检测接口给出。无任何客观性,仅供参考。 1 数据源 知乎 话题...

4916
来自专栏SDNLAB

软件定义光网络故障恢复与资源分配

前言 传统IP分组交换网使用域内路由协议(Interior Gateway Protocol,IGP)和域间路由协议(Border Gateway Protoc...

3369
来自专栏工科狗和生物喵

《实时软件控制设计》MATLAB-PIL测试报告基于Qemu Cortex-M 3的环境

正文之前 首先,跟助教说声抱歉,我们组因为一些因素没有按时完成PIL的测试,还要申请延期。另外也感谢助教的催促,让我们能够在今天下午就完成PIL测试,也算是为本...

4168
来自专栏数据和云

Oracle Database 18c 的10大新特性一览

在 2017 Oracle OpenWorld大会上,关于 Oracle 18c 的一系列新特性已经被披露出来,借助分散在各个会场的公开分享主题和内容、OOW提...

56811
来自专栏灯塔大数据

每周学点大数据 | No.77 众包算法实践——成为众包工人

编者按:灯塔大数据将每周持续推出《从零开始学大数据算法》的连载,本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作,以对话的形式深入浅出的从何为大数据说到大数据算...

45211
来自专栏FreeBuf

极客DIY:制作一款智能家用温控器(PART 2)

引文 在上一部分,我主要是对于外壳以及如何利用树莓派完成了一些简单的计划任务,下面将会对其余的计划任务进行制作。 写在前面 这里主要是需要了解作者用到了两个部分...

2158
来自专栏AI研习社

深度学习训练时 GPU 温度过高?几行命令就可迅速降温!

新买回来的不带水冷公版GPU,在满负载运行的时候,温度从室温马上飙升到85度,而且模型训练不是几分钟完事,很有可能要长期保持在高温状态下运行,让如此昂贵的GPU...

3664
来自专栏人工智能LeadAI

深度学习训练时GPU温度过高?几个命令,为你的GPU迅速降温。

新买回来的不带水冷公版GPU,在满负载运行的时候,温度从室温马上飙升到85度,而且模型训练不是几分钟完事,很有可能要长期保持在高温状态下运行,让如此昂贵的GPU...

6157
来自专栏玉树芝兰

如何免费云端运行Python深度学习框架?

想运行TuriCreate,却没有苹果电脑,也没有Linux使用经验,怎么办?用上这款云端应用,让你免安装Python运行环境。一分钱不用花,以高性能GPU,轻...

3561
来自专栏生信技能树

【直播】我的基因组 32:使用annovar注释vcf

ANNOVAR软件用法看我以前的博客: 1.Annovar使用记录 (http://www.bio-info-trainee.com/641.html) 2.用...

4858

扫码关注云+社区

领取腾讯云代金券