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