排队论公式笔记

2023-08-04

服务速率 $$\mu$$

到达速率 $$\lambda$$

是不是到达速率小于服务速率，就不用排队了？不是的。到达速率是单位时间内，平均到达的请求个数。但是到达是有分布的，并不是说来一个请求，固定多少间隔，再来一个请求这种方式的平均，而是有可能短时间到达了多个，而一段时间没有到达。最终计算期望值，得到的到达速率。关于请求到达的分布的假设是泊松分布。

排队是一直都在发生的，只是概率上的不同，这个概率正好是 $$\frac \lambda \mu$$

到达速率必须小于服务速率，也就是 $$\lambda < \mu $$，否则就表示服务速度跟不上，排队的队列越来越长，系统雪崩。

使用率和 idle 率

使用率 $$\frac \lambda \mu$$

idle 率 $$1 - \frac \lambda \mu $$

如果用概率的角度来解释，当一个请求到达时，当前排队请求数量是0的概率，也就是等于 idle 率。

换成计算机里面的语言，也就是"说人话"：系统的吞吐的理论上限 $$\mu $$ ，当前的吞吐QPS = $$\lambda $$。

平均队列长度

$$ \frac \lambda {\mu - \lambda} $$

平均队列长度的推导是用队列长度为0、队列长度为1、队列长度为2 ... 的概率得到期望值求得的。

这个推导其实不难理解。可以拿抽奖来做一个类比，抽中的概率是 P，那么抽一次就抽中的概率是多少？是 P。抽到第二次抽中的概率是多少？(1-P)*P。第三次才抽中的概率是多少 (1-P)^2*P... 第n次中的概率是多少？(1-P)^n * P。那么，平均需要多少次可以抽中？就是算这个期望。

平均队列长度怎么算的？就跟算平均抽多少次可以抽中一样，只不过 P 和 1-P 就是前面公式中的 idle 率使用率。

Little's Law

$$ L = \lambda * W $$

Little's Law 是搞 IT 的人都应该知道的一个公式，非常重要。

一个朴素的理解方式是：单位时间会进来 $$\lambda$$ 个请求，每个请求处理的耗时是 W，那么当前系统内逗留的请求数是多少，或者说系统容量是多少？也就是两者相乘。在排队论里边，L 就是队列长度。W 是处理时间，也就是排队时间 + 服务时间。

平均延迟(响应时间)公式

$$ W = \frac 1 {\mu - \lambda} $$

网上写请求系统逗留时间，应该服从 $$\mu - \lambda $$ 的负指数分布，然后通过负指数分布的期望推导出来 W。有了 L 和 W 就可以推出它们的关系，从而得到 Little's Law。

我没法理解这个处理时间服从负指数分布，"因为请求到达服务泊松分布，所以处理时间服从负指数分布"，对我来说太抽象了...

所以我就直接从 Little's Law 推导出来平均延迟，也就是在这里把 Little's Law 当作公理使用，那么 W 就等于 $$ \frac L \lambda $$

其中，前面知道了队列长度 L 是 $$\frac \lambda {\mu - \lambda} $$

那么 W 就是 $$W = \frac 1 {\mu - \lambda} $$

平均排队延迟

$$\frac \lambda {\mu * ({\mu - \lambda})} $$

请求延迟等于排队延迟加上处理时间，服务速率是 $$\mu $$，所以纯粹的处理时间是 $$\frac 1 \mu $$

所以排队延迟就等于总的延迟减去处理时间，也就是

$$ {\frac 1 {\mu - \lambda}} - {\frac 1 \mu} $$，也就是

$$ {\frac 1 {\mu - \lambda}} - {\frac 1 \mu} == \frac {\mu - ({\mu - \lambda})} {\mu ({\mu - \lambda})} == \frac \lambda {\mu ({\mu - \lambda})} $$

平均等待队列长度

$$ \frac {\lambda^2} {\mu * ({\mu - \lambda})} $$

Little's Law 是既适用于整体的 L，也适合于排队的 L 的。也就是

$$ Lq = \lambda * Wq $$

所以从平均排队延迟得到平均等待队列长度，只需要乘以一个 $$\lambda $$

使用率与响应时间

$$ \frac 1 {\mu * (1 - \rho)} $$

最后这个公式就是我们前一篇提到的，并不是说 CPU 利用低的时候，就不排队 or CPU 没使用满，那么 CPU 就不是瓶颈。

响应时间公式是

$$ W = \frac 1 {\mu - \lambda} $$

其中 $$\frac \lambda \mu $$ 是使用率，如果我们用 $$\rho $$ 表示，那么用 $$\lambda = \mu * \rho $$ 替换掉 W 里面的 $$\lambda $$

则可以得到使用率与响应时间的关系。

这个公式是 M/M/1 的公式，也就是服务台个数为1的时候。我看到网上写，推广到 M/M/c 多个服务台c 的场景，使用率跟响应时间大致有这样一个关系：

$$ W \propto {\frac 1 {1 - \rho^c}} $$

如果要记两个公式，那么就记 little's law 和延迟公式，剩下的都可以从这两个公式推导。

最后，看一看具体例子。

假设服么器一秒钟理论上限处理 300 个请求，也就是 $$ \mu = 300$$，当前的使用率 20% 50% 80% 90% 95% 99% 会发生什么？

20% 时，响应延迟 4.16667ms, 其中排队延迟 0.8333ms ... 排队延迟占比 20%
50% 时，响应延迟 6.66667ms, 其中排队延迟 3.3333ms ... 排队延迟占比 50%
80% 时，响应延迟 16.667ms, 其中排队延迟 13.3333ms .. 排队延迟占比 80%
90% 时，响应延迟 33.333ms, 其中排队延迟 30ms
95% 时，响应延迟 66.667ms，其中排队延迟 63.333ms
99% 时，响应延迟 333.333ms，其中排队延迟 330ms ... 排队延迟占比 99%

看出来什么了么？使用率高了之后，请求在系统中大部分耗时是在排队！