Go 語言 負(fù)載均衡

原文鏈接：https://chai2010.cn/advanced-go-programming-book/ch6-cloud/ch6-05-load-balance.html

6.5 負(fù)載均衡

本節(jié)將會(huì)討論常見的分布式系統(tǒng)負(fù)載均衡手段。

6.5.1 常見的負(fù)載均衡思路

如果我們不考慮均衡的話，現(xiàn)在有 n 個(gè)服務(wù)節(jié)點(diǎn)，我們完成業(yè)務(wù)流程只需要從這 n 個(gè)中挑出其中的一個(gè)。有幾種思路:

1. 按順序挑: 例如上次選了第一臺(tái)，那么這次就選第二臺(tái)，下次第三臺(tái)，如果已經(jīng)到了最后一臺(tái)，那么下一次從第一臺(tái)開始。這種情況下我們可以把服務(wù)節(jié)點(diǎn)信息都存儲(chǔ)在數(shù)組中，每次請求完成下游之后，將一個(gè)索引后移即可。在移到盡頭時(shí)再移回?cái)?shù)組開頭處。
2. 隨機(jī)挑一個(gè): 每次都隨機(jī)挑，真隨機(jī)偽隨機(jī)均可。假設(shè)選擇第 x 臺(tái)機(jī)器，那么 x 可描述為 ?rand.Intn()%n?。
3. 根據(jù)某種權(quán)重，對(duì)下游節(jié)點(diǎn)進(jìn)行排序，選擇權(quán)重最大或最小的那一個(gè)。

當(dāng)然了，實(shí)際場景我們不可能無腦輪詢或者無腦隨機(jī)，如果對(duì)下游請求失敗了，我們還需要某種機(jī)制來進(jìn)行重試，如果純粹的隨機(jī)算法，存在一定的可能性使你在下一次仍然隨機(jī)到這次的問題節(jié)點(diǎn)。

我們來看一個(gè)生產(chǎn)環(huán)境的負(fù)載均衡案例。

6.5.2 基于洗牌算法的負(fù)載均衡

考慮到我們需要隨機(jī)選取每次發(fā)送請求的節(jié)點(diǎn)，同時(shí)在遇到下游返回錯(cuò)誤時(shí)換其它節(jié)點(diǎn)重試。所以我們設(shè)計(jì)一個(gè)大小和節(jié)點(diǎn)數(shù)組大小一致的索引數(shù)組，每次來新的請求，我們對(duì)索引數(shù)組做洗牌，然后取第一個(gè)元素作為選中的服務(wù)節(jié)點(diǎn)，如果請求失敗，那么選擇下一個(gè)節(jié)點(diǎ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",
}

// 重點(diǎn)在這個(gè) 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 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[idx])
        if err == nil {
            break
        }
        idx++
    }

    if err != nil {
        // logging
        return err
    }

    return nil
}

我們循環(huán)一遍 slice，兩兩交換，這個(gè)和我們平常打牌時(shí)常用的洗牌方法類似?？雌饋頉]有什么問題。

6.5.2.1 錯(cuò)誤的洗牌導(dǎo)致的負(fù)載不均衡

真的沒有問題么？還是有問題的。這段簡短的程序里有兩個(gè)隱藏的隱患:

1. 沒有隨機(jī)種子。在沒有隨機(jī)種子的情況下，?rand.Intn()? 返回的偽隨機(jī)數(shù)序列是固定的。
2. 洗牌不均勻，會(huì)導(dǎo)致整個(gè)數(shù)組第一個(gè)節(jié)點(diǎn)有大概率被選中，并且多個(gè)節(jié)點(diǎn)的負(fù)載分布不均衡。

第一點(diǎn)比較簡單，應(yīng)該不用在這里給出證明了。關(guān)于第二點(diǎn)，我們可以用概率知識(shí)來簡單證明一下。假設(shè)每次挑選都是真隨機(jī)，我們假設(shè)第一個(gè)位置的節(jié)點(diǎn)在 len(slice) 次交換中都不被選中的概率是 ((6/7)*(6/7))^7≈0.34。而分布均勻的情況下，我們肯定希望被第一個(gè)元素在任意位置上分布的概率均等，所以其被隨機(jī)選到的概率應(yīng)該約等于 1/7≈0.14。

顯然，這里給出的洗牌算法對(duì)于任意位置的元素來說，有 30% 的概率不對(duì)其進(jìn)行交換操作。所以所有元素都傾向于留在原來的位置。因?yàn)槲覀兠看螌?duì) shuffle 數(shù)組輸入的都是同一個(gè)序列，所以第一個(gè)元素有更大的概率會(huì)被選中。在負(fù)載均衡的場景下，也就意味著節(jié)點(diǎn)數(shù)組中的第一臺(tái)機(jī)器負(fù)載會(huì)比其它機(jī)器高不少 (這里至少是 3 倍以上)。

6.5.2.2 修正洗牌算法

從數(shù)學(xué)上得到過證明的還是經(jīng)典的 fisher-yates 算法，主要思路為每次隨機(jī)挑選一個(gè)值，放在數(shù)組末尾。然后在 n-1 個(gè)元素的數(shù)組中再隨機(jī)挑選一個(gè)值，放在數(shù)組末尾，以此類推。

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

在 Go 的標(biāo)準(zhǔn)庫中已經(jīng)為我們內(nèi)置了該算法:

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

在當(dāng)前的場景下，我們只要用 rand.Perm 就可以得到我們想要的索引數(shù)組了。

6.5.3 ZooKeeper 集群的隨機(jī)節(jié)點(diǎn)挑選問題

本節(jié)中的場景是從 N 個(gè)節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)發(fā)送請求，初始請求結(jié)束之后，后續(xù)的請求會(huì)重新對(duì)數(shù)組洗牌，所以每兩個(gè)請求之間沒有什么關(guān)聯(lián)關(guān)系。因此我們上面的洗牌算法，理論上不初始化隨機(jī)庫的種子也是不會(huì)出什么問題的。

但在一些特殊的場景下，例如使用 ZooKeeper 時(shí)，客戶端初始化從多個(gè)服務(wù)節(jié)點(diǎn)中挑選一個(gè)節(jié)點(diǎn)后，是會(huì)向該節(jié)點(diǎn)建立長連接的。之后客戶端請求都會(huì)發(fā)往該節(jié)點(diǎn)去。直到該節(jié)點(diǎn)不可用，才會(huì)在節(jié)點(diǎn)列表中挑選下一個(gè)節(jié)點(diǎn)。在這種場景下，我們的初始連接節(jié)點(diǎn)選擇就要求必須是 “真” 隨機(jī)了。否則，所有客戶端起動(dòng)時(shí)，都會(huì)去連接同一個(gè) ZooKeeper 的實(shí)例，根本無法起到負(fù)載均衡的目的。如果在日常開發(fā)中，你的業(yè)務(wù)也是類似的場景，也務(wù)必考慮一下是否會(huì)發(fā)生類似的情況。為 rand 庫設(shè)置種子的方法:

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

之所以會(huì)有上面這些結(jié)論，是因?yàn)槟硞€(gè)使用較廣泛的開源 ZooKeeper 庫的早期版本就犯了上述錯(cuò)誤，直到 2016 年早些時(shí)候，這個(gè)問題才被修正。

6.5.4 負(fù)載均衡算法效果驗(yàn)證

我們這里不考慮加權(quán)負(fù)載均衡的情況，既然名字是負(fù)載 “均衡”。那么最重要的就是均衡。我們把開篇中的 shuffle 算法，和之后的 fisher yates 算法的結(jié)果進(jìn)行簡單地對(duì)比：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

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

輸出：

map[0:224436 1:128780 5:129310 6:129194 2:129643 3:129384 4:129253]
map[6:143275 5:143054 3:143584 2:143031 1:141898 0:142631 4:142527]