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: Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, Ion Stoica Venue:   NSDI 2011 This work presents a very computationally efficient scheduling algorithm in the context of data centers. The problem is presented as fair resource allocation, but the goal is accomplished through choosing which task to schedule (and how many of each). This done by assigning each task with a resource vector of it's requirements, and a corresponding vector of available resources. The algorithm considers each job's allocation via it's dominant resource. For example, if a job uses 1 CPU and 1 GB of memory, but there are 4 CPUs and 8GB of memory, it would be dominated  by it's CPU usage (1/4 > 1/8). Tasks are continually scheduled such that the job with the lowest dominant resource share will be given priority. The algorithm takes O(log(n)) for n tasks. The work presents 4 main properties, and was well as 4 other "nice to have". I'll briefly ...

Authors: Benjamin Hindman, Andy Konwinski, Matei Zaharia, Ali Ghodsi, Anthony D. Joseph, Randy Katz, Scott Shenker, Ion Stoica Venue: NSDI 2011 Mesos is a thin management layer that allows various cluster computing frameworks to efficiently share resources. The two key principles leveraged by Mesos are its fine-grained resource sharing model at the level of tasks, and a distributed (decentralized) scheduling mechanism. The result is a framework which offers better overall system utilization, scalability to at least 50,000 nodes, and flexibility to port to many different (and future) frameworks. Fine-grain resource sharing is done via a notion of resource-offers, which are each a list of free resources on multiple slaves. The master decides how many resources to offer each framework, this distribution is done via a pluggable allocation module. A scheduler  registers with the master to be offered resources, and an executor process is launched on slave notes to run the framework'...