week5

发布于: 8 小时前

标准差:

3162.2776601683795

每个server 产生 40 × 4 个虚拟节点

对每个key算hash,kv落到大于该值的第一个hash对应的server上

package pkg;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
public class ConsistentHashing {
private Map<Integer, String> hash = new HashMap<Integer, String>();
private List<Integer> keys = new ArrayList<Integer>();
public ConsistentHashing(List<String> servers) {
build(servers);
}
private static int computeHashKey(String k) {
MessageDigest md = null;
try {
md = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
System.exit(1);
}
md.update(k.getBytes());
byte[] bytes = md.digest();
return (bytes[0] & 0xff) << 24 | (bytes[1] & 0xff) << 16 | (bytes[2] & 0xff) << 8 | (bytes[3] & 0xff);
}
private void build(List<String> servers) {
MessageDigest md = null;
try {
md = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
System.exit(1);
}
for (String server : servers) {
for (int i = 0; i < 40; i++) {
String tmp = server + i;
md.update(tmp.getBytes());
byte[] bytes = md.digest();
int k = 0;
for (int j = 0; j < bytes.length; j += 4) {
k <<= 8;
k |= bytes[j] & 0xff;
k <<= 8;
k |= bytes[j + 1] & 0xff;
k <<= 8;
k |= bytes[j + 2] & 0xff;
k <<= 8;
k |= bytes[j + 3] & 0xff;
keys.add(k);
hash.put(k, server);
}
}
}
keys.sort(Comparator.<Integer>naturalOrder());
}
public String getServer(String inputKey) {
int hashValue = computeHashKey(inputKey);
int ret = Collections.binarySearch(keys, hashValue);
if (ret < 0) {
ret = -ret - 1;
}
if (ret == keys.size()) {
ret = 0;
}
return hash.get(ret);
}
public static void main(String[] args) {
List<String> servers = new ArrayList<>();
for (int i = 0; i < 10; i++) {
servers.add("server" + i);
}
ConsistentHashing consistentHashing = new ConsistentHashing(servers);
Map<String, Integer> count = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) {
String s = consistentHashing.getServer("k" + i);
count.merge(s, 0, Integer::sum);
}
double mean = 1_000_000 * 1.0 / count.size();
double d = 0;
for (String server : servers) {
int cnt = count.getOrDefault(server, 0);
d += Math.pow(cnt - mean, 2);
}
d /= count.size();
double result = Math.sqrt(d / mean);
System.out.println(result);
}
}

用户头像

Geek_2e7dd7

关注

还未添加个人签名 2018.11.08 加入

还未添加个人简介

评论

发布
暂无评论
week5