Reducing Latency by Replicating Jobs

通过复制作业减少延迟

• 批准号: 1538204
• 负责人: Mor Harchol-Balter
• 金额: $ 29.97万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1538204&HistoricalAwards=false
• 关键词: Reducing; Latency; Replicating; Jobs

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.

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