常见限流算法

Ⅰ Golang中的限速器 time/rate

在高并发的系统中，限流已作为必不可少的功能，而常见的限流算法有：计数器、滑动窗口、令牌桶、漏斗(漏桶)。其中滑动窗口算法、令牌桶和漏斗算法应用最为广泛。

这里不再对计数器算法和滑动窗口作介绍了，有兴趣的同学可以参考其它相关文章。

非常很好理解，就像有一个漏斗容器一样，漏斗上面一直往容器里倒水(请求)，漏斗下方以 固定速率 一直流出(消费)。如果漏斗容器满的情况下，再倒入的水就会溢出，此时表示新的请求将被丢弃。可以看到这种算法在应对大的突发流量时，会造成部分请求弃用丢失。

可以看出漏斗算法能强行限制数据的传输速率。

令牌桶算法

从某种意义上来说，令牌算法是对漏斗算法的一种改进。对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发情况。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。

令牌桶算法是指一个固定大小的桶，可以存放的令牌的最大个数也是固定的。此算法以一种 固定速率 不断的往桶中存放令牌，而每次请求调用前必须先从桶中获取令牌才可以。否则进行拒绝或等待，直到获取到有效令牌为止。如果桶内的令牌数量已达到桶的最大允许上限的话，则丢弃令牌。

Golang标准库中的限制算法是基于令牌桶算法(Token Bucket) 实现的，库名为golang.org/x/time/rate

对于限流器的消费方式有三种，分别为 Allow()、 Wait()和 Reserve()。前两种内部调用的都是Reserve() ,每个都对应一个XXXN()的方法。如Allow()是AllowN(t, 1)的简写方式。

主要用来限速控制并发事件，采用令牌池算法实现。

使用 NewLimiter(r Limit, b int) 函数创建限速器，令牌桶容量为b。初始化状态下桶是满的，即桶里装有b 个令牌，以后再以每秒往里面填充 r 个令牌。

允许声明容量为0的限速器，此时将会拒绝所有操作。

// As a special case, if r == Inf (the infinite rate), b is ignored.
有一种特殊情况，就是 r == Inf 时，此时b参数将被忽略。

Limiter 提供了三个主要函数 Allow, Reserve, 和 Wait. 大部分时候使用Wait。其中 AllowN, ReserveN 和 WaitN 允许消费n个令牌。

每个方法都可以消费一个令牌，当没有可用令牌时，三个方法的处理方式不一样

AllowN方法表示，截止在某一时刻，目前桶中数目是否至少为n个。如果条件满足，则从桶中消费n个token，同时返回true。反之不消费Token，返回false。

使用场景：一般用在如果请求速率过快，直接拒绝请求的情况

输出

当使用Wait方法消费Token时，如果此时桶内Token数量不足(小于N)，那么Wait方法将会阻塞一段时间，直至Token满足条件。否则直接返回。
// 可以看到Wait方法有一个context参数。我们可以设置context的Deadline或者Timeout，来决定此次Wait的最长时间。

输出

// 此方法有一点复杂，它返回的是一个*Reservation类型，后续操作主要针对的全是这个类型
// 判断限制器是否能够在指定时间提供指定N个请求令牌。
// 如果Reservation.OK()为true，则表示需要等待一段时间才可以提供，其中Reservation.Delay()返回需要的延时时间。
// 如果Reservation.OK()为false,则Delay返回InfDuration, 此时不想等待的话，可以调用 Cancel()取消此次操作并归还使用的token

输出

https://www.cyhone.com/articles/analisys-of-golang-rate/
https://zhuanlan.hu.com/p/100594314
https://www.jianshu.com/p/1ecb513f7632
https://studygolang.com/articles/10148

Ⅱ 限流策略

在开发高并发系统时，为了保证系统的高可用和稳定性，常见的有以下几种策略：

一般来说，限流的常用处理手段有：

计数器是一种比较简单粗暴的限流算法：
在一段时间间隔内，对请求进行计数，与阀值进行比较判断是否需要限流，一旦到了时间临界点，将计数器清零。

计数器算法存在“时间临界点”缺陷。比如每一分钟限制100个请求，可以在00:00:00-00:00:58秒里面都没有请求，在00:00:59瞬间发送100个请求，这个对于算法来是允许的，然后在00:01:00再次发送100个请求，意味着在短短1s内发送了200个请求，如果量更大呢，系统可能会承受不住瞬间流量，导致系统崩溃。（如下图所示）

针对计数器算法的缺陷，滑动窗口做了优化，将时间进行划片，并随着时间流逝，进行移动，固定数量可以移动固定的格子，进行计数并判断阀值。

格子的具体数量影响滑动窗口算法的精度，时间片的概念其实不能根本解决临界点的问题。

原理和计数器类似，不做进一步引申

描述如下：

1、一个固定容量的漏桶，按照固定速率流出水滴
2、如果桶是空的，没有水滴流出
3、水滴以任意速率的流速入桶
4、如果水超过桶的容量，则溢出（请求被丢弃）

通俗的讲，我们有一个固定容量的桶，有水流入，也有水流出。对于流进来的水（请求）来说，我们无法预计一共会有多少水流进来，也无法估计流入水的速度。但是对于流出去的水来说，我们这个桶是可以按照固定流出的速率。从而达到流量控制的效果。

由于漏桶的出水的速率是恒定的，如果爆发了大流量的话，将会有大量的请求被丢弃（溢出），为了解决这个问题，令牌桶进行了算法改进，算法描述如下：

1、有一个固定容量的桶，桶一开始是空的。
2、以固定的速率向桶内填充令牌，到达桶的容量后，多余令牌将被丢弃。
3、每一个请求过来，就会尝试从令牌桶中移除一个令牌，如果没有令牌，请求无法通过。

在正常请求下，桶中会积累一定量的令牌，这就使这个算法支持一定程度的大流量访问。也就是说，如果桶中有100个令牌，那就可以瞬时允许100个请求通过。从这点来说，对用户比较友好，因此业内大部分用的是该算法。
当然，不管是令牌桶拿不到令牌被拒绝还是漏桶满了被抛弃，都是为了保证大部分流量的正常访问，牺牲少部分流量，这个是合理的。

不同的限流算法没有所谓的谁比谁更优，主要还是看具体业务情况，比如令牌桶我们更多的是用于保护自身，而漏桶的限制流速则可以用于保护他人。

Ⅲ 关于API网关（四）——限流

通俗的说，流量控制就是控制用户请求的策略，主要包括：权限、限流、流量调度。
权限上一篇已经讲过了，这一篇讲限流，下一篇讲流量调度。
限流是指限制用户调用的频率（QPS/QPM）或者次数。

流量限制，站在用户或者运营的角度看，最直观能感受到的作用是——收费
各大主流开放平台的对外API，一般都有一些免费的额度，可以供个人测试用，一旦想大规模调用，就需要付费购买更大的额度（频率、次数），根据调用次数或者频率进行收费。一旦超过拥有的额度，就会被限制调用。

其实这才是限流最大的用处，只是用户或者运营同学无感，所以不太被大多数人了解。
网关后面是各个服务，各个服务的接口通过网关透出去给用户调用。理论上说，用户的流量是不可预知的，随时可能来一波，一旦流量的峰值超过了服务的承载能力，服务就挂了，比如有大新闻发生时的某浪微博，比如前些年的12306.
所以， 网关必须保证，放过去到达后端服务的流量一定不可以超过服务可以承载的上限 。这个上限，是网关和各个服务协商出来的。

由简到难，限流可以 分为单机限流、单集群限流、全集群限流 。
这里不讨论具体的如漏桶、令牌桶等限流算法，只说概念和思想。

单机限流的思想很简单，就是每个机器的限流值 x 机器数量 = 总的限流值。
举个例子，A用户的QPS限制是100，网关部署了10台机器，那么，每台机器限制10QPS就可以了。
先说好处，这种方法实现起来非常简单，每台机器在本地内存计算qps就可以了，超过阈值就拒流。
不过单机限流的缺陷也十分明显，主要体现在两点：
 当网关部署的机器数量发生变化时，每台机器的限流值需要根据机器数调整。现实中，因为扩容、缩容、机器宕机等原因，机器数的变化是常有的事。
 单机限流的前提是，每台网关承载的用户的流量是平均的，但是事实上，在某些时间，用户的流量并不是完全平均分布在每台机器上的。
举个例子：
10台机器，每台限qps10，其中3台每台实际qps是15，因为超限导致用户流量被拒。其余7台每台qps是7。这样用户总的qps = 15 * 3 + 7 * 7 = 94. 用户qps并没有超限，但是却有一部分流量被拒了，这样就很有问题。
实际上，单台限流的阈值也会设置的稍微大一些，以抵消流量不均的问题。
因为上面的问题， 单机限流通常作为一种兜底的备用手段，大多数时候用的还是集群限流 。

先来看一个示意图：

相比单机限流，集群限流的计数工作上移到redis集群内进行，解决了单机限流的缺陷。
但是集群限流也不是完美的，因为引入了redis，那么，当网关和redis之间的网络抖动、redis本身故障时，集群限流就失效了，这时候，还是得依靠单机限流进行兜底。
也就是说， 集群限流 + 单机限流配合，才是一个比稳妥的方案 。

接下来我们来思考这样一个问题：大型网关一般都是多机房、多地域部署的，当然，后端的服务也是多机房、多地域部署的，在保护服务这一点来说，集群限流是够用了。但是对用户来说，还是有一些问题：
比如，用户购买的QPS上限是30，我们的网关部署在中国北、中、南三个地域，那么这30QPS怎么分配呢？
平均肯定不行，用户的流量可能是明显不均衡的，比如用户的业务主要集中在中国北方，那么用户的流量大部分都会进入北方的网关，网关如果限制QPS为10的话，用户肯定来投诉。
那每个地域都限制为30行不行？也不行，如果用户的流量比较均匀的分布在各个地域，那么用户购买了30QPS，实际上可能使用了90QPS，这太亏了。
按照解决单机限流流量不均的思路，搞一个公共的redis集群来计数行不行？
也不行，受限于信号传播速度和天朝的广阔疆域，每个流量都计数，肯定不现实，rt太高会导致限流失去意义，带宽成本也会变得极其昂贵，对redis的规格要求也会很高。总之，很贵还解决不了问题。
有一种巧妙的解决办法是：本地集群阶梯计数 + 全集群检查。
还是刚才的例子：
限流阈值时90，那么三个地域各自计数，当本地域的数值达到30时，去其他两个地域取一次对方当前的计数值，三个地域的计数值加起来，如果超了，告诉另外两个地域超了，开始拒流。如果没超，本地QPS每上涨10，重复一次上述的动作。
这样就能有效的减少与redis的交互次数，同时实现了全地域真·集群限流。
当然，这种全地域集群限流，因为rt和阶梯计数间隔的存在，一定是不准的，但是，比单集群限流还是好很多。

当某个用户流量特别大的时候，redis计数就会遇到典型的热点key问题，导致redis集群单节点压力过大， 有两种办法可以解决这个问题：打散和抽样。

打散是指，把热点key加一些后缀，使其变成多个key，从而hash到不通的redis节点上，均摊压力。
比如热点key是abcd，那么打散后，key变成了abcd1、abcd2、abcd3、abcd4。技术时，轮流加1、2、3、4的后缀就可以了。

抽样是指，针对热点key，不是每个每个请求到来时都进行计数，而是进行一个抽样，比如每10个请求记一次数，这样redis的压力就会降低到十分之一。

说着把流量调度的也说完了哈哈，那下一篇再说说监控好了，顺便推一下我现在在用的国产网关：GOKU，来自Eolinker。我觉得比KONG好用，感兴趣的同学可以自行去了解一下。
www.eolinker.com

Ⅳ 限流算法

计数器是一种最简单限流算法，其原理就是：在一段时间间隔内，对请求进行计数，与阀值进行比较判断是否需要限流，一旦到了时间临界点，将计数器清零。
这种方法虽然简单，但也有个大问题就是没有很好的处理单位时间的边界。

滑动窗口是针对计数器存在的临界点缺陷，所谓 滑动窗口（Sliding window） 是一种流量控制技术，这个词出现在 TCP 协议中。滑动窗口把固定时间片进行划分，并且随着时间的流逝，进行移动，固定数量的可以移动的格子，进行计数并判断阀值。
假设一个时间窗口是一分钟，每个时间窗口有 6 个格子，每个格子是 10 秒钟。每过 10 秒钟时间窗口向右移动一格。我们为每个格子都设置一个独立的计数器 Counter，假如一个请求在 0:45 访问了那么我们将第五个格子的计数器 +1（也是就是 0:40~0:50），在判断限流的时候需要把所有格子的计数加起来和设定的频次进行比较即可。
想让限流做的更精确只需要划分更多的格子就可以了，为了更精确我们也不知道到底该设置多少个格子，格子的数量影响着滑动窗口算法的精度，依然有时间片的概念，无法根本解决临界点问题。

漏桶算法（Leaky Bucket），原理就是一个固定容量的漏桶，按照固定速率流出水滴。用过水龙头都知道，打开龙头开关水就会流下滴到水桶里，而漏桶指的是水桶下面有个漏洞可以出水。如果水龙头开的特别大那么水流速就会过大，这样就可能导致水桶的水满了然后溢出。
一个固定容量的桶，有水流进来，也有水流出去。对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率（处理速度），从而达到 流量整形 和 流量控制 的效果。
漏桶算法有以下特点：

漏桶限制的是常量流出速率（即流出速率是一个固定常量值），所以最大的速率就是出水的速率，不能出现突发流量。

令牌桶算法（Token Bucket）是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。
我们有一个固定的桶，桶里存放着令牌（token）。一开始桶是空的，系统按固定的时间（rate）往桶里添加令牌，直到桶里的令牌数满，多余的请求会被丢弃。当请求来的时候，从桶里移除一个令牌，如果桶是空的则拒绝请求或者阻塞。
令牌桶有以下特点：

令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌...），并允许一定程度突发流量。

参考：
https://mp.weixin.qq.com/s/GOZkM2PGctqim4sp_uIEsg
https://mp.weixin.qq.com/s/-wU7SA8Hjh1Y2vOySdgGJw

Ⅳ 分布式组件-Sentinel-常见流量控制算法

在指定周期内累加访问次数，当访问次数达到设定的阈值时，触发限流策略，当进入下一个时间周期时进行访问次数的清零。

限定每一分钟能够处理的总的请求数为100，在第一个一分钟内，一共请求了60次。接着到第二个一分钟，counter又从0开始计数，在一分半钟时，已经达到了最大限流的阈值，这个时候后续的所有请求都会被拒绝。这种算法可以用在短信发送的频次限制上，比如限制同一个用户一分钟之内触发短信发送的次数。

这种算法存在一个临界问题，这种算法针对的是固定周期的累加访问次数，但是如果服务器需要做到的是限制每个一分钟内的访问量，这种算法显然就不适用了，因为计数器算法无法限制每隔一段时间内的访问量均不超过阈值。

在第一分钟的0：58和第二分钟的1：02这个时间段内，分别出现了100个请求，整体来看就会出现4秒内总的请求量达到200，超出了设置的阈值。

滑动窗口算法是将时间周期分为N个小周期（窗口），分别记录每个小周期内访问次数，然后根据时间将窗口往前滑动并删除过期的小时间窗口。最终只需要统计滑动窗口范围内的所有小时间窗口总的计数即可。

将一分钟拆分为4个小时间窗口，每个小时间窗口最多能够处理25个请求。并且通过虚线框表示滑动窗口的大小（当前窗口的大小是2，也就是在这个窗口内最多能够处理50个请求）。同时滑动窗口会随着时间往前移动，比如前面15s结束之后，窗口会滑动到15s～45s这个范围，然后在新的窗口中重新统计数据。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。此算法可以很好的解决固定窗口算法的临界问题。

令牌桶是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。对于每一个请求，都需要从令牌桶中获得一个令牌，如果没有获得令牌，则需要触发限流策略。

系统会以一个恒定速度（r tokens/sec）往固定容量的令牌桶中放入令牌，如果此时有客户端请求过来，则需要先从令牌桶中拿到令牌以获得访问资格。

假设令牌生成速度是每秒10个，也就等同于QPS=10，此时在请求获取令牌的时候，会存在三种情况：

• 请求速度大于令牌生成速度：那么令牌会很快被取完，后续再进来的请求会被限流。

• 请求速度等于令牌生成速度：此时流量处于平稳状态。

• 请求速度小于令牌生成速度：说明此时系统的并发数并不高，请求能被正常处理。

由于令牌桶有固定的大小，当请求速度小于令牌生成速度时，令牌桶会被填满。所以令牌桶能够处理突发流量，也就是在短时间内新增的流量系统能够正常处理，这是令牌桶的特性。

漏桶限流算法的主要作用是控制数据注入网络的速度，平滑网络上的突发流量。

在漏桶算法内部同样维护一个容器，这个容器会以恒定速度出水，不管上面的水流速度多快，漏桶水滴的流出速度始终保持不变。访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。实际上消息中间件就使用了漏桶限流的思想，不管生产者的请求量有多大，消息的处理能力取决于消费者。

在漏桶限流算法中，存在以下几种可能的情况：

• 请求速度大于漏桶流出水滴的速度：也就是请求数超出当前服务所能处理的极限，将会触发限流策略。

• 请求速度小于或者等于漏桶流出水滴的速度，也就是服务端的处理能力正好满足客户端的请求量，将正常执行。

漏桶限流算法和令牌桶限流算法的实现原理相差不大，最大的区别是漏桶无法处理短时间内的突发流量，漏桶限流算法是一种恒定速度的限流算法。

Ⅵ 单机限流算法笔记

限流算法为了防止问题：并发过高导致内存吃不消，系统崩溃。

计数器

计数器算法的特点是把系统运行时间划分为一个一个时间段，每个时间段通过计数器限制请求量，超过了则放弃掉。

这种算法适合长时间高并发访问的情况，但是互联网环境很多时候有点类似潮汐，某些时间点会出现大量并发访问，其他时间则访问很少。这会造成临界问题。

滑动窗口

滑动窗口的特点依然是先把时间划分为多个小段，然后使用一个时间窗口来扫描时间，请求数没满就加入到队列中，满了则抛弃。这个算法看似和计数器差不多，如果时间段设定合理，倒是可以缓解洪峰带来的损失。区间越小，算法需要的空间容量越大。

漏斗

这个算法有2个部分，一个是容器，用来存放“水滴”，另一个就是漏斗口，用来消费“水滴”，关键在于漏斗口通过控制能处理的最大速率来起到限流作用。这个算法重点关注的是保护cpu处理的能力，如果设置的漏口过小，则在高峰时期会影响到业务处理的效率。

令牌桶

令牌桶也有一个容器，也有一个控制流量的阀门，但是令牌空关注的是访问速率，完全放开cpu的限制，这个思路比漏斗要优的地方就是可以处充分利用处理能力，问题就是访问量的控制如果太宽松，系统也会有承受不住的问题。

令牌桶算法是目前主流的单机限流方案。也有一些框架例如guava，对这个算法提供了封装，并且再这个基础上进一步做了优化。比如 平滑预热限流 、 平滑突发限流 。

Ⅶ 四川北大青鸟分享分布式限流的运行原理

分布式编程架构技术我们在前几期的文章中已经给大家简单分析过很多次了，今天我们就一起来了解一下API网关分布式限流的运行原理都有哪些。
API网关中针对一个API、API分组、接入应用APPID,IP等进行限流。
这些限流条件都将会产生一个限流使用的key，在后续的限流中都是对这个key进行限流。
限流算法通常在API网关中可以采用令牌桶算法实现。
必须说明一点的是分布式限流由于有网络的开销，TPS的支持隔本地限流是有差距的，因此在对于TPS要求很高的场景，建议采用本地限流进行处理。
下面讨论我们应该采用redis的哪一种分布式锁的方案：由于redis事务要得到锁的效果需要在高TPS时会产生大量的无效的访问请求，所以不建议在这种场景下使用。
SETNX/EX的锁方案会产生在过期时间的问题，同时也有异步复制master数据到slave的问题。
相比lua方案会产生更多的不稳定性。
我建议采用lua的方案来实施分布式锁，因为都是单进程单线程的执行，因此在TPS上和二种方案没有大的区别，而且由于只是一个lua脚本在执行，甚至是可能纯lua执行可能会有更高的TPS。
当然是lua脚本中可能还是会去设置过期时间，但是应用server宕机并不会影响到redis中的锁。
当然master异步复制的问题还是有，但是并不会造成问题，因为数据只会有1个lua脚本执行问题，下一个执行就正常了。
在实现方案的时候使用了Jedis库，四川java课程http://www.kmbdqn.cn/认为有一些问题在方案的实现层面我已经去做过验证了，可能也会是读者的疑问。

Ⅷ 武汉北大青鸟分享分布式限流的运行原理

分布式编程架构技术我们在前几期的文章中已经给大家简单分析过很多次了，今天我们就一起来了解一下API网关分布式限流的运行原理都有哪些。
API网关中针对一个API、API分组、接入应用APPID,IP等进行限流。
这些限流条件都将会产生一个限流使用的key，在后续的限流中都是对这个key进行限流。
限流算法通常在API网关中可以采用令牌桶算法实现。
必须说明一点的是分布式限流由于有网络的开销，TPS的支持隔本地限流是有差距的，因此在对于TPS要求很高的场景，建议采用本地限流进行处理。
下面讨论我们应该采用redis的哪一种分布式锁的方案：由于redis事务要得到锁的效果需要在高TPS时会产生大量的无效的访问请求，所以不建议在这种场景下使用。
SETNX/EX的锁方案会产生在过期时间的问题，同时也有异步复制master数据到slave的问题。
相比lua方案会产生更多的不稳定性。
我建议采用lua的方案来实施分布式锁，因为都是单进程单线程的执行，因此在TPS上和二种方案没有大的区别，而且由于只是一个lua脚本在执行，甚至是可能纯lua执行可能会有更高的TPS。
当然是lua脚本中可能还是会去设置过期时间，但是应用server宕机并不会影响到redis中的锁。
当然master异步复制的问题还是有，但是并不会造成问题，因为数据只会有1个lua脚本执行问题，下一个执行就正常了。
在实现方案的时候使用了Jedis库，武汉java课程http://www.kmbdqn.cn/认为有一些问题在方案的实现层面我已经去做过验证了，可能也会是读者的疑问。

Ⅸ 分布式解决方案之：限流

限流在日常生活中限流很常见，例如去有些景区玩，每天售卖的门票数是有限的，例如 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 计数，

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

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

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

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

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