架构师训练营 - 作业 5

发布于: 22 小时前

作业:用你熟悉的语言实现一致性hash算法,编写测试用例测试此算法,测试100万KV数据,10个服务器节点的情况下,计算服务器分布数量的标准差,以评估算法的存储负载的不均衡性

/**
* Create By lhu on 7/7/2020
*/
public class ConsistentHashTest {
// 物理节点
private Set<String> physicalNodes = new TreeSet<String>() {};
//虚拟节点
private int VIRTUAL_COPIES = 150; // 物理节点至虚拟节点的复制倍数
private TreeMap<Long, String> virtualNodes = new TreeMap<>();
/**
* hash算法,输出64位的值
*/
public long hash(final byte[] data, int length, int seed) {
final long m = 0xc6a4a7935bd1e995L;
final int r = 47;
long h = (seed & 0xffffffffl) ^ (length * m);
int length8 = length / 8;
for (int i = 0; i < length8; i++) {
final int i8 = i * 8;
long k = ((long) data[i8 + 0] & 0xff)
+ (((long) data[i8 + 1] & 0xff) << 8)
+ (((long) data[i8 + 2] & 0xff) << 16)
+ (((long) data[i8 + 3] & 0xff) << 24)
+ (((long) data[i8 + 4] & 0xff) << 32)
+ (((long) data[i8 + 5] & 0xff) << 40)
+ (((long) data[i8 + 6] & 0xff) << 48)
+ (((long) data[i8 + 7] & 0xff) << 56);
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
switch (length % 8) {
case 7:
h ^= (long) (data[(length & ~7) + 6] & 0xff) << 48;
case 6:
h ^= (long) (data[(length & ~7) + 5] & 0xff) << 40;
case 5:
h ^= (long) (data[(length & ~7) + 4] & 0xff) << 32;
case 4:
h ^= (long) (data[(length & ~7) + 3] & 0xff) << 24;
case 3:
h ^= (long) (data[(length & ~7) + 2] & 0xff) << 16;
case 2:
h ^= (long) (data[(length & ~7) + 1] & 0xff) << 8;
case 1:
h ^= (long) (data[length & ~7] & 0xff);
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
return h;
}
public long hash(final byte[] data, int length) {
return hash(data, length, 0xe17a1465);
}
public long Hash(final String data) {
byte[] bytes = toBytesWithoutEncoding(data);
return hash(bytes, bytes.length);
}
private byte[] toBytesWithoutEncoding(String str) {
int len = str.length();
int pos = 0;
byte[] buf = new byte[len << 1];
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
buf[pos++] = (byte) (c & 0xFF);
buf[pos++] = (byte) (c >> 8);
}
return buf;
}
// 根据物理节点,构建虚拟节点映射表,使用默认的虚拟节点数量1
public ConsistentHashTest(Set<String> physicalNodes) {
this(physicalNodes,0);
}
// 根据物理节点,构建虚拟节点映射表
public ConsistentHashTest(Set<String> physicalNodes, int virtualCopyCount) {
for (String nodeIp : physicalNodes) {
addPhysicalNode(nodeIp);
}
if (virtualCopyCount>=1)
VIRTUAL_COPIES = virtualCopyCount;
}
// 添加物理节点
public void addPhysicalNode(String nodeIp) {
for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
long hash = Hash(nodeIp + "#" + idx);
virtualNodes.put(hash, nodeIp);
}
physicalNodes.add(nodeIp);
}
// 删除物理节点
public void removePhysicalNode(String nodeIp) {
for (int idx = 0; idx < VIRTUAL_COPIES; ++idx) {
long hash = Hash(nodeIp + "#" + idx);
virtualNodes.remove(hash);
}
physicalNodes.remove(nodeIp);
}
// 查找对象映射的节点
public String getObjectNode(String object) {
long hash = Hash(object);
SortedMap<Long, String> tailMap = virtualNodes.tailMap(hash); // 所有大于 hash 的节点
Long key = tailMap.isEmpty() ? virtualNodes.firstKey() : tailMap.firstKey();
return virtualNodes.get(key);
}
// 统计对象与节点的映射关系
public void dumpObjectNodeMap(String label, int objectMin, int objectMax) {
// 统计
Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT
for (int object = objectMin; object <= objectMax; ++object) {
String nodeIp = getObjectNode(Integer.toString(object));
Integer count = objectNodeMap.get(nodeIp);
objectNodeMap.put(nodeIp, (count == null ? 1 : count + 1));
}
// 打印
double totalCount = objectMax - objectMin + 1;
System.out.println("======== " + label + " ========");
double[] counts4StandardDiviation = new double[objectNodeMap.entrySet().size()];
int i = 0;
for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) {
int count = entry.getValue();
counts4StandardDiviation[i] = count;
System.out.println("IP=" + entry.getKey() + ": count=" + count + "");
i++;
}
System.out.println("Physical node count: "+physicalNodes.size()+", Virtual node count per physical node: "+VIRTUAL_COPIES+", standard deviation: "+StandardDeviation(counts4StandardDiviation));
}
//方差s^2=[(x1-x)^2 +...(xn-x)^2]/n 或者s^2=[(x1-x)^2 +...(xn-x)^2]/(n-1) 标准差σ=sqrt(s^2)
public static double StandardDeviation(double[] x) {
int m=x.length;
double sum=0;
for(int i=0;i<m;i++){//求和
sum+=x[i];
}
double dAve=sum/m;//求平均值
double dVar=0;
for(int i=0;i<m;i++){//求方差
dVar+=(x[i]-dAve)*(x[i]-dAve);
}
//reture Math.sqrt(dVar/(m-1));
return Math.sqrt(dVar/m);
}
public static void main(String[] args) {
Set<String> physicalNodes = new TreeSet<String>() {
{
add("192.168.1.101");
add("192.168.1.102");
add("192.168.1.103");
add("192.168.1.104");
add("192.168.1.105");
add("192.168.1.106");
add("192.168.1.107");
add("192.168.1.108");
add("192.168.1.109");
add("192.168.1.110");
}
};
ConsistentHashTest ch = new ConsistentHashTest(physicalNodes,180);
// 初始情况
ch.dumpObjectNodeMap("初始情况", 1, 1000000);
// 删除物理节点
ch.removePhysicalNode("192.168.1.103");
ch.dumpObjectNodeMap("删除物理节点", 1, 1000000);
// 添加物理节点
ch.addPhysicalNode("192.168.1.111");
ch.addPhysicalNode("192.168.1.112");
ch.dumpObjectNodeMap("添加物理节点", 1, 1000000);
}
}

测试结果:

用户头像

进击的炮灰

关注

还未添加个人签名 2020.05.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营-作业5