C#实现一致性Hash算法及测试

本文是架构师训练营第五周课后作业,作业题是:1、用你熟悉的编程语言实现一致性 Hash 算法;2、编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

由于比较熟悉 C# 编程语言,现使用 C# 实现一致性 Hash 算法。

基础算法类代码

namespace KetamaHash 
{ 
   internal class HashAlgorithm 
   { 
       public static long ash(byte[] digest, int nTime) 
       { 
           long rv = ((long)(digest[3 + nTime * 4] & 0xFF) << 24) 
                   | ((long)(digest[2 + nTime * 4] & 0xFF) << 16) 
                   | ((long)(digest[1 + nTime * 4] & 0xFF) << 8) 
                   | ((long)digest[0 + nTime * 4] & 0xFF); 
           return rv & 0xffffffffL; // Truncate to 32-bits 
       } 
       /// <summary> 
       /// Get the md5 of the given key. 
       /// </summary> 
       /// <param name="k"></param> 
       /// <returns></returns> 
       public static byte[] ComputeMd5(string k) 
       { 
           MD5 md5 = new MD5CryptoServiceProvider(); 
           byte[] keyBytes = md5.ComputeHash(Encoding.UTF8.GetBytes(k)); 
           md5.Clear(); 
           return keyBytes; 
       } 
   } 
}

节点功能类代码

namespace KetamaHash 
{ 
   public class KetamaNodeLocator 
   { 
       private SortedList<long, string> ketamaNodes = new SortedList<long, string>(); 
       /// <summary> 
       /// 一致性哈希的实现 
       /// </summary> 
       /// <param name="nodes">实际节点</param> 
       /// <param name="nodeCopies">虚拟节点的个数</param> 
       public KetamaNodeLocator(List<string> nodes, int nodeCopies) 
       { 
           //对所有节点,生成nCopies个虚拟结点 
           foreach (string node in nodes) 
           { 
               //每四个虚拟结点为一组 
               for (int i = 0; i < nodeCopies / 4; i++) 
               { 
                   //getKeyForNode方法为这组虚拟结点得到惟一名称  
                   byte[] digest = HashAlgorithm.ComputeMd5(node + i); 
                   //Md5是一个16字节长度的数组,将16字节的数组每四个字节一组,分别对应一个虚拟结点,这就是为什么上面把虚拟结点四个划分一组的原因  
                   for (int h = 0; h < 4; h++) 
                   { 
                       long m = HashAlgorithm.Hash(digest, h); 
                       ketamaNodes[m] = node; 
                   } 
               } 
           } 
       } 
       /// <summary> 
       /// 一致性哈希的实现 
       /// </summary> 
       /// <param name="nodes">实际节点</param> 
       public KetamaNodeLocator(List<string> nodes): this(nodes, 10) 
       { 
       } 
       /// <summary> 
       /// 查找Key值所在的节点 
       /// </summary> 
       /// <param name="key"></param> 
       /// <returns></returns> 
       public string GetNode(string key) 
       { 
           byte[] digest = HashAlgorithm.ComputeMd5(key); 
           string rv = GetNodeForKey(HashAlgorithm.Hash(digest, 0)); 
           return rv; 
       } 
       /// <summary> 
       /// 通过Key值获取节点 
       /// </summary> 
       /// <param name="hash"></param> 
       private string GetNodeForKey(long hash) 
       { 
           string rv; 
           long key = hash; 
           //如果找到这个节点,直接取节点,返回    
           if (!ketamaNodes.ContainsKey(key)) 
           { 
               //得到大于当前key的那个子Map,然后从中取出第一个key,就是大于且离它最近的那个key 说明详见: 
               var tailMap = from coll in ketamaNodes 
                             where coll.Key > hash 
                             select new { coll.Key }; 
               if (tailMap == null || tailMap.Count() == 0) 
                   key = ketamaNodes.FirstOrDefault().Key; 
               else 
                   key = tailMap.FirstOrDefault().Key; 
           } 
           rv = ketamaNodes[key]; 
           return rv; 
       } 
   } 
}

测试用例代码

namespace KetamaHash 
{ 
   internal class HashAlgorithmTest 
   { 
       private Random rand = new Random(); 
       /** key's count */ 
       private const int KEY_COUNT = 1000000; 
       private const int NODE_COUNT = 10; 
       private const int VIRTUAL_NODE_COUNT = 10000; 
       public void Test() 
       { 
           /** Records the times of locating node*/ 
           var nodeRecords = new Dictionary<string, int>(); 
           var allNodes = GetNodes(NODE_COUNT); 
           var locator = new KetamaNodeLocator(allNodes, VIRTUAL_NODE_COUNT); 
           List<String> allKeys = GetAllStrings(); 
           foreach (string key in allKeys) 
           { 
               string node = locator.GetNode(key); 
               if (!nodeRecords.ContainsKey(node)) 
               { 
                   nodeRecords[node] = 1; 
               } 
               else 
               { 
                   nodeRecords[node] = nodeRecords[node] + 1; 
               } 
           } 
           Console.WriteLine("Nodes count : " + NODE_COUNT + ", Keys count : " + KEY_COUNT + ", Normal percent : " + (float)100 / NODE_COUNT + "%"); 
           Console.WriteLine("-------------------- boundary  ----------------------"); 
           foreach (string key in nodeRecords.Keys) 
           { 
               Console.WriteLine($"Node name :{key} - Times : {nodeRecords[key]} - Percent : { (float)nodeRecords[key] / KEY_COUNT * 100} %"); 
           } 
           //计算标准差 
           double avg = (double)KEY_COUNT / (double)NODE_COUNT; 
           double variance = 0; 
           foreach (int val in nodeRecords.Values) 
           { 
               variance += Math.Pow(val - avg, 2.0); 
           } 
           double sd = Math.Sqrt(variance / (double)NODE_COUNT); 
           Console.WriteLine("-------------------- boundary  ----------------------"); 
           Console.WriteLine($"Nodes Standard deviation : { sd}"); 
           Console.ReadLine(); 
       } 

       /// <summary> 
       ///  
       /// </summary> 
       /// <param name="nodeCount"></param> 
       /// <returns></returns> 
       private List<string> GetNodes(int nodeCount) 
       { 
           List<string> nodes = new List<string>(); 
           for (int k = 1; k <= nodeCount; k++) 
           { 
               string node = "Node" + k; 
               nodes.Add(node); 
           } 
           return nodes; 
       } 
       private List<string> GetAllStrings() 
       { 
           var allStrings = new List<string>(KEY_COUNT ); 
           for (int i = 0; i < KEY_COUNT ; i++) 
           { 
               allStrings.Add(GenerateRandomString(rand.Next(50))); 
           } 
           return allStrings; 
       } 

       private string GenerateRandomString(int length) 
       { 
           var sb = new StringBuilder(length); 
           for (int i = 0; i < length; i++) 
           { 
               sb.Append((char)(rand.Next(95) + 32)); 
           } 
           return sb.ToString(); 
       } 
   } 
}

测试结果:

Hash一致性算法测试结果
Hash一致性算法测试结果

参考资料:

一致性Hash算法原理:https://www.cnblogs.com/myseries/p/10956835.html

《C#实现一致性Hash算法及测试》的相关评论

发表评论

必填项已用 * 标记,邮箱地址不会被公开。