学步园

摘要：

考虑一种情况，一组机器来提供一个服务，客户端要以相同的机会访问各台机器，而且其中一台机器负载过高的时候，要减少对这台服务器的访问，直到它的负载降低下来，而且如果我们添加了一台新的服务器，要把客户端的请求也均衡到这台新机器上。

思路及分析：
说到负载均衡，多半会用到哈希算法，比如说我们有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)