写点什么

第五周作业

用户头像
Griffenliu
关注
发布于: 2020 年 11 月 22 日



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

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



package com.lgf;
public class Hash32 {
/**
* Generates 32 bit hash from byte array of the given length and
* seed.
*
* @param data byte array to hash
* @param length length of the array to hash
* @param seed initial seed value
* @return 32 bit hash of the given array
*/
public static int hash32(final byte[] data, int length, int seed) {
// 'm' and 'r' are mixing constants generated offline.
// They're not really 'magic', they just happen to work well.
final int m = 0x5bd1e995;
final int r = 24;
// Initialize the hash to a random value
int h = seed^length;
int length4 = length/4;
for (int i=0; i<length4; i++) {
final int i4 = i*4;
int k = (data[i4+0]&0xff) +((data[i4+1]&0xff)<<8)
+((data[i4+2]&0xff)<<16) +((data[i4+3]&0xff)<<24);
k *= m;
k ^= k >>> r;
k *= m;
h *= m;
h ^= k;
}
// Handle the last few bytes of the input array
switch (length%4) {
case 3: h ^= (data[(length&~3) +2]&0xff) << 16;
case 2: h ^= (data[(length&~3) +1]&0xff) << 8;
case 1: h ^= (data[length&~3]&0xff);
h *= m;
}
h ^= h >>> 13;
h *= m;
h ^= h >>> 15;
return h;
}
/**
* Generates 32 bit hash from byte array with default seed value.
*
* @param data byte array to hash
* @param length length of the array to hash
* @return 32 bit hash of the given array
*/
public static int hash32(final byte[] data, int length) {
return hash32(data, length, 0x9747b28c);
}
/**
* Generates 32 bit hash from a string.
*
* @param text string to hash
* @return 32 bit hash of the given string
*/
public static int hash(final String text) {
final byte[] bytes = text.getBytes();
return hash32(bytes, bytes.length);
}
}



package com.lgf;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
public class ConsistentHash {
private int virtualNodeNumbers = 1;
private TreeMap<Integer, String> virtualNodes = new TreeMap<>();
public ConsistentHash(List<String> servers){
this(servers, 150);
}
public ConsistentHash(List<String> servers, int virtualNodeNumbers){
assert (servers!=null);
this.virtualNodeNumbers = virtualNodeNumbers;
// 初始化虚拟节点
for(String server: servers){
for(int i=0;i<this.virtualNodeNumbers;i++){
// 生成hashcode
String key = server + "_virtual_node" + i;
int code = getHashcode(key);
// System.out.println("hashcode: " + code);
virtualNodes.put(code, server);
}
}
}
private static int getHashcode(String key){
return Math.abs(Hash32.hash(key));
}
public String getServer(String key) {
int hashcode = getHashcode(key);
SortedMap<Integer, String> sortedNodes = virtualNodes.tailMap(hashcode);
if(sortedNodes.isEmpty()){
return virtualNodes.get(virtualNodes.firstKey());
}else {
return virtualNodes.get(sortedNodes.firstKey());
}
}
public static void main(String[] args){
List<String> servers = new ArrayList<>();
servers.add("172.30.200.100");
servers.add("172.30.200.101");
servers.add("172.30.200.102");
servers.add("172.30.200.103");
servers.add("172.30.200.104");
servers.add("172.30.200.105");
servers.add("172.30.200.106");
servers.add("172.30.200.107");
servers.add("172.30.200.108");
servers.add("172.30.200.109");
servers.add("172.30.200.110");
ConsistentHash chash = new ConsistentHash(servers);
Map<String, AtomicInteger> counters = new HashMap<>();
for(int i=0;i<1000000;i++){
String key = "test(" + i + ")";
String server = chash.getServer(key);
AtomicInteger counter = counters.get(server);
if(counter==null){
counter = new AtomicInteger(0);
counters.put(server, counter);
}
int count = counter.incrementAndGet();
System.out.println(key + " in server: " + server + ", count: " + count);
}
System.out.println(counters);
}
}



{172.30.200.105=79388, 172.30.200.104=82971, 172.30.200.103=89800, 172.30.200.102=90917, 172.30.200.109=98879, 172.30.200.108=88523, 172.30.200.107=92379, 172.30.200.106=87194, 172.30.200.101=93622, 172.30.200.100=99036, 172.30.200.110=97291}



发布于: 2020 年 11 月 22 日阅读数: 60
用户头像

Griffenliu

关注

还未添加个人签名 2020.07.05 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业