Go
by smallnest

平滑的基于权重的轮询算法

轮询算法是非常常用的一种调度/负载均衡的算法。依照百度百科上的解释:

Round-Robin，轮询调度，通信中信道调度的一种策略，该调度策略使用户轮流使用共享资源，不会考虑瞬时信道条件。从相同数量无线资源（相同调度时间段）被分配给每条通信链路的角度讲，轮询调度可以被视为公平调度。然而，从提供相同服务质量给所有通信链路的角度而言，轮询调度是不公平的，此时，必须为带有较差信道条件的通信链路分配更多无线资源（更多时间）。此外，由于轮询调度在调度过程中不考虑瞬时信道条件，因此它将导致较低的整体系统性能，但与最大载干比调度相比，在各通信链路间具有更为均衡的服务质量。

更广泛的轮询调度应用在广度的服务调度上面，尤其在面向服务或者是面向微服务的架构中，比可以在很多知名的软件中看到它的身影，比如LVS、Nginx、Dubblo等。但是正如上面的百度百科中的介绍一样，轮询调度有一个很大的问题，那就是它认为所有的服务的性能都是一样的，每个服务器都被公平的调度，在服务器的性能有显著差别的环境中，性能比较差的服务器被调度了相同的次数，这不是我们所期望的。所以本文要介绍的是加权的轮询算法，轮询算法可以看成是加权的轮询算法的一个特例，在这种情况下，每个服务器的权重都是一样的。

本文介绍了Nginx和LVS的两种算法，比较了它们的优缺点，并提供了一个通用的 Go 语言实现的加权轮询算法库： weighted,可以用在负载均衡/调度/微服务网关等场合。

WRR(weighted round-robin) 也是周而复始地轮询分组服务资源，但不同的是WRR算法为每个服务资源分配一个权值，当轮询到某个服务的时候，将根据它所具有权值的大小决定其是否可以提供服务。由于WRR是基于轮询的，因此它只是在大于一个轮询周期的时间上才能显示是公平的。

本文介绍了Nginx和LVS基于权重的轮询算法，这两个算法都是通过巧妙的运算得到每次要提供的服务对象，但各自又有自己的特点。

Nginx算法

Nginx基于权重的轮询算法的实现可以参考它的一次代码提交： Upstream: smooth weighted round-robin balancing。

它不但实现了基于权重的轮询算法，而且还实现了平滑的算法。所谓平滑，就是在一段时间内，不仅服务器被选择的次数的分布和它们的权重一致，而且调度算法还比较均匀的选择服务器，而不会集中一段时间之内只选择某一个权重比较高的服务器。如果使用随机算法选择或者普通的基于权重的轮询算法，就比较容易造成某个服务集中被调用压力过大。

举个例子，比如权重为{a:5, b:1, c:1)的一组服务器，Nginx的平滑的轮询算法选择的序列为{ a, a, b, a, c, a, a },这显然要比{ c, b, a, a, a, a, a }序列更平滑，更合理，不会造成对a服务器的集中访问。

算法如下：

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.

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
func nextWeighted(servers []*Weighted) (best *Weighted) {
	total := 0
	for i := 0; i < len(servers); i++ {
		w := servers[i]
		if w == nil {
			continue
		}
		w.CurrentWeight += w.EffectiveWeight
		total += w.EffectiveWeight
		if w.EffectiveWeight < w.Weight {
			w.EffectiveWeight++
		}
		if best == nil || w.CurrentWeight > best.CurrentWeight {
			best = w
		}
	}
	if best == nil {
		return nil
	}
	best.CurrentWeight -= total
	return best
}

如果你使用weighted库，你可以通过下面的几行代码就可以使用这个算法进行调度：

1
2
3
4
5
6
7
8
9
10
11
12
func ExampleW_() {
	w := &W1{}
	w.Add("a", 5)
	w.Add("b", 2)
	w.Add("c", 3)
	for i := 0; i < 10; i++ {
		fmt.Printf("%s ", w.Next())
	}
	// Output: a c b a a c a b c a
}

LVS算法

LVS使用的另外一种算法，它的算法的介绍可以参考它的网站的wiki。

算法用伪代码表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Supposing that there is a server set S = {S0, S1, …, Sn-1};
W(Si) indicates the weight of Si;
i indicates the server selected last time, and i is initialized with -1;
cw is the current weight in scheduling, and cw is initialized with zero; 
max(S) is the maximum weight of all the servers in S;
gcd(S) is the greatest common divisor of all server weights in S;
while (true) {
    i = (i + 1) mod n;
    if (i == 0) {
        cw = cw - gcd(S); 
        if (cw <= 0) {
            cw = max(S);
            if (cw == 0)
            return NULL;
        }
    } 
    if (W(Si) >= cw) 
        return Si;
}

可以看到它的代码逻辑比较简单，所以性能也很快，但是如果服务器的权重差别较多，就不会像Nginx那样比较平滑，可以在短时间内对权重很大的那台服务器压力过大。

使用weighted库和上面一样简单，只是把类型W换成W2即可：

1
2
3
4
5
6
7
8
9
10
11
12
func ExampleW_() {
	w := &W2{}
	w.Add("a", 5)
	w.Add("b", 2)
	w.Add("c", 3)
	for i := 0; i < 10; i++ {
		fmt.Printf("%s ", w.Next())
	}
	// Output: a a a c a b c a b c
}

性能比较

可以看到，上面两种方法的使用都非常的简单，只需生成一个相应的W对象，然后加入服务器和对应的权重即可，通过Next方法就可以获得下一个服务器。

如果服务器的权重差别很大，出于平滑的考虑，避免短时间内会对服务器造成冲击，你可以选择Nginx的算法，如果服务器的差别不是很大，可以考虑使用LVS的算法，因为测试可以看到它的性能要好于Nginx的算法:

1
2
BenchmarkW1_Next-4      20000000                50.1 ns/op             0 B/op          0 allocs/op
BenchmarkW2_Next-4      50000000                29.1 ns/op             0 B/op          0 allocs/op

实际上两者的性能都非常的快，十个服务器的每次调度也就是几十纳秒的级别，而且没有额外的对象分配，所以无论使用哪种算法，这个调度不应成为你整个系统的瓶颈。