限流计算

什么是限流

是指系统在高并发，大量请求的情况下，限制新的流量对系统的访问，从而保证系统服务的安全性。

为什么会限制限流？

常的业务上有类似秒杀活动、双十一大促或者突发新闻等场景，用户的流量突增，后端服务的处理能力是有限的，如果不能处理好突发流量，后端服务很容易就被打垮，导致整个系统崩溃！

亦或是爬虫等不正常流量，我们对外暴露的服务都要以最大恶意去防备我们的调用者。我们不清楚调用者会如何调用我们的服务。假设某个调用者开几十个线程一天二十四小时疯狂调用你的服务，不做啥处理咱服务也算完了。更胜的还有DDos攻击。

限流算法

计数限流算法

最简单的限流算法就是计数限流了，例如系统能同时处理100个请求，保存一个计数器，处理了一个请求，计数器加一，一个请求处理完毕之后计数器减一。

每次请求来的时候看看计数器的值，如果超过阈值要么拒绝。

非常的简单粗暴，计数器的值要是存内存中就算单机限流算法。存中心存储里，例如 Redis 中，集群机器访问就算分布式限流算法。

优点就是：简单粗暴，单机在 Java 中可用 Atomic 等原子类、分布式就 Redis incr。

缺点就是：假设我们允许的阈值是1万，此时计数器的值为0， 当1万个请求在前1秒内一股脑儿的都涌进来，这突发的流量可是顶不住的。缓缓的增加处理和一下子涌入对于程序来说是不一样的。

固定窗口限流算法

首先维护一个计数器，将单位时间段当作一个“窗口”，计数器只记录 这个 “窗口”接受到的请求

• 当次数小于限流阈值，就允许访问，并且计算器+1
• 当次数大于限流阈值，就拒绝访问
• 当“窗口”时间过去之后，计算器清零

假设单位时间是1秒，限流阀值为3。在单位时间1秒内，每来一个请求,计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。等到1s结束后，计数器清0，重新开始计数。

限流1.png

期望的流量 - 实际流量

限流2.png

问题：

1. 一段时间内（不超过时间窗口）系统服务不可用。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第1ms来了100个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。
2. 窗口切换时可能会产生两倍的阈值流量请求假设限流阀值为5个请求，单位时间窗口是1s,如果我们在单位时间内的前0.8-1s和1-1.2s，分别并发5个请求。虽然都没有超过阀值，但是如果算0.8-1.2s,则并发数高达10，已经超过单位时间1s不超过5阀值的定义啦，通过的请求达到了阈值的两倍。
   限流4.png

为了解决这个问题引入了滑动窗口限流

滑动窗口限流

滑动窗口为了限流解决固定窗口临界值的问题，可以保证在任意时间窗口内都不会超过阈值。

限流5.png

相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多。
规则如下，假设时间窗口为 1 秒：

• 记录每次请求的时间
• 统计每次请求的时间 至 往前推1秒这个时间窗口内请求数，并且 1 秒前的数据可以删除。
• 统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

[图片上传失败...(image-f7c9ba-1668061853226)]

从图中不难看出，滑动窗口算法就是固定窗口的升级版。将计时窗口划分成一个小窗口，滑动窗口算法就退化成了固定窗口算法。而滑动窗口算法其实就是对请求数进行了更细粒度的限流，窗口划分的越多，则限流越精准。

问题：

1. 滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。
   们所想的限流场景，例如每秒限制 100 个请求。希望请求每 10ms 来一个，这样我们的流量处理就很平滑，但是真实场景很难控制请求的频率。因此可能存在 5ms 内就打满了阈值的情况。

当然对于这种情况还是有变型处理的，例如设置多条限流规则。不仅限制每秒 100 个请求，再设置每 10ms 不超过 2 个。

漏桶算法

漏桶算法面对限流，就更加的柔性，不存在直接的粗暴拒绝。
它的原理很简单，可以认为就是注水漏水的过程。往漏桶中以任意速率流入水，以固定的速率流出水。当水超过桶的容量时，会被溢出，也就是被丢弃。因为桶容量是不变的，保证了整体的速率。

• 流入的水滴，可以看作是访问系统的请求，这个流入速率是不确定的。
• 桶的容量一般表示系统所能处理的请求数。
• 如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）

• 流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。

  
  限流6.png

看到这想到啥，是不是和消息队列思想有点像，削峰填谷。经过漏洞这么一过滤，请求就能平滑的流出，看起来很像很挺完美的？实际上它的优点也即缺点。

问题：

1. 面对突发请求，服务的处理速度和往常一样的，这其实不是我想要的；我想要可以定制化去改变处理速度。

令牌桶算法能够在一定程度上解决流量突发的问题。

令牌同算法

• 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。
• 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。
• 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；
• 如果拿不到令牌，就直接拒绝这个请求。

限流7.png

可以看出令牌桶在应对突发流量的时候，桶内假如有 100 个令牌，那么这 100 个令牌可以马上被取走，而不像漏桶那样匀速的消费。所以在应对突发流量的时候令牌桶表现的更佳。

限流结论

• 固定窗口算法实现简单，性能高，但是会有临界突发流量问题，瞬时流量最大可以达到阈值的2倍。
• 为了解决临界突发流量，可以将窗口划分为多个更细粒度的单元，每次窗口向右移动一个单元，于是便有了滑动窗口算法。
• 滑动窗口当流量到达阈值时会瞬间掐断流量，所以导致流量不够平滑。
• 想要达到限流的目的，又不会掐断流量，使得流量更加平滑？可以考虑漏桶算法！需要注意的是，漏桶算法通常配置一个FIFO的队列使用以达到允许限流的作用。
• 由于速率固定，即使在某个时刻下游处理能力过剩，也不能得到很好的利用，这是漏桶算法的一个短板。
• 限流和瞬时流量其实并不矛盾，在大多数场景中，短时间突发流量系统是完全可以接受的。令牌桶算法就是不二之选了，令牌桶以固定的速率v产生令牌放入一个固定容量为n的桶中，当请求到达时尝试从桶中获取令牌。
• 当桶满时，允许最大瞬时流量为n；当桶中没有剩余流量时则限流速率最低，为令牌生成的速率v。
• 如何实现更加灵活的多级限流呢？滑动日志限流算法了解一下！这里的日志则是请求的时间戳，通过计算制定时间段内请求总数来实现灵活的限流。
• 当然，由于需要存储时间戳信息，其占用的存储空间要比其他限流算法要大得多。
  不管黑猫白猫，能抓到老鼠的就是好猫。限流算法并没有绝对的好劣之分，如何选择合适的限流算法呢？不妨从性能，是否允许超出阈值，落地成本，流量平滑度，是否允许突发流量以及系统资源大小限制多方面考虑。

当然，市面上也有比较成熟的限流工具和框架。如Google出品的Guava中基于令牌桶实现的限流组件，拿来即用；以及alibaba开源的面向分布式服务架构的流量控制框架Sentinel更会让你爱不释手，它是基于滑动窗口实现的。

具体的实现限流的方式

1）Tomcat 使用 maxThreads 来实现限流。

2）Nginx 的 limit_req_zone 和 burst 来实现速率限流。

3）Nginx 的 limit_conn_zone 和 limit_conn 两个指令控制并发连接的总数。

4）时间窗口算法借助 Redis 的有序集合可以实现。

5）漏桶算法可以使用 Redis-Cell 来实现。

6）令牌算法可以解决Google的guava包来实现。

限流按照规模来分类：

1）单节点限流：限流的方案仅适用于单节点规模，在大规模集群下不适用

2）分布式系统限流：适用于大规模集群限流，当然单节点也支持，例如：redis、zookeeper、Sentinel

需要注意的是借助Redis实现的限流方案可用于分布式系统，而guava实现的限流只能应用于单机环境。

参考资料：

https://blog.csdn.net/budongfengqing/article/details/124437962

https://blog.csdn.net/u013735734/article/details/123494680

https://blog.csdn.net/sshduanzhijun/article/details/115019205