架构师 01 期，第五周课后作业



作业一（2 选 1）：

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

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



package com.zzw.www;



import java.util.LinkedList;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;

/**

• @author 臧子文

• @version 1.0

• @Date 创建时间：2020年10月25日 下午8:03:11

• @Date 最新修改时间：2020年10月25日 下午8:03:11

• @ClassName 一致性hash

• @Description 类描述

*/

public class ConsistentHashingWithoutVirtualNode {

//服务器列表

private static String[] servers = {"192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4",

"192.168.0.5","192.168.0.6", "192.168.0.7", "192.168.0.8", "192.168.0.9", "192.168.0.10"};



//真实节点列表

private static List<String> realNodes = new LinkedList<String>();



//虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称

private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();



//每个真实节点对应的虚拟节点的数

private static final int VIRTUAL_NODES = 100;



static{

//先把原始的服务器添加到真实结点列表中

for(int i=0; i<servers.length; i++)

realNodes.add(servers[i]);



//再添加虚拟节点

for (String str : realNodes){

for(int i=0; i<VIRTUAL_NODES; i++){

String virtualNodeName = str + "&&VN" + String.valueOf(i);

int hash = getHash(virtualNodeName);

System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);

virtualNodes.put(hash, virtualNodeName);

}

}

}



//获取hash值

private 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;

}



//得到应当路由到的结点

private static String getServer(String key){

int hash = getHash(key);

// 得到大于该Hash值的所有Map

SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);

String virtualNode=new String();

if(subMap.isEmpty()){

//如果没有比该key的hash值大的，则从第一个node开始

virtualNode = virtualNodes.get(virtualNodes.firstKey());

}else{

//第一个Key就是顺时针过去离node最近的那个结点

virtualNode = subMap.get(subMap.firstKey());

}

//virtualNode虚拟节点名称要截取一下

if(virtualNode!=null&&!("").equals(virtualNode)){

return virtualNode.substring(0, virtualNode.indexOf("&&"));

}

return virtualNode.substring(0,virtualNodes.get(virtualNodes.firstKey()).indexOf("&&"));

}

public static void main(String[] args){

int number= 100*10000;

int node1=0;

int node2=0;

int node3=0;

int node4=0;

int node5=0;

int node6=0;

int node7=0;

int node8=0;

int node9=0;

int node10=0;

for(int i=0; i<number; i++) {

String random = String.valueOf(Math.random());

String server = getServer(random);

System.out.println("[" + random + "]的hash值为" +

getHash(random) + ", 被路由到结点[" + server + "]");

if("192.168.0.1".equals(server)) {

node1=node1+1;

}else if("192.168.0.2".equals(server)) {

node2=node2+1;

}else if("192.168.0.3".equals(server)) {

node3=node3+1;

}else if("192.168.0.4".equals(server)) {

node4=node4+1;

}else if("192.168.0.5".equals(server)) {

node5=node5+1;

}else if("192.168.0.6".equals(server)) {

node6=node6+1;

}else if("192.168.0.7".equals(server)) {

node7=node7+1;

}else if("192.168.0.8".equals(server)) {

node8=node8+1;

}else if("192.168.0.9".equals(server)) {

node9=node9+1;

}else {

node10=node10+1;

}

}

System.out.println("node1="+node1+";node2="+node2+";node3="+node3+";node4="+node4+";node5="+node5+";node6="+node6

+";node7="+node7+";node8="+node8+";node9="+node9+";node10="+node10);

}

}



node1=107860;node2=93708;node3=101471;node4=84868;node5=113853;node6=110601;node7=116448;node8=89292;node9=92306;node10=89593