秒杀系统设计中不得不说的限流算法

大家好我是小白，最近在牛客热榜中，小马哥持续霸榜，关于怎么设计一个秒杀系统：直达帖子，我也来蹭一蹭小马哥热度。秒杀系统近两年来，后端开发的同学简历中几乎人手一个，但是当面试官深挖秒杀系统的时候，你真的能hold住嘛？今天小白补充一个秒杀系统中的细节——限流算法.

热榜

限流算法是我们秒杀系统中绕不开的一个关键性算法，在高并发的场景下它能有效在入口为我们降低90%以上的流量，有效保护我们的下游系统。我们可能相对熟悉的是漏桶算法和令牌桶算法，这也是我们秒杀系统中常用的两个算法。如果在面试过程中被问到限流算法，有时候如果我们在面试过程中 “不小心” 给面试官侧漏一下这些算法的实习原理，有时候会达到眼前一亮的效果。（难道非要我去学电焊，才能亮瞎面试官）

让人眼前一亮的男人

实际上常用的限流算法有4种：计数器算法、滑动时间窗口限流算法、漏桶算法、令牌桶算法

下面小白带大家深入介绍这四个限流算法老大哥，首先是一哥计数器算法。

计数器算法

一哥头脑简单四肢发达，毫无技巧性统计固定的时间窗口的流量，比如我设置一个一分钟的时间窗口，每次从第0s开始统计，第60s结束统计流量。如果从第0s到第60s中间有累计有超过1w个请求，一哥就给它掐断接下来的请求，第二分钟重新归零统计。显然，这种设计会有一个非常大的漏洞，比如我在第一分钟的第59s突然来了9999个请求，然后在第二分钟的第1s来了9999个请求，然而 “聪明” 的一哥会觉得很正常，它认为你第一分钟的流量，跟我第二分钟有个毛线关系，反正两个时间窗口都没超过1w。但是实际上短短两秒内就有19998个请求进来了，违背了我们的限流原则，存在临界值的问题，有可能导致下游系统崩了。

滑动时间窗口限流算法

二哥滑动时间窗口限流算法看着一哥的限流方式，觉得它应该有什么大病，跟一哥这样的虫豸为伍怎么可能限好流，它汲取了TCP滑动窗口的灵感，设计出时间滑动窗口。经常刷算法题的同学应该还是比较清楚滑动窗口，总结来说，就是维持时间滑动窗口内的请求数<=阈值，当请求数超过阈值的时候，时间窗口后面的所有请求都会抛弃。所谓的滑动时间窗口，当你滑动到最新的时间片段，就会把最前面的时间片段给抛弃，它就像一个固定长度的队列一样，假设长度为一分钟，我们把这一分钟分为60个时间片段，也就是每个时间片段1s，窗口往前滑动一个时间片段，就会抛弃最后面那个时间片段。类似于队头入队一个元素，队尾就要出队一个元素，始终维持这个窗口大小不变。同时在滑动的过程中统计时间片段的请求数。其实我们可以发现，其实我们设置时间片段的大小确实会影响滑动时间窗口算法的精确性，我们时间片段越小，每次向前滑动的步子越小，限流的统计就会越精确。我们微服务体系中的sentinel框架就是基于这种限流算法来实现的，

二哥虽然解决了一哥存在的临界值问题，但是它真的是完美的吗？滑动时间窗口限流算***记录每次合法请求的时刻日志，然后靠当前请求时间与时间窗口大小做一个范围查询数据并求和，来判断是否超过阈值。在较高阈值和小时间片段的情况下，其实通过窗口累积求和的方式是不够高效的，特别是我们处于高并发这种场景下，对效率的要求更高。基于此，我们的三哥和四哥出现了。

漏桶算法

三哥漏桶算法其实非常好理解，所谓的漏桶就是一个底部漏水的桶，我们的请求可以类比成桶里的水，桶的大小是固定的，请求进桶的速度是不固定的，只有漏桶底部放出去的请求速度是固定的

漏桶

额，不好意思是下面这张图：

漏桶算法

从图中可以非常明显看出漏桶算法的实现机制，我们通过控制出水的速度，有效保护下游的接口。比如当我们需要调用一些银行的支付接口，该接口限定调用次数每秒不能超过1w次，此时我们通过漏桶的方式把出水速度控制在1w/s，就能有效从入口端保护接口。当然，银行也会有它们自己的限流方式做到二次保护。看起来我三哥确实能处，有流是真给你限制上了，但是存在这么一种情况，比如在秒杀场景下，大量的请求进来，然而我们漏桶的出水速度确实恒定的，这时候反馈给用户端是大量的请求失败，体验非常差。因此，最后我四哥登场了。

令牌桶算法

四哥它和三哥不同的是，它是以恒定的速度在木桶中加入令牌，木桶满了则不再加入令牌。每个请求过来都尝试从木桶中取出一个令牌，请求拿着令牌去继续执行后续的业务逻辑。没有拿到令牌的请求直接就会被丢弃，不继续执行后续的业务逻辑。上面的秒杀场景中，在秒杀之前我令牌桶有一满桶的令牌等着你用，秒杀时一瞬间大量的请求跑进来，此时我令牌桶中的令牌可以瞬间被取出，立马就可以应付大量的请求并且反馈给用户。之后的请求等我令牌桶慢慢放入令牌才能处理。可以有效处理热点场景的突发流量。