四种常用限流算法掌握一身，面试必过

在高并发访问下，比如电商大促活动，流量持续不断的涌入，服务之间的相互调用频率突然增加，引发系统负载过高，这时系统所依赖的服务的稳定性对系统的影响非常大，而且还有很多不确定因素引起雪崩，如网络连接中断，服务宕机等。一般微服务容错组件提供了限流、隔离、降级、熔断等手段，可以有效保护我们的微服务系统。本文主要说说限流。

限流，就是限制最大流量，防止操作频率超过定义的限制。系统能提供的最大并发有限，同时请求又太多，这就就需要限流，比如秒杀、大促活动业务，瞬时大量请求涌入，服务器服务不过来，就只好限流了。速率限制通过限制在给定时间段内可以到达 API 的请求数量来保护服务免受意外或恶意过度使用。在没有速率限制的情况下，任何用户都可以用请求轰炸您的服务器，从而导致其他用户饿死的情况。

为什么要限速？

• 防止资源匮乏：速率限制的最常见原因是通过避免资源匮乏来提高基于 API 的服务的可用性。如果应用速率限制，则可以防止基于负载的拒绝服务 (doS) 攻击。即使一个用户用大量请求轰炸 API，其他用户也不会挨饿。
• 安全性：速率限制可防止暴力破解登录、促销代码等安全密集型功能。对这些功能的请求数量在用户级别受到限制，因此暴力破解算法在这些场景中不起作用。
• 防止运营成本：在按使用付费模式自动扩展资源的情况下，速率限制通过对资源扩展设置虚拟上限来帮助控制运营成本。如果不采用速率限制，资源可能会不成比例地扩展，从而导致指数级的账单。

速率限制策略速率限制可应用于以下参数：

• 用户：限制在给定时间段内允许用户的请求数。基于用户的速率限制是最常见和最直观的速率限制形式之一。
• 并发性：这里限制了在给定时间范围内用户可以允许的并行会话数。并行连接数量的限制也有助于缓解 DDOS 攻击。
• 位置/ID：这有助于运行基于位置或以人口统计为中心的活动。可以限制不是来自目标人口统计的请求，以提高目标区域的可用性
• 服务器：基于服务器的速率限制是一种利基策略。这通常在特定服务器需要大部分请求时使用，即服务器与特定功能强耦合

接下来，我们将介绍四种常见的限流算法

1、漏桶算法

漏桶算法的思路，是一种简单直观的算法，就是⼀个固定容量的漏桶，按照常量固定速率流出⽔滴。如果桶是空的，则不需流出水滴。可以以任意速率流入水滴到漏桶。如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

这种算法的优点是它可以平滑请求的突发并以恒定的速率处理它们。它也很容易在负载均衡器上实现，并且对每个用户来说都是高效的内存。无论请求的数量如何，都保持到服务器的恒定接近均匀的流量。

缺点是请求的爆发可能会填满存储桶，导致新请求的匮乏。它也不能保证请求在给定的时间内完成。

优点：

• 平滑流量。由于漏桶算法以固定的速率处理请求，可以有效地平滑和整形流量，避免流量的突发和波动（类似于消息队列的削峰填谷的作用）。
• 防止过载。当流入的请求超过桶的容量时，可以直接丢弃请求，防止系统过载。

缺点：

• 无法处理突发流量：由于漏桶的出口速度是固定的，无法处理突发流量。例如，即使在流量较小的时候，也无法以更快的速度处理请求。
• 可能会丢失数据：如果入口流量过大，超过了桶的容量，那么就需要丢弃部分请求。在一些不能接受丢失请求的场景中，这可能是一个问题。

2、令牌桶算法

令牌桶算法：假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌。桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝。当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上。如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。令牌桶限流原理，如图所示。

限流服务器端的令牌桶可以根据实际服务性能和时间段来调整生成令牌的速度和桶的容量。当需要提高速率时，可以按需增加放入桶中的令牌速率

生成令牌的速度是恒定的，而请求获取令牌的速度没有限制。这意味着当面对瞬时大流量时，该算法可以在短时间内获取大量令牌，而且获取令牌的过程并不会消耗很多资源

当每次新的请求到达服务器时，会执行两个操作：

• 获取令牌：获取该用户的当前令牌数。如果它大于定义的限制，则丢弃请求。
• 更新令牌：如果获取的令牌小于持续时间 d 的限制，则接受请求并附加令牌。

该算法具有内存效率，因为我们为我们的应用程序为每个用户节省了更少的数据量。这里的问题是它可能导致分布式环境中的竞争条件。当来自两个不同应用程序服务器的两个请求同时尝试获取令牌时，就会发生这种情况。

优点：

• 可以处理突发流量：令牌桶算法可以处理突发流量。当桶满时，能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用。
• 限制平均速率：在长期运行中，数据的传输率会被限制在预定义的平均速率（即生成令牌的速率）。
• 灵活性：与漏桶算法相比，令牌桶算法提供了更大的灵活性。例如，可以动态地调整生成令牌的速率。

缺点：

• 可能导致过载：如果令牌产生的速度过快，可能会导致大量的突发流量，这可能会使网络或服务过载。
• 需要存储空间：令牌桶需要一定的存储空间来保存令牌，可能会导致内存资源的浪费。
• 实现稍复杂：相比于计数器算法，令牌桶算法的实现稍微复杂一些。

3、固定时间窗⼝算法

在固定的时间窗口内，允许一定数量的请求进入。超过数量则拒绝或排队等待下一个时间段。这种计数器限流的实现方式是在时间间隔内进行限制。如果用户在上一个时间间隔结束前发送请求（但未超过限制），同时在当前时间间隔开始时也发送请求（同样未超过限制），那么在各自的时间间隔内，这些请求都是正常的。然而，当请求在时间间隔的临界时间段内超过系统限制时，可能会导致系统过载

由于计数器算法存在时间临界点缺陷，因此在时间临界点左右的极短时间段内容易遭到攻击。比如设定每分钟最多可以请求100次某个接口，如12:00:00-12:00:59时间段内没有数据请求，而12:00:59-12:01:00时间段内突然并发100次请求，而紧接着跨入下一个计数周期，计数器清零，在12:01:00-12:01:01内又有100次请求。那么也就是说在时间临界点左右可能同时有2倍的阀值进行请求，从而造成后台处理请求过载的情况，导致系统运营能力不足，甚至导致系统崩溃。

缺点：

• 限流不够平滑。例如：限流是每秒3个，在第一毫秒发送了3个请求，达到限流，窗口剩余时间的请求都将会被拒绝，体验不好。
• 无法处理窗口边界问题。因为是在某个时间窗口内进行流量控制，所以可能会出现窗口边界效应，即在时间窗口的边界处可能会有大量的请求被允许通过，从而导致突发流量。

例如：限流是每秒3个，在第一秒的最后一毫秒发送了3个请求，在第二秒的第一毫秒又发送了3个请求。在这两毫米内处理了6个请求，但是并没有触发限流。如果出现突发流量，可能会压垮服务器。

4、滑动时间窗⼝算法

滑动窗⼝算法是把固定时间间进行划分，并且随着时间移动，移动方式为开始时间点变为时间列表中的第二时间点，结束时间点增加一个时间点，不断重复，通过这种方式可以巧妙的避开计数器的临界点的问题。

滑动窗口算法可以有效的规避计数器算法中时间临界点的问题，但是仍然存在时间片段的概念。同时滑动窗口算法计数运算也相对固定时间窗口算法比较耗时。

缺点： 还是存在限流不够平滑的问题。例如：限流是每秒3个，在第一毫秒发送了3个请求，达到限流，剩余窗口时间的请求都将会被拒绝，体验不好。

总结

介绍了四种常用的限流算法：固定窗口算法、滑动窗口算法、漏桶算法和令牌桶算法。每种算法都有其特点和适用场景，下面我们来对它们进行简单的总结和比较。

• 令牌桶算法既能平滑流量，又能处理突发流量，适用于需要处理突发流量的场景。
• 漏桶算法的优点是流量处理更平滑，但是无法应对突发流量，适用于需要平滑流量的场景。
• 固定窗口算法 实现简单，但是限流不够平滑，存在窗口边界问题，适用于需要简单实现限流的场景。
• 滑动窗口算法解决了窗口边界问题，但是还是存在限流不够平滑的问题，适用于需要控制平均请求速率的场景。

以上是四种常用限流算法掌握一身，面试必过的详细内容。更多信息请关注PHP中文网其他相关文章！