Pin the Tail: Understanding Straggler Manifestation in Internet-based Distributed Systems

分布式系统是构成互联网基础设施的基本要素，对于满足数字时代的技术和社会需求至关重要。这些系统由云计算中心、计算集群和物联网组成，负责有效地配置和执行大量可并行化的应用程序。这些系统的复杂性和规模的增加导致了紧急现象的出现，这大大降低了整体系统性能，并且不能通过简单地增加计算节点的数量来解决。这种现象被称为长尾问题，其中一小部分任务掉队者-执行异常缓慢的任务的一小部分-阻碍了整体作业完成时间，并且是所有以足够规模运行的分布式系统的系统。虽然这一领域的工作试图通过发现或缓解离散星来解决这一问题，但其有效性取决于对离散星表现的确切根本原因的理解，以及重要的是确定哪些系统条件会影响其发生。然而，考虑到众多可能的落伍者根本原因-所有这些都可能源于不同的子系统操作特性及其与其他子系统的相互作用，实现这种理解是非常具有挑战性的。由于目前对离散现象的理解仅限于定性和高级细节，因此目前无法确定什么系统操作条件（例如群集资源争用、温度、故障）极有可能为离散现象产生“完美风暴”。确定在不同操作场景中影响掉队者出现概率的系统条件对于实现可预测和快速的并行应用执行至关重要，考虑到系统规模和复杂性的持续增加。这项拟议研究的愿景是解决我们对落伍者表现形式的有限理解，并对互联网进行深入分析和建模，的分布式系统，以量化离散发生和系统行为之间的精确关系。这项研究将涉及分析和建模的落后者在真实的系统，通过全面的实验，以确定和提取关键系统参数的虚拟和物理子系统操作在整个分布式系统架构。将建立一个能够自动分析的框架，以确定生产系统中落后者的根本原因，该框架将与基于事件的模拟引擎连接，以确定避免落后者的最佳系统条件。通过与大型分布式系统的领先国际工业家合作，这项工作代表了一个重要的一步改变解决长尾问题，提供了很多寻求出来的知识，真正了解掉队者的表现。由于这个问题在每种类型的大型分布式系统中都是系统性的，这项工作的影响将对学术界和工业界产生深远的影响，并将在短期和长期内为英国数字经济的竞争力提供直接利益。这笔赠款代表了实现研究的第一步，该研究旨在科学地了解大规模互联网基础设施的运作，从而能够以前所未有的规模为未来系统设计容错技术-这是实现未来关键新兴技术的关键目标。

Distributed systems are the essential elements that form the foundation for Internet infrastructure, and are critical for fulfilling the technological and societal needs of the digital age. Comprising Cloud datacenters, compute clusters, and the Internet of Things, these systems are responsible for the effective provisioning and execution of a multitude of parallelizable applications. The increased complexity and scale of these systems has resulted in the manifestation of emergent phenomena that substantially degrades overall system performance, and cannot be solved by simply increasing the number of compute nodes. This phenomena is known as The Long Tail Problem, whereby a small proportion of task stragglers - a small subset of tasks that execute abnormally slow - impede overall job completion time, and is systemic to all distributed systems that operate at sufficient scale. While work within this area attempts to address this problem through straggler detection or mitigation, their effectiveness is underpinned by understanding the precise underlying causes for straggler manifestation, and importantly determining what system conditions influence their occurrence. However achieving this understanding is incredibly challenging given the multitude of possible straggler root-causes - all of which can stem from diverse sub-system operational characteristics and their interactions with other sub-systems. As current understanding of straggler manifestation is restricted to a qualitative and high-level detail, it is presently impossible to determine what system operational conditions (e.g. cluster resource contention, temperature, failures) are highly likely to create a "perfect storm" for straggler occurrence. Determining the system conditions which influence the probability of straggler occurrence in different operational scenarios is vital towards achieving predictable and rapid parallel application execution, given the continued increase of system size and complexity.The vision of this proposed research is to address our limited understanding of straggler manifestation and conduct in-depth analysis and modelling of Internet-based distributed systems to quantify the precise relationship between straggler occurrence and system behaviour. This study will involve analysis and modelling stragglers within real systems, performed through comprehensive experimentation to identify and extract key system parameters from virtual and physical sub-system operation across the entire distributed system architecture. A framework will be constructed capable of automated analysis to determine straggler root-cause within production systems, which will interface with an event-based simulation engine for determining the optimal system conditions for avoiding stragglers.By working with leading international industrialists in massive-scale distributed systems, this work represents a significant step change towards solving The Long Tail Problem by providing much sought-out knowledge to truly understand straggler manifestation. As this problem is systemic across every type of large-scale distributed system, the impact of this work will have far reaching implications for both academia and industry, and will provide direct benefit to the competitiveness of the UKs digital economy within the short and long-term. This grant represents the first step towards realizing the research ambitious to scientifically understanding the operation of massive-scale Internet infrastructure, enabling the design of fault-tolerant techniques for future systems at unprecedented scale - a crucial objective towards realizing key emergent technologies for the future.