Repository: clusternet/clusternet
Pull request #295 (2022-04-07 09:47:06)

fix static division algorithm
Signed-off-by: Di Xu <stephenhsu90@gmail.com>

<!--  Thanks for sending a pull request!

-->

#### What type of PR is this?
kind/bug

#### What this PR does / why we need it:

#### Which issue(s) this PR fixes:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Fixes #
a follow-up of #292 

#### Special notes for your reviewer:


Garrybest: /lgtm
Garrybest: /lgtm

Patch:
diff --git a/pkg/scheduler/algorithm/dividing/static.go b/pkg/scheduler/algorithm/dividing/static.go
index fe85116..defad0d 100644
--- a/pkg/scheduler/algorithm/dividing/static.go
+++ b/pkg/scheduler/algorithm/dividing/static.go
@@ -47,35 +47,24 @@ func StaticDivideReplicas(selected *framework.TargetClusters, sub *appsapi.Subsc
 // staticDivideReplicas divides replicas by the weight list.
 func staticDivideReplicas(desiredReplicas int32, wl *weightList) []int32 {
 	res := make([]int32, len(wl.weights))
-	remain := wl.weightSum
+	remain := desiredReplicas
 	for i, weight := range wl.weights {
 		replica := weight * int64(desiredReplicas) / wl.weightSum
 		res[i] = int32(replica)
-		remain -= replica
+		remain -= int32(replica)
 	}
 	if remain == 0 {
 		return res
 	}
 
-	remainInt := int(remain)
 	clusterIndices := sortByWeight(wl.weights)
-	if remainInt <= len(clusterIndices) {
-		for i := 0; i < remainInt; i++ {
-			res[clusterIndices[i]]++
-		}
-	} else {
-		avg, bounder := remainInt/len(clusterIndices), remainInt%len(clusterIndices)
-		for i := range clusterIndices {
-			if i < bounder {
-				res[clusterIndices[i]] += int32(avg) + 1
-			} else {
-				res[clusterIndices[i]] += int32(avg)
-			}
-		}
+	for i := 0; i < int(remain); i++ {
+		res[clusterIndices[i]]++
 	}
 	return res
 }
 
+// sortByWeight sorts the cluster index based on their weight
 func sortByWeight(weights []int64) []int {
 	clusterIndices := make([]int, len(weights))
 	for i := range weights {


Test patch:
diff --git a/pkg/scheduler/algorithm/dividing/static_test.go b/pkg/scheduler/algorithm/dividing/static_test.go
new file mode 100644
index 0000000..464546a
--- /dev/null
+++ b/pkg/scheduler/algorithm/dividing/static_test.go
@@ -0,0 +1,99 @@
+/*
+Copyright 2022 The Clusternet Authors.
+
+Licensed 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.
+*/
+
+package dividing
+
+import (
+	"reflect"
+	"testing"
+)
+
+func TestSortByWeight(t *testing.T) {
+	tests := []struct {
+		name    string
+		weights []int64
+		want    []int
+	}{
+		{
+			weights: []int64{3, 1, 2},
+			want:    []int{0, 2, 1},
+		},
+		{
+			weights: []int64{1, 2, 3, 4},
+			want:    []int{3, 2, 1, 0},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if got := sortByWeight(tt.weights); !reflect.DeepEqual(got, tt.want) {
+				t.Errorf("sortByWeight() = %v, want %v", got, tt.want)
+			}
+		})
+	}
+}
+
+func TestStaticDivideReplicas(t *testing.T) {
+	tests := []struct {
+		name            string
+		desiredReplicas int32
+		wl              *weightList
+		want            []int32
+	}{
+		{
+			name:            "exact division",
+			desiredReplicas: 5,
+			wl: &weightList{
+				weightSum: 5,
+				weights:   []int64{2, 1, 0, 2},
+			},
+			want: []int32{2, 1, 0, 2},
+		},
+		{
+			name:            "exact division (2 times)",
+			desiredReplicas: 10,
+			wl: &weightList{
+				weightSum: 5,
+				weights:   []int64{2, 1, 2},
+			},
+			want: []int32{4, 2, 4},
+		},
+		{
+			name:            "differential division - 1",
+			desiredReplicas: 6,
+			wl: &weightList{
+				weightSum: 5,
+				weights:   []int64{2, 1, 0, 2},
+			},
+			want: []int32{3, 1, 0, 2},
+		},
+		{
+			name:            "differential division -2 ",
+			desiredReplicas: 5,
+			wl: &weightList{
+				weightSum: 8,
+				weights:   []int64{5, 1, 0, 2},
+			},
+			want: []int32{4, 0, 0, 1},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			if got := staticDivideReplicas(tt.desiredReplicas, tt.wl); !reflect.DeepEqual(got, tt.want) {
+				t.Errorf("staticDivideReplicas() = %v, want %v", got, tt.want)
+			}
+		})
+	}
+}
diff --git a/pkg/scheduler/algorithm/generic_test.go b/pkg/scheduler/algorithm/generic_test.go
index 07a8da0..5e0b033 100644
--- a/pkg/scheduler/algorithm/generic_test.go
+++ b/pkg/scheduler/algorithm/generic_test.go
@@ -38,7 +38,7 @@ func newDeploymentFeed(name string) *appsapi.Feed {
 	}
 }
 
-func Test_genericScheduler_divideReplicas(t *testing.T) {
+func TestDivideReplicas(t *testing.T) {
 	desiredReplicas := int32(12)
 	type args struct {
 		selected *framework.TargetClusters