balanced_allocation.go

Documentation: k8s.io/kubernetes/pkg/scheduler/framework/plugins/noderesources

     1  /*
     2  Copyright 2019 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package noderesources
    18  
    19  import (
    20  	"context"
    21  	"fmt"
    22  	"math"
    23  
    24  	v1 "k8s.io/api/core/v1"
    25  	"k8s.io/apimachinery/pkg/runtime"
    26  	"k8s.io/kubernetes/pkg/scheduler/apis/config"
    27  	"k8s.io/kubernetes/pkg/scheduler/apis/config/validation"
    28  	"k8s.io/kubernetes/pkg/scheduler/framework"
    29  	"k8s.io/kubernetes/pkg/scheduler/framework/plugins/feature"
    30  	"k8s.io/kubernetes/pkg/scheduler/framework/plugins/names"
    31  )
    32  
    33  // BalancedAllocation is a score plugin that calculates the difference between the cpu and memory fraction
    34  // of capacity, and prioritizes the host based on how close the two metrics are to each other.
    35  type BalancedAllocation struct {
    36  	handle framework.Handle
    37  	resourceAllocationScorer
    38  }
    39  
    40  var _ framework.PreScorePlugin = &BalancedAllocation{}
    41  var _ framework.ScorePlugin = &BalancedAllocation{}
    42  
    43  // BalancedAllocationName is the name of the plugin used in the plugin registry and configurations.
    44  const (
    45  	BalancedAllocationName = names.NodeResourcesBalancedAllocation
    46  
    47  	// balancedAllocationPreScoreStateKey is the key in CycleState to NodeResourcesBalancedAllocation pre-computed data for Scoring.
    48  	balancedAllocationPreScoreStateKey = "PreScore" + BalancedAllocationName
    49  )
    50  
    51  // balancedAllocationPreScoreState computed at PreScore and used at Score.
    52  type balancedAllocationPreScoreState struct {
    53  	// podRequests have the same order of the resources defined in NodeResourcesFitArgs.Resources,
    54  	// same for other place we store a list like that.
    55  	podRequests []int64
    56  }
    57  
    58  // Clone implements the mandatory Clone interface. We don't really copy the data since
    59  // there is no need for that.
    60  func (s *balancedAllocationPreScoreState) Clone() framework.StateData {
    61  	return s
    62  }
    63  
    64  // PreScore calculates incoming pod's resource requests and writes them to the cycle state used.
    65  func (ba *BalancedAllocation) PreScore(ctx context.Context, cycleState *framework.CycleState, pod *v1.Pod, nodes []*framework.NodeInfo) *framework.Status {
    66  	state := &balancedAllocationPreScoreState{
    67  		podRequests: ba.calculatePodResourceRequestList(pod, ba.resources),
    68  	}
    69  	cycleState.Write(balancedAllocationPreScoreStateKey, state)
    70  	return nil
    71  }
    72  
    73  func getBalancedAllocationPreScoreState(cycleState *framework.CycleState) (*balancedAllocationPreScoreState, error) {
    74  	c, err := cycleState.Read(balancedAllocationPreScoreStateKey)
    75  	if err != nil {
    76  		return nil, fmt.Errorf("reading %q from cycleState: %w", balancedAllocationPreScoreStateKey, err)
    77  	}
    78  
    79  	s, ok := c.(*balancedAllocationPreScoreState)
    80  	if !ok {
    81  		return nil, fmt.Errorf("invalid PreScore state, got type %T", c)
    82  	}
    83  	return s, nil
    84  }
    85  
    86  // Name returns name of the plugin. It is used in logs, etc.
    87  func (ba *BalancedAllocation) Name() string {
    88  	return BalancedAllocationName
    89  }
    90  
    91  // Score invoked at the score extension point.
    92  func (ba *BalancedAllocation) Score(ctx context.Context, state *framework.CycleState, pod *v1.Pod, nodeName string) (int64, *framework.Status) {
    93  	nodeInfo, err := ba.handle.SnapshotSharedLister().NodeInfos().Get(nodeName)
    94  	if err != nil {
    95  		return 0, framework.AsStatus(fmt.Errorf("getting node %q from Snapshot: %w", nodeName, err))
    96  	}
    97  
    98  	s, err := getBalancedAllocationPreScoreState(state)
    99  	if err != nil {
   100  		s = &balancedAllocationPreScoreState{podRequests: ba.calculatePodResourceRequestList(pod, ba.resources)}
   101  	}
   102  
   103  	// ba.score favors nodes with balanced resource usage rate.
   104  	// It calculates the standard deviation for those resources and prioritizes the node based on how close the usage of those resources is to each other.
   105  	// Detail: score = (1 - std) * MaxNodeScore, where std is calculated by the root square of Σ((fraction(i)-mean)^2)/len(resources)
   106  	// The algorithm is partly inspired by:
   107  	// "Wei Huang et al. An Energy Efficient Virtual Machine Placement Algorithm with Balanced Resource Utilization"
   108  	return ba.score(ctx, pod, nodeInfo, s.podRequests)
   109  }
   110  
   111  // ScoreExtensions of the Score plugin.
   112  func (ba *BalancedAllocation) ScoreExtensions() framework.ScoreExtensions {
   113  	return nil
   114  }
   115  
   116  // NewBalancedAllocation initializes a new plugin and returns it.
   117  func NewBalancedAllocation(_ context.Context, baArgs runtime.Object, h framework.Handle, fts feature.Features) (framework.Plugin, error) {
   118  	args, ok := baArgs.(*config.NodeResourcesBalancedAllocationArgs)
   119  	if !ok {
   120  		return nil, fmt.Errorf("want args to be of type NodeResourcesBalancedAllocationArgs, got %T", baArgs)
   121  	}
   122  
   123  	if err := validation.ValidateNodeResourcesBalancedAllocationArgs(nil, args); err != nil {
   124  		return nil, err
   125  	}
   126  
   127  	return &BalancedAllocation{
   128  		handle: h,
   129  		resourceAllocationScorer: resourceAllocationScorer{
   130  			Name:         BalancedAllocationName,
   131  			scorer:       balancedResourceScorer,
   132  			useRequested: true,
   133  			resources:    args.Resources,
   134  		},
   135  	}, nil
   136  }
   137  
   138  func balancedResourceScorer(requested, allocable []int64) int64 {
   139  	var resourceToFractions []float64
   140  	var totalFraction float64
   141  	for i := range requested {
   142  		if allocable[i] == 0 {
   143  			continue
   144  		}
   145  		fraction := float64(requested[i]) / float64(allocable[i])
   146  		if fraction > 1 {
   147  			fraction = 1
   148  		}
   149  		totalFraction += fraction
   150  		resourceToFractions = append(resourceToFractions, fraction)
   151  	}
   152  
   153  	std := 0.0
   154  
   155  	// For most cases, resources are limited to cpu and memory, the std could be simplified to std := (fraction1-fraction2)/2
   156  	// len(fractions) > 2: calculate std based on the well-known formula - root square of Σ((fraction(i)-mean)^2)/len(fractions)
   157  	// Otherwise, set the std to zero is enough.
   158  	if len(resourceToFractions) == 2 {
   159  		std = math.Abs((resourceToFractions[0] - resourceToFractions[1]) / 2)
   160  
   161  	} else if len(resourceToFractions) > 2 {
   162  		mean := totalFraction / float64(len(resourceToFractions))
   163  		var sum float64
   164  		for _, fraction := range resourceToFractions {
   165  			sum = sum + (fraction-mean)*(fraction-mean)
   166  		}
   167  		std = math.Sqrt(sum / float64(len(resourceToFractions)))
   168  	}
   169  
   170  	// STD (standard deviation) is always a positive value. 1-deviation lets the score to be higher for node which has least deviation and
   171  	// multiplying it with `MaxNodeScore` provides the scaling factor needed.
   172  	return int64((1 - std) * float64(framework.MaxNodeScore))
   173  }
   174
View as plain text