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

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

演示思路

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

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