Improving Kubernetes Scheduler Performance

Placing quality and throughput are always a tradeoff. Kubernetes, now, uses a naive algorithm that goes over all its nodes and finds the best placement. This is simple and effective for most web workload, when most of your scheduled jobs will take "forever" to run. And as it states in the blog post, after some simple optimization, now the scheduler can schedule tens of jobs per second. There are other limits make it slower overall. So we stop optimizing scheduler to avoid adding unnecessary complexity in its early days.

job placement is also an NP-hard problem.

They also removed two rate-limiters that someone had (presumably intentionally) put into the code. You always have to wonder when you see "protective code" like that - why was it added in the first place? Was it premature optimization? A guess? Often if a weak component is strengthened, you end up with "forgotten" code like this and it's always an effort to find and remove it.

Yes, essentially. Of course the real work is in creating all of the benchmarks and harnesses to start measuring and investigating; as it always is in these non-trivial systems. The full story summary:

First, hit a rate limiter, removing it partially solved the performance issue at low scale.

Second, there was a slightly expensive "initialization operation" that should be only done once, made sure it only happened once.

Finally, found the expensive round math operation with micro-benchmarks and improving the math operation resulted in doubled throughput.

Thanks for reading it so carefully. Let me explain it one by one:

> they optimized "Round" which took 18 seconds

This is CPU profile. The overall sampled time is 79 seconds. The Round() method took 18 seconds. This has no direct indication to scheduling latency.

> by that reduced total cpu time from 53 to 23 seconds

This is about scheduling latency. In this experiment, we schedule 1000 pods on 1000 nodes and see how much time it took to schedule a pod, aka scheduling latency. Before the optimization, the latency is 53 seconds; after, 23 seconds. Of course, this is just one of the steps we kept optimizing.