高并发系统利器之限流

限流是保护高并发系统的三把利器之一，另外两个是熔断降级和缓存服务。

今天主要讲解限流。有很多场景可以使用限流，比如限购秒杀，保证系统和其它关联系统持续可用。

以下从网上转载：

常用的限流方式和场景有：限制总并发数（比如数据库连接池、线程池）、限制瞬时并发数（如nginx的limit_conn模块，用来限制瞬时并发连接数，Java的Semaphore也可以实现）、限制时间窗口内的平均速率（如Guava的RateLimiter、nginx的limit_req模块，限制每秒的平均速率）；其他还有如限制远程接口调用速率、限制MQ的消费速率。另外还可以根据网络连接数、网络流量、CPU或内存负载等来限流。

=========转载终了=========

一、限流应用解读
①首先从高位看，如果是分布式系统，那就是分布式限流，需要计算出，整个系统最大的容纳流量是多少，其中要参考的诸如，DB、单个程序服务器可承受量以及其它一些边边角角的功能系统可承受量。个人觉得一旦计算出整个系统的可承受量，那么限流处理可以放在网关进行处理（同时网关也可以处理诸如一些鉴权、UV和PV的累加等等）。

② 再次，从中位看，分布式限流已ok，那么我们业务节点服务器是否可以不用做任何限流限制了？正常情况下是不允许的！比如说，你计算好的整个分布式系统最大可承受量为5000/s，但是业务单节点服务器最大可承受为800/s，恰好其它同业务节点，全部宕掉，所有的请求全部转到这个节点上，就会造成了雪崩效应，一样会导致这个节点的服务器宕掉，导致服务彻底不可用。所以说单机限流也是必要的配备。

③ 最后，低位角度，说完系统和业务功能子系统后，再来说下粒度更低的功能节点限流，最为经典的是数据库连接池，通常我们对池子进行配置的时候会设置最大连接数、最小保持连接数，等待超时时间等，这个最大连接数就是限流的体现。首先，数据库的连接数是有上限的，而且创建连接和销毁连接的代价很大，如果不能较好的设置数据库的连接数和连接池的最大连接数，会导致DB不可用！

将我理解的限流分为，高位系统级限流、中位子业务节点限流和业务功能节点限流，算法理念都是一样的，但是面对的场景不一样。

四种常见的限流算法：
1、计数器算法。简单、粗暴、直接，比如限制一秒钟的请求数量为10，来一个请求就给对应的数值加1，达到10以后就等待或者拒绝处理，等到一秒结束后，清零，重复之前的逻辑，实现思路是：
①利用Java的AtomicLong原子类的incrementAndGet，第一次的时间和当前时间比对，一秒内则加1并判断，超过1秒则清零。
②利用Redis的incr命令，将key的过期时间设置为一秒，取出的时候进行判断，如果不存在则加一，存在加一并判断是否超过阀值。

计数器.jpg

这种算法可以应对单位时间内的突发流量，但是无法将请求进行匀速操作。题外话，此思路可以用作登陆防止暴力破解密码。
但是此算法有个致命的问题，即时间临界问题。

计数器算法漏洞.jpeg

2、滑动窗口。简单点说，每个小格就是我们自己划分的单位时间内请求次数，小格单位时间越小，统计就越精确，查找时，按照当前时间，向前推进1分钟的范围内，所有请求次数。这种算法有效解决了，计数器算法的的漏洞。

滑动窗口.jpeg

3、漏桶算法。为了实现匀速操作，漏桶算法呼之欲出，将请求比喻为水滴，一个底部有小口的漏桶，漏桶容量为我们设置的阀值，请求来时，相当于向水桶里倾倒了一个水滴，而漏桶底部有一个小口，水匀速的从小口流出，流出的速率不受请求多少的影响，
无论调用方是突发瞬流还是稳流，漏桶的流出的速率不受任何影响，如果水桶已达容量上线（超过用户规定的阀值），可以选择等待水桶有空余空间，或者直接拒绝此次请求。
实现思路，类似基于Redis的的消息队列，一个队列A存储请求，队列的大小是用户规定的阀值，同时存在一个线程，定期从该队列取出一个或者多个（取决于用户的流出策略）请求进行处理。
这种算法可以使请求以匀速的方式进行处理，但是无法应对突发流量。

漏桶.png

4、令牌桶算法。二者优点的结合体赛亚人二代，计数器算法可以应对突发流量，但是无法确保匀速，漏桶算法可以确保匀速操作，但是无法应对突发流量。令牌桶算法，能够在限制调用的平均速率的同时还允许一定程度的突发调用。
算法中，存在一个储存令牌的桶，令牌桶盛放令牌的数量就是用户设定的阀值，然后以一定的速率向桶中放入n块令牌（假如用户设定10秒只能处理100次请求，那么算法会在10秒内向令牌桶中存入100块令牌），当桶中令牌数量达到阀值，就丢弃令牌。
请求来了之后，每个请求首先会在令牌桶中拿取一块令牌，然后进行逻辑处理，如果当前桶中没有令牌，要么等待，要么拒绝请求。

令牌桶.png