Cloud Native Computing Foundation KubeCon + CloudNativeCon North America 2021, 29 Oct 2021

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Trimaran: Real Load Aware Scheduling in Kubernetes - Abdul Qadeer, PayPal & Chen Wang, IBM

Description

Don’t miss out! Join us at our next event: KubeCon + CloudNativeCon Europe 2022 in Valencia, Spain from May 17-20. Learn more at https://kubecon.io The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects.

Trimaran: Real Load Aware Scheduling in Kubernetes - Abdul Qadeer, PayPal & Chen Wang, IBM

Kubernetes is a popular solution for container orchestration and cluster management. Cluster management creates opportunity to improve resource utilization which can provide an organization with cost savings. To achieve this, we can make the native Kubernetes scheduler aware of the gap between its declarative resource allocation model and actual node resource utilization. We can pack pods more efficiently in a lower number of nodes considering real load of nodes. Native scheduler on the other hand only considers pod requests and allocable resources on nodes with its default plugins. We introduced two plugins to the scheduler community - TargetLoadPacking and LoadVariationRiskBalancing under the Trimaran framework to address this problem with collaboration between PayPal and IBM. The plugins provide scheduling support for all pod QoS guarantees.

A

Okay good afternoon and welcome everybody uh in person and online. um Thank you for joining us for trimaran real load, we're scheduling in kubernetes. um Would you all join me in welcoming um abdul kadir from paypal and chen wang from ibm.

B

uh Good afternoon, everyone- those present here and greetings to my uh my greetings to those virtual present virtually so I'm abdul khadir. I I'm a senior software engineer at paypal, I'll be presenting on load, aware scheduling with my collaborator chen wang, who is a research scientist at ibm.

B

So the image you see here is of trimaran, so what it stands for is like a three hulled boat, which provides more stability and safety in the ocean. All right, let's get started.

B

So this is the agenda for today uh we'll go over the motivation, the background and the problem, definition followed by the primer and architecture, the design and the plugins. We contributed to the open source community. The first one is the target load packing and the second one, the load variation risk balancing plug-in.

B

Then we have a demo and then some of the challenges, timer and phases how we overcome them, followed by good practices in using primary in production and some future work that we have to do so. Let's get started with further review.

B

So, as many of you may know, kubernetes provides a declarative resource model for its pods. What I mean by declarative model is that the resource usage that you define for your pod or the container needs to be defined in a spec before you're able to run it and run your workload and the core components in kubernetes, namely the cubelet, the scheduler uh they honor honor it to behave consistently with respect to the quality of service guarantees.

B

Now, given this the developers they tend to over provision the resources with this model, uh which you know, one of the reasons is that they want to avoid the penalties of evictions and cpu throttling that the kubernetes would do now. One way to solve this problem of declarative uh model is to benchmark your applications, but we we know that, like it could be comparison to do for all your production applications and, in general, estimating real load is hard now.

B

With that background, the main problem we are trying to solve is that the default scheduler in kubernetes it uses allocation based scheduling model and it can lead to under provision nodes in terms of resources and fragmentation, of course, across the cluster.

B

What you see on the right bottom right is a graph from 29 day google trace in their cluster, and you can observe here that the usage is about 40 of the requests which implies a lot of it is over provisioned, okay, now moving on to the primer and design and architecture.

B

So around the time we started working on this problem, the cube the scheduler provides kubernetes scheduler framework. It was in beta api and it was moving towards stable. So we decided to leverage it to contribute our plugins. In now the framework it provides flexibility to extend the scheduler in different apis and uh trimaran plugins.

B

They do so in an extension point called scoring extension point if there's an upcoming talk by uh six scheduling, folks uh and you're, more than welcome to attend that, if you want, if you're interested in a scheduling, deep life now for a given scoring plugin, uh what you have is like you, get an input as a set of nodes and what you output are different, node scores for that for those nodes.

B

So that depends on the algorithm you define in your scoring plugin.

B

So in the diagram you can see that the timer and plugins are part of the kubernetes scheduler, so they run in the same binary.

B

Now the next major component in our design is the load watcher, so load washer can be defined as a cluster-wide aggregator of metrics, which is backed by a third-party metrics provider.

B

We'll I'll explain in the next slide what all metric providers we support. The load watcher also maintains the cache in memory for fast lookups whenever the plugins need to talk to the load watcher to get the live metrics.

B

It also maintains its cache in in a db, to provide some fault tolerance if there is a failure and fast recovery during restarts uh more in the next slide about load watcher. So another way to think about load watcher is that it is sort of a wrapper which uh unifies metrics from different providers into a common format that the tramadon plugins understand and the currently supported ones which we added are prometheus signalfx by splunk and the native kubernetes metrics provider.

B

It can be extended by the users to support any other metrics provider if needed. Now from the diagrams, you can see that there are two options of using the load watcher. So first one is that you can use it as a service and then the second one is that as a library, so each one of them has their pros and cons it's up to the users to decide what works best for them.

B

For example, in the case of using it as a service, you have a separation of failure component from the scheduler process and the ap additional api call latency from contacting over the network.

B

It can be minimized if you use like a local container through the scheduler pod, and the other point is that it scales separately from the kubernetes scheduler. So this is important for us, because in the future we want to make it a bit more complex by adding machine learning models which could make the washer process more cpu intensive, and we don't want it to compete with the scheduler for resources.

B

What you see, on the other hand, if you use it as a library from the plugins inside you have, of course no api call over the network, which is important. When you have fast scheduling cycles, then you have a much simpler deployment.

B

We at paypal use it as a service and red hat folks. They they integrated uh trimaran in their product, offering on kubernetes openshift and they use library as in in their offering. What you see in the rightmost column is a sample data that the road watcher process maintains in the cache.

B

So it maintains windows of different metrics that are needed by the plugins and the window. Durations range from 15 minutes to five minutes and we use each one of them as needed, depending on the use case. It also adds some more metadata to enrich the water cache.

B

Coming to the meat of the design, uh so for the first plugin that we contributed, uh there are two main objectives we had in mind when we designed the target load packing plugin. The first one is that we want to achieve high utilization across all the running nodes in the cluster, and basically we want it to be around a given threshold that we can set before we run the plug-in, and we do so by packing the pods as long as the cpu utilization is under the given threshold.

B

The other objective is to maintain some sort of safe margin for cpu usage spikes, which can happen due to unpredictable loads. So we like to do that by spreading the the incoming pods onto the nodes, which can result in higher safety. Higher safety here implies that there's more uh leftover, cpu cores left.

B

uh Here's some here's, the algorithm for the target load packing plugin I'll, try to explain that in similar words.

B

So what you see on the right is a graph of the different scores that that the plugins provides versus utilization. Now the kubernetes framework uh it supports this, it was. It wants a scores in the range 0 to 100, so a node if it is scored higher, it means that it has more chances to be selected for scheduling.

B

So the first line you see is an increasing function. So, as the utilization increases from 0 to 50, we favor the nodes by scoring them high. This implies the bin packing. I talked about that. We keep tracking the ports on the nodes now, as you reach 50, that is our threshold utilization.

B

The graph shown here is like for the utilization of 50 by the way, so there is a drop there is a discontinuous function. So what that implies is that we would like to penalize nodes which are trying to exceed the utilization that we set for as a threshold. So we try to favor the nodes lesser as the utilization goes beyond 50 percent.

B

Now in point number, two and three just explains uh how we calculate the incoming parts uh usage, because we we don't have the usage metrics for it yet so we predicted predicted based on uh it's different, based on the quality of service of that specific port. If we have both requests and limits, then we we specify the limits as the usage or more like the prediction. And then, if there are no limits, then we have a multiplier for the requests and if there are, if it's the best referred pod, there is no request or limits.

B

Then we assume some number, which is a minimum utilization.

B

So that said, another way to look at the algorithm is that it switches from a best straight variant of bin, packing to a least straight variant as the utilization changes from zero to hundred.

B

Okay, so here's some results from an experiment we did uh with about 100 nodes and 400 pods. uh We did this using an open source tool called kds cluster simulator, with some changes to incorporate out of three out of three plugins, which is what we contributed.

B

So the pods here have birth, stable qos, so the limits are larger and different than the requests, and they have a normal distribution of utilizations which remain constant throat through the time they they run. Now. The graph on the left you see is for the native humanities scheduler and the graph on the right is for primal.

B

Now there are multiple observations you can make from these two graphs by analyzing them. The first one is that the area that you see under the threshold mark the red line that you're seeing is much higher for target load packing, which implies better capacity utilization across the cluster.

B

The second one is that there are lesser number of hot nodes uh in the case of target load packing by hot nodes. I mean that any nodes which exceed the of threshold utilization that we had as an objective so that they are minimized in the case of a targeted, packing plugin.

B

The last one is that there are lesser number of fragmented cores. So the way you can tell that is so each bar here respond corresponds to a specific node. So the variance in the height of the nodes is much lesser in the case of target load packing.

B

So that implies. There are lesser number of fragmented courses compared to the default scheduling.

A

B

Moving on to the next important question for production, how well does trimaran perform so these tests were done in scheduler perf tests from the kubernetes main ripple. So just for the background, it is what kubernetes uses to publish their uh scheduler metrics so that they know that the metrics, for example the latencies, the algorithm latencies and the end-to-end port scheduling duration, is within the slos or not. So we modified that to include our own plugins, and uh so we did two experiments here.

B

The first one is that we used 5000 nodes and 1000 calls to schedule. The other one is with 500 nodes and thousand pods. There are same 500 number of init pods in each of them. These are like a set of standard tests which you can use to compare now before, and we can see that the trimaran beats the default scheduler in both of the experiments.

B

Now before I explain why this happens.

B

I like to mention that the default scheduler it has a set of scoring plugins that are configured by default. Now framaran uses two lesser plugins than what is present that default. So essentially, you have like one less plugin compared to the default. So first reason for the performance benefit. Is that there's like one less plugin who's doing scoring, so it is faster.

B

The other one is that we optimized the plugin to use fast, json, encoding and decoding libraries, and we have a background thread that fetches such as metrics from the load watcher cache so that it doesn't it prefetches before each scheduling cycle.

A

B

So, moving on to my last slide, this is about the strategies of primary primary at paypal, as I explained uh so. The main use case for us uh working in infrastructure team is to maintain and ensure efficiency of the fleet, so paypal relying on the cloud we would like to also minimize the costs. Now this translates to the uh technical requirements I mentioned for target load packing plugin the objectives.

B

One thing I didn't mention is that we also have a requirement for the replicas of an application to be spread across topologies by topologies. Here I mean it could be nodes or node pools or different zones, for example.

B

So that said, we combine our plug-in the target load packing and port topology spread to achieve these requirements.

B

The current status is that it is actively tested in for for deployment in qa, followed by production, so this will be uh enabling efficient fleet for a majority of the people applications over to my collaboration.

C

Okay, thank you. So um next I will introduce the load variation risk, balancing plugin uh that is designed to solve, and you should be observing uh one of our production clusters, so we observe that um even the nodes will have different will have the same average utilization.

C

When you consider the preference to schedule the power, they may have significant different load variations and it's very important to account the usage variations and notes when scheduling paths, namely the higher vibrations of the workload you have on the node, the higher risk. You will have to schedule that path and then, if the power runs there and there's some birthday workload, you will easily end up with like pod evictions or some performance issues. So this plugin is designed to balance such a risk.

C

So let's take and take a look at an example.

C

Suppose we have two nodes like each has: a capacitive, eight cpus and only five are requested on both nodes, and in that case those two two nodes are deemed equivalent uh when the default scheduler is trying to schedule paths and then it can fully fit in both nodes and then if we can only consider the average utilization and you may have exactly the the same average utilization on both nodes, so considering the utilization average utilization, you will also regard these two are the same and then um so.

C

But if you look at the variations on these two nodes, apparently on node 2 at peak usage, the maximum utilization is much higher. So the scoring plugin we want to propose is to consider not only the average utilization but also the variation on that on that node.

C

So if a path can fit in both nodes in this case, in order to minimize the risk of over committing at the peak hour, it is much safer to choose node one than that node two right, so to better understand what we are actually balancing uh based on what we can balance based on the average and standard deviation.

C

um Let's just draw all knows average and standard deviation in a new sigma plot, where mu is the average and sigma refers to the standard deviation.

C

So when your scheduler is trying to balance the average utilization across all nodes and their uh node utilization will look like the top left chart where it is the vertical line and all nodes average utilization are the same. So if you want to balance the vibrations on on available notes, it will look like the horizontal line on the red part top left plot. So if you want to balance something like the your variation is proportional to your average, it looks like the lower left chart.

C

I don't know if there is a practical use case for that, but it's a very good illustrative example to explain the last one which is balancing the risk, so the higher average utilization you have. You want lower uh variation on that node and the higher variations you have. You may want lower average utilization and it will look like this line and which is basically mu, plus sigma equals to some constant.

C

So this is exactly how we design this uh scoring plugin.

C

So, assuming you have a path coming and it's requested resource, let's denote it as r and then specifically what the album is doing is it is going throughout the node for each node, it's going to get the sliding window average and the standard deviation of resource utilization, and then it used the average utilization plus the arrival paths request as the prediction of the future average utilization on that node and then so. We also use the standard deviation.

C

We observed in the past time window to assume uh assume it will be similar in the future time window and then, if we place them together, just as what I have shown in the uh graph in the previous chart, eight will be our risk, so we want to balance this risk. Of course we want to bound it by the risk in the range like zero to one and then so. We can scale it up to the priority score in the because it's lower risk. You have the higher score.

C

You will prefer to choose that node, so it's one minus row multiplied by the maximum priority score and then finally, the scheduler will just choose. Whatever is a high score, so next I will show a simple uh two simple demos on how our two plugins can be deployed and how it behaves in a real cluster.

C

So here we are in the cluster of three nodes and we are going to first deploy the target load, packing load, packing plugin.

C

So, let's take a look at details. What you want to create and then including a service account you want to use for this scheduler uh all the arbitrals that are needed by the scheduler plugins. You want to bond, bind this these rows with your service account, including uh also the cube scheduler cluster row, and then you want to create a config map to wrap all the scheduler configurations there uh and within that config map, you want to disable the complete, complicated plugins and enable our target load packing plugin.

C

So here the important parameter to configure is for the target load. Packing is like the percentage of utilization. You want and the endpoint of your measure provider, and then we can mount it to the deployment of the scheduler where we just use the upstream scheduler plug-in image.

C

So we go ahead, creating namespace trimmer run and within the traman namespace. We deploy this scheduler and we can also see if it's running now. So I record all the demo, because the whole demo will run for like an hour and we can speed up a little bit in deploying those workloads.

C

So now we log into the scheduler um part, see all the detailed messages and then we go ahead to take a look at the workload we are going to deploy in the cluster. So this is a simple hamster application.

C

It's used around 400 millicourse, but it's requesting only 200 millicourse and we are going to see the target load. Packing will pack nodes up to the predefined utilization percentage.

C

So here we prepare a simple script to generate the workload and then it will create a part every once a while and totally we can define how many parts we want to create in the cluster.

C

And what it does is just replacing the id in the part template so totally we are going to create this part 36 times.

C

And here I speed up a little bit uh because it will run for longer and uh on the lower bottom window you can see the target load, packing uh plugins logging, some messages on binding paths and and on the right hand, side. The first one is the actual part usage versus the request. The second one is the the utilization on each node.

C

So what you are seeing is it go ahead to pack on one node onto reaching the target utilization percentage, and then it starts on the other node and the third one is the number of paths testing paths scheduled on that node. So similarly, it starts packing on one and then spreading to so when all of those reach to like the target utilization, the scheduler will try to spread the paths across nodes to balance the risk.

C

Okay, next, let's take a look at the load variation risk, balancing plugging.

C

So similarly, we will create all those service accounts, uh our back views and deployment. It's all in our documentation. You can find it in the tremoran plugin ripple.

C

So I will explain a little bit on the right hand: side on the right hand, side we will have a testing part request versus the usage and also the the cpu utilization on all nodes. Sorry, this is.

C

Okay, so it was replaying the previous uh demo yeah. Here we have the the behavior of the node version risk balancing plugin in the cluster. We have three nodes on the left, showing their uh allocable resources and the variation of the usage on each node. In the middle we see we show the statistics of the average and standard deviation, and then we go ahead to create a testing workload.

C

This workload is just a simple stress workload with some variations.

C

So now we are creating a testing work namespace for the workload and created the path and, on the right hand, side. We have all the logs from the load version risk balancing plugin. You can see the details about like it is computing, the cpu and memory average utilization and standard deviation, and it adds them together to compute the risk score and then based on the risk. It's coming up with the score.

C

And it actually also combined the resources. So if you have a higher score on cpu but lower score on memory, it will always choose the memory, uh the bottleneck resource score. So now you can see um there's bigger variations on the first node and the third node, and that's why even uh their average utilization are similar. The part will eventually be scheduled to the middle one.

C

Okay, so just a summary: if what, if we have a birthday arrival pass, and during that time we may not have enough metrics changing and then we look like the matrix like every five minutes, but when you have like a hundred parts arriving in one minute and then it's not reflected to the nose what we do so in that case the matrix would be missing, but we we still have the previous utilization window and also the arrivals of path.

C

So we can use the arrival supply to predict what would be happening in the next time window. So for those parts we request and limits, we always come with the limit. So if you have 10 parts arrived and each one is requesting um one cpu, we add up to 10 cpus and then for those parts with only request values. We can configure a multiplier to leave some safe margin of your inaccurate prediction and then for those parts of that best effort.

C

You can also configure what might be the threshold for your uh for your power request, pod usage and in the case that one provider is not accessible. One metric provider is not accessible. We can always fall back to the metric server solutions and uh you can also like in the future we plan to use multiple metric sources and do cross validation in the load water. So if one metric provider fails, we can switch to the other so from development to test and testing of these plugins, we learned several licenses throughout the way.

C

First, we should be very careful about how frequently we retrieve metric data, so the load on metric providers are not acceptable. You are not overwhelming, uh like a promises and but the interval should not be too large.

C

Then we have like outdated metric data um so, and this is exactly why we introduced load virtual library, which only fetch data from providers periodically and cache it in the scheduler plugin, and so it's ready to be used whenever the pod arrives and second, we should always have a fallback solution, especially for plugins that use a lot of metric data, because metric provider can be inaccessible.

C

Third, it's important to not use complicated plugins together, for example, target load packing is targeting the average utilization and then the load variation risk. Balancing is targeting both average equalization and standard deviation, so they have some complicated objectives.

C

You should not use them together, so, but even with tremor and plugins, uh we can never predict the load, variation or load usage a hundred percent accurately. So you can always end up with some over provisioning uh node uh if the pod usage climbs up so here are some future work. We want to do first, we want to integrate load washer with, for example, this scatterer to the schedule paths based on their actual usage to solve the reported issue.

C

I show here and second, we plan to include some additional resources, such as io and natural boundaries, and here we propose a new proposal. New cab proposal in the community called network award scheduler proposal, and it doesn't only consider the bandwidth allocation, but also the latencies requirements you may have in either a distributed cloud or in a data center cloud and in the future. We also want to try some machine learning models to have a more accurate uh prediction of utilization of our load schedulers.

C

So here are some references if you want more details and lastly, we would like to express our appreciation to those who cannot attend the conference in person, including tan and drinan, from paypal and other from ibm research that all contributors to this project, and we really appreciate help from uh all members in the sixth scheduling team- and here is questions.