架构师训练营 - 作业 5

关注
发布于: 2020 年 07 月 09 日
C# 一致性Hash算法
﻿
1. FNV算法https://www.cnblogs.com/guodf/p/9677959.html
如下是引用FNV标准算法公式，引用博客园的文章。
FNV-1算法公式
hash = FNV_offset_basis
   for each byte_of_data to be hashed
   		hash = hash * FNV_prime
   		hash = hash ^ byte_of_data
return hash
﻿
FNV-1a算法公式
hash = FNV_offset_basis
   for each byte_of_data to be hashed
   		hash = hash ^ byte_of_data
   		hash = hash * FNV_prime
return hash
﻿为什么选FNV作为一致性算法，而不是 MD5，SHA 算法呢？如下是3中算法的结果大小比较
﻿
如图可以看出，FNV结果最小，但是对一般用于分布式缓存的一致性hash算法来说，是够的。
而且较小的大小，有利于更快速定位节点。
﻿
2. 一致性Hash算法测试100W数据的，10个服务器节点下，数据的分布标准差
这里使用的是32位算法
声明有序的虚拟节点链表virtualNodes，并在构造函数中将服务器节点倍化成VIRTUALNODE_CARDINALITY 倍
声明一个计算key 应该所在节点的函数
FNV算法
MD5算法是为了更好的计算key的 FNV Hash值
因为测试100w数据时直接将变量 i 进行 FNV hash 计算，导致分布不均太验证，想了个双重hash方案
﻿
		public class ConsistentHashing
    {
        private const uint VIRTUALNODE_CARDINALITY = 256;
        private const uint FNV_PRIME = 16777619;
        private const ulong FNV_OFFSET_BASIS = 2166136261L;
        private SortedList<ulong, string> virtualNodes = new SortedList<ulong, string>();
        public ConsistentHashing(List<string> physicalNodes, uint cardinality = VIRTUALNODE_CARDINALITY)
        {
            foreach (var physicalNode in physicalNodes)
            {
                for (int i = 0; i < cardinality; i++)
                {
                    ulong hash = FNVHash(MD5Hash($"{physicalNode}#{i}"));
                    virtualNodes[hash] = physicalNode;
                }
            }
        }
        public string CalcualteObjectNode(string key)
        {
            var hash = FNVHash(MD5Hash(key));
            var nearestNode = virtualNodes.Where(x => x.Key > hash);
            if (nearestNode == null || nearestNode.Count() == 0)
                return virtualNodes.FirstOrDefault().Value;
            return nearestNode.FirstOrDefault().Value;
        }
        private ulong FNVHash(byte[] array)
        {
            var hash = FNV_OFFSET_BASIS;
            for (int i = 0; i < array.Length; i++)
            {
                hash *= FNV_PRIME;
                hash ^= array[i];
            }
            return hash;
        }
        private byte[] MD5Hash(string key)
        {
            MD5 md5 = new MD5CryptoServiceProvider();
            byte[] bytes = md5.ComputeHash(Encoding.UTF8.GetBytes(key));
            md5.Clear();
            return bytes;
        }
    }
﻿
		static void Main(string[] args)
    {
      Console.WriteLine($"Consistent Hashing Demo");
      List<string> physicalNodes = new List<string>
      {
        "192.168.1.1",
        "192.168.1.2",
        "192.168.1.3",
        "192.168.1.4",
        "192.168.1.5",
        "192.168.1.6",
        "192.168.1.7",
        "192.168.1.8",
        "192.168.1.9",
        "192.168.1.10"
        };
      ConsistentHashing consistentHashing = new ConsistentHashing(physicalNodes);
      Dictionary<string, int> rateDic = GetRateDic(physicalNodes);
      int loopCount = 1000_000;
      Parallel.For(0, loopCount, i =>
                   {
                     Console.WriteLine($"current number：{i}");
                     //KeyValuePair<int, int> temp = new KeyValuePair<int, int>(i, i);
                     var node = consistentHashing.CalcualteObjectNode(i.ToString());
                     if (!string.IsNullOrEmpty(node))
                       rateDic[node] += 1;
                   });
      foreach (var rate in rateDic)
      {
        double percent = (rate.Value * 100.00 / loopCount);
        Console.WriteLine($"IP={rate.Key},Rate={percent.ToString("0.00")}%");
      }
    }
    private static Dictionary<string, int> GetRateDic(List<string> physicalNodes)
    {
      Dictionary<string, int> rateDic = new Dictionary<string, int>();
      foreach (var node in physicalNodes)
      {
        rateDic.TryAdd(node, 0);
      }
      return rateDic;
    }
﻿
结果标准差还算均匀。
﻿
发布于: 2020 年 07 月 09 日阅读数: 56
紫极

关注
还未添加个人签名 2018.08.28 加入
还未添加个人简介
发布
暂无评论
创作场景

架构师训练营 - 作业 5

1. FNV算法

FNV-1算法公式

FNV-1a算法公式

﻿

为什么选FNV作为一致性算法，而不是 MD5，SHA 算法呢？

2. 一致性Hash算法

紫极

评论
