平滑的加權輪詢算法怎么實現

這篇文章給大家分享的是有關平滑的加權輪詢算法怎么實現的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

輪詢算法

在討論如何實現負載均衡時,我們很容易就能甩出一大堆常見的算法，比如輪詢法，隨機法，源地址哈希法，最小連接數法等等。而這里我要總結的是輪詢法的進階版平滑的加權輪詢算法。

什么叫輪詢

基于維基百科的介紹，輪詢(Polling)是一種CPU決策如何提供周邊設備服務的方式，又稱“程控輸入輸出”（Programmed I/O）。輪詢法的概念是：由CPU定時發出詢問，依序詢問每一個周邊設備是否需要其服務，有即給予服務，服務結束后再問下一個周邊，接著不斷周而復始。也就是說在我們的場景中就是給定一組服務器列表，依次的將每一個進來的請求輪流的分配給列表中的每一臺服務器來實現負載均衡。

• 優點：實現容易,每臺服務器請求數相同(￣□￣｜｜好像也就這一個優點了)

• 確定：效率偏低,無法滿足服務器配置不同的情況(說好的能者多勞呢)

什么叫普通的加權輪詢

基于上面簡單輪詢所帶來的問題，就有了輪詢的變種加權輪詢。
所謂的加權輪詢也就是在配置服務器列表時，給每一臺服務器配置一個權重值。 舉個例子：現在有3臺服務器(A:3)(B:2)(C:1)，數字分別代表它們的權重值，數字越大表示所能承受的壓力越大。將3臺服務器的權重值相加3+2+1=6,也就是說現在每6個請求進來其中會有3個分配個A，2個分配個B，剩下的一個分配給C，依次循環A-A-A-B-B-C-A-A-A-B-B-C-A.

• 優點：根據權重，可將性能更優越的服務器分配更多的請求數

• 缺點：因為是按順序依次輪詢將請求分配給服務器，所以權重大的服務器會在單位時間內分配到權重比例的請求數，這并不是一種均勻的分配方法。

平滑的加權輪詢算法

鑒于普通的加權輪詢算法存在的問題，有了更好的平滑的加權輪詢算法，在該算法中，對于權重情況{3,1,2},會得到這樣一組結果{ACABCA}而不再是{AAABCC}. 這方面運用的比較成功的一個開源項目即Nginx中的加權輪詢算法，

算法說明

算法步驟：

• 首先每個節點分別有CurrentWeight(當前權重值)，EffectiveWeight(有效權重值)，Weight(配置權重值)三個權重字段， 其中Weight即用戶配置的權重值，EffectiveWeight初始為取Weight值，在實際運行中會根據服務器的失敗情況所相應的增減，CurrentWeight即當前服務器權重值，初始取EffectiveWeight值

• 在選擇服務器節點時，每次取CurrentWeight最大的一項，獲取到之后再將該節點的CurrentWeight值改為(CurrentWeight=CurrentWeight-total)即，當前權重等于當前權重減去總權重，而總權重又是所有節點的有效權重值相加。 下圖是取自Github Nginx項目提交說明：

算法實現

需要說明的是，我這里的代碼是基于Nginx開源實現而改寫的一個golang版本的簡要版，省略了失敗降權等優化操作，寫出平滑加權輪詢的基本操作。有興趣的同學也可以直接去看Nginx的源碼，大概位置是ngx_http_upstream_round_robin.c和ngx_http_upstream_round_robin.h這2個文件

package main

import (
	"log"
)

//Peer 單個配置節點
type Peer struct {
	Sockaddr        string //id地址
	CurrentWeight   int    //當前權重
	EffectiveWeight int    //有效權重
	Weight          int    //配置權重
}

//Peers 服務器地址池
type Peers struct {
	number      int     //服務器數量
	TotalWeight int     //總權重
	peer        []*Peer //服務器節點數組
}

//PeerData 解析后的服務器數據
type PeerData struct {
	Peers *Peers //服務器池數據
}

//ServerConfig 模擬配置文件
//配置節點
type ServerConfig struct {
	Addr   string
	Weight int
}

//InitPeer 節點初始化
func InitPeer(cf []ServerConfig) *PeerData {
	pd := new(PeerData)
	pd.Peers = new(Peers)
	c := len(cf)
	pd.Peers.number = c
	pd.Peers.peer = make([]*Peer, c, c)
	for i := 0; i < pd.Peers.number; i++ {
		pd.Peers.peer[i] = new(Peer)
		pd.Peers.peer[i].Weight = cf[i].Weight
		pd.Peers.peer[i].Sockaddr = cf[i].Addr
		pd.Peers.peer[i].EffectiveWeight = cf[i].Weight //將EffectiveWeight初始為Weight值
	}
	return pd
}

//GetPeer 獲取一臺節點地址
func GetPeer(rrp *PeerData) *Peer {
	var best *Peer
	total := 0

	for i := 0; i < rrp.Peers.number; i++ {
		peer := rrp.Peers.peer[i]
		peer.CurrentWeight += peer.EffectiveWeight //將當前權重與有效權重相加

		total += peer.EffectiveWeight //累加總權重

		if best == nil || peer.CurrentWeight > best.CurrentWeight {
			best = peer
		}

	}
	if best == nil {
		return nil
	}
	best.CurrentWeight -= total //將當前權重改為當前權重-總權重
	return best
}

func main() {
	//測試數據，模擬服務器配置列表
	testData := []ServerConfig{
		ServerConfig{
			Addr:   "a",
			Weight: 3,
		}, ServerConfig{
			Addr:   "b",
			Weight: 1,
		}, ServerConfig{
			Addr:   "c",
			Weight: 2,
		},
	}
	pd := InitPeer(testData)
	//模擬12次請求進入
	for i := 0; i < 12; i++ {
		p := GetPeer(pd)
		log.Println(p.Sockaddr)
	}
}

感謝各位的閱讀！關于“平滑的加權輪詢算法怎么實現”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！