「架构师训练营」Week5 作业
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
老实说，这个作业题感觉很懵没有很清晰的思路，还是借鉴抄袭了网上其他同学的代码，才有了一个初步的认识，在此感谢。
public 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;
}
}
public class CustomerHashing
{
//虚拟节点个数
private int virtualNodeNumber;
//服务节点列表
private readonly List<string> serverNodes;
//虚拟节点信息
private readonly List<int> virtualNodes;
//虚拟节点和真实节点映射表
private readonly Dictionary<int, string> nodeMap;
public CustomerHashing(int virtualNodeNum = 100)
{
this.virtualNodeNumber = virtualNodeNum;
this.serverNodes = new List<string>();
this.virtualNodes = new List<int>();
this.nodeMap = new Dictionary<int, string>();
}
public bool AddNodes(params string[] serveHosts)
{
if (serveHosts == null || serveHosts.Length == 0)
{
return false;
}
this.serverNodes.AddRange(serveHosts);
foreach (var item in serveHosts)
{
//此处循环为类似“192.168.3.1”这样的真实ip字符串从1加到1000，算作虚拟节点。192.168.3.11，192.168.3.11000
for (var i = 1; i <= virtualNodeNumber; i++)
{
//计算一个hash，此处用自定义hash算法原因是字符串默认的哈希实现不保证对同一字符串获取hash时得到相同的值。和int.MaxValue进行位与操作是为了将获取到的hash值设置为正数
var currentHash = HashAlgorithm.GetHashCode(item + i) & int.MaxValue;
//因为hash可能会重复，如果当前hash已经包含在虚拟节点和真实节点映射中，则以第一次添加的为准，此处不再进行添加
if (!nodeMap.ContainsKey(currentHash))
{
//将当前虚拟节点添加到虚拟节点中
virtualNodes.Add(currentHash);
//将当前虚拟节点和真实ip放入映射中。
nodeMap.Add(currentHash, item);
}
}
}
//操作完成之后进行一次映射，是为了后面根据key的hash值查找虚拟节点时使用二分查找。
virtualNodes.Sort();
return true;
}
public bool RemoveNode(string host)
{
if (!serverNodes.Remove(host)) //如果将指定节点从真实节点集合中移出失败，后序操作不需要进行，直接返回
{
return false;
}
for (var i = 1; i <= virtualNodeNumber; i++)
{
var currentHash = HashAlgorithm.GetHashCode(host + i) & int.MaxValue; //计算一个hash，此处用自定义hash算法原因是字符串默认的哈希实现不保证对同一字符串获取hash时得到相同的值。和int.MaxValue进行位与操作是为了将获取到的hash值设置为正数
if (nodeMap.ContainsKey(currentHash) && nodeMap[currentHash] == host) //因为hash可能会重复，所以此处判断在判断了哈希值是否存在于虚拟节点和节点映射中之后还需要判断通过当前hash值获取到的节点是否和指定节点一致，如果不一致，则证明这个这个虚拟节点不是当前hash值所拥有的
{
virtualNodes.Remove(currentHash); //从虚拟节点中移出
nodeMap.Remove(currentHash); //从虚拟节点和真实ip映射中移出
}
}
virtualNodes.Sort(); //操作完成之后进行一次映射，是为了后面根据key的hash值查找虚拟节点时使用二分查找。
return true;
}
public List<string> GetAllServerHostNodes()
{
var nodes = new List<string>(serverNodes.Count);
nodes.AddRange(serverNodes);
return nodes;
}
public int GetAllServerHostNumber()
{
return this.serverNodes.Count;
}
public void ResetVirtualNodeNumber(int newVirtualNodeNumber)
{
if(this.virtualNodeNumber == newVirtualNodeNumber || newVirtualNodeNumber < 0)
{
return;
}
var nodes = new List<string>(serverNodes.Count);
nodes.AddRange(serverNodes); //将现有的真实节点拷贝出来
this.virtualNodeNumber = newVirtualNodeNumber; //设置倍数
serverNodes.Clear();
virtualNodes.Clear();
nodeMap.Clear(); //清空数据
this.AddNodes(nodes.ToArray()); //重新添加
}
public string GetNodeByKey(string key)
{
var hash = HashAlgorithm.GetHashCode(key) & int.MaxValue;
var start = 0;
var end = virtualNodes.Count - 1;
while (end - start > 1)
{
var index = (start + end) / 2;
if (virtualNodes[index] > hash)
{
end = index;
}
else if (virtualNodes[index] < hash)
{
start = index;
}
else
{
start = end = index;
}
}
return nodeMap[virtualNodes[start]];
}
}
///<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;
}
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;
}
static void Main(string[] args)
{
var customerHash = new CustomerHashing();
customerHash.AddNodes(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();
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 = customerHash.GetNodeByKey(item);
if (!map10.ContainsKey(item))
{
map10.Add(item, host);
}
if (!mapCount10.ContainsKey(host))
{
mapCount10.Add(host, 1);
}
else
{
mapCount10[host]++;
}
}
#endregion
#region 11个节点
customerHash.AddNodes("192.168.137.11");
foreach (var item in data)
{
var host = customerHash.GetNodeByKey(item);
if (!map11.ContainsKey(item))
{
map11.Add(item, host);
}
if (!mapCount11.ContainsKey(host))
{
mapCount11.Add(host, 1);
}
else
{
mapCount11[host]++;
}
}
#endregion
#region 9个节点
customerHash.RemoveNode("192.168.137.11");
customerHash.RemoveNode("192.168.137.10");
foreach (var item in data)
{
var host = customerHash.GetNodeByKey(item);
if (!map9.ContainsKey(item))
{
map9.Add(item, host);
}
if (!mapCount9.ContainsKey(host))
{
mapCount9.Add(host, 1);
}
else
{
mapCount9[host]++;
}
}
#endregion
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);
Console.ReadKey();
}
还未添加个人签名 2018.09.17 加入
还未添加个人简介
评论