公司里某存储系统使用 ip+port 直连,并且使用了下列洗牌算法来进行负载均衡:

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
}

从 shuffle 过的数组中取第一个节点进行请求,如果失败,就选下一个节点重试。

乍看之下没有什么问题。但下游经常会跑来吐槽说你们的请求在我们这里分布不均匀。但这个算法虽然不是标准的 fisher yates 洗牌,但也确实看不出啥问题来。所以一直没有深入研究。

直到有一天,有人用这个洗牌算法写出了一个简单的 demo:

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)
}

如果算法没什么问题的话,对每个节点的数值求和总值应该也差不了太多,而结果让人大跌眼镜。

[19992636 29992636 20007364 30007364]

所以这显然是一个错误的洗牌算法。所以最正确的洗牌算法还是 fisher yates 算法。即每次生成一个随机数,并选出该位置的牌放在整个数组的尾部。

产生这种现象的本质在于伪随机数的解空间有限,覆盖不到 N! 的解空间。更为具体的原因之前在陈皓的博客中已经有讨论和分析,这里就不赘述了:

https://coolshell.cn/articles/8593.html/comment-page-1#comments