在上一篇文章中，提到了限流的方式分为单机限流和集群限流，在这篇文章中，就来看一下集群限流如何实现。
对于集群限流，我们一般会考虑以下三方面：
- 分布式：能够进行全局限流，尤其在访问受限制的资源的情况下。比如某个第三方接口只允许每秒100次的访问量，但我们的应用是部署在多台服务器上，在这种情况下，就需要进行全局限流了；
- 滑动窗口：能够避免流量突变(比如洪峰)对系统的影响。比如我们限制了1秒的访问量不能超过100，但很有可能出现一种情况就是前900毫秒没有任何请求，但900毫秒的时候突然来了100个请求；在第2秒的前100毫秒又来了100个请求。这也就意味着在200毫秒的时间涌入了200个请求。这种情况也很有可能把系统打挂掉。
- 最小请求间隔：为了避免请求太频繁，还需要限制调用端的请求时间间隔，如果时间间隔太短，同样也需要限制；
对于分布式的限流，需要使用分布式存储来存放请求的状态数据，在这里，我们使用Redis作为存储引擎。
第一版实现
限流的标准实现一般是使用令牌桶算法，实现思路如下：
- 每个接口都有一个对应的令牌桶，桶中含有若干令牌；
- 当用户发起请求的时候，首先从桶中获取一个令牌。在获取令牌的时候，首先会检查桶中剩余的令牌；
- 如果桶是空的，则表明已经达到上限，请求将被阻塞住；
- 反之，从桶中移除一个令牌，执行用户请求；
- 随着时间推移，按照一定的频率往桶里放入令牌，直到达到容量上限。
这种算法的好处在于占用存储空间小，每个接口只需要一个整形计数器即可，不足之处在于：需要有额外的处理程序往桶里放令牌。如果系统有很多的接口，那也就意味着系统需要有很多的桶，而且每个桶都需要按照固定的速率放入令牌，那么这不仅会增加系统的压力，也会增加系统的复杂性。于是我们可以在此基础上进行优化：
改进实现
- 每个接口有2个对应的key：令牌桶和桶被填充满时的时间戳；
- 当接口被访问的时候，读取对应的时间戳；
- 计算从上次访问到现在该请求可以获取的令牌数量；
- 如果满足要求，请求继续执行。
不幸的是，这个算法也存在缺陷：我们需要同步令牌桶和时间戳的状态，如果同步失败，这种方案将会失效。Redis可以通过批量操作来保证原子操作，但计算用户可以获取多少令牌的时候，我们需要与Redis有两次交互：第一次获取上次访问的时间戳，第二次设置令牌的数量。如果你不想钻研Redis Lua脚本，恐怕我们无法在一个原子操作中实现上述需求。鉴于此，如果有2个客户端在同一时间来校验用户请求的时候，我们可能会得到下面的执行顺序：
- 用户有足够的令牌来执行一个请求；
- 前后请求的间隔内，并没有新的令牌放入桶中；
- 客户端1获得存储的时间戳和令牌数量；
- 客户端2获得存储的时间戳和令牌数量；
- 客户端1通过计算断定令牌足够，放行请求，通知redis清空令牌桶；
- 客户端2通过计算也断定令牌足够，放行请求，通知redis清空令牌桶；
无需多言，上述方案完全失效了，显然这情况并不是我们想要的。
最佳实践
幸运的是，Redis有另外一种数据结构可以避免上述竞态条件-Sorted Set。下面是实现思路：
- 每个接口都有一个对应的Sorted Set，set中key和value是唯一的，key和value都为请求提交时的时间戳；
- 当客户端提交请求时，首先将某个时间间隔前的元素全部清除，这个操作可以使用Redis的ZREMRANGEBYSCORE命令实现；
- 使用ZRANGE(0, -1)命令获取set中剩余的所有元素；
- 使用ZADD命令将当前请求的时间戳添加到set中；
- 设置TTL给set；TTL=限制请求的时间间隔。
进行完上述所有操作后，计算获取到的元素数量，如果超出限制，则拒绝请求；
同时，获取获取的元素中最大的时间戳，与当前请求时间做比较。如果间隔太小，则拒绝请求；
这种方案的好处是所有的redis请求都可以使用MULTI命令作为一个原子操作。这意味着如果两个客户端请求相同的接口，是能够避免前面提到的竞态条件出现的。