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

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