Reducing Latency by Replicating Jobs

计算机系统设计中的一个新的冗余概念是有目的地复制作业，将每个副本分派到不同的队列，并且只等待第一个完成(丢弃所有剩余的副本)。虽然还处于起步阶段，但谷歌、微软和加州大学伯克利分校最近的研究表明，冗余可以将数据中心和云服务的平均延迟减少高达50%。不幸的是，几乎没有关于冗余的分析研究。研究小组将提供第一个准确的冗余分析，了解冗余的利弊。这项研究的结果将影响多个不同的研究领域，包括运筹学、排队论、编码理论、云计算、数据中心优化和医疗保健，还将增加K-12 STEM学生的机会。冗余需要一种新的排队模式：每个作业不再有一个拷贝，一个拷贝一完成，冗余拷贝就消失了。不同类别的作业可能具有不同的冗余级别，这就需要一个复杂的状态空间，其中必须跟踪所有队列中所有作业的所有副本的确切顺序。具有冗余的系统与其他经典的硬操作研究系统有一些相似之处，如分叉连接系统、耦合处理器系统和灵活的服务器系统。研究团队的目标是明确描述复制作业的延迟优势以及无法复制的作业带来的痛苦(延迟增加)。该研究还将调查冗余的好处如何受到现实世界的外部性的影响，如取消成本、用户违约和服务时间的可变性。冗余还将通过云系统中的分析和实验与其他调度策略进行比较。

A new notion of redundancy in computer systems design is the act of purposely replicating a job, dispatching each replica to a different queue, and only waiting for the first completion (all remaining replicas are discarded). While still nascent, recent studies at Google, Microsoft, and U.C. Berkeley have shown that redundancy can reduce mean latency in data centers and cloud services by up to 50 percent. Unfortunately, there are almost no analytical studies of redundancy. The research team will provide the first exact analysis of redundancy, understanding both the pros and cons of redundancy. The results of this research will impact several diverse research communities including: operations research, queueing theory, coding theory, cloud computing, data center optimization, and healthcare, and will also increase K-12 STEM opportunities for students. Redundancy requires a new queueing paradigm: there is no longer a single copy of each job, and redundant copies disappear as soon as one copy completes. Different classes of jobs may have different levels of redundancy, necessitating a complex state space where the exact ordering of all copies of all jobs in all queues must be tracked. Systems with redundancy bear some resemblance to other classically hard operations research systems, like fork-join systems, coupled-processor systems, and flexible server systems. The research team aims to explicitly characterize the latency benefit to jobs that are replicated as well as the pain inflicted (increase in latency) on those jobs that cannot be replicated. The research will also investigate how the benefit of redundancy is affected by real-world externalities, like cancellation cost, reneging of users, and variability of service times. Redundancy will also be compared with other dispatching policies both via analysis and experimentation in cloud systems.