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