bboyjing's blog

跟开涛学架构五【限流】

发表于 | 分类于

限流就是通过一系列手段来控制并发请求量，以保证整个系统可用。下面就先来看常见的限流算法，然后再看如何具体应用。

限流算法

常见的限流算法有令牌桶和漏桶。

令牌桶算法

令牌桶算法是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。令牌桶算法的描述如下：(该描述完全拷贝书上内容)

  • 假设限制r/s，表示每秒会有r个令牌放入桶中，或者说每过1/r秒桶中增加一个令牌
  • 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝
  • 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上
  • 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流(要么丢弃，要么在缓冲区等待)

漏桶算法

漏桶算法的描述如下：

  • 一个固定容量的漏桶，按照常量固定速率流出水滴
  • 如果桶是空的，则不需要流出水滴
  • 可以以任意速率流入水滴盗漏桶
  • 如果流入水滴超出了桶的容量，则流入的水滴溢出了(被丢弃)，而漏桶容量是不变的

令牌桶是限制平均流入速度，并且允许一定程度的突发流量，只要桶中有令牌就可以处理请求；而漏桶算法限制的是常量流出速度，可以平滑地处理流入速度。乍一看，两者好像并没有本质区别，用的时候再细细体会吧。

限流算法的使用

Guava提供了令牌桶算法实现，可以直接拿来使用。其RateLimiter提供的的令牌桶算法可用于平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。下面在real_server_1项目中简单测试下，首先添加guava依赖：

1
2
3
4
5
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

SmoothBursty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 表示桶容量为5，且每秒新增5个令牌，即每格200毫秒新增一个令牌
RateLimiter limiter = RateLimiter.create(5);
/**
 * acquire()表示消费一个令牌
 * 如果当前桶中有足够令牌，则成功(返回0)
 * 如果桶中没有令牌，则等待一段时间再去消费令牌
 */
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
输出如下：
0.0
0.197007
0.196617
0.199382
0.198855
0.196794

从输出结果可以看出，第一个acquire()成功获取到令牌，接下来差不多每隔200毫秒(结果的输出单位为秒)左右才能消费到令牌。这种实现将突发请求速率平均为固定请求速率。
再看一个突发的例子：

1
2
3
4
5
6
7
8
9
RateLimiter limiter = RateLimiter.create(5);
System.out.println(limiter.acquire(5));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
输出如下：
0.0
0.996835
0.193916

令牌桶算法允许一定程度的突发，所以可以一次性消费5个令牌，但是接下来的差不多需要等待1秒，桶中才有令牌可消费。可以理解为预消费了未来的令牌，但是不会影响生产速度。接着，后面的请求被整形为固定速度了。
再看一个突发例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RateLimiter limiter = RateLimiter.create(2);
System.out.println(limiter.acquire());
Thread.sleep(2000l);
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
输出如下：
0.0
0.0
0.0
0.0
0.499701
0.491598

第二、三个acquire()消费的是桶中积攒的令牌，从第四个acquire()开始正常计算了。
SmoothBursty允许一定程度的突发，如果担心瞬时流量可能会击垮整个系统，那么有一种平滑速率的限流方式，可以再系统冷启动后慢慢趋于平均固定速率。Guava提供了SmoothWarmingUp来实现这种需求，也可以认为是漏桶算法。

SmoothWarmingUp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
RateLimiter limiter = RateLimiter.create(5, 1000, TimeUnit.MILLISECONDS);
for (int i = 0; i < 5; i++) {
    System.out.println(limiter.acquire());
}
Thread.sleep(1000l);
for (int i = 0; i < 5; i++) {
    System.out.println(limiter.acquire());
}
输出如下：
0.0
0.516515
0.352645
0.217478
0.199864
0.0
0.364917
0.220114
0.195786
0.196516

可以看出速率呈梯形上升，也就是说冷启动时会以一个比较打的速率慢慢达到平均速率，然后趋于平均速率。
这里的限流的使用方式是应用级别的，假设部署到多台机器，应用级限流方式只是单应用内的请求限流，不能进行全局限流。因此，需要用分布式限流或者介入层限流来解决这个问题。

分布式限流

分布式限流可以使用Redis+Lua或者Nginx+Lua来实现，这两种都比较简单，就不演示了，有兴趣的话可以去看下作者的书。

接入层限流

接入层通常指请求流量入口，这里我们用了OpenResty，就直接使用它提供的Lua限流模块lua-resty-limit-traffic。假设一个场景，需要将平均请求速率限制在500毫秒一个，下面就一步步来实现：

  1. 在conf/lua目录下新建limit_req.lua文件，内容如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    local limit_req = require("resty.limit.req")
    -- 固定平均速率为2r/s，也就是500毫秒一个请求
    local rate = 2
    -- 桶容量
    local burst = 3
    local error_status = 503
    -- 是否需要不延迟处理
    local nodelay = false
    -- 共享字典
    local lim, err = limit_req.new("limit_req_store", rate, burst)
    if not lim then
        ngx.exit(error_status)
    end
    -- IP维度的限流
    local key = ngx.var.binary_remote_addr
    local delay, err = lim:incoming(key, true)
    -- 超出桶大小
    if not delay and err == "rejected" then
        ngx.exit(error_status)
    end
    if delay > 0 then
        if not nodelay then
            -- 直接突发处理
        else
            -- 延迟处理
            ngx.sleep(delay)
        end
    end

  2. 修改conf/nginx.conf配置：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    http {
        # 共享全局变量，在所有worker间共享
        lua_shared_dict limit_req_store 100m;
        server {
            listen 80;
            
            location = /limit {
                access_by_lua_file /Users/zhangjing/IdeaProjects/hunger/conf/lua/limit_req.lua;  
                echo "access";  
                lua_code_cache off;
                access_log logs/access.log;
            }
        }
    }

  3. 启动nginx，利用AB测试工具简单的测试下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # -n 表示总的请求次数 -c 表示并发数
    ab -c 6 -n 6 http://127.0.0.1/limit
    # nginx的access log输出如下：
    127.0.0.1 - - [10/Oct/2017:23:21:30 +0800] "GET /limit HTTP/1.0" 200 7 "-" "ApacheBench/2.3"
    127.0.0.1 - - [10/Oct/2017:23:21:30 +0800] "GET /limit HTTP/1.0" 200 7 "-" "ApacheBench/2.3"
    127.0.0.1 - - [10/Oct/2017:23:21:30 +0800] "GET /limit HTTP/1.0" 200 7 "-" "ApacheBench/2.3"
    127.0.0.1 - - [10/Oct/2017:23:21:30 +0800] "GET /limit HTTP/1.0" 200 7 "-" "ApacheBench/2.3"
    127.0.0.1 - - [10/Oct/2017:23:21:30 +0800] "GET /limit HTTP/1.0" 503 219 "-" "ApacheBench/2.3"
    127.0.0.1 - - [10/Oct/2017:23:21:30 +0800] "GET /limit HTTP/1.0" 503 219 "-" "ApacheBench/2.3"

从输出可以看出，有请求被限流了。这里只是做了个简单的测试，lua-resty-limit-traffic模块还有更丰富的功能，可以去查阅其文档。

节流

有时候我们想在特定时间窗口内对重复的相同事件最多只处理一次，或者想限制多个连续相同事件最小执行间隔事件，那么可以使用节流(Throttle)实现，这个概念本人还没接触过，一起来学下吧。节流主要有如下集中方法：throttleFirst、throttleLast、throttleWithTimeout。

throttleFirst/throttleLast

throttleFirst/throttleLast是指一个窗口内，如果有重复的多个相同事件要处理，则指处理第一个或最后一个，从而提升性能。一个场景是网页中的一些操作事件，比如resize、scroll等，当快速连续执行这些操作时，可能会造成UI反应慢，甚至卡顿。节流这时候就可以派上用场了，比如同类事件可以只响应最后一次操作。

throttleWithTimeout

throttleWithTimeout也叫做debounce(去抖)，限制两个连续事件的先后执行时间不得小于某个事件窗口。处理方式是，当两个连续事件的间隔事件小于最小间隔时间窗口，就会丢弃上一个事件，而如果最后一个事件等待了最小事件间隔后还没有新的事件到来，那么会处理最后一个事件。比如搜索关键词自动补全，如果用户每录入一个字就发送一个请求，而先输入的字的自动补全很快会被到来的下一个字符覆盖，那么会导致先期的自动补全是无用的。throttleWithTimeout正好可以来解决这个问题，通过它来减少频繁的网络请求。

这一章节就了解到这里了。