限流算法剖析
type
status
date
slug
summary
tags
category
icon
password
限流是什么？
故宫大家一定都听说过，是我们国家的著名名胜古迹，大家都想去哪里看一看，但是如果全国14亿人民，都想在五月一日劳动节那天去故宫玩一下，那么估计故宫的地砖都会被踩烂，所以故宫为了确保文物和人流的安全所以每天只售卖3万张票供游客购买，这就是平常生活中的限流，限流的意义就是：限制到达系统的并发请求数，使得系统能够正常的处理 部分用户的请求，来保证系统的稳定性。
Wikipedia
在计算机网络中，限流就是控制网络接口发送或接收请求的速率，它可防止DoS攻击和限制Web爬虫。
常见的限流算法
固定窗口限流
- 描述
通过一个计数器 counter 来统计一段时间内请求的数量，并且在指定的时间之后重置计数器。
该方法实现简单，但是有临界问题。例如，允许一分钟内通过的请求数为 N，如果在重置计数器的前后一小段时间内分别请求 N 次，那么在这一小段时间内总共请求了 2N 次，超出了规定的 N 次。
滑动窗口限流
滑动窗口限流解决固定窗口临界值的问题。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。
一张图解释滑动窗口算法，如下：
假设单位时间还是1s，滑动窗口算法把它划分为5个小周期，也就是滑动窗口（单位时间）被划分为5个小格子。每格表示0.2s。每过0.2s，时间窗口就会往右滑动一格。然后呢，每个小周期，都有自己独立的计数器，如果请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。
我们来看下滑动窗口是如何解决临界问题的？
假设我们1s内的限流阀值还是5个请求，0.8~1.0s内（比如0.9s的时候）来了5个请求，落在黄色格子里。时间过了1.0s这个点之后，又来5个请求，落在紫色格子里。如果是固定窗口算法，是不会被限流的，但是滑动窗口的话，每过一个小周期，它会右移一个小格。过了1.0s这个点后，会右移一小格，当前的单位时间段是0.2~1.2s，这个区域的请求已经超过限定的5了，已触发限流啦，实际上，紫色格子的请求都被拒绝啦。
TIPS: 当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
漏桶算法限流
漏桶算法面对限流，就更加的柔性，不存在直接的粗暴拒绝。
它的原理很简单，可以认为就是注水漏水的过程。往漏桶中以任意速率流入水，以固定的速率流出水。当水超过桶的容量时，会被溢出，也就是被丢弃。因为桶容量是不变的，保证了整体的速率。
- 流入的水滴，可以看作是访问系统的请求，这个流入速率是不确定的。
- 桶的容量一般表示系统所能处理的请求数。
- 如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）
- 流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。
在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量
的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求提升用户体验。
令牌桶算法限流
面对突发流量的时候，我们可以使用令牌桶算法限流。
令牌桶算法原理：
- 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。
- 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。
- 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；
- 如果拿不到令牌，就直接拒绝这个请求。
如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。
漏桶算法与令牌桶算法的适用场景
并不能说明令牌桶一定比漏洞好，她们使用场景不一样。**令牌桶可以用来保护自己，主要用来对调用者频率进行限流，为的是让自己不被打垮。**所以如果自己本身有处理能力的时候，如果流量突发（实际消费能力强于配置的流量限制），那么实际处理速率可以超过配置的限制。**而漏桶算法，这是用来保护他人，也就是保护他所调用的系统。**主要场景是，当调用的第三方系统本身没有保护机制，或者有流量限制的时候，我们的调用速度不能超过他的限制，由于我们不能更改第三方系统，所以只有在主调方控制。这个时候，即使流量突发，也必须舍弃。因为消费能力是第三方决定的。
总结起来：如果要让自己的系统不被打垮，用令牌桶。如果保证别人的系统不被打垮，用漏桶算法
Loading...