三色漏桶算法

‘壹’ 流量整形的流量整形的核心算法

流量整形的核心算法有以下两种，具体采用的技术为GTS（Generic Traffic Shaping），通用流量整形： 漏桶算法（Leaky Bucket）
漏桶算法是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。 令牌桶算法（Token Bucket）
有时人们将漏桶算法与令牌桶算法错误地混淆在一起。而实际上，这两种算法具有截然不同的特性并且为截然不同的目的而使用。它们之间最主要的差别在于：漏桶算法能够强行限制数据的传输速率，而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使某一个单独的流突发到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。

‘贰’ GTS的通用流量整形

流量整形(traffic shaping)典型作用是限制流出某一网络的某一连接的流量与突发，使这类报文以比较均匀的速度向外发送。流量整形通常使用缓冲区和令牌桶来完成，当报文的发送速度过快时，首先在缓冲区进行缓存，在令牌桶的控制下再均匀地发送这些被缓冲的文。
流量整形的核心算法有以下两种，具体采用的技术为GTS（Generic Traffic Shaping），通用流量整形
漏桶算法（Leaky Bucket）
漏桶算法是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。
令牌桶算法（Token Bucket）
有时人们将漏桶算法与令牌桶算法错误地混淆在一起。而实际上，这两种算法具有截然不同的特性并且为截然不同的目的而使用。它们之间最主要的差别在于：漏桶算法能够强行限制数据的传输速率，而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使某一个单独的流突发到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。
GTS
GTS可以对不规则或不符合预定流量特性的流量进行整形，使得网络上下游之间的带宽匹配。GTS与CAR一样均采用了令牌桶技术来控制流量，但主要区别在于：利用CAR进行报文流量控制时对不符合流量特性的报文进行丢弃，而GTS对于不符合流量特性的报文则是进行缓冲减少了报文的丢弃，同时满足报文的流量特性。
GTS可以对接口上指定的报文流或所有报文进行整形当报文到来的时候，首先对报文进行分类如果报文不需要进行GTS处理，就继续发送不经过令牌桶的处理；如果报文需要进行 GTS处理，则与令牌桶中的令牌进行比较。
令牌桶按用户设定的速度向桶中放置令牌，如果令牌桶中有足够的令牌可以用来发送报文，则报文直接被继续发送下去，同时令牌桶中的令牌量按报文的长度做相应的减少，当令牌桶中的令牌少到报文不能再发送时，报文将被缓存入GTS队列中。
当GTS队列中有报文的时候，GTS按一定的周期从队列中取出报文进行发送。 每次发送都会与令牌桶中的令牌数作比较。直到令牌桶中的令牌数减少到队列中的报文不能 再发送或是队列中的报文全部发送完毕为止。

‘叁’ Redis 限制频繁请求拦截处理

项目运维人员发现NGINX日志中短时间内有同一IP、同一用户、同一设备发出的大量请求，比用户正常行为产生的请求频率要高出很多，所以有对单位时间内访问频次限制的需求。

一般就会在服务器端将用户信息和访问信息做下关联，以此来实现访问频次限制。通常大家都会选择 Redis 来作为此中间件的存储介质。

几种最常用的限流算法：

固定窗口计数器算法概念如下：

固定窗口计数器是最为简单的算法，但这个算法有时会让通过请求量允许为限制的两倍。考虑如下情况：限制 1 秒内最多通过 5 个请求，在第一个窗口的最后半秒内通过了 5 个请求，第二个窗口的前半秒内又通过了 5 个请求。这样看来就是在 1 秒内通过了 10 个请求。

滑动窗口计数器算法概念如下：

滑动窗口计数器是通过将窗口再细分，并且按照时间"滑动"，这种算法避免了固定窗口计数器带来的双倍突发请求，但时间区间的精度越春厅高，算法所需的空间容量就越大。

漏桶算法概念如下：

漏桶算法多使用 队列 实现，服务的请求会存到队列中，服务的提供方则按照固定的速率从队列中取出请求并执行，过多的请求则放在队列中排队或直接拒绝。

漏桶算法的缺陷也很明显，当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。

令牌桶算法概念如下：

令牌桶算法既能够将所有的请求平均分布到时间区间内，又能接受服务器能够纯凯承受范围内的突发请求，因此是目前使扒裤隐用较为广泛的一种限流算法。

业务对此要求不高，所以用了简单的固定窗口计数器算法。

‘肆’ 分布式解决方案之：限流

限流在日常生活中限流很常见，例如去有些景区玩，每天售卖的门票数是有限的，例如 2000 张，即每天最多只有 2000 个人能进去游玩。那在我们工程上限流是什么呢？限制的是 “流”，在不同场景下“流”的定义不同，可以是 每秒请求数、每秒事务处理数、网络流量 等等。通常意义我们说的限流指代的是限制到达系统的并发请求数，使得系统能够正常的处理部分用户的请求，来保证系统的稳定性。

日常的业务上有类似秒杀活动、双十一大促或者突发新闻等场景，用户的流量突增，后端服务的处理能力是有限的，如果不能处理好突发流量，后端服务很容易就被打垮。另外像爬虫之类的不正常流量，我们对外暴露的服务都要以最大恶意为前提去防备调用者。我们不清楚调用者会如何调用我们的服务，假设某个调用者开几十个线程一天二十四小时疯狂调用你的服务，如果不做啥处理咱服务基本也玩完了，更胜者还有ddos攻击。

对于很多第三方开放平台来说，不仅仅要防备不正常流量，还要保证资源的公平利用，一些接口资源不可能一直都被一个客户端占着，也需要保证其他客户端能正常调用。

计数器限流也就是最简单的限流算法就是计数限流了。例如系统能同时处理 100 个请求，保存一个计数器，处理了一个请求，计数器就加一，一个请求处理完毕之后计数器减一。每次请求来的时候看看计数器的值，如果超过阈值就拒绝。计数器的值要是存内存中就算单机限流算法，如果放在第三方存储里（例如Redis中）集群机器访问就算分布式限流算法。

一般的限流都是为了限制在指定时间间隔内的访问量，因此还有个算法叫固定窗口。

它相比于计数限流主要是多了个时间窗口的概念，计数器每过一个时间窗口就重置。规则如下：

这种方式也会面临一些问题，例如固定窗口临界问题：假设系统每秒允许 100 个请求，假设第一个时间窗口是 0-1s，在第 0.55s 处一下次涌入 100 个请求，过了 1 秒的时间窗口后计数清零，此时在 1.05 s 的时候又一下次涌入100个请求。虽然窗口内的计数没超过阈值，但是全局来看在 0.55s-1.05s 这 0.1 秒内涌入了 200 个请求，这其实对于阈值是 100/s 的系统来说是无法接受的。

为了解决这个问题，业界又提出另外一种限流算法，即滑动窗口限流。

滑动窗口限流解决固定窗口临界值的问题，可以保证在任意时间窗口内都不会超过阈值。相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多。

规则如下，假设时间窗口为 1 秒：

但是滑动窗口和固定窗口都无法解决短时间之内集中流量的冲击问题。 我们所想的限流场景是： 每秒限制 100 个请求。希望请求每 10ms 来一个，这样我们的流量处理就很平滑，但是真实场景很难控制请求的频率，因为可能就算我们设置了1s内只能有100个请求，也可能存在 5ms 内就打满了阈值的情况。当然对于这种情况还是有变型处理的，例如设置多条限流规则。不仅限制每秒 100 个请求，再设置每 10ms 不超过 2 个，不过带来的就是比较差的用户体验。

而漏桶算法，可以解决时间窗口类的痛点，使得流量更加平滑。

如下图所示，水滴持续滴入漏桶中，底部定速流出。如果水滴滴入的速率大于流出的速率，当存水超过桶的大小的时候就会溢出。

规则如下：

水滴对应的就是请求。

与线程池实现的方式方式如出一辙。

面对突发请求，服务的处理速度和平时是一样的，这并非我们实际想要的。我们希望的是在突发流量时，在保证系统平稳的同时，也要尽可能提升用户体验，也就是能更快地处理并响应请求，而不是和正常流量一样循规蹈矩地处理。

而令牌桶在应对突击流量的时候，可以更加的“激进”。

令牌桶其实和漏桶的原理类似，只不过漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，然后请求只有拿到了令牌才能通过，之后再被服务器处理。

当然令牌桶的大小也是有限制的，假设桶里的令牌满了之后，定速生成的令牌会丢弃。

规则：

令牌桶的原理与JUC的Semaphore 信号量很相似，信号量可控制某个资源被同时访问的个数，其实和拿令牌思想一样，不同的是一个是拿信号量，一个是拿令牌。信号量用完了返还，而令牌用了不归还，因为令牌会定时再填充。

对比漏桶算法可以看出 令牌桶更适合应对突发流量 ，假如桶内有 100 个令牌，那么这100个令牌可以马上被取走，而不像漏桶那样匀速的消费。不过上面批量获取令牌也会致使一些新的问题出现，比如导致一定范围内的限流误差，举个例子你取了 10 个此时不用，等下一秒再用，那同一时刻集群机器总处理量可能会超过阈值，所以现实中使用时，可能不会去考虑redis频繁读取问题，转而直接采用一次获取一个令牌的方式，具体采用哪种策略还是要根据真实场景而定。

1、计数器 VS 固定窗口 VS 滑动窗口

2、漏桶算法 VS 令牌桶算法

总的来说

单机限流和分布式限流本质上的区别在于 “阈值” 存放的位置，单机限流就是“阀值”存放在单机部署的服务/内存中，但我们的服务往往是集群部署的，因此需要多台机器协同提供限流功能。像上述的计数器或者时间窗口的算法，可以将计数器存放至 Redis 等分布式 K-V 存储中。又如滑动窗口的每个请求的时间记录可以利用 Redis 的 zset 存储，利用 ZREMRANGEBYSCORE 删除时间窗口之外的数据，再用 ZCARD 计数，

可以看到，每个限流都有个阈值，这个阈值如何定是个难点。定大了服务器可能顶不住，定小了就“误杀”了，没有资源利用最大化，对用户体验不好。一般的做法是限流上线之后先预估个大概的阈值，然后不执行真正的限流操作，而是采取日志记录方式，对日志进行分析查看限流的效果，然后调整阈值，推算出集群总的处理能力，和每台机子的处理能力(方便扩缩容)。然后将线上的流量进行重放，测试真正的限流效果，最终阈值确定，然后上线。

其实真实的业务场景很复杂，需要限流的条件和资源很多，每个资源限流要求还不一样。

一般而言，我们不需要自己实现限流算法来达到限流的目的，不管是接入层限流还是细粒度的接口限流，都有现成的轮子使用，其实现也是用了上述我们所说的限流算法。

具体的使用还是很简单的，有兴趣的同学可以自行搜索，对内部实现感兴趣的同学可以下个源码看看，学习下生产级别的限流是如何实现的。

限流具体应用到工程还是有很多点需要考虑的，并且限流只是保证系统稳定性中的一个环节，还需要配合降级、熔断等相关内容。