search

nereuschen / blog

blog
44 stars 11 forks source link

限流技术 #37

Open nereuschen opened 8 years ago

nereuschen commented 8 years ago

限流

the wall

绝境长城（冰与火之歌）

通常限流主要是限制并发数以及QPS，从而避免异常流量对系统的冲击；

并发数和QPS是紧密相关的，可以参考Little's Law(律特法则)：L = λW （proven 1961）

一个排队系统在稳定状态下，在系统里面的个体的数量的平均值 L， 等于 平均个体到达率λ （单位是λ个每单位时间）乘以 个体的平均逗留时间W

数学定理（严格的数学推理，非经验公式） 排队论的理论

限流算法

最粗暴的实现方式是每执行一次delay一定时间，从而达到限制QPS的效果

比如，我们想以最大的QPS为10去处理1000个业务逻辑，那么代码很可能这么写

    for (int i = 0; i < 1000; i++) {
        doSomething();
        Thread.sleep(100);
    }

这种写法有什么弊端？

因此，采用delay这种粗暴的实现方式很难将QPS稳定地控制在10

要想解决这个问题，就必须做到

Fixed_Sliding_Window

Leaky bucket(漏桶算法)正好解决了这些问题

Token bucket(令牌桶算法)和它一样，都是最常见的两种限流算法

Leaky bucket漏桶算法

算法实现

Leaky bucket

不断的往桶里面注水，无论注水的速度是大还是小，水都是按固定的速率往外漏水；

如果桶满了，水会溢出；

特点

Token bucket

令牌发送：每秒往桶里面发送r个令牌(token)

桶的容量：桶中最多可以存放b个token；当放入的token数量超过b时，新放入的token会被丢弃

请求访问：每次请求访问时先check桶中有没有剩余的令牌

由于每秒会不断地往桶中放r个token，所以当无业务请求需处理时，桶中的token数量会不断增加，止到达到桶的容量b为止

特点

对比项 Leakly bucket Token bucket Token bucket的备注
依赖token 否 是
立即执行 是 否 有足够的token才能执行
堆积token 否 是
速率恒定 是 否 可以大于设定的QPS

具体实现

Guava的RateLimiter实现

在Guava中RateLimiter的实现有两种：SmoothBursty和SmoothWarmUp

补充类图

SmoothBursty

RateLimiter rateLimiter = RateLimiter.create(permitsPerSecond);//创建一个SmoothBursty实例

rateLimiter.acquire();//获取1个permit；可能会被阻塞止到获取到为止

以下场景，调用acquire()时何时有返回值？

QPS=1,4个线程在以下时间点依次调用acquire()方法

T0 at 0    seconds  --> 0 excute

T1 at 1.05 seconds  --> 1.05

T2 at 2    seconds  --> 2.05(=1.05+1)

T3 at 3    seconds  --> 3.05(=2.05+1)

注意：SmoothBursty中maxBurstSeconds的默认值是1，并且不可以修改，所以SmoothBursty最多只能积累permitsPerSecond个permits

SmoothWarmingUp

  • 基于Leaky bucket算法实现
  • QPS是固定的
  • 不支持burst
  • 使用于需要预热时间的使用场景 RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)
//创建一个SmoothWarmingUp实例；warmupPeriod是指预热的时间
RateLimiter rateLimiter =
            RateLimiter.create(permitsPerSecond,warmupPeriod,timeUnit);
rateLimiter.acquire();//获取1个permit；可能会被阻塞止到获取到为止

预热期间QPS会平滑地逐步加速到最大的速率（也就是QPS）

简单用例代码

public class RateLimiterUseCase {

    private Logger logger = LoggerFactory.getLogger(RateLimiterUseCase.class);
    private int qps;
    private int requestCount;

    private RateLimiter rateLimiter;

    public RateLimiterUseCase(int qps, int requestCount) {
        this.qps = qps;
        this.requestCount = requestCount;
    }

    private void buildRateLimiter(RateLimiter rateLimiter) {
        this.rateLimiter = rateLimiter;
    }

    private void processRequest(int requestCount) {
        logger.info("RateLimiter 类型:{}", rateLimiter.getClass());
        long startTimeMillis = System.currentTimeMillis();
        for (int i = 0; i < requestCount; i++) {
            rateLimiter.acquire();
        }
        long usedTimeMillis = System.currentTimeMillis() - startTimeMillis;
        logger.info("处理请求数:{},耗时:{},限流的qps:{},实际的qps:{}", requestCount, usedTimeMillis, rateLimiter.getRate(), Math.ceil(requestCount / (usedTimeMillis / 1000.00)));
        logger.info("");
    }

    private void sleep(int sleepTimeSeconds) {
        logger.info("等待{}秒后，继续处理下一批{}个请求", sleepTimeSeconds, requestCount);
        try {
            Thread.sleep(sleepTimeSeconds * 1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void processWithTokenBucket() {
        buildRateLimiter(RateLimiter.create(qps));
        doProcess();
    }

    public void processWithLeakBucket() {
        buildRateLimiter(RateLimiter.create(qps, 0, TimeUnit.MILLISECONDS));
        doProcess();
    }

    private void doProcess() {

        sleep(0);
        processRequest(requestCount);

        sleep(1);
        processRequest(requestCount);

        sleep(5);
        processRequest(requestCount);

        sleep(10);
        processRequest(requestCount);
    }

    public static void main(String[] args) {
        RateLimiterUseCase test = new RateLimiterUseCase(10, 100);
        test.processWithLeakBucket();
        test.processWithTokenBucket();

        test = new RateLimiterUseCase(10, 15);
        test.processWithLeakBucket();
        test.processWithTokenBucket();
    }
}

运行结果

09:55:47.662 [main] INFO  c.n.guava.RateLimiterUseCase - 等待0秒后，继续处理下一批100个请求
09:55:47.668 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:55:57.573 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:9904,限流的qps:10.0,实际的qps:11.0
09:55:57.574 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:55:57.574 [main] INFO  c.n.guava.RateLimiterUseCase - 等待1秒后，继续处理下一批100个请求
09:55:58.578 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:56:08.481 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:9903,限流的qps:10.0,实际的qps:11.0
09:56:08.481 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:56:08.481 [main] INFO  c.n.guava.RateLimiterUseCase - 等待5秒后，继续处理下一批100个请求
09:56:13.486 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:56:23.388 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:9902,限流的qps:10.0,实际的qps:11.0
09:56:23.388 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:56:23.388 [main] INFO  c.n.guava.RateLimiterUseCase - 等待10秒后，继续处理下一批100个请求
09:56:33.391 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:56:43.293 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:9902,限流的qps:10.0,实际的qps:11.0
09:56:43.294 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:56:43.294 [main] INFO  c.n.guava.RateLimiterUseCase - 等待0秒后，继续处理下一批100个请求
09:56:43.294 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:56:53.195 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:9901,限流的qps:10.0,实际的qps:11.0
09:56:53.196 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:56:53.196 [main] INFO  c.n.guava.RateLimiterUseCase - 等待1秒后，继续处理下一批100个请求
09:56:54.197 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:57:03.194 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:8997,限流的qps:10.0,实际的qps:12.0
09:57:03.194 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:03.194 [main] INFO  c.n.guava.RateLimiterUseCase - 等待5秒后，继续处理下一批100个请求
09:57:08.198 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:57:17.102 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:8904,限流的qps:10.0,实际的qps:12.0
09:57:17.103 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:17.103 [main] INFO  c.n.guava.RateLimiterUseCase - 等待10秒后，继续处理下一批100个请求
09:57:27.107 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:57:36.012 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:100,耗时:8905,限流的qps:10.0,实际的qps:12.0
09:57:36.012 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:36.012 [main] INFO  c.n.guava.RateLimiterUseCase - 等待0秒后，继续处理下一批15个请求
09:57:36.013 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:57:37.416 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:1403,限流的qps:10.0,实际的qps:11.0
09:57:37.416 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:37.416 [main] INFO  c.n.guava.RateLimiterUseCase - 等待1秒后，继续处理下一批15个请求
09:57:38.417 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:57:39.820 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:1402,限流的qps:10.0,实际的qps:11.0
09:57:39.821 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:39.821 [main] INFO  c.n.guava.RateLimiterUseCase - 等待5秒后，继续处理下一批15个请求
09:57:44.825 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:57:46.228 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:1403,限流的qps:10.0,实际的qps:11.0
09:57:46.229 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:46.229 [main] INFO  c.n.guava.RateLimiterUseCase - 等待10秒后，继续处理下一批15个请求
09:57:56.233 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothWarmingUp
09:57:57.636 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:1403,限流的qps:10.0,实际的qps:11.0
09:57:57.636 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:57.636 [main] INFO  c.n.guava.RateLimiterUseCase - 等待0秒后，继续处理下一批15个请求
09:57:57.636 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:57:59.037 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:1400,限流的qps:10.0,实际的qps:11.0
09:57:59.037 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:57:59.037 [main] INFO  c.n.guava.RateLimiterUseCase - 等待1秒后，继续处理下一批15个请求
09:58:00.038 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:58:00.539 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:501,限流的qps:10.0,实际的qps:30.0
09:58:00.540 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:58:00.540 [main] INFO  c.n.guava.RateLimiterUseCase - 等待5秒后，继续处理下一批15个请求
09:58:05.542 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:58:05.945 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:403,限流的qps:10.0,实际的qps:38.0
09:58:05.946 [main] INFO  c.n.guava.RateLimiterUseCase - 
09:58:05.946 [main] INFO  c.n.guava.RateLimiterUseCase - 等待10秒后，继续处理下一批15个请求
09:58:15.947 [main] INFO  c.n.guava.RateLimiterUseCase - RateLimiter 类型:class com.google.common.util.concurrent.SmoothRateLimiter$SmoothBursty
09:58:16.350 [main] INFO  c.n.guava.RateLimiterUseCase - 处理请求数:15,耗时:403,限流的qps:10.0,实际的qps:38.0
09:58:16.350 [main] INFO  c.n.guava.RateLimiterUseCase -

RateLimiter的结论

对于SmoothBurst [RateLimiter.create(permitsPerSecond)] 而言，是基于Token bucket算法，因此

速率不是固定的，因为允许出现burst突发情况，实际的QPS会出现大于permitsPerSecond的情况； 设定的QPS越大，需要处理的request越小时，实际的QPS越大； 设定的QPS越小，需要处理的request越大时，实际的QPS越平稳，越接近设定的QPS

对于SmoothWarmingUp [RateLimiter.create(permitsPerSecond,warmupPeriod,timeUnit)]而言，是基于Leaky bucket算法，因此

速率是固定的，因此QPS也是固定的，不会出现burst突发情况

获取permit时是否会block线程

acquire()会block线程

/**
   * Acquires a single permit from this {@code RateLimiter}, blocking until the
   * request can be granted. Tells the amount of time slept, if any.
   *
   * <p>This method is equivalent to {@code acquire(1)}.
   *
   * @return time spent sleeping to enforce rate, in seconds; 0.0 if not rate-limited
   * @since 16.0 (present in 13.0 with {@code void} return type})
   */
  public double acquire() {
    return acquire(1);
  }

tryAcquire() 不会block线程

/**
   * Acquires a permit from this {@link RateLimiter} if it can be acquired immediately without
   * delay.
   *
   * <p>
   * This method is equivalent to {@code tryAcquire(1)}.
   *
   * @return {@code true} if the permit was acquired, {@code false} otherwise
   * @since 14.0
   */
  public boolean tryAcquire() {
    return tryAcquire(1, 0, MICROSECONDS);
  }

具体应用

业务场景

淘宝双十一

如果你在双十一0点0分之后，购物的时候遇到这个页面，那么亲，你被限流了，必须排到等待

天猫限流

用户洪峰

特点：

为了提升用户体验，需要支持爆发量，所以采用令牌桶算法

令牌桶算法

允许最大的访问速率：b+r 爆发持续时间：T=b/(m-2r) 爆发量：L=T*r

回调洪峰

特点：

采用漏桶算法

漏桶算法

限流框架

分成几个主要模块

限流框架的处理流程

处理流程

小米秒杀

TODO

分层架构

Nginx限流

Nginx限流模块

vi /etc/nginx/conf.d/default.conf

......

upstream myapp {
    server 127.0.0.1:8081;
}

limit_req_zone $binary_remote_addr zone=login:10m rate=10r/s;

server {
    server_name _;

    location / {
        proxy_pass http://myapp;
        proxy_set_header X-Real-IP $remote_addr;
        proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
        proxy_set_header Host $http_host;
    }

    location /account/login/ {
        # apply rate limiting
        limit_req zone=login burst=5 nodelay;

        # boilerplate copied from location /
        proxy_pass http://myapp;
        proxy_set_header X-Real-IP $remote_addr;
        proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
        proxy_set_header Host $http_host;
    }
}

参数说明

从示例配置信息中可以看出：

对访问/account/login/的请求根据访问的IP进行了限速，QPS是10；

对于同一个IP地址只允许每秒10个请求访问该URL；

如果请求量大于QPS(10)，会立即返回503（因为配置了参数nodelay）；

如果没有配置参数nodelay，那么超过QPS访问量的请求会先积压到桶中(可以积压5个)，

如果桶满了，就返回503。

nginx限流模块默认使用的是漏桶算法，而当配置了nodelay时采用的是令牌算法，此时允许burst请求

重点说明一下对burst+nodelay的理解

limit_req_zone $binary_remote_addr zone=login:10m rate=1r/s;

......

 location /account/login/ {
        # apply rate limiting
        limit_req zone=login burst=15 nodelay;
 }
时间点 并发请求量 拒绝的请求次数 成功的请求次数
10:00:01 15 0 15
10:00:15 15 0 15
10:00:30 15 0 15
10:00:45 15 0 15
11:00:01 15 0 15
11:00:02 15 14 1
11:00:03 15 14 1
11:00:04 15 14 1

针对这个case的理解:

（1）在[10:00:01到10:00:45]期间，每隔15秒会有15个并发请求，虽然在这些时间点上并发

请求大于rate，但在每个15秒内其QPS是1，依旧未超过rate，所以每次的15个并发请求能够

被成功处理

（2）在[11:00:01到11:00:05]期间，每秒15个并发请求，在11:00:01时，请求量未超过burst，

并且由于配置了nodelay，所以当时15个请求立即被执行了；而在其他的时间点上QPS大于

rate，所以超出rate的请求直接被拒绝

Nginx+lua

REDIS

http://redis.io/commands/INCR#pattern-rate-limiter https://github.com/UsedRarely/spring-rate-limit https://github.com/colley/spring-ratelimiter https://github.com/nlap/dropwizard-ratelimit https://github.com/sudohippie/throttle https://github.com/coveo/spillway https://github.com/marcosbarbero/spring-cloud-starter-zuul-ratelimit

API 调用次数限制实现

Java Rate-Limiting API

ZK

Distributed Atomic Long

Shared Semaphore

HTTP&DUBBO&MQ

可以借助在filter中通过RateLimiter来实现正对单机的限流

DB

淘宝双十一秒杀业务

秒杀特点：瞬时并发高、数据一致性高、热点更新频率高

大量更新DB中的同一条记录时，会产生锁等待，导致DB性能急剧下降

当大量的并发更新同一条记录时，使用排队的方式来保证高并发下热点记录更新依然能保持

较好的性能，为threads_running设置一个硬上线，当并发超过此值是，拒绝执行sql，

保护MySQL，我们将这个称之为高水位限流，这样就给数据库加上了一层限流的功能，使得

数据库不被瞬间的高爆发请求打爆。

高水位限流实现：

监控系统status变量threads_running，当满足拒绝条件，拒绝执行sql，返回用户：

MySQL Server is too busy，判断逻辑在dispatch_command中，sql解析之后。

增加的系统variables：

  1.threads_running_ctl_mode： 限流的sql类型，有两个取值：[ALL | SELECTS]，

  默认SELECTS，设置为ALL需谨慎。

  2.threads_running_high_watermark： 限流水位值，只有threads_running

  超过此值才会触发，默认值为max_connections，当set global 

  threads_running_high_watermark=0时自动设置为max_connections

拒绝必要条件：

 1.threads_running超过threads_running_high_watermark

 2.threads_running_ctl_mode与sql类型相符

以下情况不拒绝：

 1.用户具有super权限

 2.sql所在事务已经开启

 3.sql为commit/rollback

参考资料

Token bucket算法图片

Better Rate Limiting in .NET

[阿里双11系统管控调度架构与实践.pdf]()

Nginx限流模块

edwinmin commented 8 years ago

爆发持续时间：T=b/(m-2r)这个时间是怎么计算的

qyvlik commented 5 years ago

@nereuschen 如果我想要 10秒 100 次限频，如果第 1 秒用完 100 次，剩下 9 秒都需要等待。这种使用哪种限流算法比较好。

Marszx commented 5 years ago

@nereuschen 如果我想要 10秒 100 次限频，如果第 1 秒用完 100 次，剩下 9 秒都需要等待。这种使用哪种限流算法比较好。

感觉你说的就是时间窗口内burst的问题，但是总得有个窗口大小。比如你10秒限制100次，听上去好像跟20秒限制200次差不多，但是我20秒限制200次我可以第一秒用掉200次，但是你10秒100次就不行。所以感觉跟1秒10次差不多？只不过看你允许的burst到底有多大。

所以我理解第一秒就填充所有时间窗口内的令牌是不是就符合你的要求。 比如你的窗口大小是10秒，我初始化的时候就放了100个，然后到10秒结束的时候就放100个，桶最大是100，溢出丢弃。但是这个10秒的意义可能就是允许的burst到底有多大了。