第五周作业

发布于: 2020 年 07 月 09 日

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

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

public class ConsistencyHash {
private final SortedMap<Integer,String> notes;
private int virtualNoteNumber = 0;
public ConsistencyHash(){
notes = new TreeMap<>();
}
public ConsistencyHash(int virtualNoteNumber){
this();
this.virtualNoteNumber = virtualNoteNumber;
}
public ConsistencyHash(List<String> notes,int virtualNoteNumber) {
this(virtualNoteNumber);
addNotes(notes);
}
public void addNotes(List<String> notes){
for (String note : notes) {
if(virtualNoteNumber > 0) {
for (int i = 0; i < this.virtualNoteNumber; i++) {
int noteHash = getHash(note+"###"+i);
this.notes.put(noteHash, note);
//System.out.println("["+note+"###"+i+"]加入集合,hash值:"+noteHash);
}
}else{
int noteHash = getHash(note);
this.notes.put(noteHash, note);
//System.out.println("["+note+"]加入集合,hash值:"+noteHash);
}
}
}
/**
* 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别
*/
public static int 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;
}
/**
* 得到路由节点
* @param key
* @return
*/
public String getServer(String key){
SortedMap<Integer, String> sortedMap = this.notes.tailMap(getHash(key));
if(sortedMap.size() <= 0){
sortedMap = this.notes;
}
return sortedMap.get(sortedMap.firstKey());
}
}

public class ConsistencyHashTest {
public static void main(String[] args) {
List<String> cacheNotes = new ArrayList<>(10);
cacheNotes.add("192.168.0.1:8081");
cacheNotes.add("192.168.0.2:8081");
cacheNotes.add("192.168.0.3:8081");
cacheNotes.add("192.168.0.4:8081");
cacheNotes.add("192.168.0.5:8081");
cacheNotes.add("192.168.0.6:8081");
cacheNotes.add("192.168.0.7:8081");
cacheNotes.add("192.168.0.8:8081");
cacheNotes.add("192.168.0.9:8081");
cacheNotes.add("192.168.0.10:8081");
int[] virtualNumber = new int[]{20,50,100,150,200,500,1000,2000,4000,8000};
for (int i = 0; i < 10; i++) {
test(cacheNotes,virtualNumber[i]);
}
}
private static void test(List<String> cacheNotes,int virtualNumber) {
ConsistencyHash consistencyHash = new ConsistencyHash(cacheNotes,virtualNumber);
Map<String, AtomicInteger> map = new HashMap<>();
int [] array = new int[virtualNumber];
for(int i = 0;i<1000000;i++){
String server = consistencyHash.getServer(i + "");
AtomicInteger atomicInteger = map.get(server);
if(null == atomicInteger){
atomicInteger = new AtomicInteger();
}
atomicInteger.addAndGet(1);
map.put(server,atomicInteger);
}
int i = 0;
for(String server : map.keySet()){
array[i] = map.get(server).get();
//System.out.println("服务器:"+server+",存储数量:"+map.get(server).get());
i++;
}
System.out.println("虚拟节点数:"+virtualNumber+",标准差:"+StandardDiviation(array));
}
//标准差σ=sqrt(s^2)
public static double StandardDiviation(int[] 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);
}
return Math.sqrt(dVar/m);
}
}

虚拟节点数:20,标准差:51652.91375130739
虚拟节点数:50,标准差:40269.389089977514
虚拟节点数:100,标准差:30162.625967246287
虚拟节点数:150,标准差:24993.333392638004
虚拟节点数:200,标准差:21821.283071350317
虚拟节点数:500,标准差:14017.568843704674
虚拟节点数:1000,标准差:9954.714354314743
虚拟节点数:2000,标准差:7054.797328626812

用户头像

好名字

关注

还未添加个人签名 2018.09.08 加入

还未添加个人简介

评论

发布
暂无评论
第五周作业