Resource allocation
The resource allocation module contains the policy that the Mesos master uses to determine the type and quantity of resource offers that need to be made to each framework. Organizations can customize it to implement their own allocation policy—for example, fair sharing, priority, and so on—which allows for fine-grained resource sharing. Custom allocation modules can be developed to address specific needs.
The resource allocation module is responsible for making sure that resources are shared in a fair manner among competing frameworks. The choice of algorithm used to determine the sharing policy has a great bearing on the efficiency of a cluster manager. One of the most popular allocation algorithms, max-min fairness, and its weighted derivative are described in the following section.
Max-min fair share algorithm
Imagine a set of sources (1, 2, ..., m) that has resource demands x1, x2, ..., xm. Let the total number of resources be R. We will initially give R/m of the resource to each of the m sources. Now, starting with the source with the least demand, we will compare the allocation to the actual demand. If initial allocation (R/m) is more than the demand requirements of source 1, we will redistribute the excess resources equally among the remaining sources. We will then compare the new allocation to the actual demand of the source with the second-lowest demand and continue the process as before. The process ends when each source gets allocated resources that are less than or equal to its actual demand. If any source gets allocated resources less than what it actually needs, the algorithm ensures that no other source can get more resources than such a source. Such an allocation is called a max-min fair share allocation because it maximizes the minimum share of sources whose demands are not met.
Consider the following example:
How to compute the max-min fair allocation for a set of four sources, S1, S2, S3, and S4, with demands 2, 2.5, 4, and 5, respectively, when the resource has an overall capacity of 10.
Following the methodology described earlier, to solve this, we will tentatively divide the resource into four portions of size 2.5 each. Next, we will compare this allocation with the actual demand of the source with the least demand (in this case, S1). As the allocation is greater than the actual demand, the excess 0.5 is divided equally among the remaining three sources, S2, S3, and S4, giving them 2.666 each. Continuing the process, we will note that the new allocation is greater than the actual demand of source S2. The excess 0.166 is again divided evenly among the remaining two sources S3 and S4, giving them 2.666 + 0.084 = 2.75 each. The allocation for each of the sources is now less than or equal to the actual demand, so the process is stopped here. The final allocation is, therefore, S1 – 2, S2 – 2.5, S3 – 2.75, and S4 – 2.75.
This works well in a homogenous environment—that is, one where resource requirements are fairly proportional between different competing users, such as a Hadoop cluster. However, scheduling resources across frameworks with heterogeneous resource demands poses a more complex challenge. What is a suitable fair share allocation policy if user A runs tasks that require two CPUs and 8 GB RAM each and user B runs tasks that require four CPUs and 2 GB RAM each? As can be noted, user A's tasks are RAM-heavy, while user B's tasks are CPU-heavy. How, then, should a set of combined RAM and CPU resources be distributed between the two users?
The latter scenario is a common one faced by Mesos, designed as it is to manage resources primarily in a heterogeneous environment. To address this, Mesos has the Dominant Resource Fairness algorithm (DRF) as its default resource allocation policy, which is far more suitable for heterogeneous environments. The algorithm and its role in efficient resource allocation will be discussed in more detail in the next chapter.
