公司内部有一个流传很广的负载均衡算法，大概的流程如下：
数组元素对应的是 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]
哈哈哈。
