Cloud Native Computing Foundation KubeCon + CloudNativeCon Europe 2019 (Barcelona), 23 May 2019

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Intro: Scheduling SIG - Da Ma & Shivram Srivastava, Huawei

Description

Join us for Kubernetes Forums Seoul, Sydney, Bengaluru and Delhi - learn more at kubecon.io

Don't miss KubeCon + CloudNativeCon 2020 events in Amsterdam March 30 - April 2, Shanghai July 28-30 and Boston November 17-20! Learn more at kubecon.io. The conference features presentations from developers and end users of Kubernetes, Prometheus, Envoy, and all of the other CNCF-hosted projects

Intro: Scheduling SIG - Da Ma & Shivram Srivastava, Huawei

A novel Flow Network Graph based Scheduling approach in Kubernetes: Today’s Kubernetes clusters can comprise of 5,000-10,000 nodes, increase by an order of magnitude from original design specs. The default Kubernetes scheduler dates back from earlier more modest deployments. It is queue-based, processing unscheduled pods in sequential fashion. For a large Kubernetes clusters, such scheduler processing logic can introduce long, even unbounded scheduling latencies, negatively affecting overall throughput for workload deployments. This talk outlines how Kubernetes is a victim of its own success, scheduling-wise. It lays out the current pod queuing challenges and describes a novel scheduling approach based on Flow Network Graph technique, enabling low workload scheduling latencies at scale. The presentation details the resulting extreme efficiencies and high quality placement decisions of such an approach and the accompanying pluggable scheduling policies.

https://sched.co/MPiV

A

B

A

Time I'm going to give our introduction about six Gabby, and this is cows, the cost schedule, sorry co-leader office, things cavity.

C

I am one of the co-owners of second project which is currently under a six, so I'll be talking on the per second part per second informant side. So what I will be.

C

A

So so this is a chart of the six cavity I talking from our chart chart page, you highlighted something is here we didn't seek scattering. We used a worse thing, but it was a major target of six getting a true to make the Pope s magnetization, and there are also several distinctive studs, a resource called her and controller, something something like that. This can be at least autumn. Officially is his out of scope of six caddy, but we are. We are also interesting this part. So if they're related us to seek scattering, you can't talk.

A

You can't discard with us, but officially we focus on the poor placement decision in this things come in part, and this is the award for our sick scalping. Oh generally, we have two meeting now the first one I think this is the more friendly to the to the Europe, and you ask I mean our one is the more friendly to Asia. So if you are interesting, you can't join, choose the medium to try ass, wait, how truly there for each for you to seek, and the first one is a bogey, okay, yeah and another one.

A

Is me yeah. We also house like also how many, no least and the other thing here's our issue. So if we you only have an interesting want to contribute, you can pick up some easier submitted protests and we are also open to join our city meeting to to show your proposals or your idea or something like that and for the stick scalping with how in the in the past few years, so we initiatives several sub programs here now for the for the six cutting the major scheduler is a coops gatherer.

A

This is the default scatter in the upstream, and we also you could be several other things now. The first one is a new batch crew batch is a candle for batch scheduler focus on to run such kind of wonky eye test flow, something like that. Another one is disc Adler which have default scattered to make.

A

Misguided none of the current Iran import, another one is the president. They try to use a different prism to resolve the problem to resolve the pole placement Department. Are we okay well or of each of each one? So you can't have a lot of our our six. Now, the first one I'm the major work of six caddy as the default scatter, the default gatherer will try to do the scheduling poll by boat.

A

We have work, you here's, oh sorry, and now we try to find a better to pass the poll for the personal for the polar tube placed. This is the the major lot, the major target of who of divorce gatherer. So we have to meet your face now. The first one is the predicts. We need to make sure the to no match the basic requirement of hope for them, who some know the Slagter. Some note of an eatery, something like that, where you fill out some to know, did not meet my requirement.

A

This is the these are predicts face. Another one is the party the face we already to filter out two three: four: we will fight the best one. We have several policies here, such as Empire, something like that. We will find it the best one. So in this case the no.3 is how to how have a high score here. So we will push the pole in the internal two three right.

A

So this is the default scatterer and we also have a gift a position tomorrow, so we are going to to do how more feature more detail: topology files gatherer for this power, the second one is crew back to cool patches, are focused on the batch scheduling power. You know for the patches getting their house, they were all requirement to to the scheduler, such as accounts gathering. Maybe fair share something like that.

A

So in this page we can see that the back the targetable hello, tofu crew back, she has a pet hello, tense flow spark or something like that, and we also clarified the out of scope of coup batch because the you crew back shares only was together. We will not cover the top magnum data management has something else, as there's gonna be out of scope of crew back.

A

This is the overall architecture for true back. We have our cash to in in the crew batch to tamper, I received from the test server and we will make decision to have a you know. I will look to make a decision for for every job. Yes,.

B

A

Due to scattering on your top level such convinced that- and we have a station to to have a dump of of the cash to make sure there are no log yeah and we have predicts locate cram, should something to do to make the schedule decision for a job yeah. This is a little feature. We know the major one is cost-cutting. That's me: a foot job want to job how a say Walpole. If we for this poll we're going to reschedule only everyone get enough results.

A

For example, if you, if you have to you'll, have to power I know each one required one to two CPU and a for a new. We will make sure both of polecats to CPU. So then we will can start. If there are any one of them didn't get enough resource. Both of the mag will be pending. Yeah.

B

A

This is Herman are from the from the history of the training of AI workload and I'm here job. So, yes, they knew some. We need to start together and we also have some other funding requirement. Something some feature are how how we implement is something about. For example, we would like to how share share share, share across numerous ways to share cross job.

A

Yes, job queue, something like that and we are going to support a job level preemption. Yes, we need to prom the whole job of to release the result for the high priority job have a party with in queue. I thought you is the common concept in the batch system, a batch scheduler, so we try to introduce a queue and we form out with Dylan to define the relationship between the queue names based and maybe tenancy in the future. So anime choose the kill party depending here.

A

All this, the idea we have you see you have to pre-impact cap it into into put in here. This is the you see. Id here is your number and we for now we'll focus on the batch of schedule on powder and you this easy. We also have some other parts, such as told bagman and maybe no no not table logic or something like that, but in cou patch we only focus on the schedule. Part I would we may have discussion or maybe have some sex or progenitor for the other part yeah.

A

This is the user of fuku back and.

A

Company in china or search.

A

To see voices that up focus on.

A

We also have we will they also usually pull back. This makes yeah. Okay, you see the Pacific Park.

C

I actually had a different set of PPT, so I thought like I, would have a longer session, so I'll try to skip.

C

So yeah just to give a preamble of what was administered, so it was an University collaboration project which we started with the Cambridge University and we ended up. You know incubating that in our kubernetes 6 rapport, so they already had a shitty local form, and so pasaron is basically the integration part between kubernetes and form. So essentially it is a centralised scheduler and since kubernetes now supports multi schedulers, we have the capability to run. You know more than once is ready.

C

Let's hang so yet has extremely impressive through boots and there is a utilizations are much better than yet the schedulers, so I will just briefly go through the design. So this is the integration design of kubernetes and per second informant so form. It is essentially written in C++, where all the actual larger dealing happens and all the fiddling logic is written there. So what's happening essentially, is a kind of broker who actually understands the kubernetes objects, and he actually sends them to for moment and then for moment. Actually, you know builds its own structures.

C

You know, convert I mean possibly the second verse and so for Mundt essentially actually builds the graph and other things, and he tries to follow the graph so yeah. So initially we had heap stir, but after I think sometimes he forgot depreciated. So now what we have is, instead of that, we have something called.

C

We have written our own Informer, so basically it will listen to all the parts that is not created by Poseidon so that you know that information is actually required for the you know, scheduler to actually do a you know, schedule it properly in the sense if there is some other sailor running and if that's scheduled resources, then the other scheduler, which is not aware of touch ports. That is read you can actually, you know, mess up with the resource calculations. So we have wired that and Poseidon and for moment they actually communicate yrg RPC services.

C

So there is a four month service and so essentially the port Ranas deployments and kubernetes and yeah you can even run them as a you know, system be on the control plane. If you like.

C

Yeah- and this is the internal of the personal design, so it is the same thing like we have the APS over. We have the for moment, so is there, and this Poseidon has a couple of things like we call them as node water and hot water. So essentially, Doug gets the information from the kubernetes rapist over like know how many nodes are added out getting updated.

C

You know if there is any application happening on the nodes labels and things like that, so those informations are actually passed onto for movement and similarly, when a new part arrives those information, if the port, this has to be scheduled by Poseidon. Those information will be actually captured by this port washer and it will be set and yeah so that hipster part is yeah, so that is, the utilization starts with it, which sends to Foreman. We initially had a hipster sink, which actually was sending the information to for moment but yeah.

C

Currently we don't have that so that should you loop is the actual, so Poseidon doesn't actually do what continuous reading like the default should Euler. So it is like.

C

So we have a time interval, so the minimum time we can actually ask for you. Should you like once again so max? We have right till ten seconds so, based on your use case, you can say so it actually groups and then schedule. So it is not a continuous reading so that Tasha dealer call again AG RPC call which is actually triggered from Poseidon. So that is what it is and yeah. So the intervals of a moment I will briefly explain what it is like.

C

So what happens is when, whenever the ports and because in this case all this port and node Watchers actually send the port and denote information to firmament? And now you know, why are the geophysical so when it is received that actually we have a module called the graph manager, so the graph manager is essentially the manager I mean the module which actually builds the graph. So then it he solves. He calls the graph solver so essentially the graph.

C

So who gets the graph that is built by Poseidon and he he solves and gives back the deltas when he gives back the placement information, and that is what we sent back to you know Poseidon and then Poseidon actually called see, bind bind call so to explain the graph so yeah. So this is.

C

So this basically for moment, actually solves the shuttling problem by modeling. The you know task placements as a constraint based on you know, a flow graph Network, so it uses main course max flow algorithm to solve it and yeah. So it is basically based on the cost and capacity. I will explain you with a simple example.

C

So so, let's assume that there are two tasks or t11 and t12 in the kubernetes native thing, it can be assumed a sports, so there are two parts like t11 and t12 coming in and we have two nodes: the m1 every one node and the empty node. Okay, so yeah before that this sink and this UVA. So the flow graph has certain properties which says like the flow that starts from the source should actually reach the sink. So we actually make sure that whatever task comes from the source all meet at the sink.

C

Otherwise the flow graph is not complete. So that is one of the constraints that they have on the flow graph. And so if a task is not cannot we should do so. We have to anyways route it to sink. So we route it by our this unsettled aggregate. So we have two parts, this Delavan and t12 and say: let's assume that these two parts have the similar mem and CPU requirement like two CPU and 2 MB of memory, and this one also has 2 CP or 2 MB of memory.

C

So what we do is we try to create a easy. So this is what we call as equivalence class and we try to aggregate these two tasks into one task. So the only difference, if you see between the Quincy model and the foreman model, is they didn't? Have the this equal ends class? So what happened? Was it ended up connecting more arts so more darks?

C

Then the time taken by the graph solver is more so this equivalence class tries to I, mean II coolants or no mode actually tries to reduce the number of arts, thereby it is more efficient than the when cheese model. So I think that was there are theses.

C

So here what we do is so here we have two notes: M 1 and M 2, and we found that T 11 and it will have the same requirement and then we and we get them into one task- EC and then what we do is before the flow craft manager actually goes and he filters all the nodes. So this filtration process will actually go through all the predicate steps that is followed in the default yodeler. So he will actually go pick.

C

He will pass through all the predicate functions and even filter out all the modes from the list of node studies available, and he has actually formed two nodes, m1 and m2 that actually fit this task ECC requirement. So then what he does is he actually the flow craft manager will have to give the cost to the arcs. So now what he does is he?

C

So this m1 and m2 have a resource limit of 4, CPU and 4 MB of memory. So our input, our task is, he has an request of 2, CP and 2 MB of memory, so it again creates two virtual nodes, all the machining C's, so Machine equivalence classes it creates, and each through this machine equivalence class, only one flow one task and flow. So similarly, here which will see m2 has six m60, PU and 6 MB of memory, so it ends up creating three machine.

C

He sees because the task EC is requirement is to 2 CP R into memory, 2 MB of memory. So then what it does is the cost function after it has created a short mr. and have to returns great with all the machine he sees. It actually goes and calls the cost function. So cost function is where the actual policy or the she-demon policy of the for moment is applied. So you can have you know different cost models, so there is an interface which you can use that and implement using that.

C

So here we have used a model called CP and men, so, based on that cost model, he is actually assigning. So if you see this R, it is cost capacity and in flow, so we don't use them in flow. It is because the the open source software which we use cs2, doesn't actually support our main flow. It supports only the question capacity and the anyway, so are they meant for max I mean inflow match.

C

This thing. Algorithm is actually based on the no question capacities, so so this course is actually assigned by that function. The cost function, so it says 100 for this and it says 200 here and it says 150 for this 250 and 350 for this. So now after this graphs is built when the actual loop is called when the shading locus the schedule, call is Jen, I mean initiated or the geophysical is initiated from Poseidon.

C

What happens is the solver souls so how this is how he solved, so he actually sends the task that is T 11 for two machine m1. Why our machine, ec1 and tasks well, two machine way up to machine to machine ec2.

C

So if you see the cost, he has actually chosen the least cost, because this was 200 and this was 150. So least, cost, and by this we also achieve both spread under the sense we don't have to have a subject. You know predict a priority kind of thing to actually manage the spread of tasks across the nose, so this also does both.

C

So that is how the cost is actually assigned, so it all depends on the cost function. So this is the brief thing. So if you want to actually saw you start using Poseidon so.

C

These are some of the references.

C

The Hobie github has the for movement and those are the blocks. So if you want to create a pod- and you want if your default scheduler is also running- and you want your parts- we said it by Poseidon, then you need to give this under the Space Shuttle name as positive.

C

I mean what we found is we wrote couple of simulators as well just to test the scheduler I mean not with the API service. Another thing, so we have tested it till one hundred thousand nodes and three hundred four hundred thousand. You know pod workloads. It actually gives throughput of about 30k ports per second, but that is not the entire kubernetes ecosystem in picture flow. But these are the results which we got from cube, cube mock testing and we have also used.

C

Should you know curve in some cases, so you can see as the number of nodes increases, the new or different should Euler actually.

C

It is almost kind of consistent or slight. There is a slight deviation, so but yeah so the before should Euler is good, till Phi, K nodes, I think beyond Phi T, only the problem lies otherwise, so differentiated rate is much better in various other cases like we also implemented this affinity cases like initially when we started off with the project.

C

Now we didn't have all this policies that was available in default, scheduler present in four moment, so we built the quad affinity node of on ebay into power-down anti affinity in other cases, then what we found is I think after some time there was some huge changes in the default. Should you learn so after that those changes like default settler is actually doing much better numbers and then Poseidon in affinity and and affinity cases. So that's one thing and we also have support, aims and alterations and other things yeah.

C

The volume support is not I mean we don't do dynamic volume, provisioning present, which is not there, so we just already pre pounded one so yeah I, think code, Maps, yeah, I. Think of this is we have to colocation interferences. One of the things which the original authors were actually more concerned, and they were actually developing for moment for you know towards that, and so what is calling is interferences like.

C

So if you have a two types of jobs running and one job is actually hogging the CPU and he's you know using the underlying case mode on the rate at which the cache misses happen to the other job is more and you know so. You need to find a way to actually place this jobs or different notes. So that was their thing but I think curve.

C

We need a lot of support from you know at the cubelet level, and probably it you know the metric server level to understand like what kind of tasks are running, so that was not implemented like another thing and also the I mean most of them. They were asking like whether for moment, I mean percent and does the global rescheduling thing. So we don't actually do the rescheduling of the current task. The question they ask, so that's that was actually a tricky thing to do, because we don't create ports we only in towards him.

C

The pods are created by the controllers, basically the replica sizes or deployments and the jobs and other things. So if we go ahead- and you know preempted- my crate- that's possible in for moment, but that's not directly supported. So if you kill- and if you try to reshoot in later on some other node, then you would actually end up. You know messing up the logic of the controller, so that is something we need to get from the community side of things. So you can follow us here so quickly.

C

If you have any questions on Poseidon so.

A

Okay sense for the presenting part yeah. For now we have defaults together we have coupe action to set them home I. This is common question to me how they work together, but I'd like to say, I, don't know, we have always supported magic after.

A

The decision maybe conflict right, yeah and you know the comfort will may be acceptable to the long run, a services such as a tomcat. It helps us you just Larry Starr Tom Carroll or risk the old Tomcat to the other power, but folder for the battle clothes, the child for the NPI. If one poll, whether rajaiah was a hot dog, we need to respond, we start scheduling something like that.

A

But personally, I also have some discussion here about the Matis gatherer. Now the first one static node for each scheduler, that's gonna be the simply one asking this part. Another one is you know close all your courage. You know the trouble is several except acceptable. Choose a current behavior, so coolaser will reject your own I know you will I think this is fine. If this is fine to you, that's fine yeah.

B

A

Is dependent on your workload and depending your expectation of this part, another part I think there is a some people also proposed.

A

So some some results for the scatter one. Some results for the scatter tube, but we don't have too much effort on his part, because the way you will have to use the option for yes, we we already have what we are going to do right now in the upstream is, was scheduling, work here, yeah and the schedule will work how they will call back to make sure you can compromise your behavior, your policy, our presence, all the time.

A

So what we are going trying to do inside the weather, we can combine such candles feature into one scatter. Now we're not trying to option for, but you know, there's the old also have for here follows together how long history and to patch we use compassion initiative affords the framework. So we also house the rope here here and potato is the best song it's on the graph, so this is gonna be different, a generic tile different the implementation here, so we also have their worst are here. We would like to do that yeah.

A

This is about the scheduler power. Another chart I think this is the disc adder, be careful.

A

This pole, over the pole, if your tasks are already running here right so but afters the world after stable see after several long time or later, your this organization will be not clean now or maybe some critics maybe break because of you know, because of some some people change the note level something I live, so we introduced at least gather to have default schedule to have Krupa, and maybe some your personally customers gather. You have a chance to check the results in the cattle again.

A

If they didn't meet your installation, you just kill some pole, so the default is gatherer. Also, the controller will recreate the port yeah. Another related is scanner will reschedule a based on current policy based on the carnivalism.

A

So this is the disk at this gatherer for now to scatter in power to say, roll credits, they roll a priority at the front that he falls gatherer and I. Think when you try to use it this category, you need to make sure so this kind of decision will consist of is the whistle scatter as their crew patch or as a default scatter either. Otherwise, you know the scheduler will make a decision. One energy scheduler will make a decision to. There were kind of kim poong yeah and the finish.

A

This is the overall to this schedule, part I'm not go through one by one and you can check the least gather wrap. Oh, oh, oh this protect, I in the accumulated receives you can find a coop backside, 180 scatter! Yes, so this is a job report yeah. I know we also have a tip to have six gathering of this gathering tomorrow and Bobby will and me will kill more detail about 35 to fall schedule and over town feature tomorrow, yeah. So so this is all from the introduction. Yeah and I stimulus is a session time.

A

If we were, you know how an incursion I mean suggestion, yo, pause, Bobby and be out here.

C

So bin packing is actually a different kind of approach.

C

This resource requests priority right.

D

C

Exactly so what we yeah I said so I mean we follow exactly the same thing like that. Is there the default so dealer? So what we do is we take. First, we calculate the least hierarchy for the cost, so essentially this like for incoming port or we calculate the available resource on the node.

C

So no, no, so what we calculate is we calculate the fraction of the used resource and then we take an average of that and then we balance out with by taking the variance, I, think standard square root of standard deviation, so I mean so it actually gets us the. What to say.

C

I mean this is a simple, oh yeah, yeah yeah, because we do the mean of the CPU and call mem you units. So then we take the standard. Deviation. I mean we take a variance, so it won't be like curve.

D

C

Exactly yeah yeah, so those are the quantities are, is like not a measurable one. So what we do is currently like this. What in we calculate the affinities and anti affinities as a Cubase? Nothing only so we don't put that in the graph, because graph has a problem. We can go up till only like few dimensions. That is more metrical thing that is I.

C

Your differential is much faster in cases of an definitely an affinity, so I think many of the use cases that we get around or the machine learning stuff also involves lot of this affinity cases.

C

But you know we always try to tell them like you know, don't use affinity with informant, so that is when we we need to have a I mean the solvers that is available in the open source, like the lemons all over on the cs2 solver doesn't actually support those complex graphs, so you can actually create some X or types of graphs and do the solving, but we need to like you know. We can't have that in the open source, like it's all proprietary stuff, so it's companies yeah. We can do that.

C

A

D

When the, when.

C

The when, when the when the yeah, when the floorplans manager actually connects the passkey, see, that is the equivalence class which create first to the machine he sees so each and every line you have the cost right. So it actually calculates the cost based on the number of tasks he has and based on the number of machine in OGS, so he will assign it there itself. Yeah and I grab solver actually solves that.

C

So you have to write the cost model, so you can actually change how the cost is assigned, and you know you can actually change the behavior of the flow of the graphs.

C

So there is and was di people you can go to this website. I mean like this get up calm in that you have the mean under that, can actually see the links for the zero paper by melting. So.

C

So yeah still expressing multiple dimensions is quite a challenge, but yeah we can, if you have some good grass, always can have all the something.

B

C

Exactly so yeah the cases we can actually see that it's like true you, you see the resource availability. Currently, when you do the scheduling and you send it to Poseidon and he goes and does the binding by then assuming different settlers actually showed you, the port. That is the case. You're saying so. I won't be Abie.

C

So this what happens is like this is again because we don't create the ports, so it is up to the controller manager we after we stamp it and we send for the binding. You know the scheduler actually stay. Still. He actually gets another information from that controller, so the source controller, which actually creates that has to actually make the lifecycle of that port. Like you know, we don't actually.

C

You know reschedule it or do that, so it will be still in the pending state. Oh god, I don't know I think after bind, it should not be in pending status. Wales I think it's good. It will the bind itself a so bind if by face yeah we retry, but if the pint is succeeded and then there is a problem later, then it is not handled by a four moment, but it has to be handled by the the parent controller which created that object come in at four.

C

Yeah we to the painting so from within Poseidon. We call the bank on so Bank. All is actually tells the EPS over that this bar belongs to this node and it has to send and success message, but otherwise me if it right, although we just.

B

C

Everything is yeah, all the bind calls are threaded, yeah, all the back row, so straighter just like the deposit, because we don't have to wait for the bind. So the schedule of job is just to assign the you know, part of the node and just like the first red alert. You have a go funk and you just call the bind inside that.

A

I see the nurse gets a secure.

A

For the photo culture personally I think they may be fine. How many father you have created right. This is this should be really wrong: yeah cata, and so we so you can create a roll over here and chew scatterer to make it a sensation. There.

A

Marks a lot of kills I just kind of that.

D

B

D

A

We also, we also have some proposal in the in the crew package that we are going to support for Credit Corporation.

A

I'm trying to do that, some group.

A

Gives some some some face or some EQ face? We will stab the pony the poopoo to create cover. This is a lot similar. You cube and a wire is the probe is link. You are not a cure, so making decision pattern scatter. The scan will know whether this group for them have a card or something island in the culture controller.

A

A

A

Right, you know. Furthermore, you have force tpo.

A

D