架构师训练营 - 作业 5

用户头像
紫极
关注
发布于: 2020 年 07 月 09 日
架构师训练营-作业5

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位算法

  1. 声明有序的虚拟节点链表virtualNodes,并在构造函数中将服务器节点倍化成VIRTUALNODE_CARDINALITY

  2. 声明一个计算key 应该所在节点的函数

  3. FNV算法

  4. 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;
}



结果标准差还算均匀。



用户头像

紫极

关注

还未添加个人签名 2018.08.28 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营-作业5