Fisher–Yates shuffle 洗牌算法 和go-zookeeper库中的代码缺陷

项目中使用到一个golang的zookeeper库,使用过程中遇到一些问题待解决,看看源代码解决。记录下看源代码过程看到的一些内容。这里讲一下看到的第一个内容,该sdk里用到的洗牌算法。

该库的地址为:https://github.com/go-zookeeper/zk

这个算法在这个sdk,主要是避免所有的zookeeper客户端在使用相同的配置文件时,拿到的ip+端口列表都是同样的顺序,大家集中的去访问一个zookeeper节点,zookeeper集群内各个节点负载很不均衡。

看看源代码

// stringShuffle performs a Fisher-Yates shuffle on a slice of strings
func stringShuffle(s []string) {
	for i := len(s) - 1; i > 0; i-- {
		j := rand.Intn(i + 1)
		s[i], s[j] = s[j], s[i]
	}
}

很简单的,说人话就是,从最后一个往前,每次都在这个之前及自身随机生成一个下标确定一个元素,交换这两个数。这里注意一点:可能出现自己与自己交换的情况,这也是保证随机性的一个重要原因,否则,就会出现一个很验证的问题,就是某个元素在随机洗牌之后,肯定不会出现在自己原来的位置,这样的话就排除了一大批可能的排列,而不是真正的随机。

在该库的使用过程中,zookeeper集群配置有三个zookeeper节点,我感觉所有客户端仍然会集中的去访问相同的zookeeper节点。

分析原因:

该库的随机算法在调用rand.Intn()函数之前,没有使用任何随机因素进行初始化,可以写代码验证,未初始化的rand.Intn()每次启动,生成的都是相同的随机数。

//测试代码
package main

import (
        "fmt"
        "math/rand"
)

func main() {
        fmt.Println(rand.Intn(30))
}
#!/bin/bash

#测试运行脚本

for i in $(seq 1 10)
do
        ./rand
        sleep 1
done

可以看到所有的输出都是相同的11。所以这个库在这里是有代码缺陷的,或者我看的版本有问题。所有的客户端仍然会集中去访问相同的节点。