写点什么

架构师训练营 第五周 作业

用户头像
Poplar
关注
发布于: 2020 年 07 月 03 日

一致性hash实现,实现中没有处理多线程的情况,也就是没有加锁。

/// <summary>
/// 一致性哈希。
/// </summary>
public static class ConsistentHashing
{
/// <summary>
/// 虚拟节点倍数
/// </summary>
private static int _virtualNodeMultiple = 100;
/// <summary>
/// 真实节点信息
/// </summary>
private static readonly List<string> Nodes = new List<string>();
/// <summary>
/// 虚拟节点信息(int类型主要是为了获取虚拟节点时的二分查找)
/// </summary>
private static readonly List<int> VirtualNode = new List<int>();
/// <summary>
/// 虚拟节点和真实节点映射,在获取到虚拟节点之后,能以O(1)的时间复杂度返回真实节点
/// </summary>
private static readonly Dictionary<int, string> VirtualNodeAndNodeMap = new Dictionary<int, string>();
/// <summary>
/// 增加节点
/// </summary>
/// <param name="hosts">节点集合</param>
/// <returns>操作结果</returns>
public static bool AddNode(params string[] hosts)
{
if (hosts == null || hosts.Length == 0)
{
return false;
}
Nodes.AddRange(hosts); //先将节点增加到真实节点信息中。
foreach (var item in hosts)
{
for (var i = 1; i <= _virtualNodeMultiple; i++) //此处循环为类似“192.168.3.1”这样的真实ip字符串从1加到1000,算作虚拟节点。192.168.3.11,192.168.3.11000
{
var currentHash = HashAlgorithm.GetHashCode(item + i) & int.MaxValue; //计算一个hash,此处用自定义hash算法原因是字符串默认的哈希实现不保证对同一字符串获取hash时得到相同的值。和int.MaxValue进行位与操作是为了将获取到的hash值设置为正数
if (!VirtualNodeAndNodeMap.ContainsKey(currentHash)) //因为hash可能会重复,如果当前hash已经包含在虚拟节点和真实节点映射中,则以第一次添加的为准,此处不再进行添加
{
VirtualNode.Add(currentHash);//将当前虚拟节点添加到虚拟节点中
VirtualNodeAndNodeMap.Add(currentHash, item);//将当前虚拟节点和真实ip放入映射中。
}
}
}
VirtualNode.Sort(); //操作完成之后进行一次映射,是为了后面根据key的hash值查找虚拟节点时使用二分查找。
return true;
}
/// <summary>
/// 移除节点
/// </summary>
/// <param name="host">指定节点</param>
/// <returns></returns>
public static bool RemoveNode(string host)
{
if (!Nodes.Remove(host)) //如果将指定节点从真实节点集合中移出失败,后序操作不需要进行,直接返回
{
return false;
}
for (var i = 1; i <= _virtualNodeMultiple; i++)
{
var currentHash = HashAlgorithm.GetHashCode(host + i) & int.MaxValue; //计算一个hash,此处用自定义hash算法原因是字符串默认的哈希实现不保证对同一字符串获取hash时得到相同的值。和int.MaxValue进行位与操作是为了将获取到的hash值设置为正数
if (VirtualNodeAndNodeMap.ContainsKey(currentHash) && VirtualNodeAndNodeMap[currentHash] == host) //因为hash可能会重复,所以此处判断在判断了哈希值是否存在于虚拟节点和节点映射中之后还需要判断通过当前hash值获取到的节点是否和指定节点一致,如果不一致,则证明这个这个虚拟节点不是当前hash值所拥有的
{
VirtualNode.Remove(currentHash); //从虚拟节点中移出
VirtualNodeAndNodeMap.Remove(currentHash); //从虚拟节点和真实ip映射中移出
}
}
VirtualNode.Sort(); //操作完成之后进行一次映射,是为了后面根据key的hash值查找虚拟节点时使用二分查找。
return true;
}
/// <summary>
/// 获取所有节点
/// </summary>
/// <returns></returns>
public static List<string> GetAllNodes()
{
var nodes = new List<string>(Nodes.Count);
nodes.AddRange(Nodes);
return nodes;
}
/// <summary>
/// 获取节点数量
/// </summary>
/// <returns></returns>
public static int GetNodesCount()
{
return Nodes.Count;
}
/// <summary>
/// 重新设置虚拟节点倍数
/// </summary>
/// <param name="multiple"></param>
public static void ReSetVirtualNodeMultiple(int multiple)
{
if (multiple < 0 || multiple == _virtualNodeMultiple)
{
return;
}
var nodes = new List<string>(Nodes.Count);
nodes.AddRange(Nodes); //将现有的真实节点拷贝出来
_virtualNodeMultiple = multiple; //设置倍数
Nodes.Clear();
VirtualNode.Clear();
VirtualNodeAndNodeMap.Clear(); //清空数据
AddNode(nodes.ToArray()); //重新添加
}
/// <summary>
/// 获取节点
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public static string GetNode(string key)
{
var hash = HashAlgorithm.GetHashCode(key) & int.MaxValue;
var start = 0;
var end = VirtualNode.Count - 1;
while (end - start > 1)
{
var index = (start + end) / 2;
if (VirtualNode[index] > hash)
{
end = index;
}
else if (VirtualNode[index] < hash)
{
start = index;
}
else
{
start = end = index;
}
}
return VirtualNodeAndNodeMap[VirtualNode[start]];
}
/// <summary>
/// hash
/// </summary>
private static class HashAlgorithm
{
public static int GetHashCode(string key)
{
return Hash(ComputeMd5(key));
}
private static int Hash(byte[] digest, int nTime = 0)
{
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 (int)(rv & 0xffffffffL);
}
private static byte[] ComputeMd5(string k)
{
MD5 md5 = new MD5CryptoServiceProvider();
byte[] keyBytes = md5.ComputeHash(Encoding.UTF8.GetBytes(k));
md5.Clear();
return keyBytes;
}
}
}

测试代码,测试代码测试了9、10、11个节点分别在100倍和100倍虚拟节点情况下的数据。

class Program
{
static void Main(string[] args)
{
ConsistentHashing.AddNode(new[]
{
"192.168.137.1",
"192.168.137.2",
"192.168.137.3",
"192.168.137.4",
"192.168.137.5",
"192.168.137.6",
"192.168.137.7",
"192.168.137.8",
"192.168.137.9",
"192.168.137.10"
});
var data = LoadTestData();
Stopwatch stop = new Stopwatch();
stop.Start();
foreach (var item in data)
{
var node = ConsistentHashing.GetNode(item);
}
stop.Stop();
var map10 = new Dictionary<string, string>();
var mapCount10 = new Dictionary<string, int>();
var map11 = new Dictionary<string, string>();
var mapCount11 = new Dictionary<string, int>();
var map9 = new Dictionary<string, string>();
var mapCount9 = new Dictionary<string, int>();
#region 10个节点
foreach (var item in data)
{
var host = ConsistentHashing.GetNode(item);
if (!map10.ContainsKey(item))
{
map10.Add(item, host);
}
if (!mapCount10.ContainsKey(host))
{
mapCount10.Add(host, 1);
}
else
{
mapCount10[host]++;
}
}
#endregion
#region 11个节点
ConsistentHashing.AddNode("192.168.137.11");
foreach (var item in data)
{
var host = ConsistentHashing.GetNode(item);
if (!map11.ContainsKey(item))
{
map11.Add(item, host);
}
if (!mapCount11.ContainsKey(host))
{
mapCount11.Add(host, 1);
}
else
{
mapCount11[host]++;
}
}
#endregion
#region 9个节点
ConsistentHashing.RemoveNode("192.168.137.11");
ConsistentHashing.RemoveNode("192.168.137.10");
foreach (var item in data)
{
var host = ConsistentHashing.GetNode(item);
if (!map9.ContainsKey(item))
{
map9.Add(item, host);
}
if (!mapCount9.ContainsKey(host))
{
mapCount9.Add(host, 1);
}
else
{
mapCount9[host]++;
}
}
#endregion
#region 数据比较和存储
var tenAndNine = 0;
foreach (var item in map9)
{
if (map10[item.Key] != item.Value)
{
tenAndNine++;
}
}
var tenAndEleven = 0;
foreach (var item in map11)
{
if (map10[item.Key] != item.Value)
{
tenAndEleven++;
}
}
List<string> csv = new List<string>();
csv.Add("ip,10,10分布,9,9分布,11,11分布");
foreach (var item in mapCount11)
{
var str = item.Key;
if (mapCount10.ContainsKey(item.Key))
{
str += "," + mapCount10[item.Key];
str += "," + (mapCount10[item.Key] / (double)100000).ToString("F2");
}
else
{
str += ",";
str += ",";
}
if (mapCount9.ContainsKey(item.Key))
{
str += "," + mapCount9[item.Key];
str += "," + (mapCount9[item.Key] / (double)100000).ToString("F2");
}
else
{
str += ",";
str += ",";
}
str += "," + mapCount11[item.Key];
str += "," + (mapCount11[item.Key] / (double)100000).ToString("F2");
csv.Add(str);
}
csv.Add(string.Format("10-1的失效数据:{0},比例:{2:F2}。10+1的失效数据:{1},比例:{3:F2}", tenAndNine, tenAndEleven, (tenAndNine / (double)1000000), (tenAndEleven / (double)1000000)));
File.WriteAllLines(@"E:\1000.csv", csv, Encoding.UTF8);
#endregion
Console.ReadKey();
}
/// <summary>
/// 生成测试key
/// </summary>
/// <param name="count"></param>
/// <returns></returns>
private static List<string> LoadTestData(int count = 1000000)
{
var data = new List<string>(count);
for (var i = 0; i < count; i++)
{
data.Add(GetRandomString(15, true, true, true, false, ""));
}
return data;
}
///<summary>
///生成随机字符串
///</summary>
///<param name="length">目标字符串的长度</param>
///<param name="useNum">是否包含数字,1=包含,默认为包含</param>
///<param name="useLow">是否包含小写字母,1=包含,默认为包含</param>
///<param name="useUpp">是否包含大写字母,1=包含,默认为包含</param>
///<param name="useSpe">是否包含特殊字符,1=包含,默认为不包含</param>
///<param name="custom">要包含的自定义字符,直接输入要包含的字符列表</param>
///<returns>指定长度的随机字符串</returns>
public static string GetRandomString(int length, bool useNum, bool useLow, bool useUpp, bool useSpe, string custom)
{
byte[] b = new byte[4];
new System.Security.Cryptography.RNGCryptoServiceProvider().GetBytes(b);
Random r = new Random(BitConverter.ToInt32(b, 0));
string s = null, str = custom;
if (useNum == true) { str += "0123456789"; }
if (useLow == true) { str += "abcdefghijklmnopqrstuvwxyz"; }
if (useUpp == true) { str += "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; }
if (useSpe == true) { str += "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"; }
for (int i = 0; i < length; i++)
{
s += str.Substring(r.Next(0, str.Length - 1), 1);
}
return s;
}
}

测试结果,其中分布是以10万为基数计算的。





用户头像

Poplar

关注

还未添加个人签名 2018.04.23 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 第五周 作业