Sentinel的限流与Gateway的限流有什么差别？

问题说明：考察对限流算法的掌握情况

限流算法常见的有三种实现：滑动时间窗口，令牌桶算法，漏桶算法。gateway则采用基于Redis实现的令牌桶算法。但是我们不会去用，而Sentinel 功能比较丰富。
而sentinel内部比较复杂：

• 默认限流模式是基于滑动时间窗口算法
  针对资源做统计，一个资源对弈一个滑动窗口算法，统计的数据较少，内存使用不高。
• 流控效果为排队等待的限流模式基于漏桶算法
  需要排队等待效果
• 而流控规则的热点参数限流 是基于令牌桶算法
  参数较多，只需要记录参数对应的请求时间信息

补充

限流： 对 应用服务的请求做限制，避免因过多的请求而导致服务器过载甚至宕机。
限流算法常见的包括两种：
1.计算器算法，有包括窗口计算器算法，滑动窗口算法

2.令牌桶算法（Token Bucket）

3.漏桶算法（Leaky Bucket）

固定窗口算法

• 将时间划分为多个窗口，窗口时间跨度成为Interval(间隔). 1000ms
• 每个窗口维护一个计数器，每有一次请求就会将计数器加1，限流就是设置计数器阀值。设置为3
• 如果计算器超过了限流阀值，则超出阀值的请求都会被丢弃。
  

观上图，这种算法使用问题的，在4500-5500ms 这1s内有6个请求通过。

滑动窗口计数器算法

滑动窗口计数器算法会对一个窗口分为n个更小的区间，例如：

• 窗口时间跨度Interval为1s;区间数量 n=2,则每个小区间的时间间隔为500ms
• 限流阀值依然为3，时间窗口（1s）内请求超过阀值时，超出的请求被限流
• 窗口会根据当前请求所在的时间（currentTime）移动，窗口范围是从（currentTime-Interval)之后的第一个时区开始，到currentTime 所在时区结束

0 500 1000 1500 2000
比如是1250ms 时来个请求，1250-1000=250， 250后面的第一个时区是500-100。而1250在 1000-1500中；所以这个滑动窗口是 500-1000。

观上图，其实还是有问题，可以将区间数量设置越小，限流就越准确，但是还是不能100%准确。

令牌桶算法

• 以固定的速率生成令牌，存入令牌桶中，如果令牌桶满了以后，多余令牌丢弃
• 请求进入后，必须先尝试从桶中获取令牌后才可以被处理
• 如果令牌中没有令牌，则请求等待或丢弃

代码实现上并不是设计一个桶来存储令牌，而是存储 一定时间范围的请求信息，根据请求信息来计算是否可以拿到令牌。

漏桶算法

漏桶算法是对令牌桶算法的改进

• 将每个请求视作水滴放入漏桶进行存储
• 漏桶以固定速度向外漏出请求来执行，如果“漏桶”空了则停止“漏水”
• 如果“漏桶”满了则多余的“水滴”会被直接丢弃
  

漏桶实现 用阻塞队列

漏桶算法

Sentinel 在实现漏桶时，采用了排队等待模式：
让所有请求进入一个队列中，然后按照阀值允许的时间间隔依次执行。并发的多个请求必须等待，预期的等待时长-最近一次请求的预期等待时间+允许的间隔。如果请求预期的等待时间超出最大时长，则会拒绝。

例如： QPS=5 ，意味这没200ms处理一个队列中的请求，timeout=2000,意味着预期等待超过2000ms的请求会被拒绝并抛出异常。