wilfred-s commented on a change in pull request #48: URL: https://github.com/apache/incubator-yunikorn-site/pull/48#discussion_r617268999
########## File path: docs/design/gang_scheduling.md ########## @@ -0,0 +1,631 @@ +--- +id: gang_scheduling +title: Gang scheduling design +--- + +<!-- + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + --> +# Gang Scheduling Implementation +## Change log + +| Change Date | Editors | Description | +| ----------- | --------------------- | ---------------------------------------------- | +| 2020-11-25 | Wilfred Spiegelenburg | Initial document | +| 2020-11-26 | Wilfred Spiegelenburg | Allocation release definition, order change | +| 2020-11-27 | Wilfred Spiegelenburg | Sequence diagram | +| 2020-12-12 | Wilfred Spiegelenburg | Application submit and cleanup | +| 2020-12-15 | Wilfred Spiegelenburg | AllocationRelease message and cleanup sequence | +| 2020-12-24 | Wilfred Spiegelenburg | Allocation changes for recovery | +| 2021-02-15 | Wilfred Spiegelenburg | Placeholder allocation and ask cleanup | + +YUNIKORN-2 describes a new format for scheduling applications by taking into account the overall demand the application will have. +It guarantees the specified resources for the application by reserving the resources. + +There are two parts to this implementation: +* Kubernetes Shim +* Core and scheduling + +This document describes the implementation on the core side. + +## Goals +Define the following points: + +1. Define changes required for the shim to core communication (scheduler interface) +2. Scheduler storage object changes +3. Scheduler logic changes + +## Non Goals +Excluding the following major points: +1. Kubernetes shim side implementation +2. Generalised preemption on the core side + +## Generic flow +As described in the YUNIKORN-2 design documentation we have the following flow. +The flow is triggered by a pod that is submitted which triggers the application creation. +This first pod is in the case of a Spark application, the driver pod. +In case the flow is triggered from the creation of an application CRD there will not be a first pod. +This is however outside the core scheduling logic. From the core side there should be no difference between the two cases. +More details are in the chapter on the [Scheduler logic changes](#scheduler-logic-changes). + +The flow of an application submitted. The numbers in the diagram correspond to the description below the diagram. + + + +Combined flow for the shim and core during startup of an application: +* An application is submitted with TaskGroup(s) defined. (1) +* The shim creates the application and passes the application to the core. (2) +* The shim creates placeholder pods for each of the members of the TaskGroup(s) (3) +* The pods are processed and passed to the core, as per the normal behaviour, as AllocationAsks for the application with the correct info set. (4) +* The placeholder AllocationAsk’s are scheduled by the core as if they were normal AllocationAsk’s. (5) +* All Allocations, even if they are the result of the placeholder AllocationAsks being allocated by the scheduler, are communicated back to the shim. +* The original real pod is passed to the core as an AllocationAsk. (6) +* After the real pod and all all the placeholder pods are scheduled the shim starts the real pod that triggered the application creation. (7) + +After the first, real, pod is started the following pods should all be handled in the same way (8): +* A real pod is created on k8s. +* The pod is processed and an AllocationAsk is created. +* The scheduler processes the AllocationAsk (more detail below) and replaces a placeholder with the real allocation. + + +## Application submit handling +### Total placeholder size + +The application if requesting one or more TaskGroups should provide the total size of all the TaskGroup members it is going to request. +The total resource size is required for the case that the application is scheduled in a queue with a resource limit set. + +The value is important for three cases: +1. gang request is larger than the queue quota +2. start of scheduling reservations +3. resource pressure while scheduling reservations + +Further detail will be given below in [scheduling in queues with a quota set](#scheduling-in-queues-with-a-quota-set) + +The information passed on from the shim should be part of the AddApplicationRequest. +Detailed information on the build up of the taskGroup(s), or the number of members are not relevant. +The total resource requested by all taskGroup members is calculated using: + + + +This total placeholderAsk is added as an optional field to the AddApplicationRequest message. +The calculation can be made by the shim based on the CRD or annotation provided in the pod description. + +If the placeholderAsk is larger than the queue quota set on the queue the application must be rejected. +This rejection is based on the fact that we cannot in any way honor the request For all other cases the application is accepted and will be scheduled as per normal. + +### Handling queue with a FAIR sort policy +If an application is submitted to a queue that has a FAIR sort policy set it must be rejected. +Queue sorting for the queue that an application with gang requests runs in must be set to FIFO or StateAware. + +Other queue policies cannot guarantee that there is only one New application processed at a time. +In the case of the FAIR policy we could be allocating multiple New applications at the same time making quota management impossible to enforce. +The other side effect of using FAIR as a policy could be that we get multiple applications with only a partial allocated guarantee. + +Auto-scaling can be triggered due to the fact that the core can not place the placeholders on any node. +In case the queue would use the FAIR sorting this could lead to other applications taking the scaled up nodes instead of the placeholders again breaking the gang. + +## Scheduling in queues with a quota set +The main case already described above is handling a total placeholder request size that is larger than the quota set on the queue. +When the application is submitted we can already assess that we cannot satisfy that requirement and reject the request. + +In the case that the total placeholder ask does fit in the queue we should not start scheduling until there are enough resources available in the queue to satisfy the total request. +However this does not stop scheduling of other applications in the queue(s). +Applications that are already running in the queue could ask for more resources. +From an application perspective there is no limit set on the resource it can request. +The gang defined on the application is a guaranteed number of resources, not a maximum number of resources the application can request. + +This is complicated by the fact that we have a queue hierarchy. +There is the possibility that the quota is not set directly on the queue the application is running. +It could be set on one of the parent queues. +This case could become complex, and we need to make sure that we keep in mind that we could live lock the scheduling. + +In this first phase we should focus on the case that the gang resources requested are also the maximum number of resources the application will request. +When we look at the queues we should focus on a single queue level with quotas. + +These two assumptions are correct for the spark use case without dynamic allocation using a dynamic mapping from a namespace to a queue. + +Furthermore, we assume that the quota set on the queue can be totally allocated. +If the cluster does not have enough resources the cluster will scale up to the size needed to provide all queues with their full quota. + +The follow up should add further enhancements for deeper hierarchies and dynamic allocation support. +This could also leverage preemption in certain use cases, like preempting allocations from applications over their total gang size. + +Further enhancements could be added by allowing specifying the time and application will wait for the placeholders to be allocated, or the time to start using the held resources. + + +## Scheduler logic changes +The scheduler logic change needs to account for two parts of cycle: +* The placeholder asks and their allocation. +* The allocation replacing the placeholder. + +The basic assumption is that all pods will generate a placeholder pod request to the core. +This includes the pod that triggered the application creation if we do not use the application CRD. +This assumption is needed to make sure that the scheduler core can behave in the same way for both ways of submitting the application. +The placeholder pods must be communicated to the core before the real pod. + +Queue sorting for the queue that the application runs in must be set to _FIFO_ or _StateAware_. +Other queue policies cannot guarantee that there is only one _New_ application processed at a time. +In the case of the _FAIR_ policy we could be allocating multiple _New_ applications at the same time making quota management impossible to enforce. +The other side effect of using _FAIR_ as a policy could be that we get multiple applications with only a partial allocated guarantee. Review comment: copy paste error, fixed ########## File path: docs/design/gang_scheduling.md ########## @@ -0,0 +1,631 @@ +--- +id: gang_scheduling +title: Gang scheduling design +--- + +<!-- + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + --> +# Gang Scheduling Implementation +## Change log + +| Change Date | Editors | Description | +| ----------- | --------------------- | ---------------------------------------------- | +| 2020-11-25 | Wilfred Spiegelenburg | Initial document | +| 2020-11-26 | Wilfred Spiegelenburg | Allocation release definition, order change | +| 2020-11-27 | Wilfred Spiegelenburg | Sequence diagram | +| 2020-12-12 | Wilfred Spiegelenburg | Application submit and cleanup | +| 2020-12-15 | Wilfred Spiegelenburg | AllocationRelease message and cleanup sequence | +| 2020-12-24 | Wilfred Spiegelenburg | Allocation changes for recovery | +| 2021-02-15 | Wilfred Spiegelenburg | Placeholder allocation and ask cleanup | + +YUNIKORN-2 describes a new format for scheduling applications by taking into account the overall demand the application will have. +It guarantees the specified resources for the application by reserving the resources. + +There are two parts to this implementation: +* Kubernetes Shim +* Core and scheduling + +This document describes the implementation on the core side. + +## Goals +Define the following points: + +1. Define changes required for the shim to core communication (scheduler interface) +2. Scheduler storage object changes +3. Scheduler logic changes + +## Non Goals +Excluding the following major points: +1. Kubernetes shim side implementation +2. Generalised preemption on the core side + +## Generic flow +As described in the YUNIKORN-2 design documentation we have the following flow. +The flow is triggered by a pod that is submitted which triggers the application creation. +This first pod is in the case of a Spark application, the driver pod. +In case the flow is triggered from the creation of an application CRD there will not be a first pod. +This is however outside the core scheduling logic. From the core side there should be no difference between the two cases. +More details are in the chapter on the [Scheduler logic changes](#scheduler-logic-changes). + +The flow of an application submitted. The numbers in the diagram correspond to the description below the diagram. + + + +Combined flow for the shim and core during startup of an application: +* An application is submitted with TaskGroup(s) defined. (1) +* The shim creates the application and passes the application to the core. (2) +* The shim creates placeholder pods for each of the members of the TaskGroup(s) (3) +* The pods are processed and passed to the core, as per the normal behaviour, as AllocationAsks for the application with the correct info set. (4) +* The placeholder AllocationAsk’s are scheduled by the core as if they were normal AllocationAsk’s. (5) +* All Allocations, even if they are the result of the placeholder AllocationAsks being allocated by the scheduler, are communicated back to the shim. +* The original real pod is passed to the core as an AllocationAsk. (6) +* After the real pod and all all the placeholder pods are scheduled the shim starts the real pod that triggered the application creation. (7) + +After the first, real, pod is started the following pods should all be handled in the same way (8): +* A real pod is created on k8s. +* The pod is processed and an AllocationAsk is created. +* The scheduler processes the AllocationAsk (more detail below) and replaces a placeholder with the real allocation. + + +## Application submit handling +### Total placeholder size + +The application if requesting one or more TaskGroups should provide the total size of all the TaskGroup members it is going to request. +The total resource size is required for the case that the application is scheduled in a queue with a resource limit set. + +The value is important for three cases: +1. gang request is larger than the queue quota +2. start of scheduling reservations +3. resource pressure while scheduling reservations + +Further detail will be given below in [scheduling in queues with a quota set](#scheduling-in-queues-with-a-quota-set) + +The information passed on from the shim should be part of the AddApplicationRequest. +Detailed information on the build up of the taskGroup(s), or the number of members are not relevant. +The total resource requested by all taskGroup members is calculated using: + + + +This total placeholderAsk is added as an optional field to the AddApplicationRequest message. +The calculation can be made by the shim based on the CRD or annotation provided in the pod description. + +If the placeholderAsk is larger than the queue quota set on the queue the application must be rejected. +This rejection is based on the fact that we cannot in any way honor the request For all other cases the application is accepted and will be scheduled as per normal. Review comment: fixed -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected]
