浅谈排队论

前进者-李

排队论（Queueing Theory），或称随机服务系统理论、排队理论，是数学运筹学的分支学科。它是研究服务系统中排队现象随机规律的学科。广泛应用于电信，交通工程，计算机网络、生产、运输、库存等各项资源共享的随机服务系统，和工厂，商店，办公室和医院的设计。

排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的最佳化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。（摘自维基百科）

（天通苑地铁早高峰入口处的排队。图来自网友老歌 ）

现在社会到处都有队列，队列无处不在。比如生活中的超市与机场，到工作中的Web服务器和数据库。因此，研究一下队列行为，还是很有帮助的。

问题在于排队行为实际上与我们直觉相背离。在实际生活中碰到的大多数排队现象，通常都是在充满不确定性和随机性的情况下发生的。这就是统计概率领域的话题了，而人类的思维能力无法很直观的来处理它。

在排队论领域有一些工具可以规避这种问题：一种结合可视化的计量方法可以弥补我们直觉上的不足。这篇文章会讨论一些我在阅读排队论时发现的比较有趣的东西。

产品开发中的排队

本文中提出的大多数观点都是基于 Donald G. Reinertsen 的《产品开发流程的原理 | The Principles of Product Development Flow》，顺便说一句，这本算是我所看过的关于产品开发流程写得最好的书。

在这本书中，Reinertsen 检查了在开发新产品时，组织可能会面临的挑战，并给出了一种计量经济学框架来应对这些挑战。这个框架系统性的推翻了我们在管理产品开发时的一些固有理念。比如说“应该消除方差”、“系统应该满负荷运转”以及“集中化控制有好处”等。这些都被基于经济原理的新观点所取代，而不再基于业务原理和个人直觉。

在 Reinertsen 的书中，其中心主题有一条就是关于排队的重要性。具体来说，Reinertsen 多次提到这样的现象：产品管理员往往忽略排队的问题，而只关注到时间线和效率。当然，对时间线和效率的度量对我们是有帮助，但是对于那些高度不确定的活动，比如产品开发来说，我们其实可以做的更好。队列就是一个更好的度量工具。最起码，它们非常重要，不容忽视。

虽然在 Reinertsen 的书中这些观点都应用于产品开发领域，不过许多观点同样也同样适用于其他出现排队和随机性的场合。比如说交通管理、百货商店以及饭店的厨房，还有服务器资源管理和软件架构等。接下来，我们详细阐述。

马尔可夫过程

就像我们之前所讨论的， 真实世界中产生排队的环境中同样也存在随机性。然而，我们不会讨论关于随机性的内容。在我们推论排队的过程中，所使用的最有用的工具就是基于随机性建模的马尔可夫过程。

马尔可夫过程是一段时间内随机事件的集合，具有以下两种独特而有趣的属性：

1、下一个事件迟早会发生

2、将来事件的发生不依赖于之前的事件，即无后效性。

下图描绘出一段时间内的马尔可夫过程：

(原图为交互图，可在原文查看)

马尔可夫过程和泊松过程都很适合用来给真实世界中的事件建模，其中泊松过程是一种连续时间的特殊马尔可夫过程。 我们可以用它们来模拟事件加入排队队列这一过程。

当我们使用马尔可夫过程来给入队事件建模时，比如说上报bug、餐馆的订单、HTTP请求等，都可以通过绘制累积图来表示：

(原图为交互图，可在原文查看)

这种图每次都会重新模拟一条新的马尔科夫链。不过，它的总体形状是一样的。

可视化队列

马尔可夫过程自身并不能形成排队，它只是一堆持续增长的任务。不过可以通过结合两种马尔可夫过程来制造出排队：其中到达过程不断产生任务，服务过程处理这些任务。

虽然服务过程也可以建模为马尔可夫过程，但它与到达过程却并不一样：当队列是空的情况下，服务过程什么事都不做。没有消费者，就没有什么事情需要做的。当任务到达的时候，服务过程会遵循马尔可夫过程准则来提供服务。

我们可以将两种过程叠加来绘制到达过程和服务过程：

(原图为交互图，可在原文查看)

如果我们将图中的到达过程去掉，剩下的就是到达过程与服务过程之间的那一小块区域。也就是队列：

(原图为交互图，可在原文查看)

这种可视化工具被称为累积流程图，非常适用于展示排队情况。其本质就是绘制出队列大小随着时间推移发生的变化，具有下面这些非常有用的属性：

• 对于任意时间变量 t，线条高度就代表当前时间的队列大小
• 对于任意队列大小 y，图中长条的宽度代表系统中完成单元任务所需要的时间，这个时间由任务在队列中的等待时间和处理时间合并而成。
• 到达过程的边缘坡度（上面的那条斜线）表现了系统对队列的加入请求。
• 服务过程的边缘坡度（下面）展现出服务过程处理任务的能力。
  

产能利用率最大化的问题

在了解可视化队列的机制之后，我们再来仔细看看这些数据究竟代表什么意思。上图中展示了具有相同频率的到达过程和服务过程而形成的排队。服务的能力与入队请求相匹配。

乍一看，创建这样一个队列似乎很合理：因为毕竟资源很昂贵，所以要将资源与请求准确的匹配——不多不少。让程序员或者客服人员闲坐着没有任何意义，对吧？

然而，如果你仔细看这种资源匹配产生的排队情况，你可能会注意到那些相对较宽的部分，这是由于服务进程被困在某个非常慢的任务上时，又有连续不断的任务请求加入而形成的。而且，这种情况并不会很快缓解。

这种现象被称为diffusion，大多数人都无法凭直觉来感知它（当然其中并不包括我——作者）：如果你将到达进程和服务进程的资源相匹配，你期望的可能是队列大小尽可能的接近0.但是实际情况不是这样。只要一个耗时的任务就可以使得队列增长的很快，而且它还不会立即“自我修正”为空。排队时间迅速飙升。客户们在着急的等待，bug报告堆积如山。

“我们不能仅仅依靠随机性来解决随机性带来的问题。” —— Donald M. Reinertsen

我们可以通过一些统计数据来更进一步了解这种情况：

(原图为交互图，可在原文查看)

通过每一次的模拟情况，我们收集到了一些数据：

• 产能利用率——服务进程的工作时间（非空闲状态）。如图中所示，如果两种过程的资源能力匹配，这个值接近于100%。
• 非阻塞状态百分比——服务进程非阻塞状态的时间（可立即工作的状态）。值为“100% – 产能利用率”（几乎为0）.
• 队列中平均任务数——队列中等待被处理的任务平均数。可由公式估算”(产能利用率)2 / (1 – 产能利用率)” 。由于服务进程工作时间接近于100%，导致队列大小成指数级增长。
• 排队时间百分比——相对于任务的整个周期时间来说，在队列中时间的所占百分比。它的值约等于产能利用率。这是一个非常值得注意的现象：如果你的系统产能负载率达到95%，那么对每个任务来说，它的整个生命周期有95%的时间都将会在排队中度过。
  

增加额外产能

如果我们能将服务过程和到达过程的资源匹配程度做一些变化，那么这些数据看起来就会大有不同。

例如，如果我们给服务过程增加额外产能，那么上文提到的麻烦就会减弱不少：排队时间所占百分比下降，而且服务进程能很轻松的应对系统负载。即使发生了卡顿的情况，也可以很快清理这种问题。

不过，随之而来的问题是产能利用率下降了。当排队时间降低，产能利用率也会随之降低。我们会多出许多闲置的资源：

(原图为交互图，可在原文查看)

同时兼有较高产能利用率和较少排队时间的情况几乎是不太可能出现的。在上面的模拟情境中，我们对服务频率和到达频率做出的不同组合，通常会出现要么产能利用率过低要么排队时间太长的情况。当然，由于过程的随机性，我们偶尔也会得到幸运之神的光顾。不过仅靠运气不是长远之计。

消除可变性

如果你处于这样一种困境——由于可变队列中排队时间与产能利用率不可兼得，从而无法达到预期目标。那么或许尝试去消除过程中的随机性会有所帮助？

当然， 说起来容易做起来难。怎样保证准确预测到达请求呢？你能控制客户的到来或者控制http请求吗？你该怎样安排工作任务从而使得每个任务花费时间是确定的呢？这些事情听起来挺吸引人，但是事实上很难以实现。

而且在某些情况下，消除可变性甚至可能是不可取的。Reinertsen在他的书中就断言：无论 Six Sigma 之类的工具怎么说，在产品研发中，你无法完全的消除可变性，甚至实际上你也并不会想要完全消除它。你可以通过一些技术手段来限制可变性带来的后果，比如说用一种可变性来替换另一个。在投入与回报不对等的情况下，你甚至可以使得可变性给你带来利益——当可变性带来当成功的价值远远高于失败的成本时。

但是，即使你有能力而且同时也想要消除可变性，队列又会发生怎样的变化？

确定的到达过程

从下图可以看出，即使我们完全消除到达过程的不确定性，使得每个任务的到达时间是确定的，排队现象也依然会出现，除非服务过程有明显的产能过剩才不会产生排队。

(原图为交互图，可在原文查看)

确定的服务过程

如果我们双方互换，使得服务过程确定（这种情形在现实世界中很容易想象出来），如下图：

(原图为交互图，可在原文查看)

看来只降低或消除某一个过程的不确定性并不能解决我们的问题。可能问题的严重性是降低了，但是相应的我们付出的代价是多少？

实际上，可变性与队列大小之间的关系是线性的（然而产能利用率和队列大小是指数级的关系）。如果你只在单方面完全消除可变性，你所能期待的结果也仅仅是排队数减半而已。

完全确定的队列

只有我们将服务过程和到达过程的不确定性都完全消除，我们才能获取真正想要的成功——100%的产能利用率并且排队时间为0.

(原图为交互图，可在原文查看)

然而，在现实世界中出现排队的情况下——当然是人参与的那种排队，这种完全确定的过程超出我们的能力范围。同时就像之前讨论的那样，在某些产品设计研发的活动中，我们也并不想要这种完全确定的过程。

限制在制品数量

若队列大小和产能利用率之间存在指数级的关系，那么如果我们选择限制队列大小，或者换句说话，我们对在制品数量做限制呢？排队时间和产能利用率又会发生怎样的变化？

(原图为交互图，可在原文查看)

这似乎是一个合理有效的策略。如果我们对频繁的到达过程做出比较严格的WIP限制，就能很有效的打破产能利用率和队列大小之间的指数关系。我们可以高负荷运转，同时任务的排队时间也比较短。

当然，这样做的代价是得拒绝一些到达的请求。对在制品数目作出限制的情况下，我们只能选择丢弃一些到达的请求任务，不对这些请求做处理。对于这些HTTP请求只能返回一个网关超时的错误。

当然，对在制品做限制的手段并不只有简单丢弃请求这一种方式。相反，这种WIP限制技术是其他更高级策略的重要构建块。

• 当队列大小达到上限时，你可以引入其他兼职资源从实质上支援服务过程（或者给同一队列增加额外的服务过程）。当队列大小降下来之后，你可以去掉这些额外资源。这种策略在超市中很常见，当开始出现排队的时候，就会增加收银员来收银。IT从业人员对这种情况也比较熟悉，当某项目落后于计划时，他们就会被“召唤”过去帮忙。
• 当你打算不再接新任务时可以给上游发送信号，上游过程可以停止任务或者将在制品加入成本较低的队列池中。这种WIP信号机制是Eli Goldratt瓶颈理论(Theory of Constraints)的基础，该理论中瓶颈的WIP约束用来限制整个系统的操作速度。它同样也是丰田制造系统（Toyota Production System）中看板系统的基础，在这个系统中，过程间的在制品都在本地控制，一旦在制品数量达到上限就给上游发送信号。
  

总结

队列如此的普遍而又如此重要，对它们做定量的推理以及给它们的概率系统建模就显得很有意义。希望在这篇文章中我给你们传达出了这种意思。

鉴于这个话题的广度和深度，在文中我只做了一些简单的说明，并不完整。可能最大的疏漏点在于忽略了排队带来的经济效益：听起来好像排队都是不好的并且需要将排队问题最小化。不过，这就跟简单的说“产能利用率应该最大化”一样。实际上，可以基于经济决策来对队列大小和产能利用率做出权衡。如果你能从相同的角度来量化这二者的成本，你就可以做出这样的决策。

这一点，以及队列的其他方面，可变性，在制品等概念都在这本书《产品开发过程原理》（The Principles of Product Development Flow）中涵盖了，如果各位对这些话题感兴趣的话，我真心推荐你们阅读这本书。