架构师训练营第 5 周作业

用户头像
netspecial
关注
发布于: 2020 年 10 月 25 日



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

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



Node.java

public class Node {
private String name;
private String ip;
private int numOfKV;
public Node(String name, String ip) {
this.name = name;
this.ip = ip;
this.numOfKV = 0;
}
public String getName(){
return this.name;
}
public String getIp(){
return this.ip;
}
public void addKV(){
this.numOfKV ++;
}
public int getNumOfKV(){
return this.numOfKV;
}
}



ConsistentHash.java

import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHash {
// Virtual Nodes
private SortedMap<Integer, Node> vnodes;
// Server Node
private List<Node> nodes;
// Number of virtual nodes per server node
private int numPerNode;
public ConsistentHash(List<Node> nodes, int numPerNode){
this.nodes = nodes;
this.numPerNode = numPerNode;
init();
}
private void init(){
this.vnodes = new TreeMap<Integer, Node>();
// Generate virtual nodes
for(Node node : nodes) {
for (int i = 0; i < numPerNode; i++) {
int hashCode = getHash("NODE-" + node.getIp() + "-V-" + i);
vnodes.put(hashCode, node);
// System.out.println("Virtual Node hash: " + hashCode + " of " + node.getName() + " has been added.");
}
}
}
public Node getNode(String key){
int hashCode = getHash(key);
SortedMap<Integer, Node> tail = this.vnodes.tailMap(hashCode);
Node node = null;
if(tail.size() == 0) {
node = vnodes.get(this.vnodes.firstKey());
} else {
node = tail.get(tail.firstKey());
}
if(node != null) {
node.addKV();
}
return node;
}
// FNV1_32_HASH
private static int getHash(String str) {
// int hash = str.hashCode();
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;
}
}



ConsistentHashTest.java

import java.util.ArrayList;
import java.util.List;
public class ConsistentHashTest {
public static void main(String[] args){
final int numOfNodes = 10;
final int numPerNode = 150;
final int numOfKV = 1000000;
String name;
String ip;
List<Node> servers = new ArrayList<Node>();
for (int i = 0; i < numOfNodes; i++) {
name = String.format("Server_%d", i);
ip = String.format("192.168.0.%d", i);
Node node = new Node(name, ip);
servers.add(node);
}
ConsistentHash conHash = new ConsistentHash(servers, numPerNode);
for (int n = 0; n < numOfKV; n++){
String key = String.format("Client_%d", n);
Node server = conHash.getNode(key);
// System.out.println(key + " has been put into " + server.getName());
}
// Calculate average KV of Server
double average = numOfKV/numOfNodes;
double std = 0;
for (int i = 0; i < servers.size(); i++) {
Node server = servers.get(i);
System.out.println("Server " + server.getName() + ": " + server.getNumOfKV());
std += Math.pow((server.getNumOfKV() - average), 2);
}
// Calculate standard devition
std = Math.sqrt((std/(numOfNodes - 1)));
System.out.println("Standard Devition: " + std);
}
}



结果:

Server Server_0: 99099
Server Server_1: 106255
Server Server_2: 105439
Server Server_3: 89404
Server Server_4: 94323
Server Server_5: 102657
Server Server_6: 103662
Server Server_7: 97813
Server Server_8: 100095
Server Server_9: 101253
Standard Devition: 5173.1678238129225



用户头像

netspecial

关注

还未添加个人签名 2011.07.20 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第 5 周作业