【冬瓜哥熊文】大话流水线（2）~队列、时延与并发
对于一个传递链，不管是同步还是异步流水线，其中每个角色都需要从上游角色接收物品/消息，以及向下游角色传递物品/消息。具体如何传递？如果是实际产品包装流水线的话，那么不可能是用手去传递的，我处理完用手递给你，除非离得近，以及每次你都能在我胳膊发酸之前接过去。更方便的做法是，我将处理完的物品放到一个你我都可以方便摸得着的地方，比如一个工作台上，我只要放上去就行了，根本不用管下游操作者处于什么状态。只要大家都在全速工作，不出什么问题的话，我下一次打算往上放东西的时候，会发现原来那件物品总是能被及时的被下游操作者拿走。
然而，不能保证总不出问题。比如下游操作者突然走神了，没来得及拿走上游放在工作台上的物品，则上游打算传递下一个物品的时候，就会停住，同时也不再继续从它自己的上游那里拿走待处理物品，这会一层层反馈到源头，导致传递链停顿，或者叫Stall，阻塞。
厂长一看急了，这不行，动辄就停顿，太影响生产效率。那么你认为厂长应该如何解决这个问题？估计你也想得出来，那就是把工作台面拉长一些，弄个传送带和挡板，上扔过来的物品被源源不断传送过来（假设传送带速度非常快，忽略物品在传送带上传输的时间），并且堆积在处于下游较色眼前的挡板处。如果大家全速运行，那么任意时刻挡板处最多只有一件物品出现。一旦下游由于各种原因处理速度变慢，或者瞬间有卡顿，那么上游依然可以往传送带上放置处理完的物品，此时会发现下游的挡板处有物品堆积，下游卡顿时间越长，堆积越多，如果一直堆积到上游跟前，那么上游就知道传送带已满，就会停止处理，同理，上游的上游的传送带就会逐渐堆积，一直反馈到源头，最终导致卡顿的那个人之前的所有人都停止处理，但是卡顿的人和其下游的人会继续处理。当上游发现传送带上有空余位置的时候，就继续处理并向上放置物品，逐渐恢复流水线的运行。下游此时可以一过性加快处理速度，将传送带上的物品加速消耗，传送带中物品堆积数量越来越少，最终少到1的时候，可以恢复原来的处理速度。或者下游继续按照原有速度处理，那么此时就会在传送带上永久积压着满传送带的物品，除非源头不再有物品需要处理。
这样做的好处是将流水线上的每个工序解耦，从紧耦合变为松耦合。其本质上是在每两道工序之间加大了缓冲空间，之前缓冲空间只有1，相当于没有缓冲。至于这个缓冲空间需要有多大，一般取决于该队列下游工序的处理速度，越快，则相应的应当增加上游缓冲的空间，这样的话上游可以向该缓冲空间内存放大量的物品，以供下游角色消耗，一旦上游出现瞬间卡顿，还能保证缓冲空间内短时间内依然还有存货，下游还有的干，不会跟着一起停工。这就是缓冲的作用，缓冲的是不同角色之间处理速度的不匹配。
该缓冲空间又可以被称之为队列/Queue，其总容量又被成为队列深度，其当前已经被存了多少样物品，又被称为队列长度。不带缓冲的流水线，相当于队列深度为1的流水线，一旦任意一道工序有卡顿，会导致上游接连卡顿，影响生产效率。
如果由多个运行在计算机中的程序组成流水线来处理某种数据包/消息/请求等的话，那么该流水线的传送带很显然就应该是用异步FIFO队列来充当了，这些队列可以处于内存中某处。
排队固然好处明显，但是其原生并不是为了增加流水线吞吐量而设计的，只是为了更加松耦合，为了灵活性而生。在实际的由程序/线程组成的流水线中，每个程序/线程需要处理的事情可能比较复杂，而且有时还不可控，比如有些判断分支，命中时需要花费更多时间来处理，不命中则很快处理完，此时该程序的处理时延是不固定的。正因如此，流水线上各个步骤可能并不能真的按照实际设计时所预估的时延来全速工作达到最大吞吐量。此时队列的作用更加凸显，比如上游处理程序时延变长，不能够以原有速率向下游输出处理完后的消息/数据包，但是位于它们之间的队列此时正缓冲有部分之前积压的待处理消息/数据包，那么此时下游依然会全速处理，不受上游影响。
甚至可以这样，将源头或者流水线中间某处极易卡顿处的队列深度加大，这样所带来的缓冲效果就会更加持久，能够保证流水线持续输出，最大程度屏蔽由于任何一处卡顿所带来的流水线阻塞等待。
1. 队列长度与时延
队列缓冲固然好，但是其代价显而易见。队列中排队的物品越多，轮到队列尾部的物品被下游模块处理所需等待的时间就越长。
问一下：假设下游节点每处理一个物品需要2s，也就是每2s钟从上游队列中取出一个物品处理。请算出队列中存在2个、3个、4个物品时，最后一个物品被下游处理完输出所耗费的时间。当队列长度为2时，第二个物品输出所需耗费：第一个物品处理所需的时间+第二个物品处理所需的时间，也就是2s+2s=4s。队列长度为3时，第三个物品处理所需耗费的时间为2s+2s+2s=6s，同理可得，队列长度为n时，队列中第n个角色被下游处理完共需耗费时间为nm，m为下游模块的处理时延。
问一下：当队列长度为n，下游模块处理时延为m时，求队列中的角色被下游处理的平均处理时延。平均处理时延=n个角色总处理时延/n = [nm+(n-1)m+(n-2)m+…….+m]/n =m(n+1)/2。可以看到，队列中每多排队一个角色，就会拖慢0.5m的平均处理时延，但是吞吐量不会受音影响。所以自然有一个推论：当队列长度能够保持为1时，平均时延最低，同时吞吐量不受影响。那就等价于一个没有缓冲队列的流水线了，如果能够保证每一步处理速率绝对恒定，自然是最理想的状态。而上文中也分析过，一旦有卡顿，则流水线上游就会停顿阻塞，最终影响吞吐量。所以，吞吐量和时延天生就是一对矛盾，这个矛盾需要平衡。抵御越强烈持久的卡顿，就需要增加队列深度，那么平均时延也会升到更高。
在时间维度上长期来看的话，仔细思考可以发现这样一个本质：无缓冲流水线时延最低，吞吐量最大。加入缓冲之后，如果流水线没有任何卡顿，那么依然时延最低吞吐量最大。一旦卡顿，那么卡顿了多长时间，这些时间就会被变相的被分摊到队列中积压的角色处理时延的增加上。所以，一切都是公平的守恒的。
推论：一个角色从进入流水线中某一级的前置队列，到被该级流水线处理并输出的总时延可分为等待时延和处理时延。该级处理时延为m，则队列中排在第n个位置的角色的等待时延=(n-1)m，处理时延恒定为m。
问一下，队列长度是否对吞吐量有直接影响？没有直接影响。只要流水线不卡顿，队列存在与否、队列深度/长度对吞吐量毫无影响。卡顿时，如果队列深度过小会导致快速充满则导致上游停止工作，造成吞吐量下降。队列深度过小导致队列被充满的现象被称为过载/Overrun，同理，队列深度过小还容易导致其中缓冲的消息快速被下游消耗掉，而上游由于各种原因的卡顿尚未来得及将新消息充入队列，此时队列为空，此为欠载/Underrun。频繁过载欠载不是好事情，证明该流水线上下级处理模块的速度极不匹配，或者流水线正遭受大范围扰动，此时应该加大队列深度，抗波动能力就随之加强了。
2. 并发度与时延
假设某带缓冲队列的流水线中的某级处理模块是p路物理并发，这种情况下，p路处理模块会同时从其上游队列中分别取走一条消息进行处理，那么此时的时延模型就变了，变为每p条消息为一组，同时并行下发。那么时延公式m(n+1)/2里的n此时应该表示的是第n组消息的时延，p个消息为一组。同理，单个消息的平均等待时延换算下来就会降低p倍，当然，处理时延是不变的，总时延依然是降低的。
要想保证带有多路物理并发的流水线的吞吐量，就得精心调校从而让队列长度恒定在至少为p，压入更多消息到队列中，上文中也说过，会显著增加时延；而过少又容易导致underrun从而流水线瞬间空转。
如果队列中的多笔消息是同一个线程发出的，那么被并行执行之后，其相比非并行场景而言，时延降低了。就算下游并非是多路物理并发，而只是多级流水线，那么也依然算是一种并发，相比非多级流水线的单级超长步骤处理而言，时延依然是降低的。这就是所谓流水线可以屏蔽时延的说法依据，但是请注意，其是与非流水线处理相比，比如之前是4s钟一大步，分为4个时延为1s的小步骤，二者相比，如果有4条消息，前者总共需要16s完成，后者则只需要4s+1s+1s+1s=7s完成。但是请务必注意，每条消息自身的时延没有变化，依然是4s，只不过由于并发的原因，如果这4个消息为一组，那么其总体的时延的确降低了。那么发出这4条消息的线程就会感受到总体上的性能提升。
推论：如果多笔消息属于某个总步骤，那么流水线并发可以降低这个总步骤的时延，表面感官上的感觉就是响应时间更快了。如果多笔消息分别属于多个不同的步骤，那么流水线化之后，每个步骤感官上并没有变化，响应速度没什么变化，但是总体看来，流水线化之后可以在保持原有响应时间不变的前提下，提升总体吞吐量，也就是在维持速度体验不变的情况下可接纳的处理线程数量增多了。相反，如果没有流水线化，这多笔消息就得同步执行，排在对尾的消息等待时间会很长，响应速度变慢，多笔消息处理完总共花费的时间也很长，所以不管是这多笔消息属于同一个总步骤还是分属不同的步骤，每个步骤的感官响应时间都不好。
哪类业务非常在乎时延？有真实的人在等待且要求越快返回结果越好的那类业务，比如网购、网聊、查账、柜台/ATM业务等等。哪类业务只求吞吐量而对时延没什么要求？无人在实时等待的后台批处理业务，这类业务往往是处理一大堆数据，而根本不在乎其中某次处理耗费了多长时间，其追求总体上的吞吐量，这样才能更快的完成任务，典型场景比如大数据分析等等。
相关阅读：