程序员必学的十个算法：10年程序员谈谈限流算法的几种实现
程序员必学的十个算法：10年程序员谈谈限流算法的几种实现这种情况时有发生，解决方案有两种：一个服务A的接口可能被BCDE多个服务进行调用，在B服务发生突发流量时，直接把A服务给调用挂了，导致A服务对CDE也无法提供服务。比如web服务、对外API，这种类型的服务有以下几种可能导致机器被拖垮：这些情况都是无法预知的，不知道什么时候会有10倍甚至20倍的流量打进来，如果真碰上这种情况，扩容是根本来不及的（弹性扩容都是虚谈，一秒钟你给我扩一下试试）2、对内的RPC服务
保障服务稳定的三大利器：熔断降级、服务限流和故障模拟。
今天和大家谈谈限流算法的几种实现方式，本文所说的限流并非是Nginx层面的限流，而是业务代码中的逻辑限流。
为什么需要限流按照服务的调用方，可以分为以下几种类型服务
1、与用户打交道的服务
比如web服务、对外API，这种类型的服务有以下几种可能导致机器被拖垮：
- 用户增长过快（这是好事）
- 因为某个热点事件（微博热搜）
- 竞争对象爬虫
- 恶意的刷单
这些情况都是无法预知的，不知道什么时候会有10倍甚至20倍的流量打进来，如果真碰上这种情况，扩容是根本来不及的（弹性扩容都是虚谈，一秒钟你给我扩一下试试）
2、对内的RPC服务
一个服务A的接口可能被BCDE多个服务进行调用，在B服务发生突发流量时，直接把A服务给调用挂了，导致A服务对CDE也无法提供服务。
这种情况时有发生，解决方案有两种：
1、每个调用方采用线程池进行资源隔离
2、使用限流手段对每个调用方进行限流
限流算法实现常见的限流算法有：计数器、令牌桶、漏桶。
在算法实现方面，可以准备一个队列，用来保存请求，另外通过一个线程池（ScheduledExecutorService）来定期从队列中获取请求并执行，可以一次性获取多个并发执行。
这种算法，在使用过后也存在弊端：无法应对短时间的突发流量。
3、令牌桶算法
从某种意义上讲，令牌桶算法是对漏桶算法的一种改进，桶算法能够限制请求调用的速率，而令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用。
在令牌桶算法中，存在一个桶，用来存放固定数量的令牌。算法中存在一种机制，以一定的速率往桶中放令牌。每次请求调用需要先获取令牌，只有拿到令牌，才有机会继续执行，否则选择选择等待可用的令牌、或者直接拒绝。
放令牌这个动作是持续不断的进行，如果桶中令牌数达到上限，就丢弃令牌，所以就存在这种情况，桶中一直有大量的可用令牌，这时进来的请求就可以直接拿到令牌执行，比如设置qps为100，那么限流器初始化完成一秒后，桶中就已经有100个令牌了，这时服务还没完全启动好，等启动完成对外提供服务时，该限流器可以抵挡瞬时的100个请求。所以，只有桶中没有令牌时，请求才会进行等待，最后相当于以一定的速率执行。
实现思路：可以准备一个队列，用来保存令牌，另外通过一个线程池定期生成令牌放到队列中，每来一个请求，就从队列中获取一个令牌，并继续执行。
通过Google开源的guava包，我们可以很轻松的创建一个令牌桶算法的限流器。
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>18.0</version> </dependency>
通过RateLimiter类的create方法，创建限流器。
public class RateLimiterMain { public static void main(String[] args) { RateLimiter rateLimiter = RateLimiter.create(10); for (int i = 0; i < 10; i ) { new Thread(new Runnable() { @Override public void run() { rateLimiter.acquire() System.out.println("pass"); } }).start(); } } }
其实Guava提供了多种create方法，方便创建适合各种需求的限流器。在上述例子中，创建了一个每秒生成10个令牌的限流器，即100ms生成一个，并最多保存10个令牌，多余的会被丢弃。
rateLimiter提供了acquire()和tryAcquire()接口
1、使用acquire()方法，如果没有可用令牌，会一直阻塞直到有足够的令牌。
2、使用tryAcquire()方法，如果没有可用令牌，就直接返回false。
3、使用tryAcquire()带超时时间的方法，如果没有可用令牌，就会判断在超时时间内是否可以等到令牌，如果不能，就返回false，如果可以，就阻塞等待。
集群限流前面讨论的几种算法都属于单机限流的范畴，但是业务需求五花八门，简单的单机限流，根本无法满足他们。
比如为了限制某个资源被每个用户或者商户的访问次数，5s只能访问2次，或者一天只能调用1000次，这种需求，单机限流是无法实现的，这时就需要通过集群限流进行实现。
如何实现？
为了控制访问次数，肯定需要一个计数器，而且这个计数器只能保存在第三方服务，比如redis。
大概思路：每次有相关操作的时候，就向redis服务器发送一个incr命令，比如需要限制某个用户访问/index接口的次数，只需要拼接用户id和接口名生成redis的key，每次该用户访问此接口时，只需要对这个key执行incr命令，在这个key带上过期时间，就可以实现指定时间的访问频率。
