令牌桶算法

是一个存放固定容量令牌的桶,按照固定速率往桶里添加令牌。令牌桶算法的描述如下:

  • 假设限制2r/s,则按照500毫秒的固定速率往桶中添加令牌。
  • 桶中最多存放 b 个令牌,当桶满时,新添加的令牌被丢弃或拒绝。
  • 当一个 n 个字节大小的数据包到达,将从桶中删除n 个令牌,接着数据包被发送到网络上。
  • 如果桶中的令牌不足 n 个,则不会删除令牌,且该数据包将被限流(要么丢弃,要么缓冲区等待)。

令牌桶速率限制算法: golang.org/x/time/rate

漏桶算法

作为计量工具(The Leaky Bucket Algorithm as a Meter)时,可以用于流量整形(Traffic Shaping)和流量控制(TrafficPolicing),漏桶算法的描述如下:

  • 一个固定容量的漏桶,按照常量固定速率流出水滴。
  • 如果桶是空的,则不需流出水滴。
  • 可以以任意速率流入水滴到漏桶。
  • 如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。

漏桶率限制算法: go.uber.org/ratelimit

过载保护

令牌桶与漏桶的缺点

漏斗桶/令牌桶确实能够保护系统不被拖垮, 但不管漏斗桶还是令牌桶, 其防护思路都是设定一个指标, 当超过该指标后就阻止或减少流量的继续进入,当系统负载降低到某一水平后则恢复流量的进入。但其通常都是被动的,其实际效果取决于限流阈值设置是否合理,但往往设置合理不是一件容易的事情。

  • 集群增加机器或者减少机器限流阈值是否要重新设置?
  • 设置限流阈值的依据是什么?
  • 人力运维成本是否过高?
  • 当调用方反馈429时, 这个时候重新设置限流, 其实流量高峰已经过了重新评估限流是否有意义?

这些其实都是采用漏斗桶/令牌桶的缺点, 总体来说就是太被动, 不能快速适应流量变化。 因此我们需要一种自适应的限流算法,即: 过载保护,根据系统当前的负载自动丢弃流量。

过载保护方法

计算系统临近过载时的峰值吞吐作为限流的阈值来进行流量控制,达到系统保护。

  • 服务器临近过载时,主动抛弃一定量的负载,目标是自保。
  • 在系统稳定的前提下,保持系统的吞吐量。

利特尔法则

计算吞吐量:利特尔法则 L = λ * W

利特尔法则由麻省理工大学斯隆商学院(MIT Sloan School of Management)的教授 John Little﹐于 1961 年所提出与证明。它是一个有关提前期与在制品关系的简单数学公式,这一法则为精益生产的改善方向指明了道路。 —- MBA 智库百科 (mbalib.com)

如上图所示,如果我们开一个小店,平均每分钟进店 2 个客人(λ),每位客人从等待到完成交易需要 4 分钟(W),那我们店里能承载的客人数量就是 2 * 4 = 8 个人

同理,我们可以将 λ 当做 QPS, W 呢是每个请求需要花费的时间,那我们的系统的吞吐就是 L = λ * W ,所以我们可以使用利特尔法则来计算系统的吞吐量。

什么时候系统的吞吐量就是最大的吞吐量?

首先我们可以通过统计过去一段时间的数据,获取到平均每秒的请求量,也就是 QPS,以及请求的耗时时间,为了避免出现前面 900ms 一个请求都没有最后 100ms 请求特别多的情况,我们可以使用滑动窗口算法来进行统计。

最容易想到的就是我们从系统启动开始,就把这些值给保存下来,然后计算一个吞吐的最大值,用这个来表示我们的最大吞吐量就可以了。但是这样存在一个问题是,我们很多系统其实都不是独占一台机器的,一个物理机上面往往有很多服务,并且一般还存在一些超卖,所以可能第一个小时最大处理能力是 100,但是这台节点上其他服务实例同时都在抢占资源的时候,这个处理能力最多就只能到 80 了

所以我们需要一个数据来做启发阈值,只要这个指标达到了阈值那我们就进入流控当中。常见的选择一般是 CPU、Memory、System Load,这里我们以 CPU 为例

只要我们的 CPU 负载超过 80% 的时候,获取过去 5s 的最大吞吐数据,然后再统计当前系统中的请求数量,只要当前系统中的请求数大于最大吞吐那么我们就丢弃这个请求。

如何计算接近峰值时的系统吞吐?

  • CPU: 使用一个独立的线程采样,每隔 250ms 触发一次。在计算均值时,使用了简单滑动平均去除峰值的影响。
  • Inflight: 当前服务中正在进行的请求的数量。
  • Pass&RT: 最近5s,pass 为每100ms采样窗口内成功请求的数量,rt 为单个采样窗口中平均响应时间。

  • 我们使用 CPU 的滑动均值(CPU > 800)作为启发阈值,一旦触发进入到过载保护阶段,算法为:(pass* rt) < inflight
  • 限流效果生效后,CPU 会在临界值(800)附近抖动,如果不使用冷却时间,那么一个短时间的 CPU 下降就可能导致大量请求被放行,严重时会打满 CPU。
  • 在冷却时间后,重新判断阈值(CPU > 800 ),是否持续进入过载保护。

什么是限流

限流是指在一段时间内,定义某个客户或应用可以接收或处理多少个请求的技术。例如,通过限流,你可以过滤掉产生流量峰值的客户和微服务,或者可以确保你的应用程序在自动扩展(Auto Scaling)失效前都不会出现过载的情况。

  • 令牌桶、漏桶 针对单个节点,无法分布式限流。
  • QPS 限流
    • 不同的请求可能需要数量迥异的资源来处理。
    • 某种静态 QPS 限流不是特别准。
  • 给每个用户设置限制
    • 全局过载发生时候,针对某些“异常”进行控制。
    • 一定程度的“超卖”配额。
  • 按照优先级丢弃。
  • 拒绝请求也需要成本。

分布式限流

分布式限流,是为了控制某个应用全局的流量,而非真对单个节点纬度。

  • 单个大流量的接口,使用 redis 容易产生热点。
  • pre-request 模式对性能有一定影响,高频的网络往返。

思考:

  • 从获取单个 quota 升级成批量 quota。quota: 表示速率,获取后使用令牌桶算法来限制。

  • 每次心跳后,异步批量获取 quota,可以大大减少请求 redis 的频次,获取完以后本地消费,基于令牌桶拦截。
  • 每次申请的配额需要手动设定静态值略欠灵活,比如每次要20,还是50。

如何基于单个节点按需申请,并且避免出现不公平的现象? 初次使用默认值,一旦有过去历史窗口的数据,可以基于历史窗口数据进行 quota 请求。 思考:

  • 我们经常面临给一组用户划分稀有资源的问题,他们都享有等价的权利来获取资源,但是其中一些用户实际上只需要比其他用户少的资源。

那么我们如何来分配资源呢?一种在实际中广泛使用的分享技术称作“最大最小公平分享”(Max-Min Fairness)。 直观上,公平分享分配给每个用户想要的可以满足的最小需求,然后将没有使用的资源均匀的分配给需要‘大资源’的用户。 最大最小公平分配算法的形式化定义如下:

  • 资源按照需求递增的顺序进行分配。
  • 不存在用户得到的资源超过自己的需求。
  • 未得到满足的用户等价的分享资源。

限流的重要性

每个接口配置阈值,运营工作繁重,最简单的我们配置服务级别 quota,更细粒度的,我们可以根据不同重要性设定 quota,我们引入了重要性(criticality):

  • 最重要 CRITICAL_PLUS,为最终的要求预留的类型,拒绝这些请求会造成非常严重的用户可见的问题。
  • 重要 CRITICAL,生产任务发出的默认请求类型。拒绝这些请求也会造成用户可见的问题。但是可能没那么严重。
  • 可丢弃的 SHEDDABLE_PLUS 这些流量可以容忍某种程度的不可用性。这是批量任务发出的请求的默认值。这些请求通常可以过几分钟、几小时后重试。
  • 可丢弃的 SHEDDABLE 这些流量可能会经常遇到部分不可用情况,偶尔会完全不可用。

gRPC 系统之间,需要自动传递重要性信息。如果后端接受到请求 A,在处理过程中发出了请求 B 和 C 给其他后端,请求 B 和 C 会使用与 A 相同的重要性属性。

  • 全局配额不足时,优先拒绝低优先级的。
  • 全局配额,可以按照重要性分别设置。
  • 过载保护时,低优先级的请求先被拒绝。

熔断

断路器(Circuit Breakers): 为了限制操作的持续时间,我们可以使用超时,超时可以防止挂起操作并保证系统可以响应。因为我们处于高度动态的环境中,几乎不可能确定在每种情况下都能正常工作的准确的时间限制。断路器以现实世界的电子元件命名,因为它们的行为是都是相同的。断路器在分布式系统中非常有用,因为重复的故障可能会导致雪球效应,并使整个系统崩溃。

  • 服务依赖的资源出现大量错误。
  • 某个用户超过资源配额时,后端任务会快速拒绝请求,返回“配额不足”的错误,但是拒绝回复仍然会消耗一定资源。有可能后端忙着不停发送拒绝请求,导致过载。

如上图所示,熔断器存在三个状态:

  1. 关闭(closed): 关闭状态下没有触发断路保护,所有的请求都正常通行
  2. 打开(open): 当错误阈值触发之后,就进入开启状态,这个时候所有的流量都会被节流,不运行通行
  3. 半打开(half-open): 处于打开状态一段时间之后,会尝试尝试放行一个流量来探测当前 server 端是否可以接收新流量,如果这个没有问题就会进入关闭状态,如果有问题又会回到打开状态

Google SRE 过载保护算法

1
max(0, (requests - K*accepts) / (requests + 1))

算法如上所示,这个公式计算的是请求被丢弃的概率[3]

  • requests: 一段时间的请求数量
  • accepts: 成功的请求数量
  • K: 倍率,K 越小表示越激进,越小表示越容易被丢弃请求

这个算法的好处是不会直接一刀切的丢弃所有请求,而是计算出一个概率来进行判断,当成功的请求数量越少,K越小的时候 requests−K∗accepts 的值就越大,计算出的概率也就越大,表示这个请求被丢弃的概率越大

Gutter

基于熔断的 gutter kafka ,用于接管自动修复系统运行过程中的负载,这样只需要付出10%的资源就能解决部分系统可用性问题。 我们经常使用 failover 的思路,但是完整的 failover 需要翻倍的机器资源,平常不接受流量时,资源浪费。高负载情况下接管流量又不一定完整能接住。所以这里核心利用熔断的思路,是把抛弃的流量转移到 gutter 集群,如果 gutter 也接受不住的流量,重新回抛到主集群,最大力度来接受。

客户端流控

positive feedback: 用户总是积极重试,访问一个不可达的服务。

  • 客户端需要限制请求频次,retry backoff 做一定的请求退让。
  • 可以通过接口级别的error_details,挂载到每个 API 返回的响应里。

参考文章