Karl Taht's Research Paper Blog

Authors: Robert Grandl, Ganesh Anathanarayanan, Srikanth Kandula, Sriram Rao, Aditya Akella Venue: SIGCOMM 2014 Cluster level scheduling is a complex topic in which performance, fairness, and hard constraints must all be considered. Fundamentally, a perfectly fair solution sacrifices performance. This work presents a resource-aware cluster scheduling scheme which maximizes performance and includes additional parameters to balance fairness requirements. For simplicity, I will divide the discussion into two sections: the central idea and additional heuristics. Tetris performs scheduling by analyzing jobs resource requirements in terms of CPUs, memory, disk I/O, and network usage. Each job, task (a subset of a job), and machine is assigned a resource vector. To determine the optimal positioning of a task, a heuristic is used which takes the dot product of the job's resource requirements vs a candidates available resources. The machine with the maximum dot product is selected to p...

Authors: Kay Ousterhout, Patrick Wendell, Matei Zaharia, Ion Stoica Venue:    SOSP 2013 This work presents Sparrow, a stateless, decentralized scheduler for cluster scheduling. The scheduling component uses two key ideas: batch sampling and late binding. Batch sampling is an extension of the power of two choices [1], which shows that the "tail" can quickly be cut off by simply sampling between two machines versus randomly selecting one. Batch sampling generalizes this by sampling dm machines, and placing the m   tasks on the machine with the lowest load. Late binding delays the actual task transfer until the machine is ready to process the request. This can be thought of as having a place holder in the worker's queue, and when the worker is finally ready to process it, the actual task is transferred from the scheduler to the worker. This avoids having to rely on inaccurate metrics such as queue depth. Each worker maintains its "instance" of Sparrow, which us...

Authors: Kay Outerhout, Christopher Canel, Sylvia Ratnasamy, Scott Shenker Venue: SOSP 2017 This paper presents a data analytics framework which focuses or providing performance clarity first. Consider a user running there analytics framework on EC2. They need to improve performance. Do they invest in more vCPUs, more memory, more disks per node or more network bandwidth? If they do upgrade, what will the expected performance improvement be? To solve this, Monotasks centralizes on building a framework which decomposes all tasks into single-resource utilization: disk use, network I/O, or CPU. The framework is integrated into Spark, and referred to as "MonoSpark". By simply decomposing tasks at the worker level, the existing Spark API is maintained. By dividing tasks into individual units of disk/network/CPU, the framework can track the precise total amount of work for each, and then determine the performance changes based on the new resource constraints. Most queries are ...