架构师训练营第五章作业

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

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

package consistentHash.geekbang.com;



import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.SortedMap;

import java.util.TreeMap;



public class ConsistentHash {

// 服务器列表

private String[] servers;



// 虚拟节点数

private int nodeNum;



// 真实结点列表

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



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

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

public ConsistentHash(String[] servers, int nodeNum) {

this.servers = servers;

this.nodeNum = nodeNum;

}



public void initialize() {

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

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

realNodes.add(servers[i]);

}



for (String str : realNodes) {

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

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

int hash = getHash(virtualNodeName);

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

virtualNodes.put(hash, virtualNodeName);

}

}

System.out.println();

}

// 使用FNV132HASH算法计算服务器的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) {

// 得到key的hash值

int hash = getHash(key);

// 得到大于该hash值的所有map

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

String virtualNode;

if (subMap.isEmpty()) {

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

Integer i = virtualNodes.firstKey();

// 返回对应的服务器

virtualNode = virtualNodes.get(i);

} else {

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

Integer i = subMap.firstKey();

// 返回对应的服务器

virtualNode = subMap.get(i);

}



if (virtualNode != null && virtualNode.length() != 0) {

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

}

return null;



}



public static void main(String[] args) {

String[] servers = { "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111",

"192.168.0.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111",

"192.168.0.10:111" };

int VIRTUAL_NODES = 100;

int KV_NUMBER = 100000;

ConsistentHash ch=new ConsistentHash(servers,VIRTUAL_NODES);

ch.initialize();

HashMap<String, Integer> hm = new HashMap<String, Integer>();

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

// key的hash值

String key = "key" + i;

int keyHash = getHash(key);

// 被路由到服务器

String serverNode = getServer(key);

//System.out.println("[" + key + "]的hash值为" + keyHash + ",被路由到节点[" + serverNode + "]");



if (hm.containsKey(serverNode) == false) {

hm.put(serverNode, 1);

} else {

hm.put(serverNode, hm.get(serverNode) + 1);

}



//System.out.println(hm.get(serverNode) + 1);

}

double sum = 0.0; //统计标准差的累积和

double avg =KV_NUMBER/10; //平均值

int cacheNum =0;

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

cacheNum=hm.get(servers[i]);

System.out.println("服务器"+servers[i]+"缓存数量"+hm.get(servers[i]));

sum=sum+(cacheNum-avg)*(cacheNum-avg);

}

System.out.println(KV_NUMBER+"个KV数据在10个服务器上分布的标准差是："+Math.sqrt(sum/10));



}



}