架构师训练营第 5 周作业
发布于: 2020 年 10 月 25 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 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: 99099Server Server_1: 106255Server Server_2: 105439Server Server_3: 89404Server Server_4: 94323Server Server_5: 102657Server Server_6: 103662Server Server_7: 97813Server Server_8: 100095Server Server_9: 101253Standard Devition: 5173.1678238129225
划线
评论
复制
发布于: 2020 年 10 月 25 日 阅读数: 9
netspecial
关注
还未添加个人签名 2011.07.20 加入
还未添加个人简介
评论