看加权轮询算法实现，让你体验算法之美

什么是加权轮询

加权轮询是一直负债均衡器（load-balancer）算法，相较于轮询算法加权轮询多了个权重值。假如我们有机器A,B,C 轮询算法调度的结果，应该是

A  （第一次）
B  （第二次）
C  （第三次）
一直重复上述过程

而加权轮询会有权重配置比如

A weight=2
B weight=1
C weight=1

上面配置代表的意思是，4次请求中，A会命中2次，B命中一次，C命中一次。 相比较也加权轮询可以有稳定的命中序列，加权轮询不一定能得到稳定的命中序列，因为A命中两次，可能连续命中，也可能不连续。 在实际应用中我们最优选择是稳定平滑系列。

最理想加权限轮询的结果应该是：

A  （第一次）
B  （第二次）
C  （第三次）
A  （第四次）
一直重复上述过程

轮询算法对所有机器的命中机会均等，加权轮询可以提高某些机器的命中机会，这样的好处可以对高配置低负载的机器增加权重来提高机器使用率，从而提高服务质量。

加权算法如何实现

从上面的介绍中，我们大概知道了加权轮询的算法内涵，这个算法应该如何实现呢？

我们还是三台机器权重是:

A weight=4
B weight=2
C weight=1

希望所有读者能在脑袋思考下，如何快速实现，可以不考虑算法好坏,1分钟后再来接下看。

~~1min Later

不知道大家想好解题思路没？

先来一个暴力解题法，我们看题得只知道total权重是7，假设所有的请求数为n， 我们需要n对7取余数，所有的余数序列为 [0,1,2,3,4,5,6]，是不是只要映射（mapping）一下就好了，例如

[0 -3] -> A
[4 -5] -> B
6 -> C

package main

import "fmt"

type WeightRobin struct {
	Total int32
	Hosts []*WeightHost
}

type WeightHost struct {
	W     int32
	Host  string
	Range [2]int
}

func (wr *WeightRobin) Round(n int) (string, error) {
	m := n % int(wr.Total)
	for _, h := range wr.Hosts {
		if h.Range[0] <= m && m <= h.Range[1] {
			return h.Host, nil
		}
	}
	return "", nil
}

func main() {
	hosts := []*WeightHost{
		{
			W:    4,
			Host: "host1",
		},
		{
			W:    2,
			Host: "host2",
		},
		{
			W:    1,
			Host: "host3",
		},
	}
	var total int32 = 0
	var index = 0
	for _, h := range hosts {
		h.Range[0] = index
		h.Range[1] = index + int(h.W-1)
		index += int(h.W)
		total += h.W
	}
	w := WeightRobin{
		Total: total,
		Hosts: hosts,
	}
	for i := 0; i < 14; i++ {
		h, _ := w.Round(i)
		fmt.Println(h)
	}
}

run一下

$ go run main.go 
host1
host1
host1
host1
host2
host2
host3
host1
...
host2
host3

到了这边是现实了这个功能了，至少走出了第一步，我们才有底气做算法优化和升级。

平滑加权轮询

好了，到了这边我们考虑写上面算法的问题，稳定性可以，但是不平滑。不平滑带来的问题就是机器可能连续处理多个请求而带来瞬时负载增加。上面的算法0-3只有A机器在工作，A的机器瞬时有可能高。

能不能做到如下平滑一点:

0 -> A
1 -> B
2 -> A
3 -> C
4 -> A
5 -> B
6 -> A

到这边通用希望读者在脑袋中思考1分钟

~~1min Later

平滑主要是要设计交替规整，交替规整算法应该不难实现，我们让每个机器带一个计数器，在每一轮开始计数器的初始值为权重值，请求器每次器交替扫描这三台机器，知道他们的计数器都为0，这个时候下一轮开始又重置计数器为他们的权重值。

         A（4）     B（2）    C（1）
第1轮    A（3）     B（2）    C（1）    拿到A
第2轮    A（3）     B（1）    C（1）    拿到B
第3轮    A（3）     B（1）    C（0）    拿到C
第4轮    A（2）     B（1）    C（0）    拿到A
第5轮    A（2）     B（0）    C（0）    拿到B
第6轮    A（1）     B（0）    C（0）    拿到A
第7轮    A（0）     B（0）    C（0）    拿到A
第8轮    A（3）     B（2）    C（1）    拿到A （重置轮回了）

这个算法实现也很简单，这边就不写它的实现代码了，这里最主要想介绍一种更加完美的平滑加权轮询算法，看了之后你手写一下，肯定会跟我一样觉得这算法的作者脑袋开得真大，脑回路惊奇。

算法过程：

• Total 为所有权重最大值
• 每个host除了有自己的权重值（weight）外还有一个current_weight变量，这个current_weight每一轮都会变化，初始值为0
• 每一轮选择器 会吧 current_weight+weight 设置为 current_weight的值， 然后变量机器最大current_weight值为选择的本来目标机器，然后这个目标机器的current_weight= current_weight -Total

我们罗列一下这个算法的运算过程：

 c 		                       c+w                       遍历拿到最大的值 同时减去总数
 A-c(0)   B-c(0)   C-c(0)   -> A-c(4)  B-c(2)   C-c(1)   选出A，A-c= 4 - 7
 A-c(-3)  B-c(2）  C-c(1）   -> A-c(1)  B-c(4）  C-c(2）  选出B  B-c= 4 - 7
 A-c(1)   B-c(-3） C-c(2）   -> A-c(5)  B-c(-1） C-c(3）  选出A  A-c= 5 - 7
 A-c(-2)  B-c(1）  C-c(3）   -> A-c(2)  B-c(1）  C-c(4）  选出C  C-c= 4 - 7
 A-c(2)   B-c(1）  C-c(-3）  -> A-c(6)  B-c(3）  C-c(-2） 选出A  A-c= 6 - 7 
 A-c(-1)  B-c(3）  C-c(-2）  -> A-c(3)  B-c(5）  C-c(-1） 选出B  B-c= 2 - 7
 A-c(3)   B-c(-2） C-c(-2）  -> A-c(7)  B-c(0）  C-c(0）  选出A  A-c= 7 - 7
 A-c(0)   B-c(0）  C-c(0）   -> A-c(4)  B-c(2）  C-c(1）  选出A  C-c= 4 - 7  回到初始值 轮回了

是不是很奇妙？作者是如何想到这样子的算法的？

我们用go实现一下

package main

import "fmt"

type WeightRobin struct {
	Total int32
	Hosts []WeightHost
}

type WeightHost struct {
	W    int32
	Host string
	c    int32
}

func (wr *WeightRobin) Round() (string, error) {
	var c int32
	var best int
	for i, h := range wr.Hosts {
		wr.Hosts[i].c += h.W
		if wr.Hosts[i].c > c {
			c = wr.Hosts[i].c
			best = i
		}
	}
	wr.Hosts[best].c -= wr.Total
	return wr.Hosts[best].Host, nil
}

func main() {
	hosts := []WeightHost{
		WeightHost{
			W:    4,
			Host: "host1",
		},
		WeightHost{
			W:    2,
			Host: "host2",
		},
		WeightHost{
			W:    1,
			Host: "host3",
		},
	}

	var total int32 = 0
	for _, h := range hosts {
		total += h.W
	}

	w := WeightRobin{
		Total: total,
		Hosts: hosts,
	}
	for i := 0; i < 14; i++ {
		h, _ := w.Round()
		fmt.Println(h)
	}
}

run一下

$ go run main.go 
host1
host2
host1
host3
host1
host2
host1
host1 #在这边轮回了
...
host1