架构师训练营 Week5 命题作业

发布于: 22 小时前

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

解答:一致性哈希算法的几个关键点

1、环--一个有序的键值存储结构

2、虚拟节点

3、分布式哈希算法(某位大神引用Murmur Hash算法解决)

以下是完整代码

8import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import org.apache.coomons.lang3,RandomStringUtils;
import com.google.common.base.Charsets;
import com.google.common.hash.HashFunction;
import com.google.coomon.hash.Hashing;
public class ConsistentHashingImpl<T>{
//the number of virtual nodes
private final int numberOfReplies;
//the big ring
private final SortedMap<Integer, T> circle = new TreeMap<>();
private List<Integer> keyHashes = new ArrayList<>();
//Attention: the T node object must overwrite the toString method t oensure each node name
public ConsistentHashingImpl(int numberOfReplies, Collection<T> nodes){
this.numberOfReplies = numberOfReplies;
for(T node : nodes){
add(node);
}
}
public void add(T node){
for(int i = 0; i < numberOfReplies;i++){
int hashCode = hash(node.toString()+i);
circle.put(hashCode,node);
}
}
public void remove(T node){
for (int i = 0; i < numberOfReplies;i++){
int hashCode = hash(code.toString() + i);
circle.put(hashCode,node);
}
}
public T get(Object key){
if(circle.isEmpty()){
return null;
}
int hash = hash(String.valueOf(key));
keyHashes.add(hash);
System.out.println("hash(" + key + ")=" + hash);
if(!circle.containsKey(hash)){
SortedMap<Integer,T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty()? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
//hash Algrithm
public static int hash(String s){
HashFunction hashFunction = Hashing.murmue3_128(13);
return hashFunction.hashString(s,Charsets.UTF_8).hashCode();
}
//test
public static void main(String[] args){
int replies = 1000;
int numberOfNodes = 10;
if(args.length >= 2){
numOfNodes = Integer.valueOf(args[0]);
replies = Integer.valueOf(args[1]);
}
List<String> servers = new ArrayList<>();
for (int i = 0; i < numOfNodes; i++){
servers.add(RandomStringUtils.randomAlphabetic(8));
}
//create a clusters
ConsistentHashingImpl<String> cHash = new ConsistentHashingImpl<String>(replies,servers);
System.out.println(String.format("Created a ring which contains %s nodes ,eachnode"));
//Testing
HashMap<String, Integer> counter = new HashMap<>();
String node = "";
int sampleCnt = 1000000;
for (int i = 0; i < sampleCnt; i++) {
node = cHash.get(RandomStringUtils.randomAlphanumeric(6));
counter.put(node, counter.containsKey(node) ? counter.get(node) + 1 : 1);
}
// analysis
double mean = sampleCnt / numOfNodes;
double numi = 0.0;
double sum = 0.0;
Collection<Integer> values = counter.values();
System.out.println("Max: " + Collections.max(values));
System.out.println("Min: " + Collections.min(values));
int totalInCache = values.stream().mapToInt(v -> v.intValue()).sum();
System.out.println("Sum: " + totalInCache);
for (String nodeName : counter.keySet()) {
numi = Math.pow((counter.containsKey(nodeName) ? counter.get(nodeName) : 0) - mean, 2);
sum += numi;
}
double stdev = Math.sqrt(sum/numOfNodes);
System.out.println("Standard deviation: " + stdev);
}
}

此题借鉴了吴炳华同学的答案,本人并不是很会,会慢慢琢磨懂得。

用户头像

Up

关注

代码,思考,架构,阅读,旅行。 2018.11.02 加入

一起来进步吧,持续学习的小白!

评论

发布
暂无评论
架构师训练营Week5命题作业