Nginx平滑的基于权重轮询算法描述为：

Algorithm is as follows: on each peer selection we increase current_weight of each eligible peer by its weight, select peer with greatest current_weight and reduce its current_weight by total number of weight points distributed among peers.

算法执行2步，选择出1个当前节点：

  • 每个节点，用它们的当前值加上它们自己的权重。
  • 选择当前值最大的节点为选中节点，并把它的当前值减去所有节点的权重总和。

例如{a:5, b:1, c:1}三个节点，里面的{5,1,1}分别代表abc节点的权重。一开始我们初始化三个节点的当前值为{0, 0, 0}。 选择过程如下表：

轮数 选择前的当前权重 选择节点 选择后的当前权重
1 {5,1,1} a {-2,1,1}
2 {3,2,2} a {-4,2,2}
3 {1,3,3} b {1,-4,3}
4 {6,-3,4} a {-1,-3,4}
5 {4,-2,5} c {4,-2,-2}
6 {9,-1,-1} a {2,-1,-1}
7 {7,0,0} a {0,0,0}

我们可以发现，a, b, c选择的次数符合5:1:1，而且权重大的不会被连续选择。7轮选择后， 当前值又回到{0, 0, 0}，以上操作可以一直循环，一样符合平滑和基于权重。

Go语言实现

 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

package main

import "fmt"

type Node struct {
	Server  string
	Weight  int
	Current int
}

//平滑轮询调度实现
func SelectNext(nodes []*Node) (best *Node) {
	if len(nodes) == 0 {
		return nil
	}

	total := 0
	for _, node := range nodes {
		if node == nil {
			continue
		}

		total += node.Weight		//记录所有节点的权重总和
		node.Current += node.Weight	//每个节点，用它们的当前值加上它们自己的权重

		//每选择当前值最大的节点为选中节点
		if best == nil || node.Current > best.Current {
			best = node
		}
	}

	if best == nil {
		return nil
	}
	
	//选中节点的当前值减去所有节点的权重总和
	best.Current -= total 
	return best
}

func main() {
	nodes := []*Node{
		{Server: "127.0.0.1", Weight: 5},
		{Server: "127.0.0.2", Weight: 1},
		{Server: "127.0.0.3", Weight: 1},
	}

	for i := 0; i < 10; i++ {
		if best := SelectNext(nodes); best != nil {
			fmt.Println(i, "=>", best.Server, best.Weight)
		}
	}
}

运行输出：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

0 => 127.0.0.1 5
1 => 127.0.0.1 5
2 => 127.0.0.2 1
3 => 127.0.0.1 5
4 => 127.0.0.3 1
5 => 127.0.0.1 5
6 => 127.0.0.1 5
7 => 127.0.0.1 5
8 => 127.0.0.1 5
9 => 127.0.0.2 1

小结

这里简单做了总结笔记，很多开源项目的基于权重的轮询算法也是参考了此算法，比如著名的Go语言RPC框架https://github.com/smallnest/rpcx。

关于如何证明算法的平滑性，感兴趣的可以阅读下面的参考链接：