有驾分布式网关限流能力的落地实践
一、为什么要做限流
夏天的时候大家都会打开空调降温来抵抗酷热，此时整个地区的用电量会激增，此时国家电网会针对部分用电高峰期进行限电，那限制的目的是什么呢？近几年基建比较完善限电已经不常见了。假设没有进行限电那么如果用电量超过了负载，会不会导致整个电网瘫痪呢？答案是有可能的，可见限电是为了保护电网的安全稳定而做的一部分取舍。
那如果一个微服务矩阵的某个服务流量激增而对应服务的资源无法增加，如何保证整个微服务的稳定以及整个矩阵的安全稳定呢？毫无疑问限流是一个最强力有效的手段之一。比如限流的时候对于超过的流量采用的是丢弃还是暂时缓存的方式都会导致业务上一定的损失，但是总比整个服务不可用并且可能会雪崩其他业务要好一些。
二、有驾系统架构
当前有驾内部，使用的是中心式的网关，通过分布式的多实例部署方式承载有驾所有流量。网关提供了多个能力来保证整个有驾的业务稳定和安全，如：同步/异步转发，鉴权，openapi、限流、缓存、降级等等，本文主要介绍网关的限流功能。网关的流量转发如图，当然只是说明了最简单的两个场景，每一个服务可能会通过网关调用其他的多个服务，链路可能也会更复杂更长一些。
假设你是一个公司的CTO，招了几个菜鸟程序员，然后买了一台服务器花了几万块钱，在服务器上部署了一个服务，此时用户比较少但是都是你的核心用户，此时为了避免有人攻击你把自己的服务打挂了，你给你的核心用户加了白名单，又通过漏水桶/令牌桶/固定窗口/滑动窗口等限制了非白名单用户流量。
一切都很顺利，服务稳定，你的业务开始慢慢增长，此时单台服务器已经不太够用了，你又购置了五六台服务器，打算在每个服务器上都部署服务，此时你需要一个流量控制的工具，你发现用nginx做分服务(路径)转发，也可以实现负载均衡限流，满足业务发展的需要，顺风顺水的又发展了一年，你的日均流量逐渐从百万增长到千万、亿级别，技术架构也慢慢演进到微服务架构。
不巧的是某次断电事故导致服务器机房断电，业务受到了严重的影响，于是你开始考虑更健壮的分布式多地域多机房部署，打算北京一个机房，上海一个机房，陕西一个机房，深圳一个机房，你的服务之间的调用关系也逐渐复杂，复杂度也开始直线上升。你发现定位线上问题以及线上止损开始变得越来越困难，开始考虑全链路追踪和限流熔断。
此时你就需要解决中心式网关、分布式的多实例部署方式的一系列问题，有驾业务网关的限流就是建立在类似的业务背景之下。
三、常见限流方案调研
首先我们对业内已有的限流算法进行一个介绍，简单的分析一下各个限流算法的限流实现逻辑、其适用的场景及其局限性。
3.1、固定窗口
固定窗口的逻辑很简单，假设一个窗口大小为1秒，容量为2，那么超过2的就丢弃，当时也会有其他的问题。如图前两秒服务器的负载来说是可以处理四个请求，可能会第一秒的第三个请求会处理的时间比较长一些，但是第一秒的一个请求被丢弃了，导致业务上有损耗，可见固定窗口足够简单但也具有一定的局限性，只关注当前的时间窗口，那是否可以灵活一些呢？
3.2、滑动窗口
窗口大小为3，每个格子为1秒，最大接收的请求是5：
第一个窗口，第三秒过来四个请求，
1 + 3 + 4 > 5，所以第三秒的三个请求被丢弃，此时处理的请求为1、3、1；第二个窗口：第一秒已经过期了，第四秒过来了两个请求，但是此时窗口内未过期的请求为四个，所以第四秒只能处理一个请求，另一个请求将会被丢弃；
第三个窗口：第二秒的三个请求过期，此时窗口可以多处理三个请求，但是第五秒只过来了两个请求，所以完全可以都处理；
第四个窗口：第三秒过来的四个请求只处理了一个，所以此时第六秒过来的两个请求都可以处理；
大家以此类推：第七秒，第八秒的请求是否可以被处理，答案是可以的，大家可以自己推演一下。
最后可以算出来总请求数：16个，响应的请求：12个，丢弃的请求数：4个，窗口内最大的峰值：5。可以看到滑动窗口的处理更加的灵活一些，允许局部的出现峰值，但是通过滑动窗口可以保证一段时间内是稳定的，相对固定窗口并且可以处理更多的请求，起到了一定的削峰填谷的作用。
3.3、漏水桶
假设桶容量为 3，每秒流出的速率为 3/秒，假设：1/3、2/3、3/3处理请求，有如下请求过来：1、2、4、2、2、2、1、1
第一秒：立即进入一个请求，则可以完全处理；
第二秒：立即进入两个请求，也是可以处理的；
第三秒：四个请求
如果在第三秒的时候
1/3秒前进入四个请求，那么桶还未来得及流出(处理)，1 + 3 = 4 > 3那么第四个请求就会被丢弃掉；如果第一个请求在
1/3秒前进入，并且第四个请求在的1/3秒后进入，那么第一个请求已经被处理了，此时桶内的请求数应该是1 + 2 = 3 ≤ 3，那么第四个请求就有可能被缓存在桶中，然后延迟到下一秒进行处理。第四秒：
第四秒的
1/3时候前进入两个请求，那么2 + 2 = 4 > 3，就会有一个请求被丢弃；第四秒的
1/3时候后进入两个请求，那么1/3的时候已经处理了一个请求了，此时桶内只有一个缓存的请求，1 + 2 = 3 ≤ 3不会超过通容量，那么都会被处理了。如果此时桶内为空的：那么第四秒的两个请求都可以被处理；
如果第三秒的后
2/3秒进入三个请求，那么只有一个请求会被处理，桶内缓存两个请求，第三秒的请求对第四秒产生了影响：
综上可以看出，桶排序某种程度上有点类似于固定窗口，不过带有了一个缓冲区，且对流量进行了整流，流量速率更加的均匀。从定义来看漏水桶满足 FIFO(first in first out)，那么可能就会一个请求被缓存的时间过长，导致所有等待请求都延时处理了，那么可以加一个超时淘汰机制，入桶的时候加入通时刻，在出口的时候加一个判断，如果超过了某一个时间，比如超过1秒，则直接丢弃，重新"漏"出来一个请求进行处理。
3.4、令牌桶
令牌桶与漏水桶类似，不过是当获取到令牌的时候才会进行处理，如果没有令牌则拒绝服务。当 Token Queue令牌的生产者会定时的往令牌队列中塞令牌，如果令牌满了则停止放入，当处理的请求有一定的并发的流量时，令牌桶是可以处理的，毕竟令牌桶中有一定的 buffer，整体上相对于漏水桶不仅可以满足平均速率处理还能够应对一定的突发流量。
这里就不细说了，大家可以结合漏水桶理解。另外令牌桶是一个典型的生产者-消费者的模型可以让实现更加的简单，通过控制生产者的生产速率可以动态灵活的控制限流，也可以通过 Token Buffer进行了解耦，可以同步异步之间可以进行灵活的转换。
3.3、redis限流
redis限流适用于分布式的限流，那么使用Redis应该怎么限流呢？答案当然是 ZSet，使用请求的时间戳作为 Score，就可以拿到一个有序的队列，那么就可以结合 滑动窗口/固定窗口/漏水桶/令牌桶，进行限流，建议为限流单独搭建一个redis的服务，这样避免redis服务的负载过高导致限流组件延迟较大或者崩溃。
四、有驾网关限流落地
4.1、限流设计
在进行设计的时候调研的多种的限流方案，但是并不是很适用于分布式网关，适合网关单实例的统一入口的网关。
而针对 redis限流的方案，发现又不太适合网关是中心节点的场景，如果网关频繁请求 redis那么导致整个链路的耗时会不断叠加，redis请求耗时大概在 5ms左右，通过网关的次数越多那么耗时就会不断的累计。并且同步调用 redis的可用性直接影响到了服务的可用性。
分布式网关限流就需要考虑配置一个限流就需要对所有的网关实例生效，每一个网关接入的流量也不同，那么就需要根据网关的实际流量分配。
假设当前时刻为第
n秒，时间窗口为m秒，当前实例统计窗口m的流量；同步统计数据：每一个请求过来找到对应的统计数据，通过原子操作可以快速准确的对访问次数做到实时
+1；异步上报数据：
每一个实例有一个独立的协程上报自己
[n-m, n]时间段的数据；异步拉取数据：
总流量 > 0，按照流量比例分配限流：
ins_limit = total * total_limit / 总流量；总流量 == 0，按照实例均分：
ins_limit = total_limit/ins_total。实例数为
ins_total每一个实例有一个独立的协程拉取
[n-2*m, n-m]时间段所有实例的流量数据total；从配置中心拉取最新的限流阈值
total_limit；计算当前实例的流量来限制n秒的流量，
4.2、限流实现
4.2.1 推送数据
在每一个请求过来的时候，网关先判断是否已经超过限流，如果没有超过限流则进行转发，转发之后获取状态码，再通过加读锁和原子操作对 Counter进行计数操作，通过读写分离和原子操作极大程度的降低了竞争的临界区，降低了耗时。什么时候才会加写锁呢？只有该服务不存在的时候才会进行写操作，新增一个 RateContainers。然后通过异步推送 records的数据到 redis中。
PushManager推送数据RateContainers数据记录的容器Counter统计2XX、3XX、4XX、5XX的数据RequestInfo记录服务名等数据records统计数据[maxRecrods]*CounternoCopy包含读写锁，所以禁止拷贝RWLocker读写锁Records记录的数据，类型map[string]*RateContainers
┌─>Type┌──>Slot ││ ├─>Appidmetric-xx┌─────────┐ │ ┌───────────┐ │┌───────>│Statistic├─┼──┤RequestInfo├─┴─>Service│ └─────────┘ │ └───────────┘InsMetrics │ │┌──────────┤ ┌───────┐ │ ┌───────┐ ┌─┬─┬─┬─┐[]InsMetrics │ └──···──>│ xxxxx │ └──┤Counter├──>│ │ │ │ │┌──────────────────┐ ┌┴┬─┬─┬───┐ └───────┘ └───────┘ └─┴─┴─┴─┘┌─┤ Records ├──┤ │ │ │...│ ▲ ▲ ▲ ▲│ └──────────────────┘ └─┴─┴─┴───┘ │ │ │ ││ 2xx │4xx│┌─────────────┐ │ ┌────────────────┐ 3xx 5xx│ PullManager ├─┼─┤ lastestMetrics │└─────────────┘ │ └────────────────┘││ ┌────────────────┐└─┤ lastestSlot │└────────────────┘
拉取数据
4.2.1 拉取数据
对于拉取数据和推送数据基本一致，先获取所有实例的信息，然后拉取对应的数据计算总数，再根据计算出当前实例的分配到的限流的额度，进行更新到 InsMetrics中进行限流使用。
PullRecord拉取数据InsMetrics每一个slot的数据，类型map[string]*StatisticSlot槽的信息，理解为一个编号RequestInfo记录服务名Counter统计2XX、3XX、4XX、5XX的数据Statistic统计数据，记录服务名、流量数据、统计时的槽号lastestSlot最新记录的槽lastestMetrics最新记录的数据Records记录的数据，类型[pullMaxRecord]InsMetrics
┌─>Type┌──>Slot ││ ├─>Appidmetric-xx┌─────────┐ │ ┌───────────┐ │┌───────>│Statistic├─┼──┤RequestInfo├─┴─>Service│ └─────────┘ │ └───────────┘InsMetrics │ │┌──────────┤ ┌───────┐ │ ┌───────┐ ┌─┬─┬─┬─┐[]InsMetrics │ └──···──>│ xxxxx │ └──┤Counter├──>│ │ │ │ │┌──────────────────┐ ┌┴┬─┬─┬───┐ └───────┘ └───────┘ └─┴─┴─┴─┘┌─┤ Records ├──┤ │ │ │...│ ▲ ▲ ▲ ▲│ └──────────────────┘ └─┴─┴─┴───┘ │ │ │ ││ 2xx │4xx│┌─────────────┐ │ ┌────────────────┐ 3xx 5xx│ PullManager ├─┼─┤ lastestMetrics │└─────────────┘ │ └────────────────┘││ ┌────────────────┐└─┤ lastestSlot │└────────────────┘
五、总结
有驾网关限流的落地跟常见的限流方案还是有很大的差异的，有驾限流的复杂性不言而喻，而且有驾网关的限流是非实时的有一定延迟，取决于 槽的大小，且也能接受有一定的延迟，大约5秒左右延迟生效时间。而且第一版的设计并未考虑到极端的场景，比如某一台实例流量剧增，其实会占用其他实例的限流配额，后续进行迭代优化，限制实例的限流的上下边界，通过一定策略进行流量负载。
针对业务场景提出并实现最简洁高效的解决方案是我们追求的目标。针对中心式的分布式网关限流场景，需要保证限流的实现上支持高并发、低延时、不降低网关原有的吞吐能力、不影响网关原有的承诺可用性，上述实现方案基本达成了我们的预期目标。用数据说话，能力上线后统计发现网关平均处理耗时相较之前仅增加 10577.5ns，在不明显降低网关吞吐能力的同时，为接入的各业务都上了一道可靠的限流安全闸。
此外特别感谢张轩健同学工作闲暇抽出时间审稿，并提出宝贵的改进意见。
六、参考文档
流量控制算法：https://xie.infoq.cn/article/eca91dd0bd2455d7b3ea0f3b9
流量调整和限流技术：https://colobu.com/2014/11/13/rate-limiting/
Go：分布式高并发服务限流实现方案：https://mp.weixin.qq.com/s/GkEAVQ6AWGRadB4fEBlepg
Designing a Distributed Rate Limiter — Deep Dive：https://medium.com/wineofbits/designing-a-distributed-rate-limiter-deep-dive-76d7e8d8452d
Better Rate Limiting With Redis Sorted Sets：https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
用redis的zset实现简单的限流：https://bex.meishakeji.com/2020/04/10/用Redis的zset实现简单的限流/
kong网关限流策略：https://www.jesse.top/2021/01/19/Linux-Web/Kong Rate Limiting限流插件/
Introduction to rate limiting with Redis：
Part 1：https://www.binpress.com/rate-limiting-with-redis-1/
Part 2：https://www.binpress.com/rate-limiting-with-redis-2/