第五周作业

用户头像
胡江涛
关注
发布于: 2020 年 07 月 05 日
第五周作业
  1. 用你熟悉的编程语言实现一致性hash算法


1.1 基于C#的代码实现的,如下

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
namespace ConsoleHasCode
{
class Program
{
static void Main(string[] args)
{
//所有的服务器
List<string> listServers = new List<string>() {
"192.168.0.1","192.168.0.2","192.168.0.3"
};
//一致性hash算法类的实例
ConsHashWithVNode conHashClass = new ConsHashWithVNode(listServers);
//计算节点
String[] keys = { "太阳", "月亮", "星星", "木星" };
for (int i = 0; i < keys.Length; i++)
{
byte[] digest = HashAlgorithm.computeMd5(keys[i]);
long ll = HashAlgorithm.hash(digest, 0);
Console.WriteLine("[" + keys[i] + "]的hash值为" + ll + ", 被路由到结点[" + conHashClass.GetServer(keys[i]) + "]");
}
Console.ReadKey();
}
}
#region 带虚拟节点的一致性hash算法类
public class ConsHashWithVNode
{
// 存放服务器的Hash值(包含虚拟节点)
private SortedList<long, string> serverHashList = new SortedList<long, string>();
//虚拟节点数,每个真实节点指向为16个虚拟节点
private int numReps = 16;
//计算服务器的hash值,并放入serverHashList
public ConsHashWithVNode(List<string> listServers/*,int nodeCopies*/)
{
serverHashList = new SortedList<long, string>();
//numReps = nodeCopies;
foreach (string node in listServers)
{
//每四个虚拟结点为一组
for (int i = 0; i < numReps / 4; i++)
{
//getKeyForNode方法为这组虚拟结点得到惟一名称
byte[] digest = HashAlgorithm.computeMd5(node + i);
/** Md5是一个16字节长度的数组,将16字节的数组每四个字节一组,分别对应一个虚拟结点,这就是为什么上面把虚拟结点四个划分一组的原因*/
for (int h = 0; h < 4; h++)
{
long hashId = HashAlgorithm.hash(digest, h);
serverHashList[hashId] = node;
Console.WriteLine("虚拟节点:" + node + "#" + i + h + " 加入集合中,其hash值为:" + hashId);
}
}
}
}
/// <summary>
/// GetServer
/// </summary>
/// <param name="k"></param>
/// <returns></returns>
public string GetServer(string k)
{
byte[] digest = HashAlgorithm.computeMd5(k);
string rv = GetNodeForKey(HashAlgorithm.hash(digest, 0));
return rv;
}
/// <summary>
/// 获取当前Hashkey值匹配到的最近的服务器节点(正向循环)
/// </summary>
/// <param name="Hashkey"></param>
/// <returns></returns>
public string GetNodeForKey(long Hashkey)
{
//返回的真实的服务器节点名称
string rv;
//如果serverHashList,不包含key为Hashkey的键值对,则从hashList查询离它最近的服务器节点keyid
if (!serverHashList.ContainsKey(Hashkey))
{
var tailMap = from coll in serverHashList
where coll.Key > Hashkey
select new { coll.Key };
if (tailMap == null || tailMap.Count() == 0)
{
Hashkey = serverHashList.FirstOrDefault().Key;//直接获取服务器列表的第一个node
}
else
{
Hashkey = tailMap.FirstOrDefault().Key;//从匹配到的服务器节点列表tailMap,获取第一个node
}
}
rv = serverHashList[Hashkey];
return rv;
}
}
#endregion
#region Hash算法类
public class HashAlgorithm
{
//get hash
public static long hash(byte[] digest, int nTime)
{
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 rv & 0xffffffffL; /* Truncate to 32-bits */
}
// Get the md5 of the given key.
public static byte[] computeMd5(string k)
{
MD5 md5 = new MD5CryptoServiceProvider();
byte[] keyBytes = md5.ComputeHash(Encoding.UTF8.GetBytes(k));
md5.Clear();
//md5.update(keyBytes);
//return md5.digest();
return keyBytes;
}
}
#endregion
}




1.2 上述代码执行的结果, 如下:



虚拟节点:192.168.0.1#00 加入集合中,其hash值为:3859508548

虚拟节点:192.168.0.1#01 加入集合中,其hash值为:4241681493

虚拟节点:192.168.0.1#02 加入集合中,其hash值为:1519788697

虚拟节点:192.168.0.1#03 加入集合中,其hash值为:1335410163

虚拟节点:192.168.0.1#10 加入集合中,其hash值为:2117606811

虚拟节点:192.168.0.1#11 加入集合中,其hash值为:2962930961

虚拟节点:192.168.0.1#12 加入集合中,其hash值为:1439069030

虚拟节点:192.168.0.1#13 加入集合中,其hash值为:1720667371

虚拟节点:192.168.0.1#20 加入集合中,其hash值为:3021860632

虚拟节点:192.168.0.1#21 加入集合中,其hash值为:4137449630

虚拟节点:192.168.0.1#22 加入集合中,其hash值为:1723136726

虚拟节点:192.168.0.1#23 加入集合中,其hash值为:3837318971

虚拟节点:192.168.0.1#30 加入集合中,其hash值为:24385173

虚拟节点:192.168.0.1#31 加入集合中,其hash值为:2846465407

虚拟节点:192.168.0.1#32 加入集合中,其hash值为:349302743

虚拟节点:192.168.0.1#33 加入集合中,其hash值为:413617739

虚拟节点:192.168.0.2#00 加入集合中,其hash值为:3940033943

虚拟节点:192.168.0.2#01 加入集合中,其hash值为:1869053502

虚拟节点:192.168.0.2#02 加入集合中,其hash值为:1496059583

虚拟节点:192.168.0.2#03 加入集合中,其hash值为:1147589708

虚拟节点:192.168.0.2#10 加入集合中,其hash值为:984555294

虚拟节点:192.168.0.2#11 加入集合中,其hash值为:2080654086

虚拟节点:192.168.0.2#12 加入集合中,其hash值为:1469649516

虚拟节点:192.168.0.2#13 加入集合中,其hash值为:1854727269

虚拟节点:192.168.0.2#20 加入集合中,其hash值为:2205480806

虚拟节点:192.168.0.2#21 加入集合中,其hash值为:3683147972

虚拟节点:192.168.0.2#22 加入集合中,其hash值为:2477708060

虚拟节点:192.168.0.2#23 加入集合中,其hash值为:3676803513

虚拟节点:192.168.0.2#30 加入集合中,其hash值为:2569661811

虚拟节点:192.168.0.2#31 加入集合中,其hash值为:2296354626

虚拟节点:192.168.0.2#32 加入集合中,其hash值为:2778269837

虚拟节点:192.168.0.2#33 加入集合中,其hash值为:247034800

虚拟节点:192.168.0.3#00 加入集合中,其hash值为:3629604625

虚拟节点:192.168.0.3#01 加入集合中,其hash值为:1913940234

虚拟节点:192.168.0.3#02 加入集合中,其hash值为:2804907215

虚拟节点:192.168.0.3#03 加入集合中,其hash值为:1223802563

虚拟节点:192.168.0.3#10 加入集合中,其hash值为:1695046869

虚拟节点:192.168.0.3#11 加入集合中,其hash值为:865449427

虚拟节点:192.168.0.3#12 加入集合中,其hash值为:3005534474

虚拟节点:192.168.0.3#13 加入集合中,其hash值为:2349825225

虚拟节点:192.168.0.3#20 加入集合中,其hash值为:3922482827

虚拟节点:192.168.0.3#21 加入集合中,其hash值为:2667059133

虚拟节点:192.168.0.3#22 加入集合中,其hash值为:201480287

虚拟节点:192.168.0.3#23 加入集合中,其hash值为:1261168907

虚拟节点:192.168.0.3#30 加入集合中,其hash值为:2223677633

虚拟节点:192.168.0.3#31 加入集合中,其hash值为:652645763

虚拟节点:192.168.0.3#32 加入集合中,其hash值为:1186616498

虚拟节点:192.168.0.3#33 加入集合中,其hash值为:2075804047

[太阳]的hash值为1719020499, 被路由到结点[192.168.0.1]

[月亮]的hash值为1228027707, 被路由到结点[192.168.0.3]

[星星]的hash值为1943038706, 被路由到结点[192.168.0.3]

[木星]的hash值为3605428979, 被路由到结点[192.168.0.3]


1.3 为了验证结果的正确性,我将所有虚拟节点的hash数据,按照hash值正序排序,如下图:

1228027707,在1223802563和1261168907之间

1719020499,在1695046869和1720667371之间

1943038706,在1913940234和2075804047之间

3605428979,在3021860632和3629604625之间



虚拟节点:192.168.0.1#30 加入集合中,其hash值为:24385173

虚拟节点:192.168.0.3#22 加入集合中,其hash值为:201480287

虚拟节点:192.168.0.2#33 加入集合中,其hash值为:247034800

虚拟节点:192.168.0.1#32 加入集合中,其hash值为:349302743

虚拟节点:192.168.0.1#33 加入集合中,其hash值为:413617739

虚拟节点:192.168.0.3#31 加入集合中,其hash值为:652645763

虚拟节点:192.168.0.3#11 加入集合中,其hash值为:865449427

虚拟节点:192.168.0.2#10 加入集合中,其hash值为:984555294

虚拟节点:192.168.0.2#03 加入集合中,其hash值为:1147589708

虚拟节点:192.168.0.3#32 加入集合中,其hash值为:1186616498

虚拟节点:192.168.0.3#03 加入集合中,其hash值为:1223802563

虚拟节点:192.168.0.3#23 加入集合中,其hash值为:1261168907 //1228027707 月亮

虚拟节点:192.168.0.1#03 加入集合中,其hash值为:1335410163

虚拟节点:192.168.0.1#12 加入集合中,其hash值为:1439069030

虚拟节点:192.168.0.2#12 加入集合中,其hash值为:1469649516

虚拟节点:192.168.0.2#02 加入集合中,其hash值为:1496059583

虚拟节点:192.168.0.1#02 加入集合中,其hash值为:1519788697

虚拟节点:192.168.0.3#10 加入集合中,其hash值为:1695046869

虚拟节点:192.168.0.1#13 加入集合中,其hash值为:1720667371 //1719020499 太阳

虚拟节点:192.168.0.1#22 加入集合中,其hash值为:1723136726

虚拟节点:192.168.0.2#13 加入集合中,其hash值为:1854727269

虚拟节点:192.168.0.2#01 加入集合中,其hash值为:1869053502

虚拟节点:192.168.0.3#01 加入集合中,其hash值为:1913940234

虚拟节点:192.168.0.3#33 加入集合中,其hash值为:2075804047 //1943038706 星星

虚拟节点:192.168.0.2#11 加入集合中,其hash值为:2080654086

虚拟节点:192.168.0.1#10 加入集合中,其hash值为:2117606811

虚拟节点:192.168.0.2#20 加入集合中,其hash值为:2205480806

虚拟节点:192.168.0.3#30 加入集合中,其hash值为:2223677633

虚拟节点:192.168.0.2#31 加入集合中,其hash值为:2296354626

虚拟节点:192.168.0.3#13 加入集合中,其hash值为:2349825225

虚拟节点:192.168.0.2#22 加入集合中,其hash值为:2477708060

虚拟节点:192.168.0.2#30 加入集合中,其hash值为:2569661811

虚拟节点:192.168.0.3#21 加入集合中,其hash值为:2667059133

虚拟节点:192.168.0.2#32 加入集合中,其hash值为:2778269837

虚拟节点:192.168.0.3#02 加入集合中,其hash值为:2804907215

虚拟节点:192.168.0.1#31 加入集合中,其hash值为:2846465407

虚拟节点:192.168.0.1#11 加入集合中,其hash值为:2962930961

虚拟节点:192.168.0.3#12 加入集合中,其hash值为:3005534474

虚拟节点:192.168.0.1#20 加入集合中,其hash值为:3021860632

虚拟节点:192.168.0.3#00 加入集合中,其hash值为:3629604625 //3605428979 木星

虚拟节点:192.168.0.2#23 加入集合中,其hash值为:3676803513

虚拟节点:192.168.0.2#21 加入集合中,其hash值为:3683147972

虚拟节点:192.168.0.1#23 加入集合中,其hash值为:3837318971

虚拟节点:192.168.0.1#00 加入集合中,其hash值为:3859508548

虚拟节点:192.168.0.3#20 加入集合中,其hash值为:3922482827

虚拟节点:192.168.0.2#00 加入集合中,其hash值为:3940033943

虚拟节点:192.168.0.1#21 加入集合中,其hash值为:4137449630

虚拟节点:192.168.0.1#01 加入集合中,其hash值为:4241681493



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

2.1 获取KV数据在服务器上分布的C#代码(160个虚拟节点)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
namespace ConsoleHasCode
{
class Program
{
static void Main(string[] args)
{
//所有的服务器
List<string> listServers = new List<string>() {
"192.168.0.1","192.168.0.2","192.168.0.3",
"192.168.0.4","192.168.0.5","192.168.0.6",
"192.168.0.7","192.168.0.8","192.168.0.9","192.168.0.10"
};
//一致性hash算法类,实例类
ConsHashWithVNode conHashClass = new ConsHashWithVNode(listServers);
#region 字典存放,所有服务器上存放的cache值数据
Dictionary<string, int> dicList = new Dictionary<string, int>();
dicList.Add("192.168.0.1", 0);
dicList.Add("192.168.0.2", 0);
dicList.Add("192.168.0.3", 0);
dicList.Add("192.168.0.4", 0);
dicList.Add("192.168.0.5", 0);
dicList.Add("192.168.0.6", 0);
dicList.Add("192.168.0.7", 0);
dicList.Add("192.168.0.8", 0);
dicList.Add("192.168.0.9", 0);
dicList.Add("192.168.0.10", 0);
#endregion
//测试100万kv数据
for (int i = 0; i < 1000000; i++)
{
string testValue = "数据" + i;
byte[] digest = HashAlgorithm.computeMd5(testValue);
long longVal = HashAlgorithm.hash(digest, 0);//当前数据的hash值
string serverName = conHashClass.GetServer(testValue);//匹配到的节点服务器名称
//Console.WriteLine("[" + testValue + "]的hash值为" + longVal + ", 被路由到结点[" + serverName + "]");
dicList[serverName] = dicList[serverName] + 1;//匹配到当前服务器时,缓存数据总量加1
}
//打印数据在服务器上的存放详情
foreach (KeyValuePair<string, int> item in dicList) {
Console.WriteLine("服务器["+ item.Key + "]存放的缓存数据总量为:"+item.Value);
}
Console.ReadKey();
}
}
#region 带虚拟节点的一致性hash算法类
public class ConsHashWithVNode
{
// 存放服务器的Hash值(包含虚拟节点)
private SortedList<long, string> serverHashList = new SortedList<long, string>();
//虚拟节点数,每个真实节点指向为160个虚拟节点
private int numReps = 160;
//计算服务器的hash值,并放入serverHashList
public ConsHashWithVNode(List<string> listServers/*,int nodeCopies*/)
{
serverHashList = new SortedList<long, string>();
//numReps = nodeCopies;
foreach (string node in listServers)
{
//每四个虚拟结点为一组
for (int i = 0; i < numReps / 4; i++)
{
//getKeyForNode方法为这组虚拟结点得到惟一名称
byte[] digest = HashAlgorithm.computeMd5(node + i);
/** Md5是一个16字节长度的数组,将16字节的数组每四个字节一组,分别对应一个虚拟结点,这就是为什么上面把虚拟结点四个划分一组的原因*/
for (int h = 0; h < 4; h++)
{
long hashId = HashAlgorithm.hash(digest, h);
serverHashList[hashId] = node;
//Console.WriteLine("虚拟节点:" + node + "#" + i + h + " 加入集合中,其hash值为:" + hashId);
}
}
}
}
/// <summary>
/// GetServer
/// </summary>
/// <param name="k"></param>
/// <returns></returns>
public string GetServer(string k)
{
byte[] digest = HashAlgorithm.computeMd5(k);
string rv = GetNodeForKey(HashAlgorithm.hash(digest, 0));
return rv;
}
/// <summary>
/// 获取当前Hashkey值匹配到的最近的服务器节点(正向循环)
/// </summary>
/// <param name="Hashkey"></param>
/// <returns></returns>
public string GetNodeForKey(long Hashkey)
{
//返回的真实的服务器节点名称
string rv;
//如果serverHashList,不包含key为Hashkey的键值对,则从hashList查询离它最近的服务器节点keyid
if (!serverHashList.ContainsKey(Hashkey))
{
var tailMap = from coll in serverHashList
where coll.Key > Hashkey
select new { coll.Key };
if (tailMap == null || tailMap.Count() == 0)
{
Hashkey = serverHashList.FirstOrDefault().Key;//直接获取服务器列表的第一个node
}
else
{
Hashkey = tailMap.FirstOrDefault().Key;//从匹配到的服务器节点列表tailMap,获取第一个node
}
}
rv = serverHashList[Hashkey];
return rv;
}
}
#endregion
#region Hash算法类
public class HashAlgorithm
{
//get hash
public static long hash(byte[] digest, int nTime)
{
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 rv & 0xffffffffL; /* Truncate to 32-bits */
}
// Get the md5 of the given key.
public static byte[] computeMd5(string k)
{
MD5 md5 = new MD5CryptoServiceProvider();
byte[] keyBytes = md5.ComputeHash(Encoding.UTF8.GetBytes(k));
md5.Clear();
//md5.update(keyBytes);
//return md5.digest();
return keyBytes;
}
}
#endregion
}



2.2 运行程序得到的数据分布如下

服务器[192.168.0.1]存放的缓存数据总量为:92146

服务器[192.168.0.2]存放的缓存数据总量为:88615

服务器[192.168.0.3]存放的缓存数据总量为:101905

服务器[192.168.0.4]存放的缓存数据总量为:96188

服务器[192.168.0.5]存放的缓存数据总量为:110750

服务器[192.168.0.6]存放的缓存数据总量为:97129

服务器[192.168.0.7]存放的缓存数据总量为:101255

服务器[192.168.0.8]存放的缓存数据总量为:92696

服务器[192.168.0.9]存放的缓存数据总量为:114326

服务器[192.168.0.10]存放的缓存数据总量为:104990

2.3 用Excel表格计算10个节点服务器上,数据的标准差:7863.3763



用户头像

胡江涛

关注

放肆才叫青春 2019.05.11 加入

IT软件工程师,一枚

评论

发布
暂无评论
第五周作业