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

数组元素对应的是 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]

哈哈哈。