LOADING

Follow me

Golang漫谈之限流简介
10月 04 2019|

Golang漫谈之限流简介

除了《Kubernetes GO》系列之外,对于golang相关知识,同时准备了《Golang 漫谈》以增雅趣,不足之处,万望海涵,在此特别感谢雨痕的Golang 源码剖析

为了防止网站意外暴增的流量比如活动、秒杀、攻击等,导致整个系统瘫痪,在前后端接口服务处进行流量限制是非常有必要的。

做限流(Rate Limiting/Throttling)的时候,除了简单的控制并发,如果要准确的控制TPS,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零。此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的TPS。
因此更平滑的算法如Leaky Bucket–漏桶算法,又或者将原来单位时间内单一的Counter拆分为单位时间内的多个Buckets并滑动计算。本文内容如下:

  • 限流简介
  • 算法简介

一、限流简介

1.1 应用场景

很多做服务接口的人或多或少的遇到这样的场景,由于业务应用系统的负载能力有限,为了防止非预期的请求对系统压力过大而拖垮业务应用系统。也就是面对大流量时,如何进行流量控制?

服务接口的流量控制策略:分流、降级、限流等。本文讨论下限流策略,虽然降低了服务接口的访问频率和并发量,却换取服务接口和业务应用系统的高可用。

实际场景中常用的限流策略:

  • Nginx前端限流
    按照一定的规则如帐号、IP、系统调用逻辑等在Nginx层面做限流

  • 业务应用系统限流

    1. 客户端限流: 基于IP全局限流、基于IP的端点限流、基于IP和客户端key的端点限流、IP和客户端key的白名单、IP和客户端key自定义限制频率、端点自定义限制频率、关于被拒请求的计数器
    2. 服务端限流
  • 数据库限流
    红线区,力保数据库

1.2 常用算法

常用的限流算法由:楼桶算法和令牌桶算法。本文不具体的详细说明两种算法的原理,原理会在接下来的文章中做说明。

1、漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

漏桶

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)。因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率.

2、令牌桶算法

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.

令牌

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

1.3 Leaky Bucket 与 Token Bucket 算法

漏木桶算法简单的想象有一个木桶,有新请求就是不断的倒水进来,然后桶底下有个洞,按照固定的速率把水漏走,如果水进来的速度比漏走的快,桶可能就会满了,然后就拒绝请求。

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate),可以简单的让burst等于rate,也可以让burst更大接收更多突发请求,伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double rate;               // leak rate in calls/s
double burst; // bucket size in calls

long refreshTime; // time for last water refresh
double water; // water count at refreshTime

refreshWater() {
long now = getTimeOfDay();
water = max(0, water- (now - refreshTime)*rate); // 水随着时间流逝,不断流走,最多就流干到0.
refreshTime = now;
}

bool permissionGranted() {
refreshWater();
if (water < burst) { // 水桶还没满,继续加1
water ++;
return true;
} else {
return false;
}
}

Token Bucket 是与 Leaky Bucket 效果一样但方向相反的算法,更加容易理解。随着时间流逝,系统会按速率 1/rate 的时间间隔(如果rate=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了。新请求来临时,会各自拿走一个Token,如果没有Token可拿了就拒绝服务。


二、Guava RateLimiter

2.1 使用简介

Google Guava中的RateLimiter,实际上就实现了Token Bucket的算法。Google搜索看到有些开源项目的issues,要把自己写的Limiter换成了它。

它支持两种获取permits接口,一种是如果拿不到立刻返回false,一种会阻塞等待一段时间看能不能拿到。

Leacky Bucket算法默认一开始水桶是空的,可以立即就接收最多burst的请求,而Token Bucket就要设置初始Token的数量。
RateLimiter有两个子类,一个是WarmingUp,一个是Bursty。

  • WarmingUp,burst = warmUp时间/固定token添加间隔(即上例那个10ms),初始token数量 = burst,有算法保证系统总是相对平滑。
  • Bursty, burst = rate或另外的参数设置,初始token数量 = 0 ,当系统冷了一段时间,支持突发到burst。
  • Guava以micros为时间单位,计算token的变化。
2.2 多个滑动的Buckets

不知道这种算法的业界命名是什么,原理也很简单,将原来的1秒划分为N个bucket。每个请求到来时,计算出当前时间属于哪个bucket,bucket的counter+1,然后计算当前bucket加上前面N-1个bucket的counter总和,看看是否达到rate。


三、算法比较

Leaky Bucket只维持一个桶内水量,每个请求过来时,一是水量加一,二是根据过去的时间减少水量。
滑动Buckets 维持多个桶,每个请求过来时,一是计算出当前桶,当前桶水量加一,二是获得前面多个bucket的水量合计,三是可能需要滚动桶。

  • 滑动Buckets比Leaky Bucket需要更多的Counter。
  • 滑动Buckets需要实现滑动算法,让旧桶过期回收,或置零循环重用。
  • Leaky Bucket支持当系统有一段时间清闲之后,能接收一个较大的burst值,当然也可以把burst值调到和rate一样大来禁止它。

个人比较倾向Leaky Bucket。

3.2 集群限流

用上Redis或Memcached,哪种算法都不会难。但首先,你要有个Redis/Memcached。


后续

针对深入限流相关内容,将会在后续推出


参考资料

zouyee wechat

微信扫一扫
关注该公众号

0%