架构师训练营 第五周 【作业】

发布于: 2020 年 07 月 08 日

作业一:

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

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

代码实现如下:

/**服务器实体类**/
class ServerEntity {
String ip;//服务器地址
List<String> data = new ArrayList<>();//数据
public ServerEntity(String ip) {
this.ip = ip;
}
}
public class ConsensusAlg {
/**
* 使用FNV1_32_HASH算法计算服务器的Hash值
*/
public static int getHash(String str) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++)
hash = (hash ^ str.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
//如果算出来的值为负数则取其绝对值
//if (hash < 0)hash = Math.abs(hash);
return hash;
}
//生成随机字符串
public static String getRandomString(int stringLength) {
String string = "abcdefghijklmnopqrstuvwxyz0123456789";
StringBuffer sb = new StringBuffer();
for (int i = 0; i < stringLength; i++) {
int index = (int) Math.floor(Math.random() * string.length());
sb.append(string.charAt(index));
}
return sb.toString();
}
/**
* 一致性hash测试方法
*/
public static void mainTest() {
// 创建服务器集群
ServerEntity[] servers = new ServerEntity[] {
new ServerEntity("192.168.0.1"),
new ServerEntity("192.168.0.2"),
new ServerEntity("192.168.0.3"),
new ServerEntity("192.168.0.4"),
new ServerEntity("192.168.0.5"),
new ServerEntity("192.168.0.6"),
new ServerEntity("192.168.0.7"),
new ServerEntity("192.168.0.8"),
new ServerEntity("192.168.0.9"),
new ServerEntity("192.168.0.10")
};
int virtualCount = 150;// 每台服务器的虚拟节点数量
int dataNum = 100 * 10000;// 测试数据量
System.out.println("数据量为"+dataNum+"。服务器数量:"+servers.length+"。单个服务器虚拟节点数为:"+virtualCount);
// 创建一致性hash节点环
TreeMap<Integer, ServerEntity> tr = new TreeMap<>();
for (ServerEntity se : servers) {
tr.put(getHash(se.ip), se);
for (int i = 1; i <= virtualCount; i++) {
tr.put(getHash(se.ip + "#" + i), se);
}
}
// 放入100万数据
Entry<Integer, ServerEntity> tempEntry;//临时变量,用于获取对应的服务器节点
String dataTemp;
for (int i = 0; i < dataNum; i++) {
dataTemp = getRandomString(20);//生成随机字符串
tempEntry = tr.ceilingEntry(getHash(dataTemp));
if (tempEntry == null)
tempEntry = tr.firstEntry();
tempEntry.getValue().data.add(dataTemp);
}
// 分别显示每个服务器的数据量
for (ServerEntity se : servers) {
System.out.println(se.ip + "--->" + se.data.size());
}
// 计算方差
long avg = dataNum / servers.length;
long variance = 0;
for (ServerEntity se : servers) {
variance += (se.data.size() - avg) * (se.data.size() - avg);
}
System.out.println("方差为:" + variance);
// 计算标准差
double standardDeviation = Math.sqrt(variance / servers.length);
System.out.println("标准差为:" + standardDeviation);
}
}

运行 mainTest() 方法即可,结果如下:

数据量为1000000。服务器数量:10。单个服务器虚拟节点数为:150
192.168.0.1--->105216
192.168.0.2--->103090
192.168.0.3--->95222
192.168.0.4--->96683
192.168.0.5--->88238
192.168.0.6--->87705
192.168.0.7--->109047
192.168.0.8--->103438
192.168.0.9--->102266
192.168.0.10--->109095
方差为:541620032
标准差为:7359.48388136016

用户头像

小K

关注

还未添加个人签名 2019.11.08 加入

还未添加个人简介

评论

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