在分布式系統(tǒng)中相同的服務(wù)常常會(huì)部署很多臺(tái)，每一臺(tái)被稱為一個(gè)服務(wù)節(jié)點(diǎn)（實(shí)例）。通過一些負(fù)載均衡策略將服務(wù)請求均勻地分布到各個(gè)節(jié)點(diǎn)，以實(shí)現(xiàn)整個(gè)系統(tǒng)支撐海量請求的需求。本文描述一些簡單的負(fù)載均衡策略。
Round-robin
簡單地輪詢。記錄一個(gè)選擇位置，每次請求來時(shí)調(diào)整該位置到下一個(gè)節(jié)點(diǎn)：
curId = ++curId % nodeCnt
隨機(jī)選擇
隨機(jī)地在所有節(jié)點(diǎn)中選擇：
id = random(nodeCnt);
本機(jī)優(yōu)先
訪問后臺(tái)服務(wù)的訪問者可能本身是一個(gè)整合服務(wù)，或者是一個(gè)proxy，如果后臺(tái)服務(wù)節(jié)點(diǎn)恰好有節(jié)點(diǎn)部署在本機(jī)的，則可以優(yōu)先使用。在未找到本機(jī)節(jié)點(diǎn)時(shí)則可以繼續(xù)走Round-robin策略：
if (node->ip() == local_ip) {
return node;
} else {
return roundRobin();
}
一旦遍歷到本機(jī)節(jié)點(diǎn)，則后面的請求會(huì)一直落到本機(jī)節(jié)點(diǎn)。所以這里可以加上一些權(quán)重機(jī)制，僅是保證本機(jī)節(jié)點(diǎn)會(huì)被優(yōu)先選擇，但不會(huì)被一直選擇。例如：
// initial
cur_weight = 100;
...
// select node
cur_weight -= 5;
if (cur_weight <= 0)
cur_weight = 100;
if (cur_weight > 50 && node->ip() == local_ip) {
return node;
} else {
return roundRobin();
}
本機(jī)房優(yōu)先
服務(wù)節(jié)點(diǎn)可能會(huì)被部署到多個(gè)機(jī)房，有時(shí)候確實(shí)是需要考慮跨機(jī)房服務(wù)。同本機(jī)優(yōu)先策略類似，本機(jī)房優(yōu)先則是優(yōu)先考慮位于相同機(jī)房內(nèi)的服務(wù)節(jié)點(diǎn)。該請求是從哪個(gè)機(jī)房中的前端服務(wù)發(fā)送過來的，則需要前端在請求參數(shù)中攜帶上機(jī)房ID。
在服務(wù)節(jié)點(diǎn)對應(yīng)的數(shù)據(jù)結(jié)構(gòu)中，也最好按照機(jī)房來組織。
本機(jī)房優(yōu)先策略實(shí)際上會(huì)作為節(jié)點(diǎn)選擇的第一道工序，它可以把非本機(jī)房的節(jié)點(diǎn)先過濾掉，然后再傳入后面的各種節(jié)點(diǎn)選擇策略。這里還可以考慮節(jié)點(diǎn)數(shù)參數(shù)，如果本機(jī)房的節(jié)點(diǎn)過少，則可以不使用該策略，避免流量嚴(yán)重不均。
Weighted Round-Robin
加權(quán)輪詢。相對于普通輪詢而言，該策略中每一個(gè)節(jié)點(diǎn)都有自己的權(quán)重，優(yōu)先選擇權(quán)重更大的節(jié)點(diǎn)。權(quán)重可以根據(jù)機(jī)器性能預(yù)先配置。摘抄一下網(wǎng)上的算法：
假設(shè)有一組服務(wù)器S = {S0, S1, …, Sn-1}，W(Si)表示服務(wù)器Si的權(quán)值，一個(gè)
指示變量i表示上一次選擇的服務(wù)器，指示變量cw表示當(dāng)前調(diào)度的權(quán)值，max(S)
表示集合S中所有服務(wù)器的最大權(quán)值，gcd(S)表示集合S中所有服務(wù)器權(quán)值的最大
公約數(shù)。變量i初始化為-1，cw初始化為零。
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;
}
遍歷完所有節(jié)點(diǎn)后權(quán)重衰減，衰減到0后重新開始。這樣可以讓權(quán)重更大的節(jié)點(diǎn)被選擇得更多。
Consistent Hash
一致性哈希。一致性哈希用于在分布式環(huán)境中，分布在各個(gè)節(jié)點(diǎn)上的請求，不會(huì)因?yàn)樾略龉?jié)點(diǎn)（擴(kuò)容）或減少節(jié)點(diǎn)（節(jié)點(diǎn)宕機(jī)）而變化。如果每個(gè)服務(wù)節(jié)點(diǎn)上都有自己的緩存，其保存了該節(jié)點(diǎn)響應(yīng)請求時(shí)的回應(yīng)。正常情況下，這些緩存都可以很好地被運(yùn)用，也即cache命中率較高。
如果某個(gè)節(jié)點(diǎn)不可用了，我們的選擇策略又是基于所有節(jié)點(diǎn)的公平選擇，那么原來一直分配在節(jié)點(diǎn)A上請求就很可能被分配到節(jié)點(diǎn)B上，從而導(dǎo)致節(jié)點(diǎn)A上的緩存較難被命中。這個(gè)時(shí)候就可以運(yùn)用一致性哈希來解決。
其基本思想是，在節(jié)點(diǎn)選擇區(qū)間內(nèi)，在找節(jié)點(diǎn)時(shí)以順時(shí)針方向找到不小于該請求對應(yīng)的哈希值的節(jié)點(diǎn)。在這個(gè)區(qū)間里增加很多虛擬節(jié)點(diǎn)，每一個(gè)虛擬節(jié)點(diǎn)相當(dāng)于一個(gè)物理節(jié)點(diǎn)的引用，這樣相當(dāng)于把物理節(jié)點(diǎn)變成了一個(gè)哈希值區(qū)間。這個(gè)哈希值區(qū)間不會(huì)因?yàn)樵黾庸?jié)點(diǎn)和減少節(jié)點(diǎn)而變化，那么對某個(gè)請求而言，它就會(huì)始終落到這個(gè)區(qū)間里，也就會(huì)始終被分配到原來的節(jié)點(diǎn)。
至于這個(gè)不可用的節(jié)點(diǎn)，其上的請求也會(huì)被均勻地分配到其他節(jié)點(diǎn)中。
摘抄網(wǎng)上的一段代碼：
// 添加一個(gè)物理節(jié)點(diǎn)時(shí)，會(huì)隨之增加很多虛擬節(jié)點(diǎn)
template <class Node, class Data, class Hash>
size_t HashRing<Node, Data, Hash>::AddNode(const Node& node)
{
size_t hash;
std::string nodestr = Stringify(node);
for (unsigned int r = 0; r < replicas_; r++) {
hash = hash_((nodestr + Stringify(r)).c_str());
ring_[hash] = node; // 物理節(jié)點(diǎn)和虛擬節(jié)點(diǎn)都保存在一個(gè)std::map中
}
return hash;
}
// 選擇data對應(yīng)的節(jié)點(diǎn)，data可以是請求
template <class Node, class Data, class Hash>
const Node& HashRing<Node, Data, Hash>::GetNode(const Data& data) const
{
if (ring_.empty()) {
throw EmptyRingException();
}
size_t hash = hash_(Stringify(data).c_str()); // 對請求進(jìn)行哈希
typename NodeMap::const_iterator it;
// Look for the first node >= hash
it = ring_.lower_bound(hash); // 找到第一個(gè)不小于請求哈希的節(jié)點(diǎn)
if (it == ring_.end()) {
// Wrapped around; get the first node
it = ring_.begin();
}
return it->second;
}
參考一致性 hash 算法(consistent hashing)，Consistent Hash Ring