05 周作业—技术选型

public class ConsistentHash<T> where T : class
{
    private readonly IHash _hashFunc;
    private readonly SortedDictionary<uint, T> _hashRing;
    private uint[] _sortedKeys = null;
    private readonly int _numberOfReplicas;
    public ConsistentHash(IHash hashFunc, int numberOfReplicas, List<T> nodes)
    {
        this._hashFunc = hashFunc;
        this._numberOfReplicas = numberOfReplicas;
        this._hashRing = new SortedDictionary<uint, T>();
        if (nodes != null)
        {
            foreach (var s in nodes)
            {
                this.AddToRing(s, false);
            }
            this._sortedKeys = this._hashRing.Keys.ToArray();
        }
    }
    public void AddToRing(T node, bool updateKeys = true)
    {
        for (int i = 0; i < _numberOfReplicas; i++)
        {
            uint hash = this._hashFunc.ToHash32(CombineId(node.ToString(), i));
            this._hashRing.Add(hash, node);
        }
        if (updateKeys)
        {
            this._sortedKeys = this._hashRing.Keys.ToArray();
        }
    }
    public void RemoveFromRing(T node)
    {
        for (int i = 0; i < _numberOfReplicas; i++)
        {
            uint hash = this._hashFunc.ToHash32(CombineId(node.ToString(), i));
            this._hashRing.Remove(hash);
        }
        this._sortedKeys = this._hashRing.Keys.ToArray();
    }
    public T GetNode(String key)
    {
        if (this._hashRing.Count == 0)
        {
            return null;
        }
        uint hash = this._hashFunc.ToHash32(key);
        // too slow ...
        // if (!this._hashRing.ContainsKey(hash))
        // {
        //     var tail = this._hashRing.Keys.FirstOrDefault(x => x >= hash);
        //     hash = tail == 0 ? this._hashRing.Keys.First() : tail;
        // }
        // switch to bisect
        uint first = BisectLeft(this._sortedKeys, hash);
        return this._hashRing[this._sortedKeys[first]];
    }
    //...
}

public interface IHash
{
    public uint ToHash32(string toHash);
}
public class MD5Hash : IHash
{
    public uint ToHash32(string toHash)
    {
        // ...
    }
    public override string ToString()
    {
        return "MD5";
    }
}
public class MurmurHash3 : IHash
{
    // ...
}
public class FNVHash : IHash
{
    // ...
}

class Program
{
    const int ItemCount = 100_0000;
    const int NumberOfNodes = 10;
    const int NumberOfReplicas = 200;
    static void Main(string[] args)
    {
        var nodes = new List<Node>();
        for (int i = 1; i <= NumberOfNodes; i++)
        {
            nodes.Add(new Node($"10.1.1.{i}"));
        }
        var serverCluster = new ConsistentHash<Node>(new MurmurHash3(4049661204), NumberOfReplicas, nodes);
        TestAddOrRemove(serverCluster);
        Statistics(nodes, serverCluster);
    }
    
    private static void TestAddOrRemove(ConsistentHash<Node> cluster)
    {
        var keys = new[] { "66778899", "hello world", "consistent hashing" };
        cluster.FindNode(keys);
        var newNode = new Node($"10.1.1.{NumberOfNodes + 1}");
        cluster.AddToRing(newNode);
        Console.WriteLine($"\nAfter added a new Node [{newNode}]:\n--------------------");
        cluster.FindNode(keys);
        cluster.RemoveFromRing(newNode);
        Console.WriteLine($"\nAfter removed a Node [{newNode}]:\n--------------------");
        cluster.FindNode(keys);
    }
    private static void Statistics(IList<Node> nodes, ConsistentHash<Node> cluster)
    {
        var statDict = new Dictionary<String, int>();
        foreach (var n in nodes)
        {
            statDict.Add(n.IP, 0);
        }
        for (int i = 0; i < ItemCount; i++)
        {
            var node = cluster.GetNode($"key_{i}");
            statDict[node.IP] += 1;
        }
        var mean = statDict.Values.Average();
        var std = statDict.Values.StdDev();
        Console.WriteLine(@$"
Algorithm Statistics:
{cluster.ToString()}
--------------------
Total: {ItemCount:N0}
Mean: {mean:N0}
StdDev: {std:F2}
");
        foreach (var (k, v) in statDict)
        {
            Console.WriteLine("Node [{0}]: {1}", k, v);
        }
    }
    //...
}