架构师训练营第 5 周课后练习

关注
发布于: 2020 年 11 月 22 日
一致性Hash实现类：
namespace Geektime.ConsistentHashing
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    public class LoadBalancer
    {
        private readonly int vNodes;
        private readonly int suffixLength;
        private readonly SortedDictionary<int, string> hashRing;
        public LoadBalancer(int vNodes = 1)
        {
            this.vNodes = vNodes;
            this.suffixLength = (int)Math.Log10(vNodes) + 1;
            this.hashRing = new SortedDictionary<int, string>();
        }
        public void AddServer(string name)
        {
            for (var i = 0; i < vNodes; i++)
            {
                var nodeName = name + i.ToString($"D{suffixLength}");
                this.hashRing.Add(nodeName.GetHashCode(), name);
            }
        }
        public void RemoveServer(string name)
        {
            for (var i = 0; i < vNodes; i++)
            {
                var nodeName = name + i.ToString($"D{suffixLength}");
                this.hashRing.Remove(nodeName.GetHashCode());
            }
        }
        
        public string GetServer(string key)
        {
            var hash = key.GetHashCode();
            foreach (var kv in this.hashRing)
            {
                if (hash < kv.Key)
                {
                    return kv.Value;
                }
            }
            return hashRing.First().Value;
        }
    }
}
﻿
测试类实现 - 测试数据的Key选择是长度是30以内的随机字符串
namespace Geektime.ConsistentHashing
{
    using System;
    using System.Collections.Generic;
    using System.Diagnostics;
    using System.Linq;
    public class LoadBalancerTest
    {
        public void TestWithVNodes(int vNodes)
        {
            var lb = GetLoadBalancer(10, vNodes);
            var stats = new SortedDictionary<string, int>();
            var random = new Random();
            var randomKey = new RandomStringGenerator();
            Console.WriteLine("--------------------------------------------------");
            Console.WriteLine($"Testing Consistent Hashing with {vNodes} vNodes");
            var watch = new Stopwatch();
            watch.Start();
            for (var i = 0; i < 1_000_000; i++)
            {
                var key = randomKey.GetNext(random.Next(30));
                var serverNode = lb.GetServer(key);
                if (stats.ContainsKey(serverNode))
                {
                    stats[serverNode]++;
                }
                else
                {
                    stats[serverNode] = 1;
                }
            }
            watch.Stop();
            PrintStats(stats);
            Console.WriteLine($"Test completed in {watch.ElapsedMilliseconds} ms");
        }
        protected LoadBalancer GetLoadBalancer(int servers, int vNodes)
        {
            var lb = new LoadBalancer(vNodes);
            for (var i = 0; i < servers; i++)
            {
                lb.AddServer($"S{i}");
            }
            return lb;
        }
        protected void PrintStats(SortedDictionary<string, int> stats)
        {
            var counts = stats.Select(t => t.Value);
            var count = counts.Count();
            var avg = counts.Average();
            var sum = counts.Sum();
            var sumOfDeviation = counts.Select(t => (t - avg) * (t - avg)).Sum();
            var std = (int)Math.Sqrt(sumOfDeviation / count);
            Console.WriteLine($"Sum: {sum}\tStd: {std}");
        }
    }
  
    public class RandomStringGenerator
    {
        private readonly string allowedChars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        public string GetNext(int length)
        {
            if (length <= 0)
            {
                length = 1;
            }    
            var stringChars = new char[length];
            var random = new Random();
            for (int i = 0; i < length; i++)
            {
                stringChars[i] = allowedChars[random.Next(allowedChars.Length)];
            }
            return new string(stringChars);
        }
    }
}
﻿
测试入口
namespace Geektime.ConsistentHashing
{
    class Program
    {
        static void Main(string[] args)
        {
            var test = new LoadBalancerTest();
            test.TestWithVNodes(1);
            test.TestWithVNodes(10);
            test.TestWithVNodes(50);
            test.TestWithVNodes(100);
            test.TestWithVNodes(150);
            test.TestWithVNodes(200);
            test.TestWithVNodes(250);
        }
    }
}
﻿
测试结果：
虚拟节点达到150时，缓存数量标准差下降到比较低的水平。
目前查找Key存储服务器的算法是顺序查找，时间复杂度跟虚拟节点的总数目成线性关系。
--------------------------------------------------
Testing Consistent Hashing with 1 vNodes
Sum: 1000000    Std: 92495
Test completed in 4916 ms
--------------------------------------------------
Testing Consistent Hashing with 10 vNodes
Sum: 1000000    Std: 43158
Test completed in 5781 ms
--------------------------------------------------
Testing Consistent Hashing with 50 vNodes
Sum: 1000000    Std: 18716
Test completed in 14041 ms
--------------------------------------------------
Testing Consistent Hashing with 100 vNodes
Sum: 1000000    Std: 8198
Test completed in 24597 ms
--------------------------------------------------
Testing Consistent Hashing with 150 vNodes
Sum: 1000000    Std: 5999
Test completed in 34978 ms
--------------------------------------------------
Testing Consistent Hashing with 200 vNodes
Sum: 1000000    Std: 6641
Test completed in 47038 ms
--------------------------------------------------
Testing Consistent Hashing with 250 vNodes
Sum: 1000000    Std: 4532
Test completed in 55796 ms
﻿