Skip to main content

Healthy nodes are happy nodes - the Fair Tale of Hadoop Scheduling



With Hadoop being a great sell story for parallel data processing, the infrastructure guys are trying to squeeze the maximum buck out of it by pooling multiple consumers. No wonder, there is competition among Hadoop jobs and you guessed it higher incidence of errors. In this post, we analyze an approach for fair scheduling tasks by determining health of a node.

We begin by describing Delay scheduling introduced first in DelayScheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling (2010) by Matei Zaharia , Khaled Elmeleegy , Dhruba Borthakur , Scott Shenker , Joydeep Sen Sarma , Ion Stoica  . Thereafter we describe the job scheduling based on Node health degree published in Researchon Job Scheduling Algorithm in Hadoop by Yang Xia, Lei Wang, Qiang Zhao, Gongxuan Zhang.

The justice done by fair scheduling is subject to criticism of being too fair or unfair at times. It has been demonstrated to be suspect to head of line scheduling (allocating the top task in sorted queue to free node) and sticky slots (possibility of being allocated to same node again and again).
Further, it suffers from problem of not being able to preserve data locality, the placement of computation near its input data.  “Locality is crucial for performance in large clusters because
network bisection bandwidth becomes a bottleneck”

Enter delay scheduling, “in which a job waits for a limited amount of time for a scheduling opportunity on a node that has data for it. …
When a node requests a task, if the head-of-line job cannot launch a local task, we skip it and
look at subsequent jobs. However, if a job has been skipped long enough, we start allowing it to launch non-local tasks, to avoid starvation”

Snapshot of Hadoop Fair Scheduler algorithm with Delay scheduling:

The above approach sounds pretty good with the data locality taken care. However, Xia et al did not seem quite happy with it. Their contention has been that what if the nodes are not healthy and error prone? What is the use of fairly scheduling a task on a node which is not fit enough to complete the task?

Xia, Wang, Zhao and Zhang have therefore tried to identity variables that define a node and a task, called characteristic variables.
The characteristic variables of task describe resource usage and demand for MapReduce task…The characteristic variables of node represent the status and quality of computing resources on a node”

Characteristic Variables
Task
Node
average CPU utilization cusage
average I/O utilization Iusage
average memory usage Musage
average CPU idle rate Cldle
average I/O idle rate Ildle
average free memory Mldle



The scheduling algorithm is further outlined below:
1) When an idle task slot can be used, a pool is chosen according to the Fair scheduler;
2) if the node on which the idle task is located is healthy, then go to 5;
3) if the node on which the idle task is located is sub healthy, characteristic variables of the node are separately multiplied by the reciprocal of Health Degree of node , then go to 5;
4) if the node on which the idle task is located is unhealthy, then go to 8,and set timer on node ,its Health Degree is multiplied by 0.9 every x minutes until it reaches the state of sub healthy;
5) Computing Euclidean distances between characteristic variables of job task and characteristic variables of node, sorting them from small to large;
6) Choosing an appropriate job according to Delay Scheduler in the sorted set;
7) Assigning the task of a chosen job to a task slot to run;
8) Finish”


Take note of step 3 where the sub healthy nodes characteristics are ‘loaded’ to arrive at a fairness determined by health. 

We all know schedulers play a major role in architecture of some of the most complex systems as we discussed in one of our earlier post on multimedia search. A lot of text and code has been written on fair and capacity scheduler. This paper definitely describes a unique approach but further tests on high load multi-use clusters can further demonstrate the usage and possible incorporation in future code base. 

Comments

Popular posts from this blog

Technical deep dive into Apache Tajo

Over the past few months, a new Hadoop based warehouse called Apache Tajo has been making the buzz. We tried to do a technical deep dive in the topic and reached out to PMC chair Hyunsik Choi. Apache Tajo is an Apache top level project since March 2014 and supports SQL standards. It has a powerful distributed processing architecture which is not based on MapReduce. To get more sense on Tajo's claims for providing a distributed, fault-tolerant, low-latency and high throughput SQL engine, we asked a few questions to Choi. This Q&A is published in a two part article series on hadoopsphere.com. Read below to get a better idea on Apache Tajo.
How does Apache Tajo work? As you may already know, Tajo does not use MapReduce and has its own distributed processing framework which is flexible and specialized to relational processing. Since its storage manager is pluggable, Tajo can access data sets stored in various storages , such as HDFS, Amazon S3, Openstack Swift or local file system. …

In-memory data model with Apache Gora

Open source in-memory data model and persistence for big data framework Apache Gora™ version 0.3, was released in May 2013. The 0.3 release offers significant improvements and changes to a number of modules including a number of bug fixes. However, what may be of significant interest to the DynamoDB community will be the addition of a gora-dynamodb datastore for mapping and persisting objects to Amazon's DynamoDB. Additionally the release includes various improvements to the gora-core and gora-cassandra modules as well as a new Web Services API implementation which enables users to extend Gora to any cloud storage platform of their choice. This 2-part post provides commentary on all of the above and a whole lot more, expanding to cover where Gora fits in within the NoSQL and Big Data space, the development challenges and features which have been baked into Gora 0.3 and finally what we have on the road map for the 0.4 development drive.
Introducing Apache Gora Although there are var…

Data deduplication tactics with HDFS and MapReduce

As the amount of data continues to grow exponentially, there has been increased focus on stored data reduction methods. Data compression, single instance store and data deduplication are among the common techniques employed for stored data reduction.
Deduplication often refers to elimination of redundant subfiles (also known as chunks, blocks, or extents). Unlike compression, data is not changed and eliminates storage capacity for identical data. Data deduplication offers significant advantage in terms of reduction in storage, network bandwidth and promises increased scalability.
From a simplistic use case perspective, we can see application in removing duplicates in Call Detail Record (CDR) for a Telecom carrier. Similarly, we may apply the technique to optimize on network traffic carrying the same data packets.
Some of the common methods for data deduplication in storage architecture include hashing, binary comparison and delta differencing. In this post, we focus on how MapReduce and…