常见限流算法

简介

限流顾名思义是对流量大小进行限制，防止请求数量超过系统的负载能力，导致系统崩溃，起到保护作用。
现实生活中限流也随处可见，节假日出门旅行的人数会剧增，对于旅游景点来说往往会不堪重负，如果不进行人数控制，对整个景点的压力会非常大，游客的体验也会非常差，还容易出现安全事故等危险。
同样的在一线城市地铁限流也非常常见，早高峰为了控制乘车人数和有序进站，地铁往往会在地铁口进行拦截，一定时间内才放行一部分人进站乘车。

具体到程序，限流可以有以下几种场景

• 限制某个接口每秒最多访问多少次
• 限制某个ip每秒最多访问多少次
• 限制某个用户或某个来源每秒最多访问多少次
• 限制某些用户下载速度每秒最多多少kb
• 禁止某些用户或ip的访问

限流起到了保护作用，那么如何限呢？如果限制得太严，保护是保护到了，但是系统的处理能力下降了，体验会很差；如果限制得太松，就会被一些突增流量冲击到，或者被黑客利用进行安全攻击。如何限流需要根据系统的负载来评估，系统的负载和处理能力是动态的，例如平时的qps是1000，双11一般会进行扩容，也就是加服务节点，qps可能就是5000，这个时候系统处理能力变强的，限流策略也应该相应的调整。还有一种是出于安全的限流，例如同一个客户端ip 1s内对系统发出上万次请求，这种可以确定就是安全攻击，很可能是有人恶意破坏，或者是一些爬虫，这种可以限制请求数，超出的就直接拒绝。
如何限流是限流算法要实现的，常见的限流算法有“两桶两窗”，固定窗口、滑动窗口、漏桶与令牌桶，接下来介绍这四种算法及应用。

固定窗口

固定窗口的思想和实现非常简单，就是统计每个固定每个时间窗口的请求数，超过则拒绝。

如图我们定义了窗口大小为1s，最大请求数100，窗口内超过100的请求数将被拒绝。实现上也非常简单，利用redis的incr自增计数，当前时间秒作为缓存key，每次自增后判断是否超过指定大小即可。
固定窗口的问题是容易出现“突刺现象”，例如在1s内，100个请求都是在前100ms过来的，那么后面的900ms的请求都会被拒绝，而系统此时是空闲的。另外还有“临界问题”，如果100个请求是在后100ms过来的，而下一个1s的100个请求在前100ms过来，此时系统在这200ms内就需要处理200个请求，跟我们想要的不符合。到这里我们很容易想到，1s这个范围太大了，缩小一些就更好了，这种把固定窗口拆成更多个小窗口的做法就是滑动窗口算法了。

滑动窗口

滑动窗口的思想是将固定窗口拆成更多个小窗口，随着时间的推移，窗口不断的滑动，统计也在不断的变化。窗口拆分的越多，滑动就会越平滑，统计就会越精确，所消耗的资源就会越多。滑动窗口如果只拆为1个窗口，就退化为固定窗口。
滑动窗口算法可以解决上面固定窗口的问题，像hystrix和sentinel中都使用该算法进行数据统计，用于限流熔断等策略处理。如hystrix中图所示，在一个窗口内拆分了10个桶（bucket），随着时间的推移，会创建新的桶也会丢弃过期的桶，当然窗口的大小和拆分桶的数量都是可配置的。

漏桶

漏桶算法的思想是将请求先放到一个桶中，然后像滴水一样不断的从中取出请求执行，桶满则溢，后面的请求会被拒绝。

漏桶算法的特点是流入速度不确定，但是流出速度是确定的，漏桶可以很平滑，均衡的处理请求，但是无法应对短暂的突发流量。

令牌桶

令牌桶算法的思想是不断的生成令牌放到一个桶中，请求到来时到桶中申请令牌，申请得到就执行，申请不到就拒绝。如果桶中的令牌满了，新生成的令牌也会丢弃。

与漏桶不同的是，令牌桶是流入速度确定(生成令牌的速度)，流出速度不确定，所以它不想漏桶一样可以均衡的处理请求，但是由于有令牌桶这个缓冲，一旦有突增的流量，令牌桶里已有的令牌可以短暂的应对突发流量，由于流出速度是不限制的，此时桶中已有的令牌都可以被申请到，请求一下子就会到我们的服务，给系统带来一定的压力，所以桶的大小需要合适，不宜过大。举个栗子：令牌桶的大小是1000，每秒放100个令牌，经过一段时间后，请求有空闲时，桶里的令牌就会积压，最终保存了满1000个令牌，由于某刻流量突增，有1000个请求到来，此时能申请到1000个令牌，所有请求都会放行，最终达到我们的系统，如果令牌桶过大，系统可能会承受不了这波请求。

应用

guava RateLimiter

guava限流实现的是桶算法，通过RateLimiter.create创建，可以创建两种类型的限流器，SmoothBursty和SmoothWarmingUp，前者定时生成令牌，后者有一个预热的过程。
我们如下示例代码，每秒会创建2个令牌，并且初始化的时候就是2。定时器每200ms会申请一次令牌，每秒申请5次，只有2次成功，所有运行程序每秒有3次success和2次fail。

        RateLimiter rateLimiter = RateLimiter.create(2);
		new Timer().schedule(new TimerTask() {
			@Override
			public void run() {
				if (rateLimiter.tryAcquire()) {
					System.out.println("success");
				} else {
					System.out.println("fail");
				}
			}
		}, 0, 200);

既然是桶，那么桶的大小是多少呢？SmoothBursty里最大令牌数由maxPermits字段表示，该字段等于maxBurstSeconds * permitsPerSecond，permitsPerSecond是每秒要生成的令牌数，maxBurstSeconds默认是1。
另外还可以创建SmoothWarmingUp带有预热功能的限流器，预热的作用是通过一个过程才达到permitsPerSecond，相当于让系统有个热身的时间。

		RateLimiter rateLimiter = RateLimiter.create(5, 10, TimeUnit.MILLISECONDS);
		new Timer().schedule(new TimerTask() {
			@Override
			public void run() {
				log.info("" + rateLimiter.acquire());			
			}
		}, 0, 200);

rateLimiter.acquire()返回的是获取打令牌的时间，运行程序可以看到开始并不是每秒都能产生5个令牌，也就是不是能立刻获取到令牌，获取令牌需要的时间会越来越小，直到预热期过后就能立马获取到令牌了。
guava的限流只能提供单机版的实现，对于集群就无能为力了，并且它通常作为一个工具存在，使用还需要自己封装，集成到服务，并不能开箱即用。

bucket4j

bucket4j是一个java实现，基于令牌桶算法的限流组件。它支持分布式限流，支持多种存储，可以方便与各种框架和监控集成。github上start 1.2K，但是issues数量少，国内估计使用的人也不多，并且官方的实现存储不支持最常用的redis，它专注于限流，如果是自研或者二次开发，是一个很好的参考。

Resilience4j

之前我们介绍过它的熔断功能，Resilience4j也提供了限流的实现，可以参考这里。相比guava，Resilience4j是框架级别的，可以很方便的使用。但Resilience4j也是单机版的实现，无法支持集群功能。
Resilience4j限流实现的是令牌桶，如下配置，每1s会生成10个令牌。

resilience4j.ratelimiter:
    instances:
        backendA:
            limitForPeriod: 10
            limitRefreshPeriod: 1s
            timeoutDuration: 0
            registerHealthIndicator: true
            eventConsumerBufferSize: 100

sentinel

流量控制是sentinel最重要的一个功能，sentinel属于后起之秀，文档齐全，支持的场景更加丰富。sentinel支持集群限流，也可以像guava一样预热，还可以基于调用链路进行限流。
sentinel还提供了控制台功能，支持多种数据源的持久化，使用spring cloud的话可以通过spring cloud alibaba引入sentinel。
开源版的sentinel有一些限制，并且使用起来并不是那么方便，例如Resilience4j可以配置一个default针对所有的请求生效，但sentinel需要单个单个url去配置，显得非常麻烦，包括熔断feign接口的配置也是，这个给spring cloud alibaba提了feature，也许在下一个版本就会提供支持。

nginx

上面讲到的都是应用级别的限流，nginx通常作为网络请求的入口，从运维的角度来说，在这里做限流再合适不过，nginx本身也提供了限流的支持。
nginx比较适合对外的限流，但是我们内部不同系统间的调用一遍不经过nginx，会直接访问到对方的网关，所以两者并不矛盾。
nginx限流通过limit_req和limit_conn两个模块支持，分别对应请求限制和链接限制（一个链接可以有多个请求）。

http {  
    limit_req_zone zone=name:10m rate=100r/s;  
    server {  
        location /app/ {
            limit_req zone=name burst=500 nodelay;
        }
}

如上，定义了一个name zone，访问速率最高是100个每秒，/app路径应用了这个规则。busrt表示爆发的意思，是一个缓冲队列，用于存储突增的请求，这些请求会被缓存不会拒绝，如果超过了burst，nodelay表示不等待直接拒绝。
前面我们说到有些恶意攻击可能每秒发送上万个请求，导致服务崩溃，如果多个应用系统共用一个nginx，那么可以统一在nginx配置处理，不需要每个系统自己去实现。

limit_conn_zone $binary_remote_addr zone=name:10m;

server {    
    limit_conn name 50;    
}

如上，定义了一个name zone，$binary_remote_addr表示远端地址，也就是ip，10m表示存储空间，10m大概可以存储16w的ip地址，我们在server节点应用这个规则，50表示最多50个，超过就会拒绝。