业务系统常用限流算法浅析

Part 01

什么是限流？ 

业务系统限流是指系统在面临高并发或者大流量请求的情况下，限制新的请求对系统的访问，从而保证系统的稳定性和安全性。

Part 02

为什么要限流？  

系统资源和处理能力都是有限的，如果一个系统不限制流量，比如在秒杀活动、大促销等场景下，瞬时间大量的流量访问将超出系统的负载，最终会导致服务异常、机器宕机。

Part 03

常用的限流算法 

常用的限流算法有固定窗口算法、滑动窗口算法、漏桶算法和令牌桶算法，下面将对这几种算法分别进行介绍，这也是所有限流框架实现限流的基础。

Part 04

固定窗口算法 

固定窗口限流算法是最基础的一种限流算法。原理是将一段固定时间当做一个窗口，通过计数器记录这个窗口接收到的请求次数。当请求次数大于限流阈值，就拒绝访问；反之就允许访问，并将计数器加1。当时间窗口结束后将计数器重置为0。

该算法易于理解，实现也简单。但是缺点也很明显，会产生突刺现象和临界问题：

• 突刺现象是指窗口一段时间内服务不可用，导致流程曲线不够平滑。假如窗口大小为1分钟，限流阈值为10，然后窗口的第1秒恰好进来10个请求，导致以后59秒的请求都被拒绝。
• 临界问题是指窗口切换时产生两倍阈值流量的请求。假如窗口大小还是1分钟，限流阈值还是10，然后第一个窗口前期没有请求，恰好在第59秒进来10个请求，此时这10个请求都会放行。下一个窗口的第1秒恰好又来了10个请求，也全部放行了，相当于2秒之内通过了20个请求，而系统设定的阈值是10。恶意用户有可能通过算法的这个漏洞，在时间窗口的重置节点处突发请求，瞬间压垮业务系统。

Part 05

滑动窗口算法 

为了解决固定窗口算法中的临界问题，让流量限制更加平滑，产生了滑动窗口算法。该算法将固定窗口中分割出多个小窗口，分别记录每个小窗口内的访问次数，然后根据时间将窗口往前滑动并删除过期的小窗口。

假设窗口时间还是1分钟，滑动窗口算法把它划分为6个小周期，每个小周期是10秒，对应滑动窗口被划分为6个小格子。每隔10秒时间窗口就会往右滑动一格，每个小窗口都有独立的计数器，如果请求是43秒到达的，40秒到50秒小窗口对应的计数器就会加1。

我们看下滑动窗口是如何解决临界问题的，假设1分钟内的限流阀值还是10，50秒到60秒内（比如58秒的时候）来了10个请求，落在绿色格子里。时间过了60秒这个点之后又来10个请求，落在红色格子里。滑动窗口过了60秒这个点后会右移一个小格，当前的窗口时间段是10秒到70秒，这个区域的请求已经超过限定的10了，所以红色格子的请求都会被拒绝。

滑动窗口算法虽然解决了临界问题，但是一旦到达限流阈值后，请求都会被直接拒绝。在实际应用中我们要的限流效果不是把流量一下子掐断，而是让流量平滑地进入系统当中。

Part 06

漏桶算法 

如何更加平滑的限流，我们来看看漏桶算法。漏桶算法的限流原理可以认为就是进水漏水的过程。请求像水一样以任意速率注入漏桶，而漏桶会按照固定的速率将水漏掉；当进水速度超过漏水速度时，漏桶会装满，此后进入的水会溢出，也就是请求被丢弃。

漏桶算法主要目的是将网络中的突发流量整合成平滑稳定的流量，不过由于漏桶对流量的控制过于严格，导致部分场景下不能充分利用系统资源。因为漏桶的漏水速率是固定的，即使在某一时刻下游系统处理能力富余，漏桶也不会允许突发流量通过。流量突发时我们希望系统在稳定的同时，能尽可能快的处理用户请求，接下来介绍的令牌桶算法能够在一定程度上解决流量突发的问题。

Part 07

令牌桶算法 

令牌桶算法是对漏桶算法的一种改进，除了能够限流外，还允许一定程度的流量突发。其原理是设置一个令牌桶，以恒定速率向令牌桶放入令牌，请求到达时尝试从令牌桶中拿令牌，只有拿到令牌才能够放行，否则请求将会被拒绝。

令牌桶具有以下特点：

• 根据限流大小定速往令牌桶里放令牌。
• 如果令牌数量超过令牌桶容量的限制就丢弃令牌。
• 每一个请求首先去令牌桶拿令牌，拿到令牌就处理请求，拿不到令牌就直接拒绝。

Part 08

 小结  

最后我们对上述四种限流算法进行一下简单的总结。

固定窗口算法实现简单，但是流量曲线不够平滑有突刺现象，在窗口切换时可能会产生两倍阈值流量的临界问题。滑动窗口算法作为固定窗口算法的一种改进，有效解决了窗口切换时的临界问题。阿里开源的流量控制框架Sentinel就是基于滑动窗口实现的。

漏桶算法能够对流量起到平滑整流的作用，让随机不确定的流量以固定的速率流出，但是不能解决流量突发问题。令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。