Week 05- 作业一:一致性 hash 算法

用户头像
dean
关注
发布于: 2020 年 07 月 06 日



  • 用你熟悉的编程语言实现一致性 hash 算法。

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



基于C# 实现~~~

public class ConsistentDemo
{
private HashSet<string> _server = new HashSet<string>()
{
"server-0",
"server-1","server-2","server-3","server-4",
"server-5","server-6","server-7","server-8",
"server-9"
};
/// <summary>
/// 虚拟多少倍
/// </summary>
const int Multiples = 200;
/// <summary>
/// 测试样本数据量
/// </summary>
private const int TestItemCount = 400000;//1_000_000;
private const int FNV32_prime = 16777619;//0x01000193;
private const long FNV32_basis = 2166136261;//0x811C9DC5;
//一个哈希值对应N的VALUE.
private Dictionary<long, string> _vServers = new Dictionary<long, string>();
private long GetServerHash(string serverName)
{
long hash = FNV32_basis;
for (int i = 0; i < serverName.Length; i++)
{
hash = (hash ^ serverName[i]) * FNV32_prime;
}
hash += hash << 40;
hash ^= hash >> 8;
hash += hash << 7;
hash ^= hash >> 5;
hash ^= hash >> 4;
hash += hash << 1;
return hash;
}
public ConsistentDemo()
{
foreach (var item in _server)
{
AddServer(item);
}
}
/// <summary>
/// 新增服务器
/// </summary>
/// <param name="name"></param>
public void AddServer(string name)
{
for (int index = 0; index < Multiples; index++)
{
long hash = GetServerHash($"{name}:Virtual Server{index}");
_vServers.TryAdd(hash, name);
}
}
/// <summary>
/// 移除服务器
/// </summary>
/// <param name="name"></param>
public void RemoveServer(string name)
{
for (int index = 0; index < Multiples; index++)
{
long hash = GetServerHash($"{name}:Virtual Server{index}");
_vServers.Remove(hash);
}
}
/// <summary>
/// 获取Key-value 对应服务服务器
/// </summary>
/// <param name="theValue"></param>
/// <returns></returns>
public string GetServer(string theValue)
{
if (_server.Count == 0)
{
return string.Empty;
}
long hash = GetServerHash(theValue);
var target = _vServers.Keys.OrderBy(item => item).FirstOrDefault(item => item >= hash);
if (_vServers.ContainsKey(target))
{
return _vServers[target];
}
else
{
return _vServers.FirstOrDefault().Value;
}
}
public void Print()
{
Dictionary<string, int> data = new Dictionary<string, int>();
for (int i = 0; i < TestItemCount; i++)
{
string svrName = GetServer($"我是{i}号数据");
if (data.ContainsKey(svrName))
{
data[svrName] += 1;
}
else
{
data[svrName] = 1;
}
}
Console.WriteLine($"数据量:{TestItemCount},数据被分布在:{data.Count}台服务器上 虚拟倍数{Multiples} 总虚拟服务器个数为:{_vServers.Count}");
foreach (var item in data)
{
Console.WriteLine($"我是<{item.Key}> 我承载了{((float)item.Value / (float)TestItemCount) * 100}%数据");
}
Console.WriteLine($"标准差为:{CalculateStdDev(data.Values.ToArray())}");
}
private double CalculateStdDev(IEnumerable<int> values)
{
double ret = 0;
if (values.Count() > 0)
{
//  计算平均数   
double avg = values.Average();
//  计算各数值与平均数的差值的平方,然后求和 
double sum = values.Sum(d => Math.Pow(d - avg, 2));
//  除以数量,然后开方
ret = Math.Sqrt(sum / values.Count());
}
return ret;
}
}



static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
var xx = new ConsistentDemo();
sw.Restart();
Console.WriteLine("初始化服务器");
xx.Print();
Console.WriteLine($"总耗时:{sw.ElapsedMilliseconds}ms");
Console.WriteLine("");
sw.Restart();
Console.WriteLine("新增一个临时的");
xx.AddServer("临时服务器1");
xx.Print();
Console.WriteLine($"总耗时:{sw.ElapsedMilliseconds}ms");
Console.WriteLine("");
sw.Restart();
Console.WriteLine("删除一个");
xx.RemoveServer("server-1");
xx.Print();
Console.WriteLine($"总耗时:{sw.ElapsedMilliseconds}ms");
Console.ReadLine();
}







100W 、40W的测试

发布于: 2020 年 07 月 06 日 阅读数: 24
用户头像

dean

关注

还未添加个人签名 2019.11.06 加入

还未添加个人简介

评论

发布
暂无评论
Week 05- 作业一:一致性 hash 算法