高并发限流之漏桶算法和令牌桶算法学习

工作中对外提供的API接口设计都要考虑限流，如果不考虑限流，会成系统的连锁反应，轻者响应缓慢，重者系统宕机，整个业务线崩溃，如何应对这种情况呢，我们可以对请求进行引流或者直接拒绝等操作，保持系统的可用性和稳定性，防止因流量暴增而导致的系统运行缓慢或宕机。

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流

缓存：缓存的目的是提升系统访问速度和增大系统处理容量
降级：降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行
限流：限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

令牌与漏桶的区别

漏桶

漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。

令牌桶

生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。

漏桶算法

漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。 在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。

如图所示，把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

令牌桶算法

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。

RateLimiter 用法

https://github.com/google/guava

添加依赖

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>26.0-jre</version>
  <!-- or, for Android: -->
  <version>26.0-android</version>
</dependency>

public class Test {

    public static void main(String[] args) {
        ListeningExecutorService executorService = MoreExecutors.listeningDecorator(Executors.newFixedThreadPool(100));
        // 指定每秒放1个令牌
  RateLimiter limiter = RateLimiter.create(1);
        for (int i = 1; i < 50; i++) {
            // 请求RateLimiter, 超过permits会被阻塞
  //acquire(int permits)函数主要用于获取permits个令牌，并计算需要等待多长时间，进而挂起等待，并将该值返回
  Double acquire = null;
            if (i == 1) {
                acquire = limiter.acquire(1);
            } else if (i == 2) {
                acquire = limiter.acquire(10);
            } else if (i == 3) {
                acquire = limiter.acquire(2);
            } else if (i == 4) {
                acquire = limiter.acquire(20);
            } else {
                acquire = limiter.acquire(2);
            }
            executorService.submit(new Task("获取令牌成功，获取耗：" + acquire + " 第 " + i + " 个任务执行"));
        }
    }
}
class Task implements Runnable {
    String str;
    public Task(String str) {
        this.str = str;
    }
    @Override
  public void run() {
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        System.out.println(sdf.format(new Date()) + " | " + Thread.currentThread().getName() + str);
    }
}

响应

2018-08-11 00:26:22.953 | pool-1-thread-1获取令牌成功，获取耗：0.0 第 1 个任务执行
2018-08-11 00:26:23.923 | pool-1-thread-2获取令牌成功，获取耗：0.98925 第 2 个任务执行
2018-08-11 00:26:33.920 | pool-1-thread-3获取令牌成功，获取耗：9.996993 第 3 个任务执行
2018-08-11 00:26:35.920 | pool-1-thread-4获取令牌成功，获取耗：1.999051 第 4 个任务执行
2018-08-11 00:26:55.920 | pool-1-thread-5获取令牌成功，获取耗：19.999726 第 5 个任务执行
2018-08-11 00:26:57.920 | pool-1-thread-6获取令牌成功，获取耗：1.999139 第 6 个任务执行
2018-08-11 00:26:59.920 | pool-1-thread-7获取令牌成功，获取耗：1.999806 第 7 个任务执行
2018-08-11 00:27:01.919 | pool-1-thread-8获取令牌成功，获取耗：1.999433 第 8 个任务执行

acquire函数主要用于获取permits个令牌，并计算需要等待多长时间，进而挂起等待，并将该值返回

一个RateLimiter主要定义了发放permits的速率。如果没有额外的配置，permits将以固定的速度分配，单位是每秒多少permits。默认情况下，Permits将会被稳定的平缓的发放。

预消费能力

从输出结果可以看出，指定每秒放1个令牌，RateLimiter具有预消费的能力：

acquire 1 时，并没有任何等待 0.0 秒 直接预消费了1个令牌
acquire 10时，由于之前预消费了 1 个令牌，故而等待了1秒，之后又预消费了10个令牌
acquire 2 时，由于之前预消费了 10 个令牌，故而等待了10秒，之后又预消费了2个令牌
acquire 20 时，由于之前预消费了 2 个令牌，故而等待了2秒，之后又预消费了20个令牌
acquire 2 时，由于之前预消费了 20 个令牌，故而等待了20秒，之后又预消费了2个令牌
acquire 2 时，由于之前预消费了 2 个令牌，故而等待了2秒，之后又预消费了2个令牌
acquire 2 时 …..

也就说上一次请求获取的permit数越多，那么下一次再获取授权时更待的时候会更长，反之，如果上一次获取的少，那么时间向后推移的就少，下一次获得许可的时间更短。可见，都是有代价的。

漏桶算法和令牌桶算法的选择

漏桶算法与令牌桶算法在表面看起来类似，很容易将两者混淆。但事实上，这两者具有截然不同的特性，且为不同的目的而使用。

漏桶算法与令牌桶算法的区别在于，漏桶算法能够强行限制数据的传输速率，令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

需要注意的是，在某些情况下，漏桶算法不能够有效地使用网络资源，因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

常用的算法介绍

从简单到复杂依次介绍了如下几种算法：

1. Leaky Bucket
2. Fixed Window
3. Sliding Log
4. Sliding Window

Leaky Bucket

桶算法，做法是预先设置一个请求数的上限，小于这个上限的时候会接收请求， 大于这个上限的话会直接拒绝，只有等到系统处理掉了一些在桶里的请求， 桶里有新的坑位了，才会接收新的请求。

优点：

1. 能够平滑请求数，使系统以一个均匀的速率处理请求
2. 容易实现，可以用一个队列／FIFO 来做
3. 可以只用很小的内存做到为每个用户限流

缺点：

1. 桶满了以后，新的请求都会被扔掉，系统忙着处理旧请求
2. 无法保证请求能够在一个固定的时间内处理完

Fixed Window

固定窗口算法，设置一个时间段内（窗口）接收的请求数，超过的这个请求数的请求会被丢弃。

• 窗口通常选择人们熟悉的时间段：1 分钟／1小时
• 窗口的起始时间通常是当前时间取地板（floor），比如 12:00:03 所在的窗口 （以一分钟的窗口为例）就是 12:00:00 - 12:01:00

优点：

1. 和漏桶相比，能够让新来的请求也能够被处理到

缺点：

1. 在窗口的起始时间，最差情况下可能会带来 2 倍的流量
2. 很多消费者可能都在等待窗口被重置，造成惊群效应

Sliding Log

滑动日志算法，利用记录下来的用户的请求时间，请求数，当该用户的一个新的 请求进来时，比较这个用户在这个窗口内的请求数是否超过了限定值，超过的话 就拒绝这个请求。

优点：

1. 避免了固定窗口算法在窗口边界可能出现的两倍流量问题
2. 由于是针对每个用户进行统计的，不会引发惊群效应

缺点：

1. 需要保存大量的请求日志
2. 每个请求都需要考虑该用户之前的请求情况，在分布式系统中尤其难做到

Sliding Window

滑动窗口算法，结合了固定窗口算法的低开销和滑动日志算法能够解决的边界情 况。

1. 为每个窗口进行请求量的计数
2. 结合上一个窗口的请求量和这一个窗口已经经过的时间来计算出上限，以此 平滑请求尖锋

举例来说，限流的上限是每分钟 10 个请求，窗口大小为 1 分钟，上一个 窗口中总共处理了 6 个请求。现在假设这个新的窗口已经经过了 20 秒，那么 到目前为止允许的请求上限就是 10 - 6 * (1 - 20 / 60) = 8。

滑动窗口算法是这些算法中最实用的算法：

1. 有很好的性能
2. 避免了漏桶算法带来的饥饿问题
3. 避免了固定窗口算法的请求量突增的问题

分布式实现

同步的策略

难点在于限流上限都是针对全站的流量设置的，那么每个节点该如何协调各自处理的量呢？

解决的方法通常都是使用一个统一的数据库来存放计数，比如 Redis 或者 Cassandra。 数据库中将存放每个窗口和用户的计数值。这种方法的主要问题是需要多访问一次数据库， 以及竞争问题。

竞争问题

竞争问题就是当有两个以上的线程同时执行 i += 1 的时候，如果没有同步这 些操作的话，i 的值可能会有多种情况。

处理竞争问题可以通过加锁来做，不过在限流的场景下，这样做肯定会成为系统的瓶颈， 毕竟限流时每个请求都会来竞争这个锁。

更好的办法是通过 set-then-get 的方法，限流场景中用到的只是计数 +1， 利用这一点以及数据库实现的性能更好的原子操作可以达到我们的目的。

性能优化

image

利用集中式的数据库的另一个问题是每次请求都要查一下数据库带来的延迟开销， 数据库再快也会带来几毫秒的延迟。

解决这个问题的方法可以通过在内存里面维护一个计数值，代价是稍微的放松限 流的精确度。通过设置一个定时任务从数据库拿计数值，周期内在内存中维护这 个计数，周期结束时把计数同步到数据库并拿取新的计数，如此往复。

这个同步周期往往是做成可以配置的，小的周期能够带来更精确的限流， 大的周期则能减轻数据库的 I/O 压力。

python 可用limits库

https://github.com/hugoren/limits

可选用的limit策略