柚子快報邀請碼778899分享：學習負載均衡的算法

http://yzkb.51969.com/

什么負載均衡

負載均衡是一種計算機技術，用于在多個系統(tǒng)、網(wǎng)絡鏈接、硬盤驅動器、CPU等之間分配工作負載，以優(yōu)化資源使用、最大化吞吐量、最小化響應時間、并避免任何單一資源的過載。在網(wǎng)絡負載均衡的情況下，它可以幫助將網(wǎng)絡流量有效地分配到多個服務器。 負載均衡可以在硬件、軟件或兩者的組合中實現(xiàn)。它通常使用一種算法，如輪詢、最少連接、IP哈?；蚱渌远x方法，來決定將請求發(fā)送到哪個服務器。 在微服務架構和大規(guī)模并行處理的環(huán)境中，負載均衡尤其重要，因為它可以幫助分散大量的請求，并確保系統(tǒng)的穩(wěn)定性和可靠性。

負載均衡的算法有那些

round-robin （輪詢）random（隨機）ip-hashpower of 2 random choice （兩次隨機策略）consistent hash （一致性hash）consistent hash with bounded （有界一致性hash）least-load（最小連接）Weighted Round Robin（權重輪詢）

round-robin（輪詢）

i的類型是線程安全的，每次請求i就 +1 hosts 是目標服務器中host的slice，可以存儲多個host 每次請求我們的i就會+1然后和host是的長度進行取余來輪詢我們的目標服務器的ip。

random（隨機）

rnd 是個隨機來源 我們在調用該函數(shù)的時候需要先下一個隨機種子

rnd := rand.New(rand.NewSource(time.Now().UnixNano()))

每次我們使用的時候，會根據(jù)hosts長度的大小隨機一個該長度內的數(shù)據(jù)來獲取一個目標服務器的ip。

ip-hash （ip哈希）

我們通過代碼可以看到，傳入進來的client的ip是通過crc32進行了hash計算，算出來一個值以后和hosts的長度進行了取余。 該負責均衡的算法有個好處就是同一個ip的用戶訪問我們的服務會被分配到同一個目標服務器上。

power of 2 random choice （兩次隨機策略）

type host struct {

name string

load uint64

}

// P2C refer to the power of 2 random choice

type P2C struct {

sync.RWMutex

hosts []*host

rnd *rand.Rand

loadMap map[string]*host

}

// NewP2C create new P2C balancer

func NewP2C(hosts []string) Balancer {

p := &P2C{

hosts: []*host{},

loadMap: make(map[string]*host),

rnd: rand.New(rand.NewSource(time.Now().UnixNano())),

}

for _, h := range hosts {

p.Add(h)

}

return p

}

// Add new host to the balancer

func (p *P2C) Add(hostName string) {

p.Lock()

defer p.Unlock()

if _, ok := p.loadMap[hostName]; ok {

return

}

h := &host{name: hostName, load: 0}

p.hosts = append(p.hosts, h)

p.loadMap[hostName] = h

}

// Remove new host from the balancer

func (p *P2C) Remove(host string) {

p.Lock()

defer p.Unlock()

if _, ok := p.loadMap[host]; !ok {

return

}

delete(p.loadMap, host)

for i, h := range p.hosts {

if h.name == host {

p.hosts = append(p.hosts[:i], p.hosts[i+1:]...)

return

}

}

}

// Balance selects a suitable host according to the key value

func (p *P2C) Balance(key string) (string, error) {

p.RLock()

defer p.RUnlock()

if len(p.hosts) == 0 {

return "", NoHostError

}

n1, n2 := p.hash(key)

host := n2

if p.loadMap[n1].load <= p.loadMap[n2].load {

host = n1

}

return host, nil

}

func (p *P2C) hash(key string) (string, string) {

var n1, n2 string

if len(key) > 0 {

saltKey := key + Salt

n1 = p.hosts[crc32.ChecksumIEEE([]byte(key))%uint32(len(p.hosts))].name

n2 = p.hosts[crc32.ChecksumIEEE([]byte(saltKey))%uint32(len(p.hosts))].name

return n1, n2

}

n1 = p.hosts[p.rnd.Intn(len(p.hosts))].name

n2 = p.hosts[p.rnd.Intn(len(p.hosts))].name

return n1, n2

}

// Inc refers to the number of connections to the server `+1`

func (p *P2C) Inc(host string) {

p.Lock()

defer p.Unlock()

h, ok := p.loadMap[host]

if !ok {

return

}

h.load++

}

// Done refers to the number of connections to the server `-1`

func (p *P2C) Done(host string) {

p.Lock()

defer p.Unlock()

h, ok := p.loadMap[host]

if !ok {

return

}

if h.load > 0 {

h.load--

}

}

我們看到（兩次隨機策略）的算法和ip-hash一樣都是使用crc32的hash算法，只不過ip-hash是對key 進行一次hash然后于hosts的長度進行取余，但是（兩次隨機策略）是對同一個key進行兩次hash，一次是用key直接進行hash，另外一次是對key加鹽之后進行hash，這時候就求出來兩個值，然后在hosts里面獲取兩個ip，然后對比他們的連接數(shù)，取最小連接數(shù)。

我們還發(fā)現(xiàn)當我們傳入的key是個空值的時候，（兩次隨機策略）使用的隨機策略。

Inc 方法和Done方法是在我們進行訪問的時候會對連接的ip進行連接數(shù)的加減。

consistent hash （一致性hash）

在學習算法之前我們需要先學習下一致性hash

什么是一致性hash

一致性哈希（Consistent Hashing）是一種特殊的哈希技術，廣泛應用于分布式系統(tǒng)中，用于解決數(shù)據(jù)的分布式存儲問題。

在傳統(tǒng)的哈希表中，如果哈?？臻g的大小發(fā)生變化（例如，增加或減少服務器），幾乎所有的鍵值對都需要重新映射，這會導致大量的數(shù)據(jù)遷移，對系統(tǒng)的性能和穩(wěn)定性產(chǎn)生影響。

一致性哈希通過引入虛擬節(jié)點和環(huán)形哈?？臻g的概念，使得哈?？臻g的大小變化時，只有一小部分的鍵值對需要重新映射。這大大減少了數(shù)據(jù)遷移的數(shù)量，提高了系統(tǒng)的穩(wěn)定性。

一致性hash解決什么問題

一致性哈希（Consistent Hashing）主要解決分布式系統(tǒng)中的數(shù)據(jù)分布和負載均衡問題。

一致性哈希通過創(chuàng)建一個環(huán)形的哈?？臻g，并將節(jié)點和數(shù)據(jù)都映射到這個空間上，使得節(jié)點數(shù)量的變化只會影響哈?？臻g中的一小部分數(shù)據(jù)，大大減少了數(shù)據(jù)重新分配的數(shù)量。這使得一致性哈希非常適合動態(tài)變化的系統(tǒng)。

一致性哈希還可以通過引入虛擬節(jié)點來解決數(shù)據(jù)分布不均的問題。通過為每個節(jié)點創(chuàng)建多個虛擬節(jié)點，可以使得數(shù)據(jù)更均勻地分布在各個節(jié)點上，從而實現(xiàn)更好的負載均衡。

原理

在傳統(tǒng)的哈希表中，如果哈?？臻g的大小發(fā)生變化，幾乎所有的鍵值對都需要重新映射，這會導致大量的數(shù)據(jù)遷移，對系統(tǒng)的性能和穩(wěn)定性產(chǎn)生影響。

但是一致性哈希通過引入虛擬節(jié)點和環(huán)形哈?？臻g的概念，使得哈希空間的大小變化時，只有一小部分的鍵值對需要重新映射。這大大減少了數(shù)據(jù)遷移的數(shù)量，提高了系統(tǒng)的穩(wěn)定性。

一致性hash算法是對232 進行取模運算，是一個固定的值。通過和232 次進行取模運算的結果值組織成一個圓環(huán)。所以，一致性哈希是指將「存儲節(jié)點」和「數(shù)據(jù)」都映射到一個首尾相連的哈希環(huán)上。 在hash 環(huán)上的結果的映射是順時針方向第一個節(jié)點。 如果hash環(huán)上增加了節(jié)點，并不會想傳統(tǒng)hash一樣發(fā)生大量數(shù)據(jù)遷移的情況從而造成（hash洪水），而是只有部分數(shù)據(jù)會發(fā)生遷移。 但是一般的hash環(huán)會有個節(jié)點分布不均勻的問題，這樣會導致如會有大量的數(shù)據(jù)或請求指向同一個節(jié)點上去。 為了解決這個問題我們在hash環(huán)上引入虛擬節(jié)點來均衡實體節(jié)點在hash環(huán)上分布不均勻的問題。 這時候節(jié)點數(shù)量多了以后，節(jié)點在hash環(huán)上的分布就均勻了。 我們看一致性hash負載均衡的類，里面有hash一致性的函數(shù)。

我們在調用一致性hash的add的時候我們看源碼發(fā)現(xiàn)，針對每個host我們會創(chuàng)建10個虛擬的因子來加入到hash環(huán)上。 當我們在發(fā)送請求的時候通過我們client ip去獲取對應的server ip 這里我們需要看下c.hash這個方法

blake2b.Sum512：這一行代碼將key轉換為一個字節(jié)切片，然后使用BLAKE2b哈希算法計算其512位（64字節(jié)）的哈希值。BLAKE2b是一種密碼學哈希函數(shù)，可以生成不同長度的哈希值，這里生成的是512位的哈希值。計算結果被存儲在out中。、binary.LittleEndian.Uint64(out[:])：這一行代碼將out的前8個字節(jié)（64位）解釋為一個小端格式的無符號整數(shù)。

我們在看下search函數(shù)，該函數(shù)使用key計算出來的hash的值和hash環(huán)中的值進行比較，并返回index。 我們通過上面函數(shù)返回的index獲取到hash環(huán)中的對應的hash值，在沖hosts中獲取到對應的服務器ip。

consistent hash with bounded （有界一致性hash）

什么是有界一致性hash

有界一致性哈希（Bounded Load Consistent Hashing）是一致性哈希的一個改進版本，它在一致性哈希的基礎上增加了負載均衡的考慮。

在傳統(tǒng)的一致性哈希中，雖然理論上數(shù)據(jù)會均勻地分布在各個節(jié)點上，但在實際應用中，由于哈希函數(shù)的隨機性，可能會出現(xiàn)某些節(jié)點上數(shù)據(jù)過多，而某些節(jié)點上數(shù)據(jù)過少的情況，這被稱為"哈希傾斜"。

有界一致性哈希通過引入一個負載因子的概念來解決這個問題。每個節(jié)點都有一個負載因子，表示該節(jié)點當前承載的數(shù)據(jù)量。當一個新的數(shù)據(jù)項需要被插入時，它不僅會考慮哈希環(huán)上的位置，還會考慮各個節(jié)點的負載因子，優(yōu)先選擇負載因子較小的節(jié)點。

這樣，有界一致性哈希不僅保持了一致性哈希的優(yōu)點（如高可用性和可擴展性），還提高了系統(tǒng)的負載均衡性，使得數(shù)據(jù)在各個節(jié)點之間的分布更加均勻。

有界一致性hash 其實和一致性的hash的添加方式是一樣的，不一樣是不一樣在獲取和請求的時候，有界一致性hash多了一個對ip負載的統(tǒng)計，不廢話上代碼。

Inc是對我們請求的servic ip進行負載的原子操作+1Done是在我們對service ip 請求結束后的進行負載的原子操作-1

通過ip獲取到服務器的service ip ，接下來我們看看GetLeast hash和search這兩個函數(shù)我們在一致性hash的時候解讀過了，這里我們看看loadOk 這個函數(shù)，這個函數(shù)是來比較每個節(jié)點的平均負載，獲取最小負載的host

通過代碼我們可以看出我們要獲取到負載小于平均負載的host

我們看到代碼中*1.25 為什么這樣作呢，是為了引入一個負載因子，使得每個節(jié)點可以接受稍微超過平均負載的請求。

乘以1.25就是為了給每個節(jié)點提供一些額外的容量，允許其負載稍微超過平均負載，以應對這種情況。這樣可以提高系統(tǒng)的靈活性和魯棒性，使得在節(jié)點的負載稍微超過平均負載時，系統(tǒng)仍能正常工作，而不是立即拒絕新的請求。

least-load（最小連接）

“Least Load” 是一種負載均衡策略，其目標是將新的請求分配給當前負載最小的服務器。這種策略可以幫助確保所有的服務器都能得到充分利用，同時避免某些服務器過載。

該策略使用了斐波那契堆來實現(xiàn)

斐波那契堆（Fibonacci Heap）是一種優(yōu)先隊列數(shù)據(jù)結構，它支持一系列操作，如插入、獲取最小值、合并等，具有很好的理論性能。斐波那契堆在圖算法（如 Dijkstra 和 Prim）中特別有用，因為它可以更有效地處理減少關鍵字的操作。

斐波那契堆的特點是：

它是一組最小堆有序樹的集合，這些樹都滿足斐波那契堆的性質（即，每個節(jié)點的孩子數(shù)大于或等于其父節(jié)點的秩）。它有一個指針指向最小元素。它的所有操作（插入、刪除最小元素、減少關鍵字、合并兩個堆）都有很好的平攤時間復雜度。

我們在使用該策略的時候發(fā)現(xiàn)host讓存入了斐波那契堆里面。該堆里面還記錄了每個host的負載。 我們在每次請求的時候通過client ip 獲取對應的host，但是在請求的時候會堆該host進行負載+1，請求結束以后會進行負載 -1 所以我們在獲取service ip的時候就非常方便的從該堆里面獲取到負載最小的ip，防止我們某個服務器過載。 我們在初始化該策略的時候會將host 通過斐波那契堆的insert存入到該堆的節(jié)點里面。 我們在請求的時候需要堆host進行負載的加減，這兩個函數(shù)是通過遞歸的形式對堆里面的元素進行操作的。

柚子快報邀請碼778899分享：學習負載均衡的算法

http://yzkb.51969.com/

參考文章