高并发下的流量控制

为了应用服务的高可用，一个常用的办法是对大流量的请求（秒杀/抢购）进行限流，拦截掉大部分请求，只允许一部分请求真正进入后端服务器，这样就可以防止大量请求造成系统压力过大导致的系统崩溃，从而保护服务正常可用。

固定窗口计数器、滑动窗口计数器、漏桶(leaky bucket) 、令牌桶(Token Bucket)算法是最常用的四种限流的算法。

1. 限流算法

1.1 固定窗口计数器

优点：实现简单，容易理解。

缺点：流量曲线可能不够平滑，有 突刺现象 并且 一段时间内系统不可用，如下图所示。这样会有两个问题：

计数器固定窗口算法限流曲线

一段时间内（不超过时间窗口）系统服务不可用。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第1ms来了100个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。
窗口切换时可能会产生两倍于阈值流量的请求。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第999ms来了100个请求，窗口前期没有请求，所以这100个请求都会通过。再恰好，下一个窗口的第1ms有来了100个请求，也全部通过了，那也就是在2ms之内通过了200个请求，而我们设定的阈值是100，通过的请求达到了阈值的两倍。

1.2 滑动窗口计数器

滑动窗口限流解决固定窗口临界值的问题，可以保证在任意时间窗口内都不会超过阈值。

相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此 对内存的占用会比较多，并且没有解决 一段时间内系统不可用 的问题，仍然存在 突刺现象 不适用需要流量平滑的场景。

规则如下，假设时间窗口为 1 秒：

记录每次请求的时间
统计每次请求的时间至往前推1秒这个时间窗口内请求数，并且 1 秒前的数据可以删除。
统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

滑动窗口

1.3 漏桶

将进来的请求流量视为水滴先放入桶内
水从桶的底部以固定的速率匀速流出，相当于在匀速处理请求
当漏桶内的水满时(超过了限流阈值)则拒绝服务

不管服务调用方多么不稳定，通过漏桶算法进行限流，每 10 毫秒处理一次请求。因为处理的速度是固定的，请求进来的速度是未知的，可能突然进来很多请求，没来得及处理的请求就先放在桶里，既然是个桶，肯定是有容量上限，如果桶满了，那么新进来的请求就丢弃。

实现思路： 用有界队列来保存请求，一个consumer线程每 10 毫秒从队列中获取一个请求，并交给work线程池执行。

这种算法，在使用过后也存在弊端：无法应对短时间的突发流量，同时它的优点也是可以平滑网络上的突发流量，请求可以被整形成稳定的流量。可见 平滑流量 既是优点也是缺点，选择漏桶还是计数器要看具体的应用场景。

1.4 令牌桶

按照一定的速率生产令牌并放入令牌桶中
如果桶中令牌已满，则丢弃令牌
请求过来时先到桶中拿令牌，拿到令牌则放行通过，否则拒绝请求

令牌桶算法是对漏桶算法的一种改进，桶算法能够限制请求调用的速率，而令牌桶算法能够在 限制调用的平均速率的同时还能 应对一定程度的突发调用。

令牌桶

实现思路：用有界队列来保存令牌，通过一个producer线程定期生成令牌放到队列中，请求来时，一个consumer线程去获取令牌，获取到令牌后把请求交给worker线程池去处理。

令牌桶看起来和 Semaphore 很相似，是否可以利用它来实现？不过在Java里 Semaphore 本质是基于AQS的，AQS还是一个队列😔

2.分布限流

2.1 Redis限流

大概思路：每次有相关操作的时候，就向 redis 服务器发送一个 incr 命令，比如需要限制某个用户访问 /index 接口的次数，只需要拼接用户 id 和接口名生成 redis 的 key ，每次该用户访问此接口时，只需要对这个 key 执行 incr 命令，在这个 key 带上过期时间，就可以实现指定时间的访问频率。