Distributed Scheduler (Part 1) | Internal Working of Scheduler: Leader–Follower Pattern

The Airport Ground Crew Analogy

Imagine a large international airport. Ground crew members are assigned to service aircraft, but not every aircraft lands at exactly the same time. Some planes arrive in the morning, some in the afternoon, some are delayed. The crew does not stand on the tarmac staring at the sky continuously — that would exhaust them and waste resources. Instead, they wait in a rest room, and a dispatch system wakes the right number of crew members precisely when an aircraft is about to arrive.

A distributed scheduler works in exactly this way. Background threads (the ground crew) sleep until a particular time, wake up to perform a task (service the aircraft), and then go back to sleep. The challenge is making this system efficient: you do not want all crew members woken for one small task, and you do not want them all staring at the clock at once.

---

What Is a Scheduler?

In the simplest terms, a scheduler is a background thread that:

1. Sleeps until a given time.
2. Wakes up to perform a task.
3. Goes back to sleep.

Spring Boot does not perform any magic here. Internally it wraps ScheduledThreadPoolExecutor, a class from the Java standard library. Understanding ScheduledThreadPoolExecutor directly gives you deep insight into every scheduling behaviour you will encounter in Spring Boot.

---

ScheduledThreadPoolExecutor Basics

import java.util.concurrent.ScheduledThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class SchedulerDemo {
    public static void main(String[] args) {
        // Core pool size = 3: three worker threads live in the pool.
        ScheduledThreadPoolExecutor executor = new ScheduledThreadPoolExecutor(3);

        // Define the task as a Runnable (lambda).
        Runnable task = () -> System.out.println("Task running at: " + System.currentTimeMillis());

        // Schedule the task to run ONCE after a 5-second delay.
        executor.schedule(task, 5, TimeUnit.SECONDS);
    }
}

ScheduledThreadPoolExecutor extends ThreadPoolExecutor and adds the ability to schedule tasks at a specific future time. A normal ThreadPoolExecutor picks tasks from a queue immediately; a scheduled executor waits until the correct moment.

---

The Three Core Methods

1. schedule — Run Once

// Run ONCE, 5 seconds after submission.
executor.schedule(task, 5, TimeUnit.SECONDS);

The delay is counted from the moment the task is submitted, not from application start. The task runs exactly once.

2. scheduleAtFixedRate — Repeat at a Fixed Rate

// Initial delay: 2 seconds.  Period between runs: 4 seconds.
executor.scheduleAtFixedRate(task, 2, 4, TimeUnit.SECONDS);

Timeline example:

Event	Time
Task submitted	0 s
First execution starts	2 s (initial delay)
Second execution starts	6 s (2 + 4)
Third execution starts	10 s (6 + 4)

Formula: next execution time = previous start time + period

Critical interview detail — what if the task takes too long?

Each task has only one object inside the queue. The task object is re‑queued (with a new execution time) only after the previous execution finishes. Therefore even if a task takes longer than the period, the same task cannot run in parallel with itself. Execution is always sequential for a single task object.

Example: task starts at 2 s, finishes at 12 s.

• Compute next: 2 + 4 = 6 → already past → try 6 + 4 = 10 → past → try 10 + 4 = 14 → future.
• Next run: 14 s.

3. scheduleWithFixedDelay — Repeat with a Fixed Gap after Completion

// Initial delay: 2 seconds.  Delay after each completion: 4 seconds.
executor.scheduleWithFixedDelay(task, 2, 4, TimeUnit.SECONDS);

Formula: next execution time = previous finish time + delay

This is the key distinction from fixed rate: the delay is measured from when the task finishes, not when it starts.

Event	Time
Task submitted	0 s
First execution starts	2 s
First execution finishes	12 s
Second execution starts	16 s (12 + 4)
Second execution finishes	18 s
Third execution starts	22 s (18 + 4)

---

Internal Data Structure: DelayedWorkQueue

When you create new ScheduledThreadPoolExecutor(3), two things happen:

1. A pool of 3 worker threads is created (core pool size).
2. A DelayedWorkQueue is created — an unbounded min‑heap sorted by execution time.

The task at the head of the heap is always the one that should run soonest. As the heap is unbounded, it can grow as needed, limited only by available heap memory.

When you call executor.schedule(task, 5, SECONDS), the executor:

1. Wraps your Runnable in a ScheduledFutureTask that also stores the execution timestamp.
2. Inserts that ScheduledFutureTask into the DelayedWorkQueue (heapified by time).

---

Non‑Optimised Thread Flow (Step by Step)

Step 1 — Queue Empty, All Threads Waiting

When the pool is first created, the DelayedWorkQueue is empty. All worker threads enter the WAITING state — they do not consume CPU cycles; they wait indefinitely until signalled.

WorkerThread-1: WAITING
WorkerThread-2: WAITING
WorkerThread-3: WAITING
DelayedWorkQueue: [ empty ]

Step 2 — First Task Arrives

When the first task is submitted (via schedule / scheduleAtFixedRate / scheduleWithFixedDelay), the queue's offer() method:

• Inserts and heapifies the new task.
• Detects that this is the head element (first task in the queue).
• Calls signal() — equivalent to notify() — which wakes exactly one waiting thread.

Only one thread is woken because only one task arrived.

Step 3 — Worker Thread Checks the Head

The woken thread enters the RUNNABLE state and examines the head of the queue. Two possibilities exist:

Possibility A — Current time ≥ task execution time:

// Pseudo-code of the internal loop
ScheduledFutureTask task = queue.peek();
long delay = task.getDelay(NANOSECONDS);
if (delay <= 0) {
    queue.poll();   // Remove from queue
    task.run();     // Execute immediately
}

The thread removes the task from the queue and begins execution.

Possibility B — Current time < task execution time:

long delay = task.getDelay(NANOSECONDS); // e.g. 5 minutes remaining
// No busy wait — the thread suspends for exactly `delay` nanoseconds.
queue.awaitNanos(delay);
// The OS maintains the timer; when it expires, the OS wakes the thread.

The thread goes into a timed wait state. The JVM informs the OS of the timeout, and the OS wakes the thread when the timer expires. No CPU is consumed during this wait.

Step 4 — Task Completion and Chain Reaction

When a thread finishes a task and re‑queues it (for repeating tasks), a finally block runs:

finally {
    // If the queue still has tasks, wake one more waiting thread.
    if (queue.peek() != null) {
        queue.signal();
    }
}

This ensures that if multiple tasks are waiting in the queue, threads are chained: each finishing thread wakes the next.

---

The Problem with the Non‑Optimised Flow

Consider this scenario: three tasks all due at 14:00, all completed, and a fourth task due at 16:00. All three threads become RUNNABLE simultaneously.

Each thread:

1. Acquires the queue lock.
2. Sees that the fourth task is not yet due (delay = 1 hour).
3. Computes the remaining delay.
4. Enters a timed wait of 1 hour.
5. Releases the lock.

All three threads are now in timed wait state — the OS must maintain three separate timers for the same task. This is wasteful. The optimised solution is: only one thread should go into timed wait; the other two should go into ordinary (indefinite) wait.

---

The Leader Follower Pattern (Optimised Flow)

The leader follower optimisation uses a single leader variable:

• leader != null → a thread is already timing the next task; other threads should go into indefinite wait.
• leader == null → no thread is timing; the current thread becomes the leader and enters timed wait.

// Simplified view of the internal take() loop
private Thread leader = null;

ScheduledFutureTask<?> take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        for (;;) {
            ScheduledFutureTask<?> first = queue.peek();
            if (first == null) {
                available.await();          // Indefinite wait — no task at all
            } else {
                long delay = first.getDelay(NANOSECONDS);
                if (delay <= 0) {
                    return queue.poll();    // Task is ready — take it
                }
                first = null;               // Do not hold a reference while waiting
                if (leader != null) {
                    available.await();      // Someone is already timing — indefinite wait
                } else {
                    Thread thisThread = Thread.currentThread();
                    leader = thisThread;
                    try {
                        available.awaitNanos(delay);  // Timed wait — I am the leader
                    } finally {
                        if (leader == thisThread) {
                            leader = null;  // Reset so next thread can become leader
                        }
                    }
                }
            }
        }
    } finally {
        if (leader == null && queue.peek() != null) {
            available.signal();  // Wake one more thread if needed
        }
        lock.unlock();
    }
}

Leader Follower Walkthrough

Returning to our scenario: three threads compete for a task due at 16:00, current time is 15:00.

Thread	Action
Thread 1	leader == null → becomes leader → enters timed wait for 1 hour
Thread 2	leader != null → enters indefinite wait
Thread 3	leader != null → enters indefinite wait

At 16:00, the OS wakes Thread 1. It:

1. Sets leader = null.
2. Polls the task from the queue.
3. Executes the task.
4. Signals one more thread if additional tasks exist.

Result: the OS maintains only one timer instead of three — this is the entire purpose of the leader follower pattern.

---

Spring Boot Scheduler as a Wrapper

Spring Boot's scheduling infrastructure is simply a thin layer over ScheduledThreadPoolExecutor. The @EnableScheduling annotation triggers:

1. Loading of all scheduling‑related beans.
2. Scanning of all @Scheduled annotations.
3. Wrapping each annotated method as a Runnable and submitting it to an internal ScheduledThreadPoolExecutor.

The default thread pool in Spring Boot has one thread. You can customise this:

# application.properties
spring.task.scheduling.pool.size=5

Or define a custom TaskScheduler bean:

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.scheduling.concurrent.ThreadPoolTaskScheduler;

@Configuration
public class SchedulerConfig {

    @Bean
    public ThreadPoolTaskScheduler taskScheduler() {
        ThreadPoolTaskScheduler scheduler = new ThreadPoolTaskScheduler();
        scheduler.setPoolSize(5);
        scheduler.setThreadNamePrefix("my-scheduler-");
        scheduler.setWaitForTasksToCompleteOnShutdown(true);
        scheduler.setAwaitTerminationSeconds(30);
        return scheduler;
    }
}

ThreadPoolTaskScheduler is Spring's wrapper; internally it delegates to ScheduledThreadPoolExecutor.

---

Summary of Internal Flow

Application start
       │
       ▼
ScheduledThreadPoolExecutor created
       │
       ├─ Worker threads created → enter WAITING state
       └─ DelayedWorkQueue created (min-heap by execution time)
              │
              ▼
      task submitted via schedule / scheduleAtFixedRate / scheduleWithFixedDelay
              │
              ▼
      ScheduledFutureTask wrapped and inserted into DelayedWorkQueue
              │
              ▼
      signal() → one WAITING thread → RUNNABLE
              │
       ┌──────┴──────┐
       │             │
    time elapsed   time not elapsed
       │             │
    poll task      leader == null?
    execute          │
    re-queue    ┌────┴────┐
     (fixed)    YES       NO
                │         │
            timed wait  indefinite wait
            (leader)    (follower)

---

Interview Questions & Pitfalls

Q1: What data structure does ScheduledThreadPoolExecutor use internally, and why?

A: It uses a DelayedWorkQueue, which is an unbounded min‑heap sorted by execution time. The min‑heap property ensures that the task due soonest is always at the head in O(1) time, while insertion and removal are O(log n). This is far more efficient than a sorted list for scheduling workloads.

---

Q2: Can the same scheduled task run in parallel with itself?

A: No. Each task has exactly one ScheduledFutureTask object in the queue. That object is only re‑inserted after the current execution completes. Therefore the same task is always sequential, regardless of how long it takes or how short the period is.

---

Q3: What is the difference between scheduleAtFixedRate and scheduleWithFixedDelay?

A: scheduleAtFixedRate computes the next execution time as previous start time + period. scheduleWithFixedDelay computes it as previous finish time + delay. When a task consistently runs faster than the period, both produce similar results. When a task is slow, scheduleAtFixedRate catches up to the wall clock while scheduleWithFixedDelay always waits the full delay after each completion.

---

Q4: Why is the leader follower pattern necessary in ScheduledThreadPoolExecutor?

A: Without it, when multiple threads compete for a single future task, every thread computes the same remaining delay and each enters a timed wait. The OS must maintain one timer per thread. The leader follower pattern ensures only one thread (the leader) enters timed wait; all others enter indefinite wait. This reduces OS timer overhead and avoids unnecessary resource usage.

---

Q5: What happens when a thread in TIMED_WAITING state has its timer expire?

A: The OS level timer signals the JVM, which transitions the thread from TIMED_WAITING back to RUNNABLE. The thread re‑enters the for loop, checks the head of the DelayedWorkQueue, confirms the delay has elapsed, and removes and executes the task. The OS is responsible for maintaining the timer; no JVM busy wait occurs.

---

Q6: A Spring Boot service has a scheduler that should run every 5 minutes. The task sometimes takes 7 minutes. Using scheduleAtFixedRate, what happens?

A: The task takes 7 minutes. The scheduled executor computes the next execution time as start + 5 minutes. By the time the task finishes, the computed next time is already in the past. The executor then searches forward in multiples of 5 minutes until it finds a future time and uses that. The run is simply delayed; it never executes in parallel with itself. If strict overlapping prevention is required, use scheduleWithFixedDelay instead.

---

Q7: A common pitfall — what default thread pool size does Spring Boot use for scheduling?

A: The default is 1 thread. If you have multiple @Scheduled methods and they run concurrently by design, that single thread will serialize all of them. Always configure spring.task.scheduling.pool.size appropriately for your workload, or define a custom ThreadPoolTaskScheduler bean.