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.