第 05 周 技术选型 -01 命题作业

发布于: 2020 年 07 月 08 日
第05周 技术选型-01 命题作业

作业

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

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

一致性Hash算法代码

public class ConsistentHashBalance {
public ConsistentHashBalance(int virtualNum) {
this.virtualNum = virtualNum;
}
/**
* 物理节点
*/
private List<CacheNode> cacheNodeList = new ArrayList<CacheNode>();
/**
* 虚拟节点
*/
private TreeMap<Integer, CacheNode> virtualNodeMap = new TreeMap<Integer, CacheNode>();
/**
* 虚拟节点个数
*/
private int virtualNum;
/**
* 添加节点
*
* @param node
*/
public void addServer(CacheNode node) {
cacheNodeList.add(node);
for (int i = 0; i < this.virtualNum; i++) {
String nodeName = StrUtil.format("{}-VM-{}", node.getIp(), i);
int hash = this.getHash(nodeName);
virtualNodeMap.put(hash, node);
}
}
/**
* 获取节点
*
* @param cacheKey
* @return
*/
public CacheNode getNode(String cacheKey) {
int hash = getHash(cacheKey);
SortedMap<Integer, CacheNode> tailMap = virtualNodeMap.tailMap(hash);
Integer key = tailMap.isEmpty() ? virtualNodeMap.firstKey() : tailMap.firstKey();
return virtualNodeMap.get(key);
}
/**
* Hash 算法
*
* @param key
* @return
*/
private int getHash(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++) {
hash = (hash ^ key.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 List<CacheNode> getCacheNodeList() {
return cacheNodeList;
}
public int getVirtualNum() {
return virtualNum;
}
}
public class CacheNode {
public CacheNode(String ip, int port) {
this.ip = ip;
this.port = port;
}
private String ip;
private int port;
private List<String> data = new ArrayList<String>();
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public int getPort() {
return port;
}
public void setPort(int port) {
this.port = port;
}
public List<String> getData() {
return data;
}
public void setData(List<String> data) {
this.data = data;
}
}
public class MathUtils {
/**
* 求标准差
*
* @param x
* @return
*/
public static double standardDiviation(int[] x) {
int m = x.length;
int sum = 0;
// 求和
for (int i = 0; i < m; i++) {
sum += x[i];
}
// 求平均值
int dAve = sum / m;
int dVar = 0;
for (int i = 0; i < m; i++) {
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return Math.sqrt(dVar / m);
}
}
public class Main {
public static void main(String[] args) {
ConsistentHashBalance hashBalance = new ConsistentHashBalance(50);
//模拟服务器
for (int i = 1; i <= 10; i++) {
hashBalance.addServer(new CacheNode("192.168.1." + i, 6379));
}
//模拟数据
for (int i = 0; i < 1000000; i++) {
String key = IdUtil.objectId();
CacheNode node = hashBalance.getNode(key);
node.getData().add(key);
}
//计算标准差
int serverSize = hashBalance.getCacheNodeList().size();
int[] counters = new int[serverSize];
List<CacheNode> cacheNodeList = hashBalance.getCacheNodeList();
for (int i = 0; i < serverSize; i++) {
counters[i] = cacheNodeList.get(i).getData().size();
}
double standardDeviation = MathUtils.standardDiviation(counters);
System.out.println(StrUtil.format("物理节点 : {}个, 虚拟节点 : {}个, 标准差 : {}", serverSize, hashBalance.getVirtualNum(), standardDeviation));
//打印服务器情况
hashBalance.getCacheNodeList().forEach(x -> {
System.out.println(StrUtil.format("{} : {}", x.getIp(), x.getData().size()));
});
}
}

测试结果

  1. 物理节点 : 10个, 虚拟节点 : 50个, 标准差 : 11762.778795845818

```log

192.168.1.1 : 119251

192.168.1.2 : 109995

192.168.1.3 : 85112

192.168.1.4 : 84288

192.168.1.5 : 117143

192.168.1.6 : 101742

192.168.1.7 : 95739

192.168.1.8 : 91292

192.168.1.9 : 102372

192.168.1.10 : 93066

```

  1. 物理节点 : 10个, 虚拟节点 : 100个, 标准差 : 8582.096363942786

```

192.168.1.1 : 98606

192.168.1.2 : 101194

192.168.1.3 : 92934

192.168.1.4 : 90135

192.168.1.5 : 96867

192.168.1.6 : 106805

192.168.1.7 : 107885

192.168.1.8 : 96217

192.168.1.9 : 118988

192.168.1.10 : 90369

```

  1. 物理节点 : 10个, 虚拟节点 : 150个, 标准差 : 4501.1765128686075

```

192.168.1.1 : 98855

192.168.1.2 : 105370

192.168.1.3 : 94868

192.168.1.4 : 94463

192.168.1.5 : 98886

192.168.1.6 : 102116

192.168.1.7 : 97396

192.168.1.8 : 107686

192.168.1.9 : 104861

192.168.1.10 : 95499

```

  1. 物理节点 : 10个, 虚拟节点 : 200个, 标准差 : 6283.861392487903

```

192.168.1.1 : 106806

192.168.1.2 : 109879

192.168.1.3 : 94698

192.168.1.4 : 99010

192.168.1.5 : 90171

192.168.1.6 : 99349

192.168.1.7 : 106761

192.168.1.8 : 97480

192.168.1.9 : 103586

192.168.1.10 : 92260

```

  1. 物理节点 : 10个, 虚拟节点 : 250个, 标准差 : 5639.869679345436

```

192.168.1.1 : 105641

192.168.1.2 : 106517

192.168.1.3 : 94019

192.168.1.4 : 101799

192.168.1.5 : 87207

192.168.1.6 : 100337

192.168.1.7 : 100874

192.168.1.8 : 100788

192.168.1.9 : 105631

192.168.1.10 : 97187

```

用户头像

Jaye

关注

还未添加个人签名 2018.01.23 加入

还未添加个人简介

评论

发布
暂无评论
第05周 技术选型-01 命题作业