Scheduling and Resource Allocation in Shared Systems

Resource Management

This lecture discusses scheduling and resource allocation in shared systems, focusing on how to distribute resources among various jobs and users efficiently and fairly.

Introduction

In shared systems, a crucial decision involves allocating resources, where the cluster systems consist of numerous servers, with dynamic job arrival and termination.

Goal

The main objective is to achieve high resource utilization. However, practical utilization rates vary:

  • Twitter (using Mesos in 2014): Approximately 20% CPU utilization.

  • Google (using Borg in 2012): Approximately 25-35% CPU utilization.

Efficient resource assignment is complex.

Resources

Resources include:

  • CPUs

  • Memory

  • Disk bandwidth

  • Network bandwidth

  • Specialized resources like GPUs

Challenges

  • Diverse Frameworks: Multiple frameworks (e.g., Hadoop and Spark) often coexist on the same cluster.

  • Diverse Workloads: Clusters handle interactive OLAP applications (requiring fast response times) and large batch jobs (requiring high throughput), making it difficult to satisfy all applications.

  • Changing Usage Patterns: Usage patterns can change during job execution.

    • OLAP: Analysts submit queries, review results, and iterate.

    • Batch jobs: Can switch between CPU-bound and I/O-bound phases.

  • Dependencies: Task dependencies (e.g., Reduce tasks depending on Map tasks in MapReduce, or stages in a DAG in Spark) introduce constraints.

  • Varied Resource Needs: Different tasks require different resources.

    • MapReduce Examples:

      • Map: CPU-bound (data is local).

      • Shuffle: Network-bound (data transfer).

      • Reduce: Balanced CPU and network usage.

Policies

Three policies are examined:

  • First In, First Out (FIFO)

  • Max-Min Fairness

  • Dominant Resource Fairness (DRF)

  • α-fair utility functions

FIFO (First In, First Out)

FIFO is a simple scheduling policy where jobs are processed in the order of arrival.

  • Jobs wait in a queue.

  • Resources are allocated to the oldest job when available.

Pseudocode
while True do
    if resource demands of next job can be met then
        allocate resources to job
        start job
    else
        wait until more resources are available
Discussion

  • Pros: No starvation; every job eventually completes.

  • Cons: Throughput can suffer due to small jobs waiting behind large jobs, leading to low response times. No prioritization is considered.

Max-Min Fairness

With a fixed resource C shared among n jobs, each job i has a demand di (where 1 {le} i {le} n). A share ai of C is allocated to each job.

The condition {sum}{i=1}^{n} ai {le} C must be satisfied.

Scenarios

  • If {sum}{i=1}^{n} di {le} C, then ai = di.

  • If {sum}{i=1}^{n} di > C (demand exceeds supply), resources must be divided fairly.

Strategy

Max-min fairness aims to provide equal rights to all jobs. The allocation strategy is:

  1. Allocate ai in increasing order of di.

  2. Never allocate more than the demand: 0 < ai {le} di.

  3. Unsatisfied demands receive an equal share of the remaining resources.

Water Filling

Capacity is assigned at the same pace starting from 0 until one demand is fully satisfied or the resource is exhausted. If resources remain, the process continues with the remaining demands.

Example

Assume C = 15 and demands are 2, 3, 6, and 7 (sorted in increasing order).

  • Round 1: Divide resources into four equal shares of 3.75 each.

  • Round 2: Demands 2 and 3 are overfulfilled, so allocate their demand and redistribute the remaining 2.5 resources among the remaining demands. Each gets an additional 1.25, resulting in shares of 2, 3, 5, and 5.

How Fair is Max-Min Fairness?

Max-Min Fairness is optimal when all participants have the same access rights. However, optimality is not guaranteed when user-specific parameters like priorities are introduced.

Downsides

Max-min fairness is designed for a single resource type. In reality, various resource types (CPUs, memory, network bandwidth) need allocation. Dominant Resource Fairness (DRF) addresses this by equalizing each user’s share of their dominant resource.

Dominant Resource Fairness (DRF)

DRF extends max-min fairness to multiple resource types, attempting to equalize users’ shares across different resources.

Example

Consider a system with 9 CPUs and 18 GB RAM. User A needs 1 CPU and 4 GB RAM per task, while User B needs 3 CPUs and 1 GB RAM per task.

  • Even division (4.5 CPUs, 9 GB RAM) allows User A to run 2 tasks and User B to run 1 task.

  • Better allocation: User A runs 3 tasks (3 CPUs, 12 GB) and User B runs 2 tasks (6 CPUs, 2 GB).

DRF Properties

DRF defines fairness through:

  • Envy-freeness: No user prefers another’s share.

  • Sharing-incentive: Users benefit from sharing.

  • Pareto-efficiency: No reallocation can increase one user's share without decreasing another's.

  • Strategy-proofness: Lying about demands does not benefit the user.

Fairness Properties

Max-min fairness satisfies these for a single resource type. DRF complicates this by proportionally allocating other resources, creating dependencies between resource allocations.

DRF Allocation Policy

DRF computes a share of each resource for each user. The dominant share is the maximum share a user has of any resource. The dominant resource is the resource type corresponding to the dominant share.

  • Example:

    • User A: 1 CPU, 4 GB. Dominant share: 4/18 (memory).

    • User B: 3 CPUs, 1 GB. Dominant share: 3/9 (CPU).

DRF maximizes the smallest dominant share, then the second-smallest, and so on, applying max-min fairness across users’ dominant shares.

Formal Description

Let x be the number of tasks for User A and y be the number of tasks for User B. The constraints are:

  • x + 3y {le} 9 (CPU constraint)

  • 4x + y {le} 18 (memory constraint)

Every feasible allocation must satisfy these constraints, leading to a feasible region.

Feasibility Region

To choose fairly, equalize the dominant shares: \frac{x}{9} = \frac{y}{3}. This line intersects the feasibility border at (3,2).

Visualization

With DRF, User A runs 3 tasks (3 CPUs, 12 GB) and User B runs 2 tasks (6 CPUs, 2 GB).

Discussion

DRF provides a fair allocation. Each additional resource adds another dimension, defining a feasible space bounded by hyperplanes. Equalizing dominant shares defines a line.

Simplifications

Assumptions include:

  • Tasks from one user are identical.

  • Users can execute fractions of a task.

Discrete DRF Algorithm

The algorithm tracks:

  • Total resource capacity: C = {c1, …, cm}

  • Total resources allocated to each user: Ui = {u{i,1}, …, u_{i,m}} (initially 0)

  • Total sum of allocated resources: A = {a1, …, am} = {sum}{i=1}^{n} Ui

  • Dominant shares of each user: s_i (initially 0)

Algorithm Steps
pick user i with lowest dominant share si
Di ← demand of user i’s next task
if A + Di ≤ C then
    A = A + Di  // update total allocation vector
    Ui = Ui + Di  // update user’s allocation vector
    si = max mj=1 { ui,j / c j }  // update user’s dominant share
else
    return  // cluster is full
Example

The table illustrates how resources are scheduled between User A and User B, showing resource shares and dominant shares through each scheduling step.

Fairness vs. Efficiency

DRF may not provide the most efficient solution. For example, it might “waste” resources like 4GB of memory. Allocating fractions of resources could be more efficient, such as x = \frac{45}{11} and y = \frac{18}{11}, utilizing all available resources.

Pareto Efficiency

While Pareto-efficiency is desirable, the specific point chosen on the Pareto border differs based on the fairness criteria.

Generalization of Fairness

Fairness can be defined in terms of utility. Let Ui(ai) be the utility of allocation ai to user i. Ui is a concave, non-decreasing function (e.g., log).

Optimization Problem

The fairness problem becomes maximizing {sum}{i=1}^{n} Ui(ai) subject to {sum}{i=1}^{n} a_i {le} C. Max-min fairness maximizes the utility of the least demanding user first, then the second-least, and so on.

Alpha-fair Functions

U_{\alpha}(a) = \begin{cases} \frac{a^{1-\alpha}}{1-\alpha} & \text{for } \alpha \ge 0, \alpha \ne 1 \ log(a) & \text{for } \alpha = 1 \end{cases}

  • {lim}_{\alpha \to \infty} gives max-min fairness.

  • \alpha = 0 gives maximum efficiency.

  • \alpha = 1 gives proportional fairness.

Generalization

Alpha-fair utility functions allow balancing fairness and efficiency. Feasible regions, defined by hyperplanes, form a convex set, solvable by algorithms like gradient ascent, interior point methods, and ADMM.

Summary

Fair allocation is not limited to computing; it appears in economics as welfare maximization. Different strategies enable trading off efficiency for fairness.