浅谈分布式的负载均衡

round robin式，例如上次选了第一台，那么这次就选第二台，下次第三台；如果到了最后一台，那么下次从第一台开始。

每次都随机挑，真随机伪随机均可。假设选择了第x台机器，那么x可被描述为rand.Intn()%n

对下游节点进行排序，选择权重最大/小那一个

实际场景下我们不可能无脑轮询或者无脑随机，如果对下游请求失败了，我们还需要某种机制来进行重试，如果纯粹的随机算法，存在一定可能性下次仍然随机到这次的问题节点。

考虑到我们需要随机选取每次发送请求的节点，同时在遇到下游返回错误时换其他节点重试。所以我们设计一个大小和节点数组大小一致的索引数组，每次来请求，我们对数组进行洗牌，然后取第一个元素作为选中的服务节点，如果请求失败，那么选择下一个节点重试

var endpoints = []string{
    "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",
}

// 重点在这个 shuffle
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 apiRequest(params map[string]interface{}, ep string) error {
    fmt.Println("ep:", ep)
    return nil
}

func request(params map[string]interface{}) error {
    var indexes = []int{0, 1, 2, 3, 4, 5, 6}
    var err error
    shuffle(indexes)
    maxRetryTimes := 3
    idx := 0
    for i := 0; i < maxRetryTimes; i++ {
        err = apiRequest(params, endpoints[indexes[idx]])
        if err == nil {
            break
        }
        idx++
    }
    if err != nil {
        // logging
        return err
    }
    return nil
}

func main() {
    params := make(map[string]interface{})
    params["islocal"] = true

    for i := 0; i < 10; i++ {
        request(params)
    }
}

我们循环一遍slice，两两交换，和洗牌方法类似，看起来没什么问题。运行结果如下

$ ./test
ep: 100.69.62.32:3232
ep: 100.69.62.113:3232
ep: 100.69.62.81:3232
ep: 100.69.62.113:3232
ep: 100.69.62.42:3232
ep: 100.69.62.11:3232
ep: 100.69.62.1:3232
ep: 100.69.62.11:3232
ep: 100.69.62.81:3232
ep: 100.69.62.101:3232
$ ./test
ep: 100.69.62.32:3232
ep: 100.69.62.113:3232
ep: 100.69.62.81:3232
ep: 100.69.62.113:3232
ep: 100.69.62.42:3232
ep: 100.69.62.11:3232
ep: 100.69.62.1:3232
ep: 100.69.62.11:3232
ep: 100.69.62.81:3232
ep: 100.69.62.101:3232

上面的例子还是有问题的，有如下两个隐患：

• 没有随机种子。在没有随机种子的情况下，rand.Intn()返回的伪随机数序列是固定的，如上的输出结果，两次的结果的顺序都是一致的，是个伪随机，当我们添加上

rand.Seed(time.Now().Unix())

这句后，输出结果如下：

$ ./test
ep: 100.69.62.1:3232
ep: 100.69.62.113:3232
ep: 100.69.62.32:3232
ep: 100.69.62.11:3232
ep: 100.69.62.81:3232
ep: 100.69.62.32:3232
ep: 100.69.62.113:3232
ep: 100.69.62.32:3232
ep: 100.69.62.42:3232
ep: 100.69.62.81:3232
$ ./test
ep: 100.69.62.32:3232
ep: 100.69.62.1:3232
ep: 100.69.62.11:3232
ep: 100.69.62.42:3232
ep: 100.69.62.113:3232
ep: 100.69.62.113:3232
ep: 100.69.62.81:3232
ep: 100.69.62.101:3232
ep: 100.69.62.101:3232
ep: 100.69.62.1:3232

• 洗牌不均匀，会导致整个数组第一个节点有大概率被选中，并且多个节点的负载分布不均衡。
  关于这一点，需要用概率知识来简单证明一下，假设每次都是真随机，那么任意位置的节点在len(slice)次交换中不被选中的概率是

((6/7)*(6/7))^7 ≈ 0.34

而分布均匀情况下，我们肯定希望被第一个元素在任意位置上分布的概率均等，所以其被随机选到的概率应该约等于1/7 ≈ 0.14。显然这个洗牌算法对于任意位置的元素来说，有34%的概率不对其进行交换操作，所以所有元素都倾向于留在原来的位置，而因为我们每次输入的数组都是同一个序列，因此第一个元素有更大的概率被选中。

从数学上得到证明的还是经典的fisher-yates算法，主要思路为每次随机挑选一个值，放在数组末尾。然后在n-1个元素的数组中再随机挑选一个值，放在数组末尾，以此类推

var endpoints = []string{
    "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",
}

var indexes = []int{0, 1, 2, 3, 4, 5, 6}

func shuffle(indexes []int) {
    for i := len(indexes); i > 0; i-- {
        lastIdx := i - 1
        idx := rand.Intn(i)
        indexes[lastIdx], indexes[idx] = indexes[idx], indexes[lastIdx]
    }
}

func main() {
    for i := 0; i < 10; i++ {
        shuffle(indexes)
        fmt.Println(endpoints[indexes[0]])
    }
}

Go的标准库已经内置了这个算法：

var endpoints = []string{
    "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",
}

func shuffle(n int) []int {
    a := rand.Perm(n)
    return a
}

func main() {
    for i := 0; i < 10; i++ {
        indexes := shuffle(len(endpoints))
        fmt.Println(endpoints[indexes[0]])
    }
}

在当前场景下，我们只要用rand.Perm就可以得到我们想要的索引数组了

当前场景是从N个节点中选择一个节点发送请求，初始化请求结束后，后续的请求会重新对数组洗牌，所以每两个请求之间没有什么关联关系。但在一些特殊的场景下，例如使用ZooKeeper时，客户端初始化从多个服务节点中挑选一个节点后，是会向该节点建立长连接的，之后客户端的请求都会发送给该节点去。直到该节点不可用，才会在节点列表中挑选下一个节点。在这种场景下，我们的初始连接节点选择就要求必须是真随机，否则所有客户端启动时，都会连接同一个ZooKeeper实例。为rand库设置种子的方法：

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

func init() {
    rand.Seed(time.Now().UnixNano())
}
func shuffle1(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 shuffle2(indexes []int) {
    for i := len(indexes); i > 0; i-- {
        lastIdx := i - 1
        idx := rand.Intn(i)
        indexes[lastIdx], indexes[idx] = indexes[idx], indexes[lastIdx]
    }
}
func main() {
    var cnt1 = map[int]int{}
    for i := 0; i < 1000000; i++ {
        var sl = []int{0, 1, 2, 3, 4, 5, 6}

        shuffle1(sl)
        cnt1[sl[0]]++
    }
    var cnt2 = map[int]int{}
    for i := 0; i < 1000000; i++ {
        var sl = []int{0, 1, 2, 3, 4, 5, 6}
        shuffle2(sl)
        cnt2[sl[0]]++
    }
    fmt.Println(cnt1, "n", cnt2)
}

计算结果：

t$ ./test
map[0:223629 1:129681 2:129535 3:129578 4:129167 5:129071 6:129339] 
map[0:142152 1:142888 2:142728 3:143693 4:142578 5:143363 6:142598]

分布结果和我们推导出的结论是一致的。