分布式基础 - 限流算法

Liang

2019-12-26

分布式基础

294

一、意义

一段时间内请求过大，会给服务器造成很大的压力，限流算法就是解决高并发、大流量的一种方案，保证应用的可用性

二、算法

2.1 计数器算法

2.1.1 思想

限制一秒钟内通过的请求数

2.1.2 实例

设置限流 QPS 为 100，那么，接下来 1S 内，每来一个请求，就把计数器加一，如果类加到了 100 ，那么后续请求会全部拒绝；当 1S 到达时，把计数器恢复为 0 ，重新开始计数

2.1.3 实现

在 Java 中，可用原子类来取得最新的计数器值，并和阈值比较，例如以下伪代码

class Limiter {
    public static AtomicLong counter = new AtomicLong();
}

class Main {
    public static void main(String[] args) {
        if (Limiter.counter.get() != LIMIT_THRESHOLD) {
            // 业务操作
            Limiter.counter.incrementAndGet();
        }
    }
}

2.1.4 缺点

计数器算法会有一种叫做突刺的现象，如果现在有 1000 个请求，设置 QPS = 100，那么 1S 内，只能通过 100 个请求，如果这 100 个请求，100 ms 就搞定了，那么 900ms ，限流器也会让剩下的 900 个请求无法执行，这 900 个请求也会失败，只有等到下一个次重置计数，才开始继续执行新的请求

在于这就是所谓的 “突刺现象”，所以，计数器算法的难点在于如何设置 QPS 才能尽可能地避免这种情况，但往往难以确定，受多方面影响

2.2 漏桶算法

2.2.1 思想

设置一个类似漏桶的容器，将请求堆积到漏桶容器里，让请求以均匀的速度流出，相比于计数器，它改进了许多，可以大程度地避免常规的突此现象

2.2.2 实例

设置限流 QPS 为 100，漏桶流出请求的速度为每秒 1000 个请求，这时服务器接到了 1000 个请求，那么 100 个请求在 100ms 就会流出，此时 900 个请求，不会像上面一样丢失，会留在容器内，慢慢流出

2.2.3 实现

漏桶的底层可以用一个队列来保存请求，而服务器业务端可以通过线程池定期从队列中获取请求并执行，简单的实现思想，在 Java 中可以使用 Queue，伪代码如下

class Limiter {
    public static BlockingQueue<Request> leakyBucket = new LinkedBlockingDeque<>();
}

class Main {
    public static void main(String[] args) {
        if (Limiter.leakyBucket.size() != LIMIT_THRESHOLD) {
            Request request = Limiter.leakyBucket.take();
            // 业务代码
        }
    }
}

2.2.4 缺点

在实际使用的时候，漏桶的大小不可能使用无界的链表作为队列的实现，因为堆积太多请求会导致内存溢出，要指定漏桶的大小，或者就算是使用链表，别的地方设置一个阈值来限制漏桶的容量，一旦限制了漏桶的容量，那么突发超过桶容量的请求也会和计数器一样被丢弃

此时也会涉及两个问题，漏桶设置太大，内存溢出，设置太小请求流失过多

2.3 令牌桶算法

2.3.1 思想

设置一个令牌桶，用来保存令牌，令牌桶存放固定数量的令牌
设置一个令牌工厂，以一定的速率往桶中放令牌
规定每次调用，必须在令牌桶中取得令牌，才有机会继续执行，否则等待可用的令牌，或者直接拒绝

此时，如果有大量的令牌，进来的请求可用直接拿到令牌执行，所以令牌桶可用允许一定程度的突发请求

2.3.2 实例

设置 QPS = 100，那么限流器初始化完成一秒后，桶中就有 100 个令牌了，这时服务还么完全启动好，服务启动，来了 100 个请求时，能直接应对这一百个突发的请求

如果一开始来了 1000 个请求，设置 QPS = 100，那么，一开始能够处理 100 个突发请求，令牌桶空了，接着剩下的 1s 会以均匀的速度生成 100 令牌，那么最后会剩 800 个请求没处理，它只能**等待（阻塞）**或直接丢弃

2.3.2 实现

具体的实现，令牌工厂可用设置一个队列，令牌桶可用设置一个队列，业务代码使用线程池去取得令牌

具体参考 Google 的 guava 包，实现了令牌桶的限流器

 <dependency>

    <groupId>com.google.guava</groupId>

    <artifactId>guava</artifactId>

    <version>18.0</version>

</dependency>

public class RateLimiterMain {
    public static void main(String[] args) {
        // 每秒生成 10 个令牌
        RateLimiter rateLimiter = RateLimiter.create(10);
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {

                @Override
                public void run() {
                    // 有可用令牌执行，没有则阻塞
                    // 如果使用 tryAcquire() ，有则执行，无则返回 false
                    rateLimiter.acquire()
                    System.out.println("pass");
                }
                
            }).start();
        }
    }
}

三、参考

谈谈服务限流算法的几种实现