浅谈限流算法

Catalogue

1. 1. 前言
2. 2. 限流简介
3. 3. 限流算法
   1. 3.1. 令牌桶算法
      1. 3.1.1. 令牌桶算法的实现
   2. 3.2. 漏桶算法
      1. 3.2.1. 漏桶算法的实现
4. 4. 令牌桶算法和漏桶算法比较
5. 5. 计数器限流
   1. 5.1. 使用Java中的 AomicInteger
6. 6. 小结
7. 7. 参考链接 & 鸣谢

前言

之前有参与过一个小型的校园抢票系统的部分设计，里面就涉及到关于高并发下如何进行限流的问题，当时的做法是直接利用 redis进行限流，后期维护的时候发现自己对限流这块掌握的不好，于是就从网上查资料去研究 限流的应用，下面的总结也是基于网上的资料写的，肯定与网上的内容有重叠的情况，这里算是做个记录总结一下吧。

限流简介

在高并发项目中，经常会存在短时间内用户访问人数过多导致系统崩溃的问题，这个时候一个解决方法就是利用限流。

限流的目的是通过对并发访问、请求进行限速或者一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务，排队或等待，降级等

限流算法

常用的限流算法有: 漏桶(leaky bucket)，令牌桶(Token Bucket),计数器，下面就对三种算法进行简单分析。

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。桶中最多存放一定数量的令牌,当桶满时，新添加的令牌被丢弃或拒绝。如下图所示

上图出自开涛大神的聊聊高并发系统之限流特技这篇博客，非常形象。

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

令牌桶算法的实现

在 Google Guava中提供了一个 RateLimiter 工具类，就是基于 令牌桶算法 实现平滑突发的限流策略。

RateLimiter是一个速度控制器，可以根据配置的速度发送令牌。其中有一个重要的方法——acquire(num)方法，、该方法表示从RateLimiter消费多少个令牌，被阻塞到获取到令牌(许可证)，如果存在等待的情况的话，告诉调用者获取到该请求所需要的睡眠时间.

public class RateLimiterTest implements Runnable{
    /**
     * 令牌桶算法
     * 每秒产生 2 个令牌
     *
     */
    private static final RateLimiter limiter = RateLimiter.create(2);

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 5; i++) {
            RateLimiterTest rateLimiterTest = new RateLimiterTest();
            new Thread(rateLimiterTest).start();
        }
    }
    @Override
    public void run() {
        final double acquire = limiter.acquire();
        System.out.println("当前时间 - "+LocalDateTime.now()+" - "+Thread.currentThread().getName()+"- 阻塞时长 -"+ acquire+ "秒");

    }
}

控制台输出:

当前时间 - 2018-09-14T14:44:44.189 - Thread-1- 阻塞时长 -0.0秒
当前时间 - 2018-09-14T14:44:44.573 - Thread-2- 阻塞时长 -0.490724秒
当前时间 - 2018-09-14T14:44:45.071 - Thread-5- 阻塞时长 -0.990702秒
当前时间 - 2018-09-14T14:44:45.571 - Thread-4- 阻塞时长 -1.490681秒
当前时间 - 2018-09-14T14:44:46.072 - Thread-3- 阻塞时长 -1.990559秒

代码解读:

• RateLimiter.create(2)表示每秒新增2个令牌，即每500ms新增一个令牌
• limiter.acquire()表示消费一个令牌，如果当前桶中有足够令牌则成功 (返回值为0)，如果没有令牌则暂停一段时间，比如发令牌间隔是500ms，则大致等待500ms再去消费令牌，如上面控制台输出一样，每次阻塞间隔大致500ms左右

在江南白衣大大的服务化体系之－限流中有提到关于 RateLimiter的一些实现细节：

在RateLimiter的实现里，即使桶里没有多少令牌，依旧可以超出消耗，然后桶里面在时间段内都没有新令牌，比如桶的容量是5，桶里面现在只有1个令牌，如果你要拿5个令牌，也可以，清了桶里的一个令牌，再预借4个，然后再过800ms，桶里才会出现新令牌。

漏桶算法

漏桶作为计量工具时，可以用于流量整型和流量控制，网上大多数关于漏桶算法的描述如下:

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

漏桶算法思路很简单，水(数据或者请求)先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

漏桶它的主要目的是控制注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供了一个稳定的流量。漏桶可以看做是一个带有常量服务时间的单服务器队列，如果漏桶(包缓存)溢出，那么数据包会被丢弃。

在某些情况下，漏桶算法不能够有效使用网络资源，因为漏桶的漏出速率是固定的参数，所以，即使网络中不存在资源冲突(没有发生拥塞)，漏桶算法也不能使某一个单独的流突发到端口速率。因此，对于存在突发特性的流量来说缺乏效率，而令牌桶算法则能够满足这些具有突发特性的流量。

通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制

漏桶算法的实现

漏桶算法可以通过 信号量(Semaphore) 的方式实现，可以达到消峰的目的。Semaphore是用来控制同时访问特定资源的线程数量，它通过协调各个线程，以保证合理的使用公共资源，其应用场景就是用于流量控制，也可以说是实现了漏桶算法，比如数据库连接，如果有大量的线程访问数据库，而数据库连接数只有10个，此时我们就需要控制只有10个线程同时获取数据库连接保存数据，否则无法获取数据库连接。这种情况下，我们就可以利用 semaphore来做限流控制，示例代码如下:

public class SemaphoreTest {
    private static final int THRED_COUNT = 20;
    /**
     * 设置线程池大小为20
     */
    private static ExecutorService service = Executors.newFixedThreadPool(THRED_COUNT);
    /**
     * 设置信号量，表示只允许10个并发的执行
     */
    private static Semaphore semaphore = new Semaphore(10);
    public static void main(String[] args) {
        //20个线程在运行
        for (int i = 0; i < THRED_COUNT; i++) {
            service.execute(new Runnable() {
                @Override
                public void run() {
                    try {
                        //线程使用acquire获取一个许可证
                        semaphore.acquire();
                        System.out.println("通过,save data,线程: "+Thread.currentThread().getName());

                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    } finally {
                        semaphore.release();
                    }
                }
            });
        }
        service.shutdown();
    }
}

代码解读:

• 一共30个线程，但是只允许10个并发的执行，我们启动的线程数就表示了漏桶算法中的流入速率，该速率是任意的
• Semaphore(int permits) 接受一共整型的数字，表示可用的许可证数量，比如Semaphore(10)表示允许10个线程获取许可证，也就是最大并发数是10，其实就相当于漏桶算法中的常量固定速率
• 线程使用 acquire方法获取一个许可证，使用完之后调用release()归还许可证

测试结果:

通过,save data,线程: pool-1-thread-2
通过,save data,线程: pool-1-thread-1
通过,save data,线程: pool-1-thread-3
通过,save data,线程: pool-1-thread-4
通过,save data,线程: pool-1-thread-5
通过,save data,线程: pool-1-thread-6
通过,save data,线程: pool-1-thread-7
通过,save data,线程: pool-1-thread-8
通过,save data,线程: pool-1-thread-9
通过,save data,线程: pool-1-thread-10
通过,save data,线程: pool-1-thread-12
通过,save data,线程: pool-1-thread-11
通过,save data,线程: pool-1-thread-14
通过,save data,线程: pool-1-thread-16
通过,save data,线程: pool-1-thread-18
通过,save data,线程: pool-1-thread-17
通过,save data,线程: pool-1-thread-19
通过,save data,线程: pool-1-thread-20
通过,save data,线程: pool-1-thread-13
通过,save data,线程: pool-1-thread-15

令牌桶算法和漏桶算法比较

令牌桶和漏桶比较:

• 定义
  • 令牌桶是按照设定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求
  • 漏桶是按照常量固定速率流出请求，流入速率任意，当流入的请求数累积到漏桶容量时，新流入的请求被拒绝
• 针对突发性流量
  • 令牌桶可以限制平均流入速率，只要有令牌，允许一定程度的突发流量
  • 漏桶流入速率任意，流出速率常量，即平滑突发流入速率

计数器限流

计数器限流算法也是比较常用一种的限流方案，是最简单粗暴的，主要用来限制总并发数，比如数据库连接池大小，线程池大小，接口访问并发数等都是使用计数器算法。在我之前参与的那个校园抢票系统中实际上也是利用计数器进行限流。

使用Java中的 AomicInteger

AomicInteger是JDK 1.5提供的拥有原子特性的计数功能，在Java多线程过程中，++i和i++操作并不是线程安全的，而AtomicInteger就解决了这个问题，提供一种保证线程安全的加减操作接口，就像 redis incr一样。下面是示例代码:

public class AtomicLimiterTest implements Runnable{
    private static final AtomicInteger atomic = new AtomicInteger(0);


    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            AtomicLimiterTest atomicLimiterTest = new AtomicLimiterTest();
            new Thread(atomicLimiterTest).start();
        }
    }

    @Override
    public void run() {
        if (atomic.get() >= 3) {
            System.out.println("超出限流数，拒绝请求");
        } else {
            atomic.incrementAndGet();
            System.out.println("当前计数为: "+atomic.get());
            //处理业务逻辑
        }
    }
}

控制台输出:

当前计数为: 1
当前计数为: 2
当前计数为: 3
超出限流数，拒绝请求
超出限流数，拒绝请求

小结

对于限流来说，我们往往需要根据实际业务场景来决定使用何种算法进行限流。最好的算法不一定是最合适的。

上面简单的介绍了几种限流算法，参考了一些大神的文章，这里只是做个简单记录，如有错误之处，欢迎指出。

参考链接 & 鸣谢

• 聊聊高并发系统之限流特技
• 服务化体系之－限流
• 限流探索
• 并发工具类（三）控制并发线程数的Semaphore
• Guava官方文档-RateLimiter类