Cloud Native Computing Foundation Kubernetes AI Day EU 2021, 14 May 2021

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Fair Scheduling for Deep Learning Workloads in Kubernetes - Yodar Shafrir, Run:AI

Description

Don’t miss out! Join us at our upcoming event: KubeCon + CloudNativeCon North America 2021 in Los Angeles, CA from October 12-15. 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.

Fair Scheduling for Deep Learning Workloads in Kubernetes - Yodar Shafrir, Run:AI

In this talk we will deep dive into pod scheduling in Kubernetes. We'll discuss the importance of fair scheduling in use cases where Data Scientists share a cluster with a limited number of GPUs and examine the requirements for a fair scheduling solution. We'll look at the architecture and components of the Kubernetes scheduling and discuss how we can achieve fairness. We will also share some of the building blocks we used when building our own fair scheduler.

A

Hello: everyone thank you for joining me to this session. I'm yoda shafril and today we are going to discuss about fail scheduling for deep learning workloads in kubernetes, but first I would like to introduce myself. I'm a software team lead at run ai running. I provide the compute management platform for ai workloads.

A

I am also a contributor of kubernetes and I live and work from tel aviv. As you probably know, data scientists run their workloads on gpus.

A

The gpus are shared in the cluster between the data scientists and we see more and more clusters that are moving to use kubernetes now in deep learning, workloads can run for days or even weeks. So when the data scientists share the gpu resources, deciding which user should be able to get, the next gpu can be critical.

A

A wrong decision can cause starvation. In this talk, I will explain how does kubernetes scheduler decide? What pod should be allocated next and discuss with you? How can we achieve fairness between users when sharing gpus in kubernetes?

A

Let's start with explaining the way kubernetes schedule, pods in a very simplified way, the scheduler picks a pending pod and then attempts to bind the pod to the most suitable node.

A

We will be focusing today on the part where the scheduler picks the right part for scheduling the default scheduler stores the pending pods in a heap. The ip is sorted by the priority and by the creation time of the pods, so the next pod to be allocated will be stored at the head of the heap.

A

This is a very simplified way of presenting. How does the default scheduler decide what pod should be allocated? Next? There is also another leap, called pod, back-off queue and a map for the unscheduleable pods, but they are not relevant to the purpose of what I'm about to explain.

A

So we will not get into them using the default scheduler of kubernetes for sharing a cluster with limited number of gpus can cause fairness issues because data scientists can monopolize the cluster one way for users to monopolize the gpus is to submit pods with the highest priority they are allowed to submit as users.

A

This would make their pods move to the top of the hip, causing their pods to be allocated. First, as you can see, in this example, bob submits pods with higher priority than alice, so his pods will be at the top of the hip and therefore will be scheduled first eventually, bob can monopolize and use all the gpus in the cluster.

A

Another way to monopolize the gpus is to submit as many pods as possible. This will cause more pods to be in the hip and even have smaller creation time, as you can see. In this example, bob submitted many pods and the ip contains mostly ease parts, and therefore you will also have more gpus allocated.

A

So our motivation is to build the first scheduler one that knows to share the gpu resources between the users in a fair way, regardless of the creation time and the pod priorities.

A

So we want that even in in our examples where ellie submits less sports and she submits pods with lower priority, she would still get the same amount of gpus as bob now, let's discuss, how can we achieve such a scheduler in v115 of kubernetes? The architecture of the scheduler was changed to use the scheduling framework, the scheduling framework is more pluggable and provides several extension points to change the behavior of the scheduler.

A

It was a big game changer for building a different scheduler rather than the default scheduler, because it reduces the need for developers to build their own scheduler from sketch and try to keep up with all the kubernetes features.

A

We have examined the scheduler framework for implementing a first scheduler and we decided not to do it.

A

The reason we decided not to use the framework was that we wanted to use the different data structure for the pending parts rather than just a simple hip of parts and the framework simply doesn't let you change this data structure, so we decided to build our own scheduler.

A

The data structure we use is a two-dimensional hip in the manip, every node represents a user and we sort the ip by the number of the allocated gpus this user uses.

A

Now every node of a user is associated to another rip of ease pending parts. The pending pods are sorted just as in kubernetes, by priority and by creation time. So, if, once again, I compare this data structure to the hip of the scheduling framework.

A

Now we can associate depending pods to a specific user and sort the users according to their load on the cluster, rather than just using a simple hip of pods.

A

The way we allocate pause is this. First, we pop the first user from the user zip. Then we pop the first part of this user and allocate this part in our case. In the following example, alice is the first user in the user zip.

A

So we will allocate air first pod and update the number of allocated gpus alice currently uses. Once we will do that, the heap will be updated and bobo will now move to the top of the heap notice that at the end of the user, zip, we always have the most styled user.

A

This helps us in in the goal of achieving fairness, because we know who is the most starved user and is the one that should get the next gpu.

A

Once again, we pop the first pod from bobspots and allocate this pod.

A

We will continue to do this flow until there are no more free gpus in the cluster, so once we will update the ip alice will move once again to the top of the hip and we will allocate a pod and we will do the same for bob.

A

As you can see now, the gpus are shared fairly between alice and bob.

A

This solution will provide fairness when deciding which pods should be allocated next, but is this solution good enough in order to provide fairness between the users? Let's examine the following scenario: let's assume that bob submitted many long running pods when the gpus were free, because he was the only active user.

A

We want to allow bob to use the whole cluster and maximize due to the utilization of the gpus, so we will allocate all the gpus to bob now when alice submits spots, the pods will remain in pending state and alice will be starred until bob will finish to use the gpus bob can now run the gpus for weeks, so alice can be starred for a very long time.

A

This means that user can still monopolize the gpus.

A

In order to solve this problem, we added another algorithm to enable preemption between the users. The way we handle the preemption between the users is the following. We calculate the number of gpus every active user deserves at a given moment.

A

Then we run a simulation where we preempt the pods of the users who are monopolizing the gpus and attempt to allocate the pods of the starved user.

A

If the simulation succeeds, we preamp the pods and simply let our location algorithm to apply.

A

Let's see an example of this flow, so we add four gpus in the cluster, so we calculate how many gpus every user should have that's two gpus each, and it also means that bob uses two gpus more than it should so we preempt two of bob's pods and move those pods back to the pending pod's hip.

A

Now we have two free gpus and we simply apply our allocation algorithm.

A

So we will allocate ali's first pod and update the number of allocated gpus, but she will remain at the top of the hip because she is still starved, so we'll allocate a second bar, as you can see, bob and alex are now sharing the cluster fairly.

A

To summarize, with the allocation and preemption algorithms user can get the most of the gpus when the gpus are free, when the users submit pods, they are able to get the gpus they deserve and they will not be starved.

A

Let's see an example of all this explanation from one of our customers.

A

When you looked at the mark time window, you can see that the blue user uses about 20 gpus, while the pink user uses about 10 gpus.

A

We allow the blue user to get 20 gpus, because the gpus are available and we want to get the maximum utilization out of the cluster after a few hours in the new marked window, the pink user submits more pods. So what we do is that we preempt the blue user and we let the pink user use those gpus.

A

As you can see, the lines are getting closer to each other. This is because we took the gpus from the blue user and gave it to the pink user. So this is how the fairness actually looks like.

A

Thank you all for your time. You are more than welcome to contact me if you have any question or want to discuss about scheduling with me. Thank you.