「架构师训练营」作业:第 5 周 一致性 hash 算法

发布于: 23 小时前
  1. 用你熟悉的编程语言实现一致性 hash 算法

  2. 编写测试用例测试这个算法,测试 100 万 kv 数据,10 个服务器节点的情况下,计算这些 kv 数据在服务器上分布数据的标准差,以评估算法的存储负载不均衡性。

语言:C#

IDE:Visual Studio 2019

Sdk:.net core 3.1

class Program
{
private static readonly SortedDictionary<ulong, string> _circle = new SortedDictionary<ulong, string>();
public static string[] services = new 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"
};
static void Main(string[] args)
{
int Replicas = 100;
foreach(string ip in services)
{
AddNode(ip, Replicas);
}
List<string> nodes = new List<string>();
for (int i = 0; i < 1000000; i++)
{
nodes.Add(GetTargetNode(i + "test" + (char)i));
}
var counts = nodes.GroupBy(n => n, n => n.Count()).ToList();
counts.ForEach(index => Console.WriteLine(index.Key + " --- " + index.Count()));
var stdDeviation = CaculateStandardDeviation(counts.Select(i => i.Count()).ToArray());
Console.WriteLine();
Console.WriteLine("标准差:{0}",stdDeviation.ToString());
Console.ReadLine();
}
public static void AddNode(string node, int repeat)
{
for (int i = 0; i < repeat; i++)
{
string identifier = node.GetHashCode().ToString() + "-" + i;
ulong hashCode = Md5Hash(identifier);
_circle.Add(hashCode, node);
}
}
public static ulong Md5Hash(string key)
{
using (var hash = System.Security.Cryptography.MD5.Create())
{
byte[] data = hash.ComputeHash(Encoding.UTF8.GetBytes(key));
var a = BitConverter.ToUInt64(data, 0);
var b = BitConverter.ToUInt64(data, 8);
ulong hashCode = a ^ b;
return hashCode;
}
}
public static string GetTargetNode(string key)
{
ulong hash = Md5Hash(key);
ulong firstNode = ModifiedBinarySearch(_circle.Keys.ToArray(), hash);
return _circle[firstNode];
}
/// <summary>
/// 计算key的数值,得出空间归属。
/// </summary>
/// <param name="sortedArray"></param>
/// <param name="val"></param>
/// <returns></returns>
public static ulong ModifiedBinarySearch(ulong[] sortedArray, ulong val)
{
int min = 0;
int max = sortedArray.Length - 1;
if (val < sortedArray[min] || val > sortedArray[max])
return sortedArray[0];
while (max - min > 1)
{
int mid = (max + min) / 2;
if (sortedArray[mid] >= val)
{
max = mid;
}
else
{
min = mid;
}
}
return sortedArray[max];
}
public static double CaculateStandardDeviation(int[] arry)
{
double stdDeviation = 0;
int min = arry.Min();
int max = arry.Max();
var avg = Math.Round((decimal)arry.Average(p => p), 5);
if (arry.Length > 1)
{
double sumOfSquare = 0;
foreach(var item in arry)
{
sumOfSquare += Math.Pow((double)item - (double)avg, 2);
}
stdDeviation = Math.Sqrt(sumOfSquare / (arry.Length - 1));
stdDeviation = Math.Round(stdDeviation, 5);
}
return stdDeviation;
}
}

用户头像

Amy

关注

还未添加个人签名 2018.06.10 加入

还未添加个人简介

评论

发布
暂无评论
「架构师训练营」作业:第 5 周 一致性 hash 算法