这是一篇2017年SOSP上的会议文章 paper
问题引入
解决OS在集群上的QoS问题
当一个节点的资源竞争激烈无法满足当前请求时，转而竞争其他不太激烈的节点资源。因此用于解决由于竞争资源导致的等待所带来的尾端延迟问题。
确切地说，当一个application发出I/O请求之后，如果OS的I/O处于繁忙状态，那么此时APP就很有可能需要等待较长的一段时间才能被处理。这篇paper讨论的背景是在分布式架构下，一般数据中心对于此类问题，采取tail-tolerant来应对个别节点的延迟突刺
策略
通常的做法是wait-then-speculate，也即app主动去判断节点运行的OS是否处于资源竞争激烈状态，这需要花费一定的时间。而每个APP本身具有SLO（service-level object）的要求，对于粗粒度的请求来说是可行的，但是对于那些milliseconds的请求来说，这很难满足。
那怎么办呢？
这关键在于APP能否以较快的速度发觉OS处于繁忙状态，进而决定继续等待下去还是转到其他OS上去处理。而经典的os采用封闭式的设计，上层app是不知道OS的状态信息的，OS也不会暗示这个请求将被等待多久。虽然这种设计可以简化上层APP的设计，但是本文情况下，反而不好。
当然针对上述milliseconds的小请求，先前也提出了一些解决办法：
Cloning：采用副本方法，比如将一个请求分发到多个OS上，最先响应的那个反馈给APP，但是这有个问题就是会导致I/O密集。稍许改进的方法就是适当延迟创建duplicate request的时机，并且在同一个I/O请求已经有结果返回时，要能够快速地撤销其余duplicate request。（为了实现这种方法，必须在应用层中进行创建和撤销队列的管理）hedged requests: 在一个请求超过一定时长之后还未返回，那么发送一个重复的请求，与上述方法对比，此方法的优势是不给整个系统带来过多的负载压力。举一个典型的尾端延迟的例子，可以将请求超过预期95%延迟的时长，就发送重复的请求snitching：APP持续监控并选用最快的节点副本来响应服务，但是这种做法容易受到突发噪声的干扰，从而难以选取到最优的节点。
上述方法虽然在一定程度上有所改进，但是上述方法均未能对底层有更好的信息掌握，如果OS的状态信息可以expose给APP，那岂不是可以很好的去掌控tail-tolerant的设计啦
MittOS
—— an OS that employs a fast rejecting SLO-aware interface to support millisecond tail tolerance
- OS能够感知到APP的SLOs
- 由于资源繁忙而不能够满足其SLOs的I/O，快速地将其reject
既然APP不知道OS的信息，那么只能OS主动反馈给app。因为OS对自身的资源情况非常了解，而APP如果能够了解到OS的情况，就能更好的处理tail-tolerant问题了。
MittOS分为几个子系统：
- MittNOOP：集成在了Linux的Noop I/O scheduler中
- MittCFQ：集成在了Linux的CFQ I/O scheduler中
- MittSSD：集成在了Linux的SSD driver中
- MittCACHE：集成在了Linux的block buffer cache实现中
文中对每个子系统都进行了详细的解释和分析。
四个策略：
Fast rejection： 在PC级的应用当中，因为繁忙而被拒绝时，PC APP不能够再retry别处，只能等待；但是在数据中心，应用程序本质上运行在冗余机器上，所以reject方式很合理。SLO aware：APP需要告诉OS，它的SLOs是什么？因此，OS只需要reject那些不能够满足其SLOs 的I/OsInstant feedback/failover：feedback指的是fast rejection（小于5微妙）；failover指的是reject后转向另外一个节点，通常就是一个network hop的时间。feedback和failover都要求尽可能瞬时完成，以增强系统的tail-tolerant。
此图中第一步表明APP预期处理时间为20ms，第二、三步发送syscall给OS，第四步OS reject，第五步表示failover，转向另一个副本进行处理。Keep existing OS policies：MittOS仅仅是简单地扩展原OS的接口，并不涉及到对原有的OS的策略的修改。OS本身有自己的QoS策略，这些策略和MittOS引入的QoS策略是不冲突的。Keep application simple：APP layer不再需要实现撤销tied I/O request机制，它被推入了OS layer，这一部分代码可以被App layer复用。
主要是架构方面有点复杂，整体思路是非常清晰的，下面介绍下各参数的设计和计算。
T_wait：一个I/O请求预期的，从到达到完成的时长
T_deadline：I/O syscall传入的参数，表明App希望此I/O请求在多长时间内完成
T_hop：两个节点之间网络传输的时间
T_nextFree：磁盘下一次处于free的时刻
T_processNewIO：预期处理此I/O请求的时长
T_processActual：实际处理此I/O请求的时长
如果T_wait > T_deadline + T_hop，那么说明此I/O在本节点上无法及时完成，需要快速返回EBUSY
T_wait = T_nextFree – T_now
T_nextFree是持续追踪的，如果磁盘一直处于繁忙状态，那么就是每一次来一个I/O请求就将它的预期处理时间累加到T_nextFree上：T_nextFree += T_processNewIO。一旦磁盘处于空闲状态，那么这个累加就不再是在T_nextFree上累加，而是在当前时刻T_now上累加：T_nextFree = T_now + T_processNewIO。
由于T_processNewIO的值是一个预估的值，所以每一个I/O完成时，都需要校准T_nextFree的值：T_nextFree += T_processActual – T_processNewIO
“I want to say”
这篇paper讲解的处理尾端延迟的方式主要是在分布式架构，多副本节点下，因此可以实现reject后快速精准的转向另一个节点进行处理。这是个在可能情况下选择最优解的问题。而且这篇文章提出idea的设计并未改变原有OS的机制，只是可以通过OS向APP发送信息来告知，这种在改进APP和OS之间交互的paper好像还是第一次阅读，当然里面很多概念也是第一次碰到，比如SLO以及与之很接近的SLA。这篇文章的想法是很不错的，系统的设计思路也很清晰。
最近在阅读一些关于tail latency 的 paper，最后有时间的话也会整理一个系统的总结！
支付宝打赏
微信打赏
good luck!
