week5-（2 选 1）

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

public class SortedMapWithVirtualNode implements LoadBalancer{

private TreeMap<Integer, String> treeMapHash;

@Override

public void addServerNode(String serverNodeName) {

int hash = new GetHashCode().getHashCode(serverNodeName);

treeMapHash.put(hash, serverNodeName);

// logger.info("服务器节点：{} 上线", serverNodeName);

}

@Override

public void delServerNode(String serverNodeName) {

int hash = new GetHashCode().getHashCode(serverNodeName);

treeMapHash.remove(hash);

System.out.println("服务器节点："+serverNodeName+" 下线");

}

@Override

public String selectServerNode(String requestURL) {

int hash = new GetHashCode().getHashCode(requestURL);

// 向右寻找第一个 key

Map.Entry<Integer, String> subEntry = treeMapHash.ceilingEntry(hash);

// 设置成一个环，如果超过尾部，则取第一个点

subEntry = subEntry == null ? treeMapHash.firstEntry() : subEntry;

String VNNode = subEntry.getValue();

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

}

// 构建 Hash 环

public SortedMap<Integer, String> buildHash(TreeMap<Integer, String> treeMap) {

this.treeMapHash = treeMap;

return treeMapHash;

}

}

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

public class SortedMapWithVirtualNodeTest {

private static SortedMapWithVirtualNode sortedMapWithVirtualNode = new SortedMapWithVirtualNode();

//Hash 环

private static SortedMap<Integer, String> treeMapHash;

//服务器总数

private static final int SERVER_NUM = 100;

//每台服务器需要设置的虚拟节点数

private static final int VIRTUAL_NODES = 500;

//待加入 Hash 环的服务器列表

private static ArrayList<String> serverList = new ArrayList<>();

private static void init(){

//构造服务器数据

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

String s = new StringBuilder("192.168.0.").append(String.valueOf(i)).toString();

serverList.add(s);

}

//构建 Hash 环

treeMapHash = sortedMapWithVirtualNode.buildHash(new TreeMap<Integer,String>());

//将服务器的虚拟节点添加到 Hash 环中

for(String s : serverList){

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

String VNNode = s +"&&VN" + String.valueOf(i);

sortedMapWithVirtualNode.addServerNode(VNNode);

}

}

}

public static void main(String[] args) {

init();

// <节点，服务器>

HashMap<String, String> map = new HashMap<>();

// 请求节点

String[] nodes = new IPAddressGenerate().getIPAddress(1000000);

// <节点，服务器>

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

// 选择服务器

String serverIP = sortedMapWithVirtualNode.selectServerNode(nodes[i]);

// 记录服务器信息

map.put(nodes[i], serverIP);

}

System.out.println("虚拟节点,初始方差: " + new Analysis().analysis(map));

}

}