Python中排队理论:吞吐量与延迟

在本文中,了解高级容量估计和工作负载优化所需的排队理论基础知识。

到处都是排队!

  • Java 的 fork-join 池使用具有工作窃取机制的多个队列。
  • 相比之下,所有老式的Java 线程池默认都使用无界队列——导致延迟和内存问题。
  • Resilience4J 有许多涉及排队的实现,例如 bulkheads.
  • 所有常见的发布-订阅代理都涉及队列的使用——包括 Kafka、RabbitMQ 等。Redis也提供发布-订阅机制。
  • 当然,一般的操作系统都有多个内置的工作队列,包括CPU运行队列,磁盘IO队列,网络接口有环形缓冲区等等。

队列是当今软件中无处不在的内置机制。不熟悉队列理论的基础知识将阻碍您理解延迟和吞吐量之间的关系、高级容量估计和工作负载优化。了解队列模型的内部原理其实并不难掌握。在本文中,我将总结软件工程师在其领域更有效率所需的基本知识。

队列术语说明

  • 到达率:(lambda)——新工作项到达队列的速率。
  • 等待时间:(W)——系统中每个工作项花费的总时间。通常由两个元素组成。在队列中花费的时间(由前面的工作项决定)和服务花费的时间。
  • 服务器:(c)——指并行化级别。
  • 服务时间:(tau=1/mu)— 处理单个工作项所需的时间。它通常被翻译成速率,也被称为出发率。
  • 出发率:(mu)— 物品的处理率。
  • 利用率:(rho=lambda/mu)——简单描述到达率和离开率之间的比率。
  • 正在服务的项目数 (L):系统中的元素总数,包括正在处理和在队列中等待的元素。

在软件工程中,我们在谈论性​​能时使用的术语略有不同。您可以找到排队理论中使用的符号与其对应符号之间的映射:

  • 到达率= 吞吐量/负载:    根据上下文区分两者是很好的。到达率通常称为负载、平均负载
  • 等待时间=延迟:    他们都没有区分排队的等待时间和因被服务而等待的时间。
  • 服务器 =执行器/处理器:    我们主要指的是 CPU/worker 的数量
  • 服务时间 =执行时间/持续时间 :   以完成一项任务所需的时间衡量。通常与延迟混合。
  • 利用率 = 利用率:    实际上,利用率的计算方法多种多样。通常,利用率是指给定时间窗口(例如 5 秒)内未使用的 CPU 时钟周期与已使用的 CPU 时钟周期之比。
  • 队列长度  =饱和:    它们通常表示同一件事:系统必须应对的额外工作量是多少?“饱和”一词最流行的用法来自Google SRE 书中提到的四个黄金信号。

简单用例
1、顺序
现在,让我们设想一个类似上面的简单队列。

队列中有 8 个项目,没有新项目到达,执行时间为 100 毫秒。

吞吐量和延迟是多少?
我们可以在每 100 毫秒内生成一个队列消息,这样就有 10 个/秒。
延迟时间的确定比较麻烦。第一个项目的延迟时间为 100 毫秒。最后一个项目需要处理之前的所有项目,因此其延迟时间为 8 * 100 毫秒。
因此,延迟时间最小为 100 毫秒,最大为 800 毫秒,平均为 450 毫秒。


2、并行Parallel
让我们尝试增加执行器的数量。如果我们再添加一个,之前的用例会有什么变化?

现在,我们每100 毫秒可以生成 2 个工作项,因此吞吐量翻倍至20/s 。处理第一个项目需要100 毫秒,处理最后一个项目需要400 毫秒(我们可以在每个100 毫秒周期内处理 2 个项目)。因此,最小延迟为100 毫秒,最大延迟为400 毫秒,平均值为250 毫秒。

一个立即需要注意的重要观察是,我们所经历的延迟取决于我们在队列中的位置:如果队列为空或几乎为空 — —扩展对延迟几乎没有影响。正如我们将在接下来的部分中看到的那样,排队的工作项数量增加也有其负面影响。

3、管道Pipeline
如果我们以不同于上例的方式划分工作,情况会有什么变化?

假设我们现在有两个队列通过两个执行器相互连接。总体执行时间将与以前相同。划分工作会对延迟/吞吐量产生影响吗?

现在,我们每50 毫秒可以生成 1 个工作项,吞吐量翻倍至20 /s。第一个工作项仍需要100毫秒才能通过,但最后一个工作项只需要450 毫秒。想象一下,在第一个工作项处理完毕后,我们将每50 毫秒看到一个新的队列消息,直到队列为空。最小延迟为100 毫秒,最大延迟为450 毫秒,平均值为275 毫秒。

这就是反应库的强大之处。即使你可能认为你编写了顺序代码,但它并不是按原样执行的。只有你的因果关系声明是顺序的。你声明了一个执行管道,它将你的整体工作负载分成更小的部分并并行运行。

我可以举出很多例子,比如 Kotlin 协程、Java 可完成的未来、ReactiveX 库、Akka 等。

上面的观察仍然是正确的:如果我们的队列只有几个元素,延迟就不会改变

从上面的延迟数字可以看出,最小值不会过多地暴露队列长度。另一方面,最大延迟可以指示饱和度:它告诉您整个系统在队列上花费了多少时间。

如果您对执行持续时间不太了解,那么了解黑盒系统饱和度的一种方法是关注:

  • 最大延迟与最小延迟


  • p99(延迟) — 平均延迟

高级用例
为了能够研究更高级的用例,我们正在改变思路。我将在接下来的几个部分中使用这个简单的建模库。

稳定和不稳定的情况
如果利用率高于100%会发生什么?在这些情况下,到达率大于我们的整体吞吐量。它如何影响我们的延迟?我们的到达间隔(100ms )将比我们的执行间隔( 120ms )略小。

import matplotlib.pyplot as plt
import numpy as np
from src.queue import Queue

%matplotlib inline
plt.rcParams["figure.figsize"] = (12, 6) # (w, h)

SAMPLE_SIZE = 100
ARRIVAL_INTERVAL = 100
EXECUTION_INTERVAL = 120
EXECUTORS = 1

inter_arrival_time = np.full(shape=SAMPLE_SIZE, dtype=int, fill_value=ARRIVAL_INTERVAL)

queue = Queue(inter_arrival_time, np.full(shape=SAMPLE_SIZE, dtype=int, fill_value=EXECUTION_INTERVAL), executors=EXECUTORS)
queue.process()

fig, (queue_length, latency) = plt.subplots(1, 2)

queue_length.set_title(
"Queue length")
queue_length.set(xlabel=r'Time ($ms$)', ylabel=r'Length ($L$)')
queue_length.plot(*zip(*queue.length_with_timestamps), alpha=0.5)

latency.set_title(
"Latency")
latency.set(xlabel='Index', ylabel=r'Duration ($ms$)')
latency.plot(queue.wait_times, alpha=0.5)

fig.tight_layout()
plt.show()

print(f'Latency min: {queue.wait_times.min()}')
print(f'Latency average: {queue.wait_times.mean()}')
print(f'Latency max: {queue.wait_times.max()}')

运行结果:

  • 队列长度显示元素数量呈线性增长。达到 SAMPLE_SIZE 后,到达率降为零,队列长度开始线性递减。时间窗口等于处理所有信息所需的总时间:执行时间 * SAMPLE_SIZE。
  • 另外我们的延迟在持续增加。

如果到达率大于吞吐量,系统就必须采取行动。您有两种选择:

  • 缩减执行器:还记得我之前说过的通过扩大规模来减少延迟吗?增加执行器数量将改善延迟,直到利用率达到 100%(例如,您的系统趋于稳定)。在此之前,扩大规模无法改善延迟。
  • 使用速率限制和拒绝新到达:实际上,可以通过限制队列大小来实现这一点。

扩大规模
让我们看看在这种情况下,当我们扩展执行器的数量时会发生什么:

from ipywidgets import interactive
from src.queue import timestamps_to_intervals

def display_queue_metrics(executrs):
    inter_arrival_time = np.full(shape=SAMPLE_SIZE, dtype=int, fill_value=ARRIVAL_INTERVAL)

    fig, (queue_length, wait_times) = plt.subplots(1, 2)

    queue = Queue(inter_arrival_time, np.full(shape=SAMPLE_SIZE, dtype=int, fill_value=EXECUTION_INTERVAL), executors=executrs)
    queue.process()
    
    wait_times.set_title("Latency")
    wait_times.set(xlabel='Time', ylabel=r'Duration ($ms$)')
    wait_times.plot(queue.wait_times, alpha=0.5)
    
    queue_length.set_title(
"Queue length")
    queue_length.set(xlabel='Time', ylabel=r'Length ($L$)')
    queue_length.plot(*zip(*queue.length_with_timestamps), alpha=0.5)
    
    fig.tight_layout()
    plt.show()

interactive_plot = interactive(
    display_queue_metrics,
    executrs=(1, 8)
)

interactive_plot

当扩展到一定程度,利用率趋于稳定时,饱和现象就会消除。延迟与执行持续时间相关,增加更多执行器也不会带来更多收益。在这种情况下,延迟会有一些波动,但主要由执行时长决定。

这就是为什么在没有队列大小指标的情况下,p99(延迟) - avg(latency) 是饱和度的良好指标。

容量规划:从 DAU 到吞吐量
我们如何使用排队模型来预测工作负载?这项任务的复杂性源于到达分布的未知因素:我应该如何对用户行为进行建模?因为我们系统的整体使用情况并不恒定。通常周末或下班时间是高峰期。如果我们观察传入的请求,它们通常会形成波浪状模式,峰值负载可能是平均值的两倍。更糟糕的是——两侧的陡度通常不同。这就是利特尔定律发挥作用的地方。

好的,现在让我们假设我们有 100,000 DAU。我们如何将其转换为任何有意义的吞吐量?假设思考时间为z且平均延迟为r,则每个请求需要的总延迟为z+r。通常,在边缘,r可以从标准Web 性能指标中得出。一般来说,它应该小于2 秒。估计的思考时间大约是该数字的两倍,因此4 秒是一个很好的“估计”,这给了我们最小延迟z+r = 6 秒。如果每个“用户”均匀分布在 24 小时内,那么每分钟的窗口将为我们提供L = 70 个用户。吞吐量应该与我们的到达率相匹配,因此我们需要利特尔定律来了解如何根据给定的数字计算到达率。

利特尔定律
利特尔定律简单地说就是:L = lambda * W。

这意味着在上述情况下,lambda = L / W,或者在我们的例子中,lambda = 70/(6*60)。因此,我们预计该系统的平均操作数约为0.2 ops/min 。

注意:始终使用真实数字验证并重新评估您的估计,以便对模型的准确性有一个整体的印象。