摘要：
考慮一種情況，一組機器來提供一個服務，客戶端要以相同的機會訪問各台機器，而且其中一台機器負載過高的時候，要減少對這台服務器的訪問，直到它的負載降低下來，而且如果我們添加了一台新的服務器，要把客戶端的請求也均衡到這台新機器上。
思路及分析：
說到負載均衡，多半會用到哈希算法，比如說我們有a,b,c三台機器，我們會用一個很大的盒子去放這3台機器，比如這個盒子有10個格子，那我們這三台機器要均勻的放到各個格子裡，如下：
1-a，2-b，3-c，4-a，5-b，6-c，7-a，8-b，9-c，10-a
我們要實現一個相對均勻分布的隨機算法，每次產生一個1-10的隨機數，而且產生了100個隨機數的話，選中a和b和c的幾率接近1:1:1。
如果a機器宕機了，我們要告訴負載均衡服務器，當隨機數落在放a的格子上的時候，我們要用一種過載處理機制選擇b和c裡面的一台沒有過載的機器。
最後，如果我們新添加一台服務器，要重新把所有機器均勻的放在大盒子裡，然後重新啟用分配策略。
實現：
我們寫一個抽象類HashBase，它包含兩個抽象方法，GetRandom用來產生一個隨機數，可以在非抽象類裡實現自己的隨機數產生算法，SelectOtherUnLoadWarningItem用來在某機器負載過高或者宕機的時候把請求到該機的請求路由到別的負載低的機器。
有四個公開方法，作為對外公開的接口GetItem用來獲取一台機器的服務地址，SetLoadWarning用來告訴負載均衡服務器某台服務器過載了，UnsetLoadWarning用來通知負載均衡服務器某台服務器不過載了，ReConfig用來在添加或者摘除一台服務器的時候重新配置哈希策略。
最後我們寫了個SimpleHashImp類來繼承HashBase，我們用Random類來產生隨機數，並且在某台機器負載高的時候把請求隨機路由到另外一台機器上。
代碼實現：
HashBase
using System;
using System.Collections.Generic;
namespace HashTest
{
public abstract class HashBase<T>
{
protected fields#region protected fields
protected int _maxHashItemCount = 0;
protected object _syncRoot = new object();
protected Dictionary<int, T> _dict = null;
protected Dictionary<T, bool> _dictLoadWarning = null;
#endregion
protected abstract methods#region protected abstract methods
protected abstract int GetRandom();
protected abstract T SelectOtherUnLoadWarningItem(T ret);
#endregion
public contructs#region public contructs
public HashBase(int maxHashItemCount, IList<T> items)
{
init(maxHashItemCount, items);
}
#endregion
public virtual methods#region public virtual methods
public virtual void ReConfig(int maxHashItemCount, IList<T> items)
{
init(maxHashItemCount, items);
}
#endregion
protected methods#region protected methods
protected void init(int maxHashItemCount, IList<T> items)
{
lock (_syncRoot)
{
_maxHashItemCount = maxHashItemCount;
_dict = new Dictionary<int, T>(maxHashItemCount);
for (int i = 0; i < _maxHashItemCount; i++)
{
T item = default(T);
for (int j = items.Count; j >= 0; j--)
{
if (i % items.Count == j)
item = items[j];
}
_dict.Add(i, item);
}
_dictLoadWarning = new Dictionary<T, bool>(items.Count);
foreach (T item in items)
_dictLoadWarning.Add(item, false);
}
}
#endregion
public methods#region public methods
public T GetItem()
{
int rdn = GetRandom();
lock (_syncRoot)
{
T ret = _dict[rdn];
if (_dictLoadWarning[ret])
ret = SelectOtherUnLoadWarningItem(ret);
return ret;
}
}
public void SetLoadWarning(T t)
{
lock(_syncRoot) _dictLoadWarning[t] = true;
}
public void UnsetLoadWarning(T t)
{
lock (_syncRoot) _dictLoadWarning[t] = false;
}
#endregion
}
}
SimpleHashImp
using System;
using System.Collections.Generic;
namespace HashTest
{
class SimpleHashImp : HashBase<string>
{
private fields#region private fields
Random _random = null;
#endregion
contructs#region contructs
public SimpleHashImp(int seed, int maxHashItemCount, IList<string> items)
: base(maxHashItemCount, items)
{
_random = new Random(seed);
}
#endregion
overrid methods#region overrid methods
protected override int GetRandom()
{
return _random.Next(_maxHashItemCount);
}
protected override string SelectOtherUnLoadWarningItem(string ret)
{
foreach (KeyValuePair<string, bool> item in _dictLoadWarning)
{
if (!item.Value)
return item.Key;
}
throw new ApplicationException("503");
}
public override void ReConfig(int maxHashItemCount, IList<string> items)
{
base.init(maxHashItemCount, items);
}
#endregion
}
}
測試代碼
using System;
using System.Collections.Generic;
namespace HashTest
{
static class Program
{
/**//// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main()
{
List<string> items = new List<string>();
items.Add("a");
items.Add("b");
items.Add("c");
HashBase<string> hash = new SimpleHashImp(10, 20, items);
for (int i = 0; i < 100; i++)
{
if (i == 10)
{
hash.SetLoadWarning("a");
Console.WriteLine("機器a宕機了。。。");
}
if (i == 20)
{
hash.UnsetLoadWarning("a");
Console.WriteLine("機器a已經恢復運行");
}
Console.WriteLine(hash.GetItem());
if (i == 30)
{
items.Add("d");
hash.ReConfig(100, items);
Console.WriteLine("添加了一台新機器d，並擴大了散列集合");
}
System.Threading.Thread.Sleep(1000);
}
}
}
}
其它分析：
1、負載均衡服務器本身是個單點，如果它本身也要支持流量負載的話，要把它本身的狀態放到數據庫裡。
2、在某台機器宕機的時候把請求路由到其它機器的算法可以寫的更智能一些，目前的時候只是在其它機器裡找一台沒有過載的機器，如果都過載就給客戶端返回503應答，就是所有服務器都忙，不至於讓更多的請求把服務器壓跨，只是讓新的請求進不來。
3、產生隨機數的算法一定要選個比較均勻分布的。
4、由於考慮了可能動態擴容機器，所以代碼裡好多地方加了lock語句，不知道.net裡的lock語句到底支持多大吞吐量，可以換成其它方式來處理擴容，比如用新舊兩套處理策略，舊的一直保持到沒有新的請求過來，新來的請求訪問新的策略，這時候可能短時間內不均衡，但每套策略都運行的很快，沒有鎖。
