第 5 周作业

用户头像
田振宇
关注
发布于: 2020 年 07 月 08 日



作业一:

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

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



public class HashUtils {
/**
* 使用FNV1_32_HASH算法计算Hash值
*/
public static long 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;
}
}



import lombok.Getter;
import lombok.Setter;
import org.apache.commons.lang.StringUtils;
import java.util.ArrayList;
import java.util.List;
/**
* 服务器节点
*/
@Getter
@Setter
public class Node {
private Integer id;
private String name;
private String uniqueKey;
private List<Long> hashes;
public Node(Integer id) {
this(id, 100);
}
public Node(Integer id, int virtualNodeNum) {
this.id = id;
this.name = "node-" + id;
this.uniqueKey = this.name;
this.hashes = new ArrayList<>(virtualNodeNum);
for (int i = 0; i < virtualNodeNum; i++) {
String key = this.uniqueKey + "#" + i;
this.hashes.add(HashUtils.getHash(StringUtils.reverse(key)));
}
}
}



import com.google.common.collect.Lists;
import java.util.*;
public class Cluster {
private List<Node> nodes = new ArrayList<>();
private TreeMap<Long, List<Node>> virtualNodes = new TreeMap<>();
public Cluster(List<Node> nodes) {
nodes.forEach(node -> this.addNode(node));
}
/**
* 根据key获取集群节点
* @param key
* @return
*/
public Node get(String key){
if(virtualNodes.size() == 0){
return null;
}
long hash = HashUtils.getHash(key);
Map.Entry<Long, List<Node>> entry = virtualNodes.higherEntry(hash) == null ? virtualNodes.higherEntry(0L) : virtualNodes.higherEntry(hash);
return entry.getValue().get(0);
}
/**
* 添加节点
* @param node
*/
public void addNode(Node node) {
nodes.add(node);
node.getHashes().forEach(hash -> {
if(virtualNodes.get(hash) == null){
virtualNodes.put(hash, Lists.newArrayList(node));
} else {
virtualNodes.get(hash).add(node);
}
});
}
/**
* 移除节点
* @param node
*/
public void removeNode(Node node) {
nodes.removeIf(o -> o.getId().equals(node.getId()));
node.getHashes().forEach(hash -> {
List<Node> nodes = virtualNodes.get(hash);
nodes.removeIf(o -> o.getId().equals(node.getId()));
if(nodes.size() == 0) {
virtualNodes.remove(hash);
}
});
}
}



测试:

import com.alibaba.fastjson.JSONObject;
import org.junit.Before;
import org.junit.Test;

import java.util.*;

public class ConsistencyHashTest {

Cluster cluster;

@Before
public void setup() {
List<Node> nodes = new ArrayList<>();
for (int i = 0; i < 10; i++) {
Node node = new Node(i, 100);
nodes.add(node);
}

cluster = new Cluster(nodes);
}

@Test
public void test(){
long t1 = System.currentTimeMillis();

int num = 1000000;

Map<Integer, Integer> nodeKeyNumMap = new HashMap<>();
for (int i = 0; i < num; i++) {
String key = UUID.randomUUID().toString();
Node node = cluster.get(key);
Integer n = nodeKeyNumMap.get(node.getId());
if(n == null) {
nodeKeyNumMap.put(node.getId(), 1);
} else {
nodeKeyNumMap.put(node.getId(), n + 1);
}
}

System.out.println(nodeKeyNumMap);

double[] datas = new double[10];
for (int i = 0; i < 10; i++) {
datas[i] = nodeKeyNumMap.get(i) !=null ? nodeKeyNumMap.get(i) : 0;
}
System.out.println(JSONObject.toJSONString(datas));

System.out.println("标准差:" + standardDeviation(datas));

long t2 = System.currentTimeMillis();
System.out.println("耗时"+(t2-t1)+"ms");
}


/**
* 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
* @param datas
* @return
*/
public static double variance(double[] datas) {
int n = datas.length;
double sum = 0;
for(int i=0;i<n;i++){//求和
sum += datas[i];
}
double avg = sum / n;//求平均值
double var = 0;
for(int i=0;i<n;i++){//求方差
var += (datas[i]-avg)*(datas[i]-avg);
}
return var/n;
}

/**
* 标准差σ=sqrt(variance)
* @param datas
* @return
*/
public static double standardDeviation(double[] datas) {
return Math.sqrt(variance(datas));
}

}



输出结果:

{0=108635, 1=87537, 2=93596, 3=106065, 4=104790, 5=87272, 6=98469, 7=99616, 8=104373, 9=109647}

标准差: 7793.011446161234

耗时1506ms



作业二:

根据当周学习情况,完成一篇学习总结



缓存

队列

一致性哈希

redis集群,分桶

数据库主从,binlog日志数据复制

数据库主主,故障自动切换



用户头像

田振宇

关注

还未添加个人签名 2018.05.10 加入

还未添加个人简介

评论

发布
暂无评论
第5周作业