Golang 負載均衡算法

【導讀】本文介紹了幾種 go 負載均衡算法。

引子

負載均衡被廣泛運用在各種編排系統，微服務網關，Nginx/HAProxy 作爲前置的網站集羣等等場所。在看不到的更多領域，甚至於你所想象不到的，從未注意過的一些場所，負載均衡也以不同的面目在出沒着，例如機械硬盤、硬盤組的讀寫訪問，多核 CPU 的管線分配等等等等。

所以說負載均衡這種技術，以優化資源運用，最大化吞吐率，最小訪問時延，防止過載爲目標，存在着多種呈現方式。

由於負載均衡的基本特性在於調度輸入到不同的計算單元，所以當某個計算單元失敗時，負載均衡器能夠選擇正常工作的單元而避開該失敗單元，當單元恢復正常工作時，負載均衡器也能正確地調度請求到該單元，這樣的透明無感知的故障轉移（failover）特性也往往被與負載平衡同時提及。例如公司的專線有三條，哪一條壞了無所謂，總還有好的線路讓我們能夠出口到雲上去維護，這數條專線實際上就構成了能夠故障轉移的出口束。

在互聯網中，最基礎的服務，DNS 服務具有自動的負載均衡能力，只要你的域名有多個 A 記錄來指示特定 IP 的服務器，那麼這些服務器羣就能夠均勻地獲取到輸入請求並提供服務。

不過 DNS 服務在故障轉移的特性上沒有什麼優勢，所以限制了它可能的高級運用。正因爲如此，我們所做的大型網站集羣，前置部分一定是數臺 nginx 所構成的前置代理器，在做了 DNS 負載均衡之後，仍需要冗餘的再一層負載均衡器，因爲這樣才能將業務服務器羣的變化（上下線）有效地掩蓋起來。

除了採用 nginx/HAProxy 這類老牌的軟件負載均衡工具之外，不差錢的公司也可以選用專用的硬件負載均衡器。

當視線收縮到業務服務器羣上時，K8s 之類的編排軟件主動提供了多種負載均衡形式來暴露它的私有網絡中的節點和服務。

實際上 K8s 可能綜合代價太大（額外的服務器和計算資源需求，額外的運維管理需求等），你們可能裸體就上雲服務器了，無論是自研的服務治理還是採用知名框架例如 micro 或者 kong 之類的，它們也都提供了負載均衡調度能力。

拋開這些微服務架構不提，當你採用了融合到私有 DNS 服務器的 consul 集羣時，這個小型的綜合性 DNS 集羣也能夠提供增強的負載均衡能力，但可能需要一定的架構設計和相應的編碼適配。

上面說了這麼多，都不能掩蓋一個論斷：用軟件實現負載均衡算法始終都有其存在的價值。因爲當你的系統架構具備一定規模和複雜度之後，要求調度能力、要求攤薄請求時延、要求做到分治的 Map-Reduce 時，總之，你常常會需要手擼一小段負載均衡調度器，無論它可能會以怎樣的面目出來。

所以，纔有這組文章。

雖然已經有數不清的關於負載均衡的文章、論文、或者源碼，但仍有這組文章，是因爲它們都不是我的。我的，是我的。So，

基本的負載均衡算法

按照多方面綜合來看，至少有這些最基本的負載均衡算法：

1. 隨機

2. 輪詢

3. 最少連接數

4. hash

5. 帶權重的輪詢

下面依次做一簡單介紹，最後再來綜述一遍。

前置的介紹

我總是喜歡編碼，純粹的編碼。所以首先要介紹一些基本的接口設定：

type Peer interface {
    String() string
}

type Factor interface {
    Factor() string
}

type BalancerLite interface {
    Next(factor Factor) (next Peer, c Constrainable)
}

type Balancer interface {
  BalancerLite
  //...more
}

type FactorComparable interface {
    Factor
    ConstrainedBy(constraints interface{}) (peer Peer, c Constrainable, satisfied bool)
}

type FactorString string

func (s FactorString) Factor() string { return string(s) }

const DummyFactor FactorString = ""

type Constrainable interface {
    CanConstrain(o interface{}) (yes bool)
    Check(o interface{}) (satisfied bool)
    Peer
}

爲了不必陷入設計細節，我提綱挈領地劃重點做介紹：

• Peer 是一個後端節點。

• 負載均衡器 Balancer 持有一組 Peers。

• Factor 是 Balancer 在選取（Next(factor)）一個 Peer 時由調度者所提供的參考對象，Balancer 可能會將其作爲選擇算法工作的因素之一。

• 當你身爲調度者時，想要調用 Next，卻沒有什麼合適的 “因素” 提供的話，就提供 DummyFactor 好了。

• Constrainable 在這組系列文章的最後時分可能會另行介紹，目前將其視而不見就足夠了。

隨機算法 Random

顧名思義，從後端列表中任意挑選一個出來，這就是隨機算法。它最簡單，結合我們的前置提示，請你綜合理解下面的示例：

package main

import (
    "fmt"
    "github.com/hedzr/lb/lbapi"
    mrand "math/rand"
    "sync"
    "sync/atomic"
    "time"
)

type randomS struct {
    peers []lbapi.Peer
    count int64
}

func (s *randomS) Next(factor lbapi.Factor) (next lbapi.Peer, c lbapi.Constraintenable) {
    l := int64(len(s.peers))
    ni := atomic.AddInt64(&s.count, inRange(0, l)) % l
    next = s.peers[ni]
    return
}

func main() {
    lb := &randomS{
        peers: []lbapi.Peer{
            exP("172.16.0.7:3500"), exP("172.16.0.8:3500"), exP("172.16.0.9:3500"),
        },
        count: 0,
    }

    sum := make(map[lbapi.Peer]int)
    for i := 0; i < 300; i++ {
        p, _ := lb.Next(lbapi.DummyFactor)
        sum[p]++
    }

    for k, v := range sum {
        fmt.Printf("%v: %v\n", k, v)
    }
}

var seededRand = mrand.New(mrand.NewSource(time.Now().UnixNano()))
var seedmu sync.Mutex

func inRange(min, max int64) int64 {
    seedmu.Lock()
    defer seedmu.Unlock()
    return seededRand.Int63n(max-min) + min
}

type exP string

func (s exP) String() string { return string(s) }

randomS 實現了一個微型的、簡單的隨機算法的 LB。

儘管我也可以將其簡化到只提供寥寥數行代碼的片段，但是爲了能夠讓它是 live & runnable 的，還是略微添加的 salt，示例由此而有點長，似乎不相干的東西也有一些。

運行結果可能是：

$ go run ./_examples/simple/random/
172.16.0.8:3500: 116
172.16.0.7:3500: 94
172.16.0.9:3500: 90

嗯，隨機數發生器要均勻，數量級應該向 5K，乃至於 100K 的量級去纔有意義。所以這裏的結果並不是均分的，差不多也可以了。

正規化

需要提示的是，正式的 random LB 的代碼要比上面的核心部分還複雜一點點。原因在於我們還需要達成另外兩個設計目標：

1. 線程安全

2. 可嵌套

正因爲 random LB 的關鍵算法只不過區區 3 行：

    l := int64(len(s.peers))
    ni := atomic.AddInt64(&s.count, inRange(0, l)) % l
    next = s.peers[ni]

所以我纔有少少的篇幅來乾脆提供正式版本的代碼，其幾乎完整的片段是這樣：

package random

import (
    "github.com/hedzr/lb/lbapi"
    mrand "math/rand"
    "sync"
    "sync/atomic"
    "time"
)

var seededRand = mrand.New(mrand.NewSource(time.Now().UnixNano()))
var seedmu sync.Mutex

func inRange(min, max int64) int64 {
    seedmu.Lock()
    defer seedmu.Unlock()
    return seededRand.Int63n(max-min) + min
}

// New make a new load-balancer instance with Round-Robin
func New(opts ...lbapi.Opt) lbapi.Balancer {
    return (&randomS{}).init(opts...)
}

type randomS struct {
    peers []lbapi.Peer
    count int64
    rw    sync.RWMutex
}

func (s *randomS) init(opts ...lbapi.Opt) *randomS {
    for _, opt := range opts {
        opt(s)
    }
    return s
}

func (s *randomS) Next(factor lbapi.Factor) (next lbapi.Peer, c lbapi.Constraintenable) {
    next = s.miniNext()
    if fc, ok := factor.(lbapi.FactorComparable); ok {
        next, c, ok = fc.ConstraintBy(next)
    } else if nested, ok := next.(lbapi.BalancerLite); ok {
        next, c = nested.Next(factor)
    }
    return
}

func (s *randomS) miniNext() (next lbapi.Peer) {
    s.rw.RLock()
    defer s.rw.RUnlock()

    l := int64(len(s.peers))
    ni := atomic.AddInt64(&s.count, inRange(0, l)) % l
    next = s.peers[ni]
    return
}

func (s *randomS) Count() int {
    s.rw.RLock()
    defer s.rw.RUnlock()
    return len(s.peers)
}

func (s *randomS) Add(peers ...lbapi.Peer) {
    for _, p := range peers {
        s.AddOne(p)
    }
}

func (s *randomS) AddOne(peer lbapi.Peer) {
    if s.find(peer) {
        return
    }

    s.rw.Lock()
    defer s.rw.Unlock()
    s.peers = append(s.peers, peer)
}

func (s *randomS) find(peer lbapi.Peer) (found bool) {
    s.rw.RLock()
    defer s.rw.RUnlock()
    for _, p := range s.peers {
        if lbapi.DeepEqual(p, peer) {
            return true
        }
    }
    return
}

func (s *randomS) Remove(peer lbapi.Peer) {
    s.rw.Lock()
    defer s.rw.Unlock()
    for i, p := range s.peers {
        if lbapi.DeepEqual(p, peer) {
            s.peers = append(s.peers[0:i], s.peers[i+1:]...)
            return
        }
    }
}

func (s *randomS) Clear() {
    s.rw.Lock()
    defer s.rw.Unlock()
    s.peers = nil
}

對比前後兩者，應該能夠展示出 #%$&#%@ 的代碼竟然有辣麼多，:)

僅此一次，下面都不會有了。

輪詢算法 Round-Robin

你其實可能並不知道 robin 究竟是誰。

它其實是誰都不是，最早它是一個法語詞彙 ruban，意思是絲帶緞帶 Ribbon。但是時間沖刷了一切，後來不知道怎麼滴，就以訛傳訛漸漸演變成 robin 了。

The term round-robin is derived from the French term ruban, meaning “ribbon”. Over a long period of time, the term was corrupted and idiomized to robin.

—— Round-robin tournament

源於循環賽制的 round and ruban，最後也就稱爲了 Round-robin。至於中文版 Wiki 所提到的 round-robin letter，也不妨去看一看。當然，至於是不是愛安門的 Robin，那就是純粹的休閒時間了。

好的，這些根本不重要。重要的是這個輪詢算法就是挨個選擇一個 peer。就是這樣。

所以它的算法核心大體上是這樣子的：

func (s *rrS) miniNext() (next lbapi.Peer) {
    ni := atomic.AddInt64(&s.count, 1)
    ni %= int64(len(s.peers))
    next = s.peers[ni]
    return
}

s.count 會一直增量上去，並不會取模，這樣做的用意在於如果 peers 數組發生了少量的增減變化時，最終發生選擇時可能會更模棱兩可。

對於 Golang 來說，s.count 來到 int64.MaxValue 時繼續加一會自動迴繞到 0。這一特性和多數主流編譯型語言相同，都是 CPU 所提供的基本特性。

最少連接數 Least Connections

如果一個後端服務上的活動都連接數時全部後端中最少的，那麼就選它了。

這個算法不給實例了，因爲很多時候管理活動連接數是個不尋常的內務，麻煩不小，也會消耗額外的資源——這個資源可不是做作加法或者取個模——所以除了像 nginx 之類的專業代理服務器之外實際上用得到它的不多。

只要你的系統能夠很恰當地管理自己的後端的連接數，實作一份 Least Connections LB 沒有什麼算法上的疑難問題。

Hashing 以及 Consistent Hashing

回顧

在早些年，沒有區分微服務和單體應用的那些年，Hash 算法的負載均衡常常被當作神器，因爲 session 保持經常是一個服務無法橫向增長的關鍵因素，而針對用戶的 session-id 的 hash 值進行調度分配時，就能保證同樣 session-id 的來源用戶的 session 總是落到某一確定的後端服務器，從而確保了其 session 總是有效的。

在 Hash 算法被擴展之後，很明顯，可以用 客戶端 IP 值，主機名，url 或者無論什麼你想得到的東西去做 hash 計算，只要得到了 hashCode，就可以應用 Hash 算法了。而像諸如客戶端 IP，客戶端主機名之類的標識由於其相同的 hashCode 的原因，所以對應的後端 peer 也能保持一致，這就是 session 年代 hash 算法顯得重要的原因。

越明年，政通人和，都不用 browser session 方式了，取而代之的是無狀態模型，所以 hash 算法其實有點落寞了。

無狀態模型的本質是在 header 中帶上 token，這個 token 將能夠被展開爲用戶身份登錄後的標識，從而等效於 browser session。說了個半天，無狀態模型，例如 JWT 等，其原始的意圖就是爲了橫向縮放服務器羣。

稍後，1997 年 MIT 的 Karger 發表了所謂一致性 Hashing 的算法論文，其與傳統的 hashCode 計算的關鍵性不同在於，一方面將 hashCode 約束爲一個正整數（int32/uint32/int64 等等），一方面將正整數空間 [0, int.MaxValue] 視爲一個可迴繞的環形，即所謂的 Hash Ring，而待選擇的 peers 均勻地分佈在這個環形上，從而保證了每次選取時能夠充分平滑地選取到每個 peer。

至於選取時的下標值的計算方面是沒有限定的，所以你可以在這個下標值的計算方案上加入可選策略。

在負載均衡領域中的一致性 Hash 算法，又加入了 Replica 因子，它實際上就是在計算 Peer 的 hash 值時爲 peer 的主機名增加一個索引號的後綴，索引號增量 replica 次，這樣就得到了該 peer 的 replica 個副本。這就將原本 n 臺 peers 的規模擴展爲 n x Replica 的規模，有助於進一步提高選取時的平滑度。

代碼實現

所以說了這麼多，其算法核心大致是這樣的：

type Hasher func(data []byte) uint32

// hashS is a impl with ketama consist hash algor
type hashS struct {
    hasher   Hasher // default is crc32.ChecksumIEEE
    replica  int    // default is 32
    hashRing []uint32
    keys     map[uint32]lbapi.Peer
    peers    map[lbapi.Peer]bool
    rw       sync.RWMutex
}

func (s *hashS) Next(factor lbapi.Factor) (next lbapi.Peer, c lbapi.Constraintenable) {
    var hash uint32
    hash = s.hasher([]byte(factor.Factor()))

    ix := sort.Search(len(s.hashRing), func(i int) bool {
        return s.hashRing[i] >= hash
    })

    if ix == len(s.hashRing) {
        ix = 0
    }

    hashValue := s.hashRing[ix]
    if p, ok := s.keys[hashValue]; ok {
        if _, ok = s.peers[p]; ok {
            next = p
        }
    }

    return
}

func (s *hashS) Add(peers ...lbapi.Peer) {
    for _, p := range peers {
        s.peers[p] = true
        for i := 0; i < s.replica; i++ {
            hash := s.hasher(s.peerToBinaryID(p, i))
            s.hashRing = append(s.hashRing, hash)
            s.keys[hash] = p
        }
    }

    sort.Slice(s.hashRing, func(i, j int) bool {
        return s.hashRing[i] < s.hashRing[j]
    })
}

func (s *hashS) peerToBinaryID(p lbapi.Peer, replica int) []byte {
    str := fmt.Sprintf("%v-%05d", p, replica)
    return []byte(str)
}

在 Add 實現中建立了 hashRing 結構，它雖然是環形，但是是以數組和下標取模的方式來達成的。此外，keys 這個 map 解決從 peer 的 hash 值到 peer 的映射關係，今後（在 Next 中）就可以通過從 hashRing 上 pick 出一個 point 之後立即地獲得相應的 peer.

在 Next 中主要是在做 factor 的 hash 值計算，計算的結果在 hashRing 上映射爲一個點 pt，如果不是恰好有一個 peer 被命中的話，就向後掃描離 pt 最近的 peer。

算法思想扼要掃尾

其實不打算寫這一段了，因爲別人家畫的圖真好看啊，講的也透徹。

譬如說這張圖：

FROM Wayne’s Blog - System Design 101 - Consistent Hashing

keynote，流口水啊，我真的打算去學學了。

你要是對這個算法的每一細節都感興趣的話，還可以看看這兩個視頻：

• Consistent Hashing - Georgia Tech - Network Congestion

• A Brief Introduction to Consistent Hashing

前面我們提到了 replica，它是在 hashRing 上創建 peers 的虛擬節點的一種方法，這種思路是爲了儘可能提高 peers 發生變化後導致的不均勻不平滑的選擇結果問題。基本上最早其來自於 libketama，一個 memcached 庫，所以多數情況下同樣的思路被稱作 Ketama Hashing 算法。可以參考 這裏。

帶權重的輪詢算法 Weighted Round-robin

加上權重，是一個很重要的特性。所以在基本的 LB 算法章節我們需要以加權輪詢（wrr）爲例來提到它。

加權輪詢算法，是給每個 peer 增加一個權重，在平均化輪詢的基礎上加上這個權重來作爲調節。

最著名的加權輪詢算法實現要論及 Nginx 和 LVS 了。

Nginx 平滑加權輪詢

Nginx 採用一種依據 total 和各個權重之間的差值來平衡選擇的方法：每次選擇時，都對每個節點的 currentWeight 加上其權重值，然後選擇 currentWeight 最大的那個節點，同時該節點的 currentWeight 在減去其權重值復原到增量前。如此反覆選擇之下，權重大的節點由於增量速度更快而被選中的更多。

這一算法思想可以得到嚴格的數學證明，不過我就不說這一塊了，要點是核心實現：

func (s *wrrS) Next() (best lbapi.Peer) {
    total := 0
    for _, node := range s.peers {
        if node == nil {
            continue
        }

        total += s.mUpdate(node, 0, false)
        if s.mTest(best, node) {
            best = node
        }
    }

    if best != nil {
        s.mUpdate(best, -total, true)
    }
    return
}

func (s *wrrS) mUpdate(node lbapi.Peer, delta int, success bool) (total int) {
    if delta == 0 {
        delta = s.m[node].weight
    }
    s.m[node].current += delta
    return s.m[node].weight
}

func (s *wrrS) mTest(best, node lbapi.Peer) bool {
    return best == nil || s.m[node].current > s.m[best].current
}

上述代碼做了提煉，實際上的代碼還要複雜一些，因爲我們還需要做鎖操作。

LVS 平滑加權輪詢

至於 LVS 的加權輪詢法，核心思想在於採用 gcd（最大公約數）的方式。

/* Supposing that there is a server set S = {S0, S1, …, Sn-1}; W(Si) indicates the weight of Si; i indicates the server selected last time, and i is initialized with -1; cw is the current weight in scheduling, and cw is initialized with zero;  max(S) is the maximum weight of all the servers in S; gcd(S) is the greatest common divisor of all server weights in S;*/
while (true) {
    i = (i + 1) mod n;
    if (i == 0) {
        cw = cw - gcd(S);         if (cw <= 0) {
            cw = max(S);
            if (cw == 0)
            return NULL;
        }
    }     if (W(Si) >= cw)         return Si;
}

你可以這樣來理解它：對於三個節點 A，B，C，權重爲 x,y,z 時，想象有一個數組，其中填充了 x 次 A，y 次 B，z 次 C，然後用輪詢法掃描這個數組，是不是最終的選中比例就滿足權重分配了？

實際上，很多年前，我的第一份 wrr 實現就是這麼弄的，後來遇到權重值很大，然後就很煩惱，直到後來某一天我看到 LVS 算法的介紹，才感嘆真的就是本啊。

小結

上面已經解說了主要的基本 LB 算法。

這幾種基本算法還可以進一步組合演變，例如

• 加權隨機算法

• （請求）來源 Hash

• 目的地 Hash

• 加權最少連接數算法

• 等等

轉自：

hedzr.com/golang/algorithm/go-load-balancer-1/

Go 開發大全

參與維護一個非常全面的 Go 開源技術資源庫。日常分享 Go, 雲原生、k8s、Docker 和微服務方面的技術文章和行業動態。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OGEmSLx4DzlH-uOqGpU4gA