BBR启示:从拥塞控制到过载保护

距离上一篇记录过载保护的文章再看过载保护,已经过去有6年多了,回看那一篇文章,未免显得青涩,大部分都是错误的

文章核心理论集中在“控制任务队列长度”来规避过载,根据压测得出过载根因:并发上升 → 任务队列长度剧增 → 资源占用加剧 → 响应时间线性增加

看似没啥问题,但是压测是基于grpc服务和net/http服务的

img

net/http服务显然没有队列概念。grpc也没有内置队列,它主要依赖 HTTP/2 多路复用,在收到请求后就会启动相应的 Goroutine 进行处理

这种模型的最大问题的问题,是请求的处理顺序,完全依赖于协程调度器的策略,当过载发生的时候,无法判断这个请求在调度器里面等待了多久,是否有必要去处理

过载保护

在互联网发展了这么多年,已经不是摸黑过河了,基本上都有标准答案了(客户端的过载保护不是本文重点,在附录中列举一下)

不管是net/http还是grpc,如果需要请求排队或者进行限流,需要自行在handler套一层队列来防止过载,如下,多个Worker从Queue中消费conn:

sequenceDiagram
    participant L as ListenAndServe
    participant A as accept
    participant Q as Queue
    participant W as 每个Worker
    participant G as Goroutine

    L ->> A: 新请求 conn
    A ->> Q: 放入队列
    W ->> Q: 获取最多100个conn
    W ->> G: 对每个Conn创建Goroutine处理
    G ->> W: 处理完成
    W ->> Q: 继续获取conn
  • 引入了队列后,如果队列满了,可以直接丢弃

  • 并且在Worker获取队列中请求的时候,如果请求已经超时,可以直接丢弃

因此我以前总结的限流策略,实际上是动态调整允许同时进入的并发请求数阀值,这是错误的,正确的限流策略,需要对过载模型有深入了解,这也是本文的重点

BBR论文部分翻译

原文是Google 2017 的论文:

Cardwell N, Cheng Y, Gunn CS, Yeganeh SH, Jacobson V. BBR: congestion-based congestion control. Communications of the ACM. 2017 Jan 23;60(2):58-66.

论文副标题:Measuring Bottleneck Bandwidth and Round-trip propagation time(测量瓶颈带宽和往返传输时间)。

BBR的标题也是来自于副标题加黑部分

原文的排版实际上很糟糕,这一篇翻译的比较好

https://arthurchiao.art/blog/bbr-paper-zh/#1-%E6%8B%A5%E5%A1%9E%E5%92%8C%E7%93%B6%E9%A2%88congestion-and-bottlenecks

1 拥塞和瓶颈(Congestion and Bottlenecks)

1.1 两个物理特性:传输时延(RTprop)和瓶颈带宽(BtlBw)

对于一个(全双工)TCP 连接,在任意时刻,它在每个方向都有且只有一段最慢的链路 (exactly one slowest link)或称瓶颈(bottleneck)。这一点很重要,因为:

  • 瓶颈决定了连接的最大数据传输速率。这是不可压缩流(incompressible flow)的一个常规特性。

    例如,考虑交通高峰期的一个六车道高速公路,一起交通事故使其中一段变成了单车道, 那么这整条高速公路的吞吐就不会超过那条唯一还在正常通车的车道的吞吐。

  • 瓶颈也是持久队列(persistent queues)形成的地方

    对于一条链路,只有当它的离开速率(departure rate)大于到达速率(arrival rate)时,这个队列才会开始收缩。对于一条有多段链路、运行在最大传输速率的连 接(connection),除瓶颈点之外的地方都有更大的离开速率,因此队列会朝着瓶颈 移动(migrate to the bottleneck)。

不管一条连接会经过多少条链路,以及每条链路的速度是多少,从 TCP 的角度来看, 任何一条复杂路径的行为,与 RTT(round-trip time)及瓶颈速率相同的单条链路的行为是一样的。 换句话说,以下两个物理特性决定了传输的性能

  • RTprop (round-trip propagation time):往返传输时间
  • BtlBw (bottleneck bandwidth):瓶颈带宽

如果网络路径是一条物理管道,那 RTprop 就是管道的长度,而 BtlBw 则是管道最窄处的直径

1.2 传输时延/瓶颈带宽与 inflight 数据量的关系

图 1 展示了 inflight 数据量(已发送但还未被确认的数据量)不断增大时, RTT 和传输速率(delivery rate)的变化情况:

直观上,这张图想解释的是:随着正在传输中的数据的不断增多,传输延迟和传输速率将如何变化。 难点在于二者并没有简单的关系可以表示。不仅如此,后文还将看到二者甚至不可同 时测量 —— 就像量子力学中位置和动量不可同时测量。 译注。

Fig 1. Delivery rate and RTT vs. inflight data

  • 蓝线展示 RTprop 限制,
  • 绿线展示 BtlBw 限制,
  • 红线是瓶颈缓冲区(bottleneck buffer)

横轴表示 inflight 数据量,关键的点有三个,依次为 0 -> BDP -> BDP+BtlneckBuffSize, 后两个点做垂线,将整个空间分为了三个部分:

  1. (0, BDP):这个区间内,应用(客户端)发送的数据并未占满瓶颈带宽(容量),因此称为 应用受限(app limited)区域;
  2. (BDP, BDP+BtlneckBuffSize):这个区间内,已经达到链路瓶颈容量,但还未超过 瓶颈容量+缓冲区容量,此时应用能发送的数据量主要受带宽限制, 因此称为带宽受限(bandwidth limited)区域;
  3. (BDP+BtlneckBuffSize, infinity):这个区间内,实际发送速率已经超过瓶颈容量+缓冲区容量 ,多出来的数据会被丢弃,缓冲区大小决定了丢包多少,因此称为缓冲区受限(buffer limited)区域。

以上三者,也可以更直白地称为应用不足、带宽不足、缓冲区不足区域。 译注。

1.3 以上关系的进一步解释

我们来更具体地看一下传输时延(RTprop)和瓶颈带宽(BtlBw)与与 inflight 数据量呈现以上关系:

  1. inflight 数据量在 0 -> BDP 区间内时,发送的数据还未达到瓶颈容量,此时,

    1. 往返时间不变:对应上半部分图,因为此时还未达到瓶颈带宽,链路不会随数据量增加而带来额外延迟;
    2. 传输速率线性增大:对应下半部分图;

    因此,这个阶段的行为由 RTprop 决定。

  2. inflight 数据量刚好等于 BDP 时,

    1. 两条限制线相交的点称为 BDP 点,这也是 BDP(bandwidth-delay product,带宽-延迟乘积)这个名称的由来;
    2. 此时可以算出:inflight = BtlBw × RTprop
  3. inflight 大于 BDP 之后,管道就满了(超过瓶颈带宽)

    1. 超过瓶颈带宽的数据就会形成一个队列(queue),堆积在链路瓶颈处,然后
    2. RTT 将随着 inflight 数据的增加而线性增加,如上半部分图所示。
  4. inflight 继续增大,超过 BDP+BtlneckBuffSize 之后,即超过链路瓶颈所支持的最大缓冲区之后,就开始丢包。

灰色区域是不可达的,因为它违反了至少其中一个限制。限制条件的不同导致了三个可行区域 (app-limited, bandwidth-limited, and buffer-limited)各自有不同的行为。

1.4 拥塞和拥塞控制的直观含义

再次给出图 1,

img

Fig 1. Delivery rate and RTT vs. inflight data

直观上来说, 拥塞(congestion)就是 inflight 数据量持续向右侧偏离 BDP 线的行为, 而拥塞控制(congestion control)就是各种在平均程度上控制这种偏离程度的方案或算法。

1.5 基于丢包的拥塞控制工作机制

基于丢包的拥塞控制工作在 bandwidth-limited 区域的右侧,依靠:

  1. 很高的延迟,以及
  2. 频繁的丢包

将连接的传输速率维持在全速瓶颈带宽(full bottleneck bandwidth)。

  • 在内存很贵的年代,瓶颈链路的缓冲区只比 BDP 略大,这使得 基于丢包的拥塞控制导致的额外延迟很小
  • 随着内存越来越便宜,缓冲区已经比 ISP 链路的 BDP 要大上几个数量级了, 其结果是,bufferbloat 导致的 RTT 达到了秒级,而不再是毫秒级9。

1.6 更好的工作机制及存在的挑战

Bandwidth-limited 区域的左侧边界是比右侧更好的一个拥塞控制点。

  • 1979 年,Leonard Kleinrock16 证明了这个点是最优的, 能最大化传输速率、最小化延迟和丢包,不管是对于单个连接还是整个网络8。
  • 不幸的是,大约在同一时间,Jeffrey M. Jaffe14 证明了 不存在能收敛到这个点的分布式算法。这个结果使得研究方向从寻找一个能达到 Kleinrock 最佳工作点(operating point)的分布式算法,转向了对不同拥塞控制方式的研究。

在 Google,我们团队每天都会花数小时来分析从世界各地收集上来的 TCP 包头, 探究各种异常和反常现象背后的意义。

  • 第一步通常是寻找基本的路径特性 RTprop 和 BtlBw。
  • 能从跟踪信息中拿到这些数据这一事实,说明 Jaffe 的结论可能并没有看上去那么悲观。 Jaffe 的结果在本质上具有测量模糊性(fundamental measurement ambiguities),例 如,测量到的 RTT 增加是由于路径长度变化导致的,还是瓶颈带宽变小导致的,还是另 一个连接的流量积压、延迟增加导致的。
  • 虽然无法让任何单个测量参数变得很精确,但一个连接随着时间变化的行为 还是能清晰地反映出某些东西,也预示着用于解决这种模糊性的测量策略是可行的。

1.7 BBR:基于对两个参数(RTprop、BtlBw)的测量实现拥塞控制

组合这些测量指标(measurements),再引入一个健壮的伺服系统 (基于控制系统领域的近期进展) 12,我们便得到一个能针对对真实拥塞 —— 而非丢包或延迟 —— 做出反应的 分布式拥塞控制协议,能以很大概率收敛到 Kleinrock 的最优工作点。

我们的三年努力也正是从这里开始:试图基于对如下刻画一条路径的两个参数的测量, 来实现一种拥塞控制机制,

  • 瓶颈带宽(Bottleneck Bandwidth)
  • 往返传输时间(Round-trip propagation time)

2 瓶颈的数学表示(Characterizing the Bottleneck)

2.1 最小化缓冲区积压(或最高吞吐+最低延迟)需满足的条件

当一个连接满足以下两个条件时,它将运行在最高吞吐和最低延迟状态:

  1. 速率平衡(rate balance):瓶颈链路的数据包到达速率刚好等于瓶颈带宽 BtlBw

    这个条件保证了链路瓶颈已达到 100% 利用率。

  2. 管道填满(full pipe):传输中的总数据(inflight)等于 BDP(= BtlBw × RTprop)。

    这个条件保证了有恰好足够的数据,既不会产生瓶颈饥饿(bottleneck starvation), 又不会产生管道溢出(overfill the pipe)。

需要注意,

  • 仅凭 rate balance 一个条件并不能确保没有积压

    例如,某个连接在一个 BDP=5 的链路上,开始时它发送了 10 个包组成的 Initial Window,之后就一直稳定运行在瓶颈速率上。那么,在这个链路此后的行为就是:

    • 稳定运行在瓶颈速率上
    • 稳定有 5 个包的积压(排队)
  • 类似地,仅凭 full pipe 一个条件也无法确保没有积压

    例如,如果某个连接以 BDP/2突发方式发送一个 BDP 的数据, 那仍然能达到瓶颈利用率,但却会产生平均 BDP/4 的瓶颈积压。

在链路瓶颈以及整条路径上最小化积压的唯一方式是同时满足以上两个条件。

BufferBloat问题

总结一下,BBR的思路是解决BufferBloat问题

如果将网络路径视为一条管道,那么RTT(下图的Delay)就是管道的长度,下图的Bandwidth是管道的直径,而BDP表示的则是管道的容量大小。

在管道被灌满了之后, 继续发送数据就会导致数据被堆积在交换节点的buffer中,形成堆积的队列。同样以水管来类比的话,Bottleneck 就是下面那根比较细的水管,如果你的发送速率大于它(也就是上面那根比较粗的水管),数据就会累积在水管前的蓄水池中(也就是交换节点的buffer)

  • 一开始,注水的速度小于瓶颈链路的管道大小,整条链路的管道还没有被灌满,所以你发送数据的速度越快,实际的吞吐量就会越大

    也就是BBR论文应用受限(app limited)区域。

  • 接着,下图的Buffer filling,整条管道已经灌满了,发送速率就会受限于Bottleneck Bandwidth的大小,因为无论你发送多少数据,都会被卡在瓶颈处的缓存Buffer中,排着队等待被发送出去,所以发送方可能很卖力,但是接收方接收到的速率还是维持不变。

    也就是BBR论文带宽受限(bandwidth limited)区域。

  • 最后,下图的Buffer overflow,中间的节点无法再接受更多的数据,就会开始随机drop一部分新接收的数据(蓄水池已满,水从蓄水池中溢出来了)。

    也就是BBR论文缓冲区受限(buffer limited)区域。

    对TCP来说,也就产生了丢包(packet loss)。 CUBIC等基于丢包的算法就在此时开始降低发送的速率。

image-20250401182534882

从BufferBloat的角度看过载

过载保护

拥塞控制和过载保护的不同

每个请求耗时不一样

Buffer相对于处理能力会大得多,有可能完全在处理无效请求

附录

客户端的过载保护

负载均衡

上一篇文章总结的根据响应时间或同时进入并发请求数进行动态反馈负载均衡

这是错误的,每个请求的花费是不相同的

一般场景下,round robin即可,复杂的负载均衡策略,我博客也提过一些

重点在于如何解决每个请求花费不同,导致的下游不均衡问题呢?

有个简单的办法是分布式Work Steal,下游由于队列满或队列超时直接拒绝,上游服务在请求未超时的时候重新投递,但是要注意重新投递的最大次数,防止流量放大造成的雪崩

熔断与退避

上一篇文章没有细化熔断策略

实际上熔断是和退避一起的,下游故障进行熔断是很容易的,但是如何进行恢复就是一个问题了

以tcp为例,丢包重传计数器是2的指数倍。下游的熔断恢复也应该遵循该策略,以避免无效的资源消耗