YARN scheduling policies in Hadoop - Time & Space Complexity

Time Complexity: YARN scheduling policies

O(q * a * r)

Understanding Time Complexity

We want to understand how the time to schedule tasks grows as more jobs and resources are involved in YARN.

How does the scheduler handle more work and what affects its speed?

Scenario Under Consideration

Analyze the time complexity of the YARN Capacity Scheduler's allocation loop.

for each queue in queues:
  for each application in queue.applications:
    for each container request in application.requests:
      allocate container if resources available

This code tries to allocate containers to applications in each queue based on resource availability.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: Nested loops over queues, applications, and container requests.
• How many times: Number of queues (q), times number of applications per queue (a), times container requests per application (r).

How Execution Grows With Input

As the number of queues, applications, and requests grow, the scheduler does more work.

Input Size (q, a, r)	Approx. Operations
10 queues, 5 apps, 3 requests	10 * 5 * 3 = 150
100 queues, 10 apps, 5 requests	100 * 10 * 5 = 5,000
1000 queues, 20 apps, 10 requests	1000 * 20 * 10 = 200,000

Pattern observation: The work grows quickly as more queues, applications, or requests are added.

Final Time Complexity

Time Complexity: O(q * a * r)

This means the scheduling time grows proportionally to the number of queues, applications, and container requests.

Common Mistake

[X] Wrong: "The scheduler time only depends on the number of applications."

[OK] Correct: The scheduler also loops over queues and container requests, so all three affect the time.

Interview Connect

Understanding how scheduling time grows helps you design better resource managers and explain system behavior clearly.

Self-Check

"What if the scheduler used a priority queue to pick applications instead of looping over all? How would the time complexity change?"

Practice

1. Which YARN scheduling policy assigns resources to jobs in the order they arrive without considering job size or priority?

easy

A. Capacity Scheduler

B. Fair Scheduler

C. FIFO Scheduler

D. Priority Scheduler

Solution

1. Step 1: Understand FIFO Scheduler behavior

   FIFO (First In First Out) scheduler assigns resources to jobs strictly by arrival time, ignoring job size or priority.

2. Step 2: Compare with other schedulers

   Capacity Scheduler and Fair Scheduler consider resource sharing and fairness, while Priority Scheduler uses job priority.

3. Final Answer:

   FIFO Scheduler -> Option C

4. Quick Check:

   FIFO = order by arrival [OK]

Hint: FIFO means first come, first served order [OK]

Common Mistakes:

• Confusing FIFO with Fair Scheduler
• Thinking Capacity Scheduler ignores job order
• Assuming Priority Scheduler is default

2. Which of the following is the correct syntax to configure the Capacity Scheduler in YARN's capacity-scheduler.xml file?

easy

A. yarn.scheduler.capacity.root.queuesdefault,production

B. yarn.scheduler.fifo.root.queuesdefault,production

C. yarn.scheduler.fair.root.queuesdefault,production

D. yarn.scheduler.priority.root.queuesdefault,production

Solution

1. Step 1: Identify correct property prefix for Capacity Scheduler

   The Capacity Scheduler uses properties starting with yarn.scheduler.capacity.

2. Step 2: Verify queue configuration syntax

   The property yarn.scheduler.capacity.root.queues defines queues like default and production.

3. Final Answer:

   <property><name>yarn.scheduler.capacity.root.queues</name><value>default,production</value></property> -> Option A

4. Quick Check:

   Capacity Scheduler uses yarn.scheduler.capacity prefix [OK]

Hint: Capacity Scheduler uses 'yarn.scheduler.capacity' prefix [OK]

Common Mistakes:

• Using fifo or fair prefix for Capacity Scheduler
• Misspelling property names
• Confusing queue names with scheduler types

3. Given the following YARN Fair Scheduler configuration snippet:
<pre>queueA: minResources=2GB, maxResources=10GB queueB: minResources=4GB, maxResources=8GB Currently, queueA is using 3GB and queueB is using 5GB.
Which queue can get more resources if a new job requests 3GB?

medium

A. queueA only

B. Both queueA and queueB

C. queueB only

D. Neither queueA nor queueB

Solution

1. Step 1: Check current usage vs maxResources

   queueA uses 3GB, max is 10GB, so it can get up to 7GB more. queueB uses 5GB, max is 8GB, so it can get 3GB more.

2. Step 2: Assess if requested 3GB fits

   queueA can allocate 3GB (3+3=6GB <= 10GB). queueB can allocate 3GB (5+3=8GB = max), so it can also get 3GB.

3. Step 3: Consider Fair Scheduler policy

   Fair Scheduler tries to balance usage. Since queueA is below queueB usage, it will prioritize queueA for extra resources, but queueB can also allocate the requested resources up to its max.

4. Final Answer:

   Both queueA and queueB -> Option B

5. Quick Check:

   Fair Scheduler favors less used queue but both can allocate requested resources [OK]

Hint: Fair Scheduler favors queues with less current usage [OK]

Common Mistakes:

• Ignoring maxResources limits
• Assuming both queues get resources equally
• Not considering current usage in decision

4. You have configured the Capacity Scheduler but notice that some queues are starved and not getting resources. What is the most likely cause?

medium

A. Queue capacities are not properly set, causing imbalance

B. FIFO Scheduler is enabled instead of Capacity Scheduler

C. The yarn.scheduler.capacity.root.queues property is missing

D. Fair Scheduler is overriding Capacity Scheduler settings

Solution

1. Step 1: Understand Capacity Scheduler behavior

   Capacity Scheduler allocates resources based on configured queue capacities.

2. Step 2: Identify cause of starvation

   If queue capacities are not set correctly, some queues may get more resources, starving others.

3. Step 3: Rule out other options

   Missing property would cause scheduler failure, not starvation. FIFO and Fair Scheduler are different policies, not overriding Capacity Scheduler if configured correctly.

4. Final Answer:

   Queue capacities are not properly set, causing imbalance -> Option A

5. Quick Check:

   Capacity settings control resource distribution [OK]

Hint: Check queue capacity percentages to avoid starvation [OK]

Common Mistakes:

• Assuming missing property causes starvation
• Confusing scheduler types
• Ignoring capacity configuration importance

5. You want to run a multi-tenant Hadoop cluster where each department gets guaranteed minimum resources but can use more if available. Which YARN scheduling policy and configuration best fits this need?

hard

A. Priority Scheduler with fixed job priorities

B. FIFO Scheduler with strict job ordering

C. Fair Scheduler with no minimum resource guarantees

D. Capacity Scheduler with minimum and maximum queue capacities set

Solution

1. Step 1: Understand multi-tenant resource needs

   Departments need guaranteed minimum resources but flexible usage if available.

2. Step 2: Match policy features

   Capacity Scheduler supports minimum and maximum queue capacities, ensuring guarantees and flexible sharing.

3. Step 3: Rule out other policies

   FIFO does not guarantee resources per tenant. Fair Scheduler can share fairly but may lack strict minimum guarantees. Priority Scheduler focuses on job priority, not resource guarantees per tenant.

4. Final Answer:

   Capacity Scheduler with minimum and maximum queue capacities set -> Option D

5. Quick Check:

   Capacity Scheduler = guaranteed min + flexible max [OK]

Hint: Capacity Scheduler supports min and max resource guarantees [OK]

Common Mistakes:

• Choosing FIFO for guaranteed resources
• Ignoring min capacity in Fair Scheduler
• Confusing priority with resource guarantees