限流算法
2019-09-18 本文已影响0人
康俊1024
前言
保障服务稳定的三大利器：熔断降级、服务限流和故障模拟。限流包括Nginx层面的限流以及业务代码逻辑上的限流。
为什么需要限流
以服务的调用方来看，可以分为两种类型服务
- 对外提供的服务（web服务）
这类服务有以下几种可能导致机器被拖垮：
1.用户增长过快
2.热点事件
3.爬虫
4.刷单 - 对内提供的服务（微服务之间调用）
一个服务A的接口假如被BCDE等多个服务进行调用，如果B服务发生突发流量，就会直接把A服务调用挂了，会导致CDE无法正常使用。
解决方案：
1.每个调用方采用线程池进行资源隔离（避免资源被耗尽无法分配资源）
2.使用限流手段对每个调用方进行限流
限流算法
常见的限流算法有：计数器、令牌桶、漏桶。
- 计数器算法
计数器算法是限流算法里最简单也是最容易实现的一种算法。
需求：假设规定，对于A接口，我们1分钟的访问次数不能超过100个。
实现方案：我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，可以使用AtomicLong#incrementAndGet()实现。
问题：这个算法很简单，但是有一个十分致命的问题，那就是临界问题，还有会出现突刺现象拒绝大部分请求。
分析：假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。
解决方案：滑动窗口，将时间窗口进行多段划分，当时间到达1:00时，我们的窗口会往右移动一格，每一个格子都有自己独立的计数器counter，此时分析时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触发限流。 - 漏桶算法
漏桶算法实现限流可以解决突刺现象，当请求进来时，相当于水倒入漏斗，然后从下端小口慢慢匀速的流出。不管上面流量多大，下面流出的速度始终保持不变。如果桶满了，那么新进来的请求就丢弃。
算法实现可以准备一个队列，用来保存请求，另外通过一个线程池（ScheduledExecutorService）来定期从队列中获取请求并执行，可以一次性获取多个并发执行。
弊端无法应对短时间的突发流量。 - 令牌桶算法
从某种意义上讲，令牌桶算法是对漏桶算法的一种改进， 漏桶算法能够限制请求调用的速率，而令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用。
算法实现思路令牌桶算法，存在一个桶，用来存放固定数量的令牌。算法中存在一种机制，以一定的速率往桶中放令牌。每次请求调用需要先获取令牌，只有拿到令牌，才有机会继续执行，否则选择选择等待可用的令牌、或者直接拒绝。
算法实现过程放令牌这个动作是持续不断的进行，如果桶中令牌数达到上限，就丢弃令牌，所以就存在这种情况，桶中一直有大量的可用令牌，这时进来的请求就可以直接拿到令牌执行，比如设置qps为100，那么限流器初始化完成一秒后，桶中就已经有100个令牌了，等启动完成对外提供服务时，该限流器可以抵挡瞬时的100个请求。所以，只有桶中没有令牌时，请求才会进行等待，最后相当于以一定的速率执行。
算法实现可以准备一个队列，用来保存令牌，另外通过一个线程池定期生成令牌放到队列中，每来一个请求，就从队列中获取一个令牌，并继续执行。
开源实现Google开源的guava包
集群限流
通过外部计算器比如Redis，比如需要限制某个用户访问/query接口的次数，只需要拼接用户id和接口名生成redis的key，每次该用户访问此接口时，只需要对这个key执行incr命令，在这个key带上过期时间，就可以实现指定时间的访问频率。
