Thank you for sticking around for the last talk of the day.
I'm going to start by apologising slightly.
I'm Richard Morsier or Mort from the University of Cambridge.
I'm talking on behalf of Amjad who actually is because we did this work in his PhD,
but this visit didn't come through in time, so he wasn't able to attend.
I should also note that it was funded in part by the Edmunds Project, which is an EU project.
It was complicated because it breaks it, but it was an EU project.
So the motivation for this was that we were originally looking to try to work on getting unicernals,
really densely packed on service for those who know anything about unicernals,
but essentially small tasks, densely packed on service.
We were looking at how Kubernetes performed for that, and we were trying to analyse what performance we were achieving,
in particular how the Kubernetes Autoscaler was behaving.
And again and again and again, the results just made no sense at all.
It could make any sense out of the performance measurements that we were getting.
After some considerable time, I think I've spent about a year looking into this,
trying to work out what was going on.
We came to the conclusion that it was to do with the way the kernel schedule was behaving on the work notes.
So essentially, context which overhead was going up much more than it really should.
And that has some pretty poor knock-on effects to have the overall cluster will operate when Kubernetes is scheduling work across it.
The original focus for this was a serverless style workload, hence the relationship for the Edmunds Project,
but we suspect this is actually more general issue here.
It's not just a serverless, although a serverless is a particularly poor workload in the sense that it will see this problem quite badly.
So extremely briefly, and I'm going to refer questions to Amjad if you ask any of the two hard.
CFS is the scheduler in it's currently the main sort of scheduler.
It is trying to be fair, and it's also trying to be reasonably efficient.
So it's giving each task that's running a minimum of time slice,
and then it's trying to scale the scheduling period so that each task is able to get the same approximately time slice from that.
So it's trying to be fair and it's trying to be efficient.
Layered kind of on top of that is secrets, so the idea that you can group tasks together and schedule them as a group.
And that means that you end up with these quite complex data structures that are trying to track individual tasks and groups of tasks
and make sure that they're scheduled effectively and efficiently onto different cores in your systems.
This is a multi-core scheduling problem with groups of tasks being scheduled.
So it's fairly involved.
It turns out that there's a reasonable amount of optimization that's gone on to try to make sure that selecting the next task to run is efficient.
So this is essentially captured in a red battery, so if you look at the images on the right there,
I think if that was a treat that's fallen over on its side.
So you start at the root of the right hand side, and then you've got these kind of subgroups of tasks within that.
So in the case of Kubernetes, you end up with a coupon slice,
then you have coupon's burstable and coupon's best effort within that or beneath that.
And then within coupon's burstable, you've got all the pods that are running in each of those pods is a C group,
which may contain multiple executing tasks for the different containers that are within that pod.
So you've got this kind of nested structure to it.
The data structure that's used to represent this is a red battery, so that should be pretty efficient, right?
So good asymptotic performance.
And the other leave the leftmost bottommost task in the red battery, which is the next one that's going to be scheduled is cached.
So the point is that that's cached, so you can get find that one very quickly.
Unfortunately, because it's a red battery, when you deschedule something, when you do the context switch,
and you take something off the CPU, you have to put that back into the red battery,
and that means traversing it and rebalance in the tree on the way down.
So that can take some time, and that time can increase as the load on the system increases,
and the number of tasks increases.
So you end up with higher per context switch costs, and then you have a lot of tasks hanging around,
because they're not getting completed.
You also have a higher rate of context switching, and so you get this kind of multiplicative effect,
where you end up increasing the overhead in the system quite substantially.
We did some benchmarking to try to show this, so we've got netters resource control framework,
and we've got multiple modified sozats.
We can look at the impact of increasing the number of concurrent secrets,
as the number of secrets increases.
We looked at doing this for a very simple kind of structure, so we could try to understand the results.
So that's function traces from the azure serverless functions of the service workload.
Grouped by essentially how much computation, how heavy the function is.
So put into 10 groups, you'll notice the log scale on the y-axis,
and essentially a small number of tasks, which are extremely computationally intensive,
and then it sort of tails off, so you've got most of the tasks don't do very much computation.
So you have a large number of light tasks and a few heavy tasks in that workload.
We also looked at comparing that, which was a kind of closely workload,
where new work is only introduced as all work is finished, so it's a responsive workload.
Again, it's just doing sort of trace free play from this azure trace.
Okay, which is kind of open loop, it's not responsive in that way.
And then we measured the overhead using F trace,
instrumenting the total time spent during the course schedule of logic, spent in the schedule.
What we find, if you look, for example, throughput, which is the top plot plot A,
and you consider the time, at the same time, you're looking at the time,
spent in context switching, and the time of an individual context switch.
So this is the schedule overhead, and the per-contoi, context switch overhead.
What you see is that you're at the green section here,
you're actually getting peak performance, the throughput's higher, for the azure trace.
Okay, but as you increase past that point, so you increase the density,
you're trying to pack more things onto the system, the performance goes down,
and it's going down as the average time per schedule operation,
and in fact the average time per context switch is increasing.
So you can see on the bottom plot there that the context switch time,
so the time per context switch, is going up from perhaps a few,
a small handful of microseconds, is starting to get up towards, you know,
10, 15, 20 microseconds, so it's going up quite a lot.
So it's a significant factor, is this increase in the average cost of context switching.
So the schedule adjustment that we made, we're to say,
the problem here is that we have these long-run cues.
We've got a lot of tasks hanging around that are actually most of the idle,
as I said, this is particularly bad in serverless workflows,
because one of the things that you do in serverless workloads
to try to avoid cold start problems where you've got to spin up the task
in order to respond to the incoming request is you keep idle tasks around
a bit longer than you would do normally.
So you have this kind of deliberate idea that you want to keep things hanging
about just in case you need them in the near future in the next minute or two.
So you've got even longer run cues in that workload, which is why that workload
is particularly bad for this problem.
But even without that, you have this problem that you've got tasks hanging around
idle, you're not getting the easy tasks out of the ways that run cues
stay long so the context where it's overhead stay high.
So what was implemented instead was the usual sort of approximation to a
shortest remaining time first schedule.
To try to get the easy tasks, get the light tasks out of the way,
keep the run cues short, don't waste your time doing lots of
system bookkeeping overheads, get on and do actual useful work.
What that does is it improves the latency and it reduces all the overheads
because you're getting c-groups out of the way so you're getting work
completed and off the run cue.
The approximation I'm using is by the C-group load credit metric,
which is tracking the recent C-group usage for all the threads in a given
C-group.
So this is the sort of plot that we have.
So to try to read this, it's a cumulative distribution function.
So you're looking at the latency of completing jobs of completing
requests and the cumulative proportion of those.
And what you can see is that with the blue line, the vanilla CFS line,
for the both heavy functions of the ten sort of heaviest functions that are doing the
most work and also the 90% of the lighter functions at the end.
With the blue line, that's pushed quite a long way to the right.
So there's quite a considerable proportion of those functions, which are taking quite a long
time to complete.
If you do the Oracle version, so this is a static, best possible case that you
could achieve if you knew the future in the short remaining time for this case,
that's the purple pink line.
And you can see that that line is shifted way to the left.
And what's happening is by allowing the tail of the lightest functions to complete.
So you're getting those right hand, that right hand is like plot.
You move another long way to the left.
That's getting things out of the way.
That's also enabling there to be more time available for the
computation intensive functions to also execute and do useful work,
because you're not wasting your time context, which you know at the time.
So it's actually doing better for all of the functions in the system,
not just the ones that you're deliberately targeting,
because you're reducing the overall overheads.
The realisation of this was done as a sub scheduling architecture,
so you can apply custom policies to specific C groups.
So in this case, given it's a sort of Kubernetes setup,
replying custom policy to the Kubernetes burstable C group,
so things beneath that, having this policy applied.
So we're not affecting the rest of the system.
Other tasks that are running in a way that they would have done previously.
They're not being affected by this.
And so load credit becomes the scheduling priority that's used for the server
of functions in the server's function sequence.
There's a couple of details there about how that's actually realised.
The patches of public, if you want to have a look at them,
and I'm glad I'll be happy to answer any questions if you contact him or contact him directly or through me.
The result of this is that with this in place,
you can get greater function collocation,
so you can pack functions in more tightly onto those,
and you don't see the performance degradation.
So you're mitigating the overheads, what you're seeing on the right
with the green schedule, you see the green line remains below the blue line
as the density increases.
Looking at the performance of this in more detail,
so looking at the base line there, if you take that as the,
if you like the sort of a current practice,
which is essentially to over-provision to avoid this problem,
if you don't hit these kind of heavily loaded work in those,
then you don't see the problem.
So if you do that, for this particular work there,
you needed 14 nodes,
and if you were based on the idea that you were going to pack them in
according to what their peak requested load was,
so in the Kubernetes request field that you're putting in.
So you're making sure you've definitely got enough capacity
to support this workload.
So this is pretty wasteful, but it means that things do
at least operate efficiently in the sense of on an individual node.
So you can see the blue line there is weight for the left.
So the request latency is quite low.
Everything is humming along quite nicely,
but with quite a lot of excess capacity available.
So you see that low CPU utilization,
only 30% utilization on the work nodes, that's all the case.
If you do CFS, then you can see that's the right-hand line,
the sort of RNG line, I guess it is.
So that can do better.
It's multiplexing the workload onto a smaller number of nodes.
It's multiplexing workload onto 12 nodes.
But you can't go pack the things in too tightly,
because as soon as you start going above about 45%
node utilization, you begin to see this degradation take effect.
Contacts which overheads become significant.
With CFS lags, we can get the same performance as with CFS,
as in fact, with the base case, but with only 10 nodes,
and we're able to push the CPU utilization on the work nodes up to 55%.
So you can pack things in or you get more done,
or you get the same amount on, I guess,
but you only need 10 nodes instead of 14 nodes to achieve that.
So it's a reasonably significant improvement
in the cluster efficiency, I think.
We looked at some different alternatives to doing this.
So there's some current work, so, or recent work,
EBDF, for example, which does improve things a bit,
but the same underlying mechanism is still there,
and the same underlying problem still occurs.
I guess it's the headline for that.
It's also quite hard to tune that, effectively,
to find out what the parameters are that actually make that work,
as well as you can.
And so, I guess the conclusions here,
are that C groups are really important for managing these workloads in production.
Right, you do need them.
But the problem you've got is that, as the workload increases on the node,
reinsertion of the switched out task,
back into the red battery, begins to take considerable time,
appreciable time.
And that, because of that, you end up with more tasks still live,
because you're wasting time switching things around,
instead of getting worked on.
And because of that, you end up with more context, which is as well.
And these two things combine more flickatively to give you quite high overheads on the node,
on the worker node.
The effect of that is to increase latency variation quite dramatically.
It decrees the effective capacity on the node.
And the thing that that then causes is Kubernetes,
when it's trying to pin-pack and schedule work on different worker nodes,
it's got the wrong idea completely about how big the node is,
what the effect of capacity of a given node is.
So then put more work onto a node, thinking that it's got capacity,
and it doesn't have capacity, and so it also spirals down.
At the moment, it appears that you avoid that by other provisioning,
in the traditional way.
That's not necessarily the most efficient thing you could do.
By tweaking the schedule a bit, I mean,
I don't think it's a big patch in a normal way,
but it's quite a fiddly patch to get right.
You can end up essentially getting 10 to 20% extra capacity
after your cluster for these sorts of workflows at least.
Because you're allowing the short task to complete,
keeping the run queue short means you don't have all these contacts
which overheads.
So you're not wasting your time in bookkeeping.
You're getting actual work on instead.
And with that, with a few minutes to spare you, I'll finish.
Do we have questions?
Yes, Alex.
So I'm guessing this work has been done over several years,
but I'm sure you're aware that Shedex was merged.
Yeah.
So I'm sure you're aware that Shedex was merged last year,
and I guess the question I have is,
oh, actually, you actually have it on the slide.
Whether on this approach, we would apply to Shedex,
whether there's stuff that you can't do with Shedex.
So essentially, a whole battle.
I've got it, so I have a master student.
I'm asking on some athletes here,
but I have a master student doing his research projects,
exploring, precisely that.
So seeing how far down this path we can get using the Shedex extensions,
and in fact, looking at whether it will,
how much it might supply an arm as well just for added from.
So he's doing it on a Raspberry Pi, just because why not.
Yeah.
We've definitely seen a bunch of that going on.
The numbers you've seen on the Kubernetes side,
that we've seen, particularly on high core counts,
very busy sellers, that's something that you're effectively getting
locked out of 30 to 40 percent of cases of your hardware,
because of that.
One of the conservation that we tend to do is just slice the machine
in a few big VMs, then call it done,
which then kind of fixes the issue the other way.
But Skedex is pretty interesting for that.
So we're talking with Mike.
It's getting an actual change into a CFS.
It might be not tricky, because if you look at it the wrong way,
it's going to redress someone else somewhere that you didn't really think of.
But Skedex makes that a lot easier because night,
so the need becomes a Skedule extension,
that's optimized for Kubernetes,
optimized for Docker, optimized for whatever you're running on the machine,
and then people are going to be very willing to just run that.
I think that's completely fair point.
That's why we're interested in exploring how much you can,
how far down this patty could go over Skedex.
Having said that, putting it maybe slightly more controversial,
academic hat on this sort of thing, like I mentioned it,
I don't think it's the case that CFS is the perfect schedule
for all possible workflows,
and the sorts of situations that this is deployed into,
and not necessarily the same as when CFS was first conceived
and designed and implemented.
I think that it would be a long-term mistake
to decide that CFS can't ever be changed.
You may need to present suitable evidence,
a suggestion it's a good change you're making,
but to say you can't change it ever is,
I think, clearly wrong, particularly as kind of workload,
keep changing in this way.
So we did get, we've tried to submit this work,
trying to get it published in several academic venues,
and we keep getting pushback for different reasons,
which is becoming infuriating.
But one quite reasonable pushback we had earlier on,
which is actually the question of,
okay, this works for your workload.
What does it need for everybody else's workloads?
So that's why, after I did spend some time
with Reds couple, trying to explore other workloads
that were not this workload,
and why the changes are located just to the cube,
what's it, the cube burstable pods,
so it shouldn't affect anything else,
and then we tried to demonstrate
that it didn't affect anything else,
it just improved things for these workloads.
Other questions.
All right, thank you very much.
Thank you.
And we've done that's a wrap for the Canada Devrims,
so we'll see you next year, hopefully.