So that brings us to systems that do resource mapping and because you have large numbers of applications and they had to be scheduled on the datacenter resources and you have to take into account all of these different applications and how you can best utilize the resources and meet the quality of service requirements. So I'm going to talk about some examples of fare share schedulers. The scheduler that is used in the Hadoop framework, it uses a variant of max-min scheduling that I just mentioned earlier. What it does is if I have a machine and I break that up into scheduling slots, so I can say that I have some number of slots here. So one through 16, let's say these are the slots that are available. As I said, at any point of time, a number of applications could be running on the datacenter for I think of this machine having 16 CPUs and then one gigabyte of memory, each of these slots may be equivalent to one CPU plus 64 megabytes of memory. So that's your slot and what the scheduler or a resource manager is doing is it is allocating one task per slot, as particular job. When we talk about a job, we mean like Hadoop MapReduce job or a graph application that is running, right? So that's a job. A particular job may have a number of tasks that it has to perform, you take a MapReduce task as a whole bunch of mapping tasks, followed by a whole bunch of reduced tasks. The role of the scheduler is to allocate one task per slot that it has at any point of time. So you can think of the machine being divided into these slots and it is allocating tasks per slot, and it is going to apply max-min fairness that I have just mentioned in mapping the tasks to the slot. So in other words, if I have an application, a Job A, which has a weight of two and if I have a job B which has a weight of one, it's going to make sure that at any point of time more number of slots are going to be given to job A versus job B, that is the meaning of max-min fairness applied to this notion of slots that are kept in the scheduling framework. Now obviously, when you have this division of a machine being divided into slots, it could result in under-utilization of the slot resources or over-utilization because you're statically saying that every slot is in this particular example, one CPU and 64 megabytes of memory. Now if I have a task that is mapped to a particular slot that requires 128 megabytes, then obviously you're going to experience a lot of thrashing for that particular task. On the other hand, if I need only 32 megabytes as the memory footprint of the task that I'm running, then allocating one slot to that task is going to result in wastage of 32 megabytes. So half the allocation is going to be wasted. So these are things that you have to worry about but this is a framework that exists in the Cloud today, Hadoop framework and the bottleneck or the inherent deficiency in this particular assignment is the fact that it is thinking of every slot as being equal in terms of the amount of resource commitment, a fraction of the resource commitment of the machine. Now another allocation policy is what is called a dominant resource fairness. So the idea is to take a more holistic view of the machine's resources. For example, if I have in a machine, 10 CPUs and four gigabytes of memory, and let's say that some job A has a task that needs two CPUs and one gigabytes of memory. If you see that in terms of the ratio of the machine's resources, two CPUs out of 10 CPUs is one fifth of the resource commitment. On the other hand, if this task needs one gigabyte out of the four gigabytes that's available, it's one fourth the resource commitment for this particular task, right? So you can see that the amount of the memory commitment for this task is higher than the amount of CPU commitment for this particular task. So then in that case, we will call this a memory dominant resource or in other words, the dominant resource for this task is memory. If this task is allocated to a slot on this machine, the dominant resource share is 25 percent, because one fourth of the machine's resources is being committed to this particular task. That's the basis for the DRF scheduling, a dominant resource fairness scheduling which is basically using max-min fairness, but it is taking a holistic view of all the resources that are needed for running a particular task. So let's put this in a concrete example here. So here is a system with nine CPUs and say 18 gigabytes of memory and there are two jobs, A and B. A has tasks in which each task requires one CPU and four gigabytes of memory. So if you take it as a ratio of four gigabytes to 18 gigabytes of DRAM, you can see that the dominant resource for tasks of job A is memory. On the other hand, if the task in B requires three CPUs and one gigabyte of memory, then you can see that as a fraction of the total resource commitment to run a task of B, it's a dominant resource, it's a CPU, right? So the DRF scheduling, what it tries to do is it tries to equalize the allocation for the tasks that are competing for the resource on the dominant shares. So take this example here. So we've got nine CPUs and 18 gigabytes of memory and if I want to give equivalent share of the machine to both A and B, then I have to go along the memory access for A and the CPU access for B. Because those are the dominant resources for each of these categories of jobs. I can run three tasks of A, so three tasks can be run and if I run three task A, I'm committing three CPUs because each task requires four gigabytes of memory. I'm committing 12 gigabytes of memory for this user A. On the other hand, if I run two tasks of B, because each task requires three CPUs, I'm committing six CPU resources and two gigabytes of memory. So this way I can run three tasks of A here, and two tasks of B and you see that the resource commitment that I made for A is going to be based on its dominant resource being memory. The resource commitment that I made for B is 12 by 18, and similarly, the dominant resource for B is the CPU, and the resource commitment I made for that is 6 over 9. So we are equal. That is two-thirds of the dominant resource is being allocated to each of these guys. So that's the idea behind DRF scheduling, which is making sure that along the dominant axis category, each application is given its due share. So the question is, how do this number two-thirds come aboard, right? This particular example, you've got nine CPUs and 18 gigabytes of memory, and if I want to say, well, how do I maximize the utilization of these resources? What is the best way to do it? Scheduling, we all know is an NP-complete problem, right? So we can use heuristics and we can see which heuristic results in the best utilization for a particular set of inputs, right? So in this case, the set of inputs is the two jobs A and B and the characteristics in terms of the profile of the tasks in that. You can see that this is wasted, you are wasting two gigabytes of memory but we're using all of the CPUs available. So that one schedule in which we are saying we are maximizing utilization at least one resource which is 100 percent and ensuring that both of them get equal share of their dominant resource. In the case of job A, the dominant resource is memory and in the case of job B, dominant resource is CPU.
