你的负载均衡真的均衡么？

公司内部有一个流传很广的负载均衡算法，大概的流程如下：

数组元素对应的是 ip+port 列表，形如下面这样：

100.69.62.1:3232
100.69.62.32:3232
100.69.62.42:3232
100.69.62.81:3232
100.69.62.11:3232
100.69.62.113:3232
100.69.62.101:3232

每次来一个新请求，都对 ip+port 大小，值为索引的一个数组进行一次 shuffle。然后依次取第一个元素，如果请求失败，那么请求下一台机器。

shuffle 的过程简化过是下面这样：

func SliceShuffle(slice []string) []string {  
  for i := 0; i < len(slice); i++ {
    a := rand.Intn(len(slice))
    b := rand.Intn(len(slice))
    slice[a], slice[b] = slice[b], slice[a]
  }
  return slice
}

乍看似乎没什么问题。数组大小为 N，那么我们就进行 N 次两两交换，最后可以得到一个随机数列。当然了，如果严密一点，我们这里再加个种子：

rand.Seed(time.Now().UnixNano())

考虑到可能的性能问题，特意把种子的初始化在初始化函数中只做一次。

实际上这个算法是错误的。验证洗牌算法最简单的方式就是看洗牌之后的数据分布：

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func init() {
	rand.Seed(time.Now().UnixNano())
}

func shuffle(slice []int) {
	for i := 0; i < len(slice); i++ {
		a := rand.Intn(len(slice))
		b := rand.Intn(len(slice))
		slice[a], slice[b] = slice[b], slice[a]
	}
}

func main() {
	var cntMap = map[string]int{}
	for i := 0; i < 1000000; i++ {
		var a = []int{0, 1, 2, 3}
		shuffle(a)
		for j := 0; j < len(a); j++ {
			key := fmt.Sprintf("%d_%d", a[j], j)
			cntMap[key]++
		}
	}

	for i := 0; i < 4; i++ {
		for j := 0; j < 4; j++ {
			key := fmt.Sprintf("%d_%d", i, j)
			fmt.Printf("%d ", cntMap[key])
		}
		fmt.Println()
	}
}

不管运行几次，数据的分布总是会有一些规律：

~/test git:master ❯❯❯ go run shuffle.go
296024 235054 234245 234677
235324 296112 233536 235028
234866 234653 297225 233256
233786 234181 234994 297039

对角线上的数据偏多，而且偏的不是一点半点。对角线上的数据表示 i 元素在第 i 个位置上出现的次数。这表示我们的 shuffle 算法结果具有某种倾向性。这种倾向性为：“每个位置的数字都倾向于待在原位”。

从数学上简单证明一下，因为我们已经知道了数字倾向于不移动，我们来算一下交换操作完全不涉及到 i 的概率，如果有十个数字。那么第一个数字在十次交换中不被拿来交换的概率：

p > 9*9/10*10 = 0.81

这里为了计算方便，稍微做了一些简化。因为一个数可能被交换到其它位置，在之后的交换过程中又被交换回来了。

计算出来的概率表明，任意一个位置的值都有 81% 以上的概率完全不被交换。所以也就更倾向于留在原位了。

所以这样的洗牌加负载均衡会导致什么样的问题呢？

结论：负载的分布倾向于选择配置文件中的第一台机器。这也就是有一些被调用方会觉得调用方的负载分布不均匀的问题。

在和同事交流的过程中，另一个部门的一位同学说他们 shuffle 算法和我这个不一样，然后给出了他们的：

package main

import (  
    "fmt"
    "math/rand"
)

func Shuffle(src []int) []int {  
    dest := make([]int, len(src))
    perm := rand.Perm(len(src) / 2)
    for i, v := range perm {
        dest[v*2] = src[i*2]
        dest[v*2+1] = src[i*2+1]
    }
    return dest
}

func main() {  
    var a = []int{1, 2, 3, 4}
    var sum []int = []int{0, 0, 0, 0}
    for i := 0; i < 10000000; i++ {
        var b = Shuffle(a)
        sum[0] += b[0]
        sum[1] += b[1]
        sum[2] += b[2]
        sum[3] += b[3]
    }
    fmt.Println(sum)
}

运行一下：

~/test git:master ❯❯❯ go run shuffle.go
[19992636 29992636 20007364 30007364]

哈哈哈。