Interview questions
Deciding when: ordering work
1If two schedulers both keep the machines equally busy, why does the order they choose matter?
The total busy time is the same, so only the average time jobs spend in the system changes. For two jobs of size 1 and 100, running the short one first gives a mean of 51; long first gives 100.5. Order moves delay between jobs; it does not remove it.
Read moreWork is conserved: only delay moves
2Why is shortest-remaining-processing-time (SRPT) the best order, and why can you not simply use it?
It minimizes the mean time jobs spend in the system, but it needs each job's run time, which is unknown when the job arrives. Every other scheduling mechanism is a way to work without that number.
Read moreOne fact, one missing number
3What is head-of-line blocking in first-in, first-out scheduling, and what is FIFO good for?
A short job waits behind a long one that arrived first. FIFO needs no information and gives the lowest variance of waiting time, but it inherits all the variance in job sizes.
Read moreFIFO, priority, fair, capacity
4How does a multi-level feedback queue approximate shortest-job-first without knowing job durations?
Every job starts in the top queue and sinks to lower queues as it uses CPU, so short jobs finish near the top. It needs aging, periodically promoting jobs, so long ones do not starve.
Read moreMulti-level feedback
5Does shortest-first scheduling starve big jobs?
Not on heavy-tailed workloads, which most real ones are. The mass of tiny jobs clears so quickly that most large jobs also find a nearly empty queue, so SRPT helps most jobs, including most large ones. Starvation appears when job sizes vary little.
Read moreA correction to folklore
6What does Dominant Resource Fairness (DRF) equalize?
Each tenant's dominant share: its largest share of any single resource in the cluster. In a cluster of 9 CPUs and 18 GB, where tenant A's tasks need more memory and B's more CPU, A gets 3 tasks and B gets 2, both at a 67% dominant share, and 4 GB stays unused.
Read moreFair scheduling
8When can Earliest Deadline First (EDF) scheduling meet every deadline?
Exactly when Σ (Cᵢ / Tᵢ) ≤ 1: the work Cᵢ each task needs per period Tᵢ, summed, fits. Above 1, misses cascade like dominoes and EDF becomes the worst policy, so it needs an admission gate.
Read moreDeadline-aware scheduling
9Why does gang scheduling waste capacity?
A gang job needs all its machines at once, so the scheduler must keep machines idle while it collects a full set, and two half-allocated gangs can deadlock, so allocation must be atomic. The idle time is the price of making the job possible at all.
Read moreGang scheduling
10When is it worth waiting for a slot on a machine that holds the task's data?
Wait only if the expected wait is less than (1 − 1 / ratio) × run time, where ratio is how much slower the task runs on remote data. With 10-second tasks that run 10 times slower remotely, you may wait up to 9 seconds.
Read moreDelay scheduling
11Why can adding machines sometimes make a job made of dependent tasks slower?
Greedy schedules can behave non-monotonically, a result known as Graham's anomaly: more machines can change which tasks run first and lengthen the whole. The finish time is bounded below by the critical path, so order tasks by the remaining critical path behind them.
Read moreDAG-aware scheduling
12A service is at 20% CPU but requests take 10 seconds. What do you check first?
A shared queue or lock carrying work of very different costs. Measure the age of the oldest waiting request rather than CPU.
Read moreHead-of-line blocking
13What are the two families of fixes for head-of-line blocking?
Stop sharing (separate queues or pools per class of work), or stop the work being so uneven (bound the size of each item by splitting large jobs into chunks).
Read moreHead-of-line blocking
14What is priority inversion, and how do you fix it?
A high-priority task waits for a lock held by a low-priority task, which a medium-priority task keeps preempting. Fix it with priority inheritance or a priority ceiling; across shared services, carry the priority on the request.
Deciding where: placement
15How do you test whether data locality still matters for a job?
Compare the bytes the job reads per CPU-second with the network bandwidth available per core. A 25 Gb/s network card shared by 16 cores gives about 200 MB/s per core, close to a scan's 200–800 MB/s, so scans tolerate remote data, while shuffles do not.
Read moreThe modern test: bandwidth per core
16When does spreading a job across racks help, and when does it hurt?
It helps jobs that survive if any copy survives, such as replicated services. It hurts jobs that fail if any part fails, such as gangs: with a 1% chance per rack of failing, a gang spread over 4 racks fails 3.9% of the time, against 1% in one rack.
Read moreOR-jobs versus AND-jobs
17How do you decide whether cheap, interruptible spot machines are viable for a job?
The overhead is about τ / (2M) for a checkpoint interval τ and a mean time between interruptions M: with τ = 30 minutes and M = 6 hours, about 4.2%. Short, idempotent tasks need no checkpoints at all.
Read moreThe viability test
Scheduler architecture
18Name the four cluster-scheduler architectures, and their analogues in databases.
Monolithic (one global lock), two-level with resource offers (pessimistic locking), shared state (optimistic concurrency, compare-and-swap on a shared view), and distributed sampling (no coordination at all).
Read moreThe four architectures
19How many random machines does a sampling scheduler need to probe?
Two. Picking the shorter of two random queues gives an exponentially better tail than picking one at random; probing more improves things only by a constant factor.
Read moreSampling needs only two probes
Workload management
20How does a queue's depth relate to latency?
The worst wait is queue depth ÷ service rate: a limit of 600 at 100 requests per second is a 6-second worst wait. An unbounded queue is an unbounded wait.
Read moreThe queue is the control surface
21Why should a server check each request's deadline when it takes the request off the queue?
Requests that will miss their deadline anyway are dropped before they use the resource. That keeps goodput, results someone still wants, high, when raw throughput would count abandoned work too.
Read moreCheck the deadline at dequeue
22How does AIMD set a concurrency limit?
Add one to the limit while latency stays flat; multiply it by a factor such as 0.9 when latency rises. Your own latency is the only signal you can measure locally of a limit that is really global.
Read moreAdaptive limits: AIMD
23Why does autoscaling not absorb traffic spikes?
Its loop delay, detect + decide + provision + warm up, is 30 seconds to minutes, and a control loop cannot regulate disturbances faster than its own delay. Spikes need headroom, a queue, or load shedding.
Read moreAutoscaling
24Why do resource quotas not stop the noisy-neighbour problem?
A quota governs only resources that can be named and attributed to a tenant. Cache, memory bandwidth and network queues are consumed without being requested, and that remainder is the noisy-neighbour problem.
Read moreMulti-tenant isolation and quotas