目录
一、Sentinel 与 Gateway 的限流有什么差别？
1.1、前置知识 - 四种常见的限流算法
1.1.1、Tips
1.1.2、计数器算法
1）固定窗口计数器算法
2）滑动窗口计数器算法
1.1.3、令牌桶算法
1.1.4、漏桶算法
1.2、解决问题
一、Sentinel 与 Gateway 的限流有什么差别？
1.1、前置知识 - 四种常见的限流算法
1.1.1、Tips
限流，就是指对服务器请求量做限制，避免因为突发的请求量过多，导致服务器宕机.
比如，我们的服务器只能抗住每秒 1000 的请求量，但此时突然有 10000 的请求量来了，那么就需要把你这么大的请求量拦下来，按照服务能够承载的流量去放行，起到一个流控的效果.
如何实现呢，就来看看这主流的三种限流算法~
1.1.2、计数器算法
计数器算法又包括两种算法，如下：
1）固定窗口计数器算法
a）首先，他会将时间划分成多个窗口（时间窗口也被称为 interval），然后呢每一个窗口都会维护一个计数器，一旦有一个请求在这个窗口出现，计数器就会加一.
b）随着这一时刻突然增多，那么这个计数器就会越来越大，所以限流就是在设置这个计数器的阈值，数量超过阈值的请求就会被丢弃.
例如，窗口大小是 1000ms，阈值是3. 那么如果这 1000 ms 内的请求来了 4 个，那么超过阈值的那一个请求就会被丢弃.
这种算法会有一点缺陷：
例如，窗口大小是 1000ms，阈值是3. 我在 4000ms ~ 4500ms 之间一个请求都没有，然后在 4500ms ~ 5000ms 之间来了三个请求，你看，这是没问题的吧...
接着在 5000ms ~ 5500ms 之间又来了三个请求，并且 5500ms ~ 6000ms 之间也没有请求来，那么这一看，我这个窗口里也没超过呀.
但是！仔细思考一下，4500ms ~ 5500ms 之间不也是 1s 么，等于说你这 1s 放行了 6 个请求，如果你系统的最大 qps 是 3（每秒最多处理 3 个），岂不是就搞崩了.
如下图：
那么为了解决上述问题，就有了滑动窗口计数器算法~
2）滑动窗口计数器算法
a）滑动窗口计数算法中，有以下两个概念：
窗口：就是滑动窗口时区：会将滑动窗口划分成更小的区间，每个区间又维护了一个计数器用来统计这段时间内请求的个数. 滑动：假设窗口大小是 1000ms，时区是 500ms，那么滑动窗口每次就会向后滑动 500ms. 也就是说，从 0ms 开始，滑动窗口所在范围为 0 ~ 999ms，经过一次滑动后，滑动窗口的所在范围就是 500ms ~ 1499 ms .（统计的请求数：500~ 999ms 时区 + 1000ms + 1499ms 时区）. 请求计数：假设窗口大小是 1000ms，时区是 500ms，此时 1200ms 的时候来了一个请求，那么滑动窗口中请求所计算的范围按照最后一个请求所在的时区计算的，此处就是 500ms ~ 1499ms
b）举个栗子：例如窗口大小是 1000ms，时区是 500ms，qps 是 3.，此时来了三个请求，分别是 900ms、1200ms、1300ms，此时窗口计算的范围就是 500ms ~ 1499ms 中的请求. 如果此时 1400 ms 再来一个请求，就超出了，因此就会抛弃掉.
但是，如果按照 固定滑动窗口计数器算法 计算，0~999ms 和 1000~1999ms 没有问题，然而在 500ms ~ 1499 ms 存在 4 个请求，就出问题了...
滑动窗口就一定没有问题吗？
a）问题：如果此时 1600ms 又来了一个请求，那么滑动窗口 1000ms ~ 1999ms 好像没有问题，只有三个请求（1200ms、1300ms、1600ms）.
但是在 800ms ~ 1799ms 这个范围内却存在了 4 个请求（900ms、1200ms、1300ms、1600ms）.
b）解决方案 —— 将时区划分成更小的区间：例如上述场景中可以划分区间为 250ms 为一个时区，那么上述场景中，滑动窗口的范围在 750ms ~ 1749ms，就会发现出现了 4 个请求，此时就会淘汰掉 1600ms 请求.
1.1.3、令牌桶算法
a）令牌桶算法就说，有一个桶，这个桶里会以固定的速率去生成令牌（这个速率实际上就是 qps）.
b）当这个桶满了以后，就会把多余的令牌丢弃.
c）每一个请求来的时候都会去申请一个令牌，如果桶中没有令牌，请求就会被丢弃.
例如，qps 是5，也就是生成 令牌的速率是每秒 5 个，而此时桶中有 5 个令牌，但是忽然有 6 个请求同时到来，那么多出来的请求就会被丢掉.
令牌桶算法的缺陷：
思考这样一个问题，假设桶的容量是 5，每秒生成 5 个令牌，但非常神奇的是，第 0~ 0.99 秒的时候一个请求都没有来，而 0.99 秒突然来了 10 个请求，那么首先会先去桶里把存的 5 个令牌拿走，此时还剩 5 个请求没有通过，而第 2 秒的时候又要生成 5 个令牌，剩下的 5 个令牌是不是也能过去.
这就超过阈值了...
他的缺陷同时也是一个好处：
如果我们设置令牌的速度不是我们服务器的上限，而是一个平均值，偶尔超出也不会把服务压垮，那么令牌桶就可以很好的处理突发的请求情况（请求带有波动性的）.
例如服务器的最大并发能力是 6，我设置 qps 为 3（令牌生成速度），如果说第一秒没有请求来，那么第二秒的时候来了 6 个请求，此时就可以桶里有 6 个令牌，就都能都放行处理了，不会造成请求的丢失.
令牌桶的真正底层实现：
虽然我们讲他是利用一个桶，每秒钟生成多少令牌，但是代码真正的实现可不是这样，因为你还要弄个定时器去生成，很麻烦.
令牌桶的代码实现思路是这样的：
这个桶的话实际上里面并不会生成令牌，而是记录上一个请求来的时间，另外还记录了当前还有几个令牌了.只要记录了这两样东西，那只需要么当请求来了以后，就计算这个请求和上一个请求之间的时间差，根据这个时间差然后更新桶中令牌数量（增加多少令牌），然后判断桶中的令牌数量是否能让够当前的请求数量.
例如我每秒生成 5 个令牌，也就是 每 0.2 秒生成一个令牌. 那么假设来了两个请求 A 和 B，就可以计算一下 A 和上一个请求的时间差，比如说是 0.2 秒，此时就会根据这个时间更新桶中令牌的数量（0.2 秒，相当于令牌 + 1），然后就会看桶中剩余的令牌数，假设为 2，那么就可以放行通过.
由于令牌桶算法比较重要，因此这里我实现了一个简易的令牌桶如下：
import java.util.Date
import kotlin.math.min
class TokenBucket(
private var rate: Int, //令牌每秒生成数量(单位秒)
private var capacity: Long, //令牌桶容量
private var tokens: Long = 0, //当前令牌数量
private var lastReqTime: Date = Date() //处理上一个请求的时间
) {
/**
* 检查是否可以处理请求(获取令牌)
*/
fun canConsumeToken(): Boolean {
//计算上一个请求到这个到当前请求经过的时间
val timeDiff = System.currentTimeMillis() - this.lastReqTime.time
//根据时间差计算应该生成的令牌数
val generatedTokensDouble = (timeDiff / 1000.0) * this.rate //timeDiff单位 -> 毫秒 | rate单位 -> 秒
//对 generatedTokens 向下取整(令牌不能是小数)
val generatedTokens = generatedTokensDouble.toLong()
//更新令牌数量(不超过桶的容量)
this.tokens = min(generatedTokens + this.tokens, this.capacity)
//更新处理上一个请求的时间
this.lastReqTime = Date(System.currentTimeMillis())
//尝试消费一个令牌
return this.tryConsumeToken()
}
/**
* 尝试从桶中获取一个令牌
*/
private fun tryConsumeToken(): Boolean =
if(this.tokens > 0) {
this.tokens -= 1
true
} else {
false
}
}
fun main() {
//令牌桶创建的时候，默认上一个请求的到达的时间就是当前时间
val tokenBucket = TokenBucket(
rate = 4,
capacity = 4
)
//模拟 900ms 时，同时来了四个请求
Thread.sleep(900)
val req1 = tokenBucket.canConsumeToken()
val req2 = tokenBucket.canConsumeToken()
val req3 = tokenBucket.canConsumeToken()
val req4 = tokenBucket.canConsumeToken()
//期望: 由于 1000ms 生成 4 个令牌，因此 900ms 的时候，只生成了 3 个令牌，前 3 个请求通过
println("req1: $req1, req2: $req2, req3: $req3, req4: $req4")
}
1.1.4、漏桶算法
a）漏桶算法呢也有一个桶，只不过不是用来存令牌的，而是用来存请求的.
b）当请求来了，就会把它当成一滴水放到桶里面去，然后漏桶就会以固定的速率向漏出请求.
c）如果桶满了，多余的请求就会被丢弃.
这就像是有一个桶，但是桶下面开了一个小口，当你往桶里倒水的时候，水就会以固定的速率从这个固定大小的小口流出.
漏桶算法的优势：
应对突发的请求：假如漏桶的处理速度是每 3s 一个请求，但是如果突发来了 10 个请求，没关系，我在桶里先存起来，后面慢慢处理就可以.流量永远是平滑的：不管你每秒是来了 10 个还是 100 个请求，只要我桶够大，那么放出去的速度永远都是固定的，也就是说他处理请求的速度一直是一条直线.对比令牌桶：对于令牌桶来说，如果请求忽高忽低，这个时候令牌桶就没办法保证平滑，他有可能会出现忽高忽低的情况，因为前一秒令牌没有用完可以累计，在下一秒就有可能出现一次性被消耗完的情况.
漏桶算法的实现原理：
a）漏桶算法的请求实际上就是遵循先进先出，那么用的容器肯定就是队列.
b）当请求来的时候，这些请求就会按照时间间隔依次执行.
c）并且会有一个预期等待时间，实际上就是桶的大小. 当新的请求到来时，就会将桶中所有请求的等待时间加起来，然后再加上新的请求，如果大于预期等待时间，这个新的请求就会被抛弃.
例如，桶的预期等待时间是 2000ms（桶的大小），qps 是 5（每秒通过 5 个请求），也就相当于 200ms 处理一个请求.
突然某一时刻同时来了很多请求，那么第一个请求进来时，可以立即被执行，因此等待时间就是 0ms，第二请求就需要排队了，就是 200ms 的时候会被执行，往后以此类推. 当队列中所有请求的等待时间加起来等于 2000ms 的时候（预期等待时间），此时再来的请求就会被拒绝.
1.2、解决问题
明白上述的四种算法，回答这个问题就游刃有余了~
这个时候你就可以说，那么首先呢常见的有 3 种限流算法，分别是 计数器算法、令牌桶算法、漏桶算法. Gateway 采用的是基于 Redis 实现的令牌桶算法（key value 就是一个桶）.
而 Sentinel 内部实现的比较复杂：
默认限流模式是基于滑动时间窗口算法排队等待的限流模式则基于漏桶算法：因为漏桶算法本身就是一种排队嘛，请求来了，如果前面还有请求没被执行，就排队，并且按照固定的频率去执行.而热点参数限流则是基于令牌桶算法：热点参数的特点就是针对每个一个参数单独去统计，那么你可以看作是一个接口，比如查询商品，将来商品的参数可能就是成千上万，如果采用滑动窗口的方式，那就需要进行时间分区，并每个分区种都有一个计数器来统计，那么对内存的消耗是非常大的. 如果使用令牌桶，就只需要记住这个参数对应的令牌即可（上一个请求来的时间）.
推荐阅读
您阅读本篇文章共花了：
发表评论