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

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

到处都是排队！

  • 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 。

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