平滑的加權(quán)輪詢算法怎么實(shí)現(xiàn)

這篇文章給大家分享的是有關(guān)平滑的加權(quán)輪詢算法怎么實(shí)現(xiàn)的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

輪詢算法

在討論如何實(shí)現(xiàn)負(fù)載均衡時(shí),我們很容易就能甩出一大堆常見的算法，比如輪詢法，隨機(jī)法，源地址哈希法，最小連接數(shù)法等等。而這里我要總結(jié)的是輪詢法的進(jìn)階版平滑的加權(quán)輪詢算法。

什么叫輪詢

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

• 優(yōu)點(diǎn)：實(shí)現(xiàn)容易,每臺(tái)服務(wù)器請(qǐng)求數(shù)相同(￣□￣｜｜好像也就這一個(gè)優(yōu)點(diǎn)了)

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

什么叫普通的加權(quán)輪詢

基于上面簡(jiǎn)單輪詢所帶來(lái)的問(wèn)題，就有了輪詢的變種加權(quán)輪詢。
所謂的加權(quán)輪詢也就是在配置服務(wù)器列表時(shí)，給每一臺(tái)服務(wù)器配置一個(gè)權(quán)重值。 舉個(gè)例子：現(xiàn)在有3臺(tái)服務(wù)器(A:3)(B:2)(C:1)，數(shù)字分別代表它們的權(quán)重值，數(shù)字越大表示所能承受的壓力越大。將3臺(tái)服務(wù)器的權(quán)重值相加3+2+1=6,也就是說(shuō)現(xiàn)在每6個(gè)請(qǐng)求進(jìn)來(lái)其中會(huì)有3個(gè)分配個(gè)A，2個(gè)分配個(gè)B，剩下的一個(gè)分配給C，依次循環(huán)A-A-A-B-B-C-A-A-A-B-B-C-A.

• 優(yōu)點(diǎn)：根據(jù)權(quán)重，可將性能更優(yōu)越的服務(wù)器分配更多的請(qǐng)求數(shù)

• 缺點(diǎn)：因?yàn)槭前错樞蛞来屋喸儗⒄?qǐng)求分配給服務(wù)器，所以權(quán)重大的服務(wù)器會(huì)在單位時(shí)間內(nèi)分配到權(quán)重比例的請(qǐng)求數(shù)，這并不是一種均勻的分配方法。

平滑的加權(quán)輪詢算法

鑒于普通的加權(quán)輪詢算法存在的問(wèn)題，有了更好的平滑的加權(quán)輪詢算法，在該算法中，對(duì)于權(quán)重情況{3,1,2},會(huì)得到這樣一組結(jié)果{ACABCA}而不再是{AAABCC}. 這方面運(yùn)用的比較成功的一個(gè)開源項(xiàng)目即Nginx中的加權(quán)輪詢算法，

算法說(shuō)明

算法步驟：

• 首先每個(gè)節(jié)點(diǎn)分別有CurrentWeight(當(dāng)前權(quán)重值)，EffectiveWeight(有效權(quán)重值)，Weight(配置權(quán)重值)三個(gè)權(quán)重字段， 其中Weight即用戶配置的權(quán)重值，EffectiveWeight初始為取Weight值，在實(shí)際運(yùn)行中會(huì)根據(jù)服務(wù)器的失敗情況所相應(yīng)的增減，CurrentWeight即當(dāng)前服務(wù)器權(quán)重值，初始取EffectiveWeight值

• 在選擇服務(wù)器節(jié)點(diǎn)時(shí)，每次取CurrentWeight最大的一項(xiàng)，獲取到之后再將該節(jié)點(diǎn)的CurrentWeight值改為(CurrentWeight=CurrentWeight-total)即，當(dāng)前權(quán)重等于當(dāng)前權(quán)重減去總權(quán)重，而總權(quán)重又是所有節(jié)點(diǎn)的有效權(quán)重值相加。 下圖是取自Github Nginx項(xiàng)目提交說(shuō)明：

算法實(shí)現(xiàn)

需要說(shuō)明的是，我這里的代碼是基于Nginx開源實(shí)現(xiàn)而改寫的一個(gè)golang版本的簡(jiǎn)要版，省略了失敗降權(quán)等優(yōu)化操作，寫出平滑加權(quán)輪詢的基本操作。有興趣的同學(xué)也可以直接去看Nginx的源碼，大概位置是ngx_http_upstream_round_robin.c和ngx_http_upstream_round_robin.h這2個(gè)文件

package main

import (
	"log"
)

//Peer 單個(gè)配置節(jié)點(diǎn)
type Peer struct {
	Sockaddr        string //id地址
	CurrentWeight   int    //當(dāng)前權(quán)重
	EffectiveWeight int    //有效權(quán)重
	Weight          int    //配置權(quán)重
}

//Peers 服務(wù)器地址池
type Peers struct {
	number      int     //服務(wù)器數(shù)量
	TotalWeight int     //總權(quán)重
	peer        []*Peer //服務(wù)器節(jié)點(diǎn)數(shù)組
}

//PeerData 解析后的服務(wù)器數(shù)據(jù)
type PeerData struct {
	Peers *Peers //服務(wù)器池?cái)?shù)據(jù)
}

//ServerConfig 模擬配置文件
//配置節(jié)點(diǎn)
type ServerConfig struct {
	Addr   string
	Weight int
}

//InitPeer 節(jié)點(diǎn)初始化
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 獲取一臺(tái)節(jié)點(diǎn)地址
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 //將當(dāng)前權(quán)重與有效權(quán)重相加

		total += peer.EffectiveWeight //累加總權(quán)重

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

	}
	if best == nil {
		return nil
	}
	best.CurrentWeight -= total //將當(dāng)前權(quán)重改為當(dāng)前權(quán)重-總權(quán)重
	return best
}

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

感謝各位的閱讀！關(guān)于“平滑的加權(quán)輪詢算法怎么實(shí)現(xiàn)”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！