一篇文章弄懂限流怎么做

限流是保护高并发系统的三把利器（限流、缓存、降级）之一。限流在很多场景中用来限制并发和请求量，保护自身系统和下游系统不被巨型流量冲垮。比如秒杀业务或者一些访问量很高的基础性服务都会用到限流的技术。

几种常见的限流算法

1、计数器算法

计数器算法是限流算法里最简单也是最容易实现的一种算法。假设我们限制一分钟的能够通过的请求数为100，算法的实现思路就是从第一个请求进来开始计时，在接下去的1分钟内，每来一个请求，就把计数加1，如果累加的数字达到了100，那么后续的请求就会被全部拒绝。等到1分钟结束后，把计数恢复成0，重新开始计数。

贴一个之前IM项目中，控制每个tcp连接消息速率的限速器，基于计数器算法实现。

这个方法简单、有效，还能很好适应移动端瞬时流量的情况（因为网络原因，手机端在连上网络后可能瞬时发送多条消息到服务端）。

然而这个方法有一个十分致命伤，那就是临界问题，看下图

假设有一个恶意用户，在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮后端应用。滑动窗口可以解决这个问题

2、滑动窗口

滑动窗口，又称rolling window。如果学过TCP网络协议，一定对滑动窗口这个名词不会陌生。下图很好地解释了滑动窗口算法

在上图中，整个红色的矩形框表示一个时间窗口，在这个例子中，一个时间窗口就是一分钟。我们将滑动窗口划成6格，每格代表10秒钟。每过10秒钟，时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如一个请求在0:35秒时到达，那么0:30~0:39对应的counter就会加1。

滑动窗口怎么解决刚才的临界问题的呢？我们可以看上图，0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘黄色的格子中。当时间到达1:00时，窗口会往右移动一格，此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触发了限流。

回顾一下刚才的计数器算法，其实就是滑动窗口。只是它没有对时间窗口做进一步地划分，只有1格。

由此可见，滑动窗口格子划分越多，窗口滚动就越平滑，限流统计就会越精确。

3、漏桶算法

漏桶算法（Leaky Bucket），主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。

算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水（接口有响应速率），当水流入速度过大会直接溢出（访问频率超过接口响应速率），然后就拒绝请求，可以看出漏桶算法能强行限制数据的传输速率。

漏桶算法的实现往往依赖于队列，请求到达如果队列未满则直接放入队列，有一个处理器按照固定频率从队列头取出请求进行处理。如果请求量大，则会导致队列满，那么新来的请求就会被抛弃。

用MQ来做流量削峰，就是这个算法的一种实践！

4、令牌桶算法

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

令牌桶算法则是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。桶中存放的令牌数有最大上限，超出之后就被丢弃或者拒绝。当流量或者网络请求到达时，每个请求都要获取一个令牌，如果能够获取到，则直接处理，并且令牌桶删除一个令牌。如果获取不同，该请求就要被限流，要么直接丢弃，要么在缓冲区等待。

Guava的RateLimiter提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。

Guava是Java领域优秀的开源项目，它包含了Google在Java项目中使用一些核心库，包含集合(Collections)，缓存(Caching)，并发编程库(Concurrency)，常用注解(Common annotations)，String操作，I/O操作方面的众多非常实用的函数。

截一段RateLimiter加了注释的源代码

这4个算法涵盖了目前主要的限流思想。本文提供的实现基本都是单机环境，那么分布式环境下限流怎么做呢？