常见的限流算法

限流的作用：

应对

1.热点业务带来的突发请求

2.调用方 bug 导致的突发请求

3.恶意攻击的请求

常见的限流算法有

1）固定窗口计数器：将时间划分为多个窗口；在每个窗口内每有一次请求就讲计数器+1；如果计数器超过了限制的数量，则本窗口内所有的请求都被丢弃，当时间到达下一个窗口时，计数器重置。

算法问题：会让通过请求量是允许量的两倍。

2）滑动窗口计数器：将时间划分为多个区间；在每个区间没有一次请求就将计数器+1维持一个时间窗口，占据多个区间；每经过一个区间时间，则抛弃最老的一个区间，并纳入最新的一个区间；如果当前窗口内区间的请求技术总和超过了限制的数量，则本窗口内所有的请求都被丢弃。

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

3）漏桶算法：将每个请求看做'水滴'放入'漏桶' 进行存储；'漏桶'以固定的速率向外'漏'出请求来执行，如果'漏桶'空了则停止'漏水'；如果'漏桶'满了则多余的'水滴'会被直接丢弃；

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

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

4）令牌桶：令牌以固定的速率生成；生成的令牌放入令牌桶中存放，如果令牌桶满了则多余的令牌会被直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行；如果桶空了，那么尝试取令牌的请求 会被直接丢弃。

令牌桶算法就能够将所有 的请求平均分不到时间区间内，又能接受服务器能够承受范围内的突发请求，一次是目前使用广泛的一种限流算法。

开源的限流项目：

Google 的开源项目 guava 提供了 RateLimiter 类，实现了单点的令牌桶限流。

限流策略：多维防护+纵身防御

常见的三种：限制请求数，限制并发连接数 （请求频率），限制传输速度（请求体积）

各层级限流：

全局统一接入：

google 叫 GFE，baidu 是BFE，jd 叫 GFE，这类产品会将公司所有对外流量进行统计的接入呵呵调度，同时具备较强的通用防护能力，比如抗 D,WAF等。

熔断：

熔断的本质是一个过载保护机制。互联网系统中通常是：当下游服务因为访问压力过大而响应变慢或者失败，上游服务为了保护自己以及系统整体的可用性，可以暂时切断对下游服务的调用。

熔断的思路：

中心思想：量力而行。没有奇迹会发生，什么样的性能撑多少流量是固定的。

四个步骤：

1.定一个识别是否处于"不可用"状态的策略；

2.切断联系

3.定义一个识别是否处于'可用'状态的策略，并尝试探测；

4.重新恢复正常

如何识别是否处于不正常的策略：

1.是不是能调通

2.如果能够调通，耗时是不是超过预期的长

由于网络并不是100%的可靠，所以不能将瞬时异常等同于系统不可用。

如何解决这个问题呢：时间窗口，在某个时间段内 的情况

比如：

阈值：在10s 内出现100次无法连接或者出现大于100次大于5s 的请求

百分比：在10s 内有30%的请求无法连接或者30%的请求大 于5s。

切断联系：

切断联系要尽可能的果断，既然已经认定了对方不可用，那么索性默认失败，避免作无用功，也可以缓解对方的压力。

定义一个识别是否处于可用的状态的策略，并尝试探测

切断联系后，功能的完整性必然会受到影响，所以还是要尽快恢复回来，以提供完整的服务能力。如何自动的识别依赖系统是否可用呢。可以考虑的策略如下：

一般来说 这个策略与识别不可用的策略类似，是个反向指标：

 阈值。比如，在 10 秒内出现 100 次“调用成功”并且耗时都小于 1 秒。

百分比。比如，在 10 秒内有 95% 请求“调用成功”并且 98% 的请求小于 1 秒。

但是验证可用是个复杂的过程：

1.按照一定的比例流量去验证；

2.如果在整个通信框架都是统一的情况下，可以统一给每个系统增加一个专门用于验证程序健康状态的检测的独立接口。这个接口额外可以多返回一些系统负载信息用于判断健康状态，如 CPU、I/O 的情况等。

重新恢复正常

一旦通过了衡量可否可用的验证，整个系统就恢复了正常的状态。重新开启不可用策略。这样整体就是一个循环。

做熔断的最佳实践

什么场景最适合做熔断

一个事物在不同的场景里会发挥出不同的效果。以下是我能想到最适合熔断发挥更大优势的几个场景：

• 所依赖的系统本身是一个共享系统，当前客户端只是其中的一个客户端。这是因为，如果其它客户端进行胡乱调用也会影响到你的调用。

• 所以依赖的系统被部署在一个共享环境中（资源未做隔离），并不独占使用。比如，和某个高负荷的数据库在同一台服务器上。

• 所依赖的系统是一个经常会迭代更新的服务。这点也意味着，越“敏捷”的系统越需要“熔断”。

• 当前所在的系统流量大小是不确定的。比如，一个电商网站的流量波动会很大，你能抗住突增的流量不代表所依赖的后端系统也能抗住。这点也反映出了我们在软件设计中带着“面向怀疑”的心态的重要性。

需要注意的地方：

1.依赖系统的个别节点异常不等于所有的节点异常

2.熔断是最后的选择，优先使用降级或者限流的方案。因为'部分胜于无'，虽然无法提供完整的服务，但尽可能的降低影响。比如，抛弃非核心业务，友好提示等；