Polar Snow Documentation

花有重开日 人无再少年

go语言实现加权轮询调度算法

发表于 分类于 ， Disqus：

上篇文章中介绍了轮询调度算法, 忽略后端元素的差异性, 将请求均匀的”涂抹”到后端节点. 本篇介绍更为复杂的加权轮询调度算法, 可以根据后端节点实际承载能力, 单独调整每个节点的权重

演示思路

在编写代码前, 先来说下实现加权轮询调度算法的思路. 加权轮询, 是在轮询的基础之上, 加上了对权重值的判断, 先看下下面的权重配置实例:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
-    -    -
-    -    -
          -
          -

上面a, b, c, d四个后端节点, 配置的权重分别为4, 4, 6, 2. 也就是说, 当正好有16个请求打过来之后, 后端实际被调度的次数应该就是4, 4, 6, 2

实现加权轮询算法的核心, 依然离不开轮询调度算法, 依然需要前篇文章介绍的轮询调度算法来控制索引下标. 第一步, 我们先找出后端所有元素配置的最大权重, 结果是: 最大权重为6, 那么我们期望第一次的调度结果如下:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
-    -    -
-    -    -
          -
          ✔️

通过轮询调度算法, 依次判断哪个元素>=最大权重值6, 当内存循环到c元素时, 条件满足, 则第一次调度的结果, 在算法内部循环了3次后, 返回了c.

当有第二次请求到达时, 期望结果如下:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
-    -    -
-    -    -
          ✔️
          ✔️

操作流程同上, 依次判断哪个元素的权重>=最大权重值 最大权重值此时=8, 内部开始轮询, 根据上次的索引下标继续向下轮询, 上次轮询到c, 本次将从d开始轮询, d的值不满足>=最大权重值的条件, 应该回到a继续轮询判断, 直到符合条件为止.

这里需要注意的是, 再回到a之前, 应该将最大权重值-1, 因为在上一轮的轮询中, 已经将=最大权重值的元素消灭, 所以需要将最大权重值-1, 继续轮询判断, 是否有满足条件的元素, 我们在这里临时命名为当前最大权重值(后面用cw表示), -1操作后, cw=5.

c元素的权重值6符合>=5的条件. 立即返回, 所以第二次的调度结果, 依然是c.

当有第三次请求到达时, 期望结果如下:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
-    -    -
✔️   -    -
          ✔️
          ✔️

同上, 依次判断哪个元素的权重>=cw cw此时=5, 开始轮询, 上次轮询到c, 本次从下一个元素d开始轮询, d不满足条件, 此时一整轮轮询结束🔚, 再次将cw-1, 此时cw=4. 并从a开始重新轮询, 发现a符合>=4的条件, 立即返回, 所以第三次的调度结果为a.

当有第四次请求到达时, 期望结果如下:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
-    -    -
✔️   ✔️   -
          ✔️
          ✔️

同上, 此时cw=4, 从b元素开始轮询, b即符合条件, 立即返回, 所以第四次调度结果为b

第五次请求, 期望结果如下:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
-    -    -
✔️  ✔️   ✔️
          ✔️
          ✔️

此时cw=4, 从上次结束的下一个元素开始轮询, c即符合条件, 立即返回, 所以第五次调度结果为c

第六次请求, 期望结果如下:

1
2
3
4
5
6
7
a    b    c    d
-    -    -    -
-    -    -    -
✔️   -    -
✔️  ✔️   ✔️
          ✔️
          ✔️

此时cw=4, 从上次结束的下一个元素开始轮询, d不符合>=cw条件, 本轮轮询结束, cw-1, 此时cw=3, 从a元素开始轮询, a即符合>=cw条件, 所以第六次调度结果为a

以此类推~ 当所有的元素都被调度过一次之后, 

1
2
3
4
5
6
7
a    b   c    d
✔️  ✔️  ✔️   ✔️
✔️  ✔️  ✔️   ✔️
✔️  ✔️  ✔️
✔️  ✔️  ✔️
         ✔️
         ✔️

需要将cw的重置为最大权重值, 以供后续请求重新调度

总结: 我们总结一下上面流程的关键点

  • 通过i = (i + 1) mod n轮询每个元素(这是上一篇轮询调度算法的核心)
  • 需要取得所有元素中最大的权重值
  • 需要定义一个cw(current weight)变量, 用来记录最新的”最大权重值”
  • 每次所有的元素被轮询一次后, 都需要将cw-1
  • 当cw-1之后的值<=0时, 意味着所有的元素按照权重之比, 都已经被调度过一次了, 此时需要将cw的值重置为最大权重值, 以供后续请求重新调度

代码实现

step 0: 前期准备

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 定义带权重属性的元素结构体
type Volume struct {
	Name   string
	Weight int
}

// 定义元素集合类型
type Volumes []Volume
// GetMaxWeight 获取Slice中最大权重值
func (v Volumes) GetMaxWeight() int {
	maxWeight := 0
	for _, volume := range v {
		if maxWeight < volume.Weight {
			maxWeight = volume.Weight
		}
	}
	return maxWeight
}


// 调度索引
var i = -1

// current weight 记录当前调度的权重值
var cw = 0

step 1: 首先实现轮询调度算法

1
2
3
4
5
func (v volumes) Select() string {
    // 轮询调度算法 i = (i + 1) mod n
	i = (i + 1) % len(v)
	return v[i].name
}

step 2: 每次所有的元素被轮询一次后将cw-1

1
2
3
4
5
6
7
8
9
10
11
12
func (v volumes) Select() string {
    // 轮询调度算法 i = (i + 1) mod n
	i = (i + 1) % len(v)
	// 当 (i + 1) mod n 的余数为0时, 有两种情况
	// 1. 首次被调用执行时
	// 2. 已经轮询完一整轮, 又回到起点时
	if i  == 0 {
	   // 每次轮询完一轮之后将cw-1
	   cw = cw - 1
	}
	return v[i].name
}

step 3: cw<=0时将cw重置为最大权重值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 提前算好最大权重值, 传进去
func (v volumes) Select(maxWeight int) string {
    // 轮询调度算法 i = (i + 1) mod n
	i = (i + 1) % len(v)
	// 当 (i + 1) mod n 的余数为0时, 有两种情况
	// 1. 首次被调用执行时
	// 2. 已经轮询完一整轮, 又回到起点时
	if i  == 0 {
	   // 每次轮询完一轮之后将cw-1
	   cw = cw - 1
	   // cw 为负数或0的两种特殊情况
	   // 1. 当首次被调用时, cw的值为0, 所以执行 cw - 1 后, cw 的值为负数
	   // 2. 当所有元素都已经被调度过一次后, cw的值将递减至0
	   // 所以这里需要单独处理一下cw<=0的情况
	   if cw <= 0 {
	       cw = maxWeight
	   }
	}
	return v[i].name
}

step 4: 当索引对应的元素权重值>=cw时返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 提前算好最大权重值, 传进去
func (v volumes) Select(maxWeight int) string {
    // 轮询调度算法 i = (i + 1) mod n
	i = (i + 1) % len(v)
	// 当 (i + 1) mod n 的余数为0时, 有两种情况
	// 1. 首次被调用执行时
	// 2. 已经轮询完一整轮, 又回到起点时
	if i  == 0 {
	   // 每次轮询完一轮之后将cw-1
	   cw = cw - 1
	   // cw 为负数或0的两种特殊情况
	   // 1. 当首次被调用时, cw的值为0, 所以执行 cw - 1 后, cw 的值为负数
	   // 2. 当所有元素都已经被调度过一次后, cw的值将递减至0
	   // 所以这里需要单独处理一下cw<=0的情况
	   if cw <= 0 {
	       cw = maxWeight
	   }
	}
	// return这里需要稍加修改, 只有元素的权重值>=cw时才可以返回
	if v[i].Weight >= cw {
	   return v[i].name
	}
}

内部轮询

上面的return中, 定义了只有当元素的权重值>=cw时才可以返回, 那么该条件如果不符合时, 需要在函数内继续轮询元素, 直至有元素的权重值符合条件为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func (v volumes) Select(maxWeight int) string {
	for {
		// 轮询调度算法 i = (i + 1) mod n
		i = (i + 1) % len(v)
		// 当 (i + 1) mod n 的余数为0时, 有两种情况
		// 1. 首次被调用执行时
		// 2. 已经轮询完一整轮, 又回到起点时
		if i == 0 {
			// 每次轮询完一轮之后将cw-1
			cw = cw - 1
			// cw 为负数或0的两种特殊情况
			// 1. 当首次被调用时, cw的值为0, 所以执行 cw - 1 后, cw 的值为负数
			// 2. 当所有元素都已经被调度过一次后, cw的值将递减至0
			// 所以这里需要单独处理一下cw<=0的情况
			if cw <= 0 {
				// 将cw重置为最大权重值
				cw = maxWeight
			}
		}

		// return这里需要稍加修改, 只有元素的权重值>=cw时才可以返回
		if v[i].Weight >= cw {
			return v[i].name
		}
	}
}

优化项

  • 性能优化: 上面的代码实现中, 所有的元素每当轮询一轮后, cw都是写死了要-1, 其实这里可以可以稍加优化, 预先计算出所有元素权重值得最大公约数, 每次轮询完一轮后cw可以直接-最大公约数(gcd), 这样可以减少内部循环的次数, 而且调度效果更为分散. (当然配置的权重最大公约数计算之后如果也是1, 则该优化与直接每次-1的循环次数相同)

求最大公约数算法可参考前面的文章

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package main

import (
	"fmt"
)

// 定义带权重属性的元素结构体
type Volume struct {
	Name   string
	Weight int
}

// 定义元素集合类型
type Volumes []Volume

// 调度索引
var i = -1

// current weight 记录当前调度的权重值
var cw = 0

func (v Volumes) Select(maxWeight, gcd int) string {
	for {
		// 轮询调度算法 i = (i + 1) mod n
		i = (i + 1) % len(v)
		// 当 (i + 1) mod n 的余数为0时, 有两种情况
		// 1. 首次被调用执行时
		// 2. 已经轮询完一整轮, 又回到起点时
		if i == 0 {
			// 最新权重值 = 当前权重值 - 最大公约数
			cw = cw - gcd
			if cw <= 0 {
				// cw <= 0 时, 有两种情况
				// 1. 首次被调用执行时, cw值初始化为0, 只要maxWeight最大权重数值在0以上, cw的最新值一定<0
				// 2. 当所有的元素按照权重都被调度/选择一遍之后, cw的值一定为0
				// 此时需要将最大权重值(重新)赋值到cw
				cw = maxWeight
			}
		}

		// 当索引值 >= 最新权重值时, 返回名称
		if v[i].Weight >= cw {
			return v[i].Name
		}
	}
}

// GetMaxWeight 获取Slice中最大权重值
func (v Volumes) GetMaxWeight() int {
	maxWeight := 0
	for _, volume := range v {
		if maxWeight < volume.Weight {
			maxWeight = volume.Weight
		}
	}
	return maxWeight
}

func Gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return Gcd(b, a%b)
}

// GetGcd 获取Slice最大公约数
func (v Volumes) GetGcd() int {
	g := v[0].Weight
	for i := 0; i < len(v)-1; i++ {
		g = Gcd(g, v[i+1].Weight)
	}
	return g
}

func main() {
	v1 := Volume{
		Name:   "a",
		Weight: 4,
	}
	v2 := Volume{
		Name:   "b",
		Weight: 4,
	}
	v3 := Volume{
		Name:   "c",
		Weight: 6,
	}
	v4 := Volume{
		Name:   "d",
		Weight: 2,
	}

	vo := Volumes{
		v1, v2, v3, v4,
	}
    // 获取元素集中的最大权重值
	maxWeight := vo.GetMaxWeight()
	// 获取元素集中权重值的最大公约数
	gcd := vo.GetGcd()

	for j := 0; j < 18; j++ {
		fmt.Println(j+1, vo.Select(maxWeight, gcd))
	}
}

运行结果: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 c
2 a
3 b
4 c
5 a
6 b
7 c
8 d
9 c
10 a
11 b
12 c
13 a
14 b
15 c
16 d
17 c
18 a
相关文章