一致性哈希实现
发布于: 2020 年 07 月 08 日
一致性哈希是分布式系统中实现复杂均衡的关键技术，负载均衡的要求是把资源分布在不同的服务器节点上，一致性哈希就解决了改问题。
一致型哈希的原理是，先构造出一个长度为232整数环，根据N0-3的节点名称的hash值（分布为[0,232-1]）放到这个环上，数据也放在环上，数据落在就近的服务上。由于服务个数未知，当服务器个数比较少时，会出现负载不均衡。当服务节点增加或则减少时，也会出现大量的数据失效，这时就需要增加虚拟节点来实现。
实现一直哈希只有两个点：
1.哈希函数
2.数据哈希离服务节点哈希最近距离
代码实现如下：
服务节点 Node.java
public class Node { private String serverName; private Long hashCode; List<VisualNode> visualNodes; public Node(String serverName) { this.serverName = serverName; this.hashCode = HashMethod.hash(serverName, 0); } public void addVisualNode(VisualNode visualNode) { if (visualNodes == null) { visualNodes = new ArrayList<VisualNode>(); } visualNodes.add(visualNode); } public String getServerName() { return serverName; } public void setServerName(String serverName) { this.serverName = serverName; } public Long getHashCode() { return hashCode; } public void setHashCode(Long hashCode) { this.hashCode = hashCode; } public List<VisualNode> getVisualNodes() { return visualNodes; } @Override public String toString() { return "Node{" + "serverName='" + serverName + '\'' + ", hashCode=" + hashCode + ", visualNodes=" + visualNodes + '}'; }虚拟节点VisualNode.java
public class VisualNode { private String serverName; private long hashCode; public VisualNode(String serverName) { this.serverName = serverName; this.hashCode = HashMethod.hash(serverName, 0); } public String getServerName() { return serverName; } public void setServerName(String serverName) { this.serverName = serverName; } public long getHashCode() { return hashCode; } public void setHashCode(long hashCode) { this.hashCode = hashCode; }}hash函数类 HashMethod.java
public class HashMethod { public static Long hash(String nodeName, int number) { byte[] digest = md5(nodeName); return (((long) (digest[3 + number * 4] & 0xFF) << 24) | ((long) (digest[2 + number * 4] & 0xFF) << 16) | ((long) (digest[1 + number * 4] & 0xFF) << 8) | (digest[number * 4] & 0xFF)) & 0xFFFFFFFFL; } private static byte[] md5(String str) { try { MessageDigest md = MessageDigest.getInstance("MD5"); md.reset(); md.update(str.getBytes("UTF-8")); return md.digest(); } catch (NoSuchAlgorithmException e) { e.printStackTrace(); return null; } catch (UnsupportedEncodingException e) { e.printStackTrace(); return null; } }}一致性hash类 HashBalance.java
public class HashBalance { private List<Node> servers; private String[] serverNames; /** * 每台服务器设置的虚拟服务器个数 */ private int visualNodeNum ; /** * 虚拟服务器和主服务器的哈希值 value对应的主服务器信息 */ private TreeMap<Long, Node> serverMap; /** * 统计命中信息 */ private Map<Node, Long> countMap; /** * 测试数据的总个数 */ private long totalCount = 0; public HashBalance(String[] serverNames, int visualNodeNum) { this.serverNames = serverNames; this.visualNodeNum = visualNodeNum; //初始化服务器信息 initialization(); } private void initialization() { countMap = new HashMap<>(10); serverMap = new TreeMap<>(); servers = new ArrayList<>(serverNames.length); for (String serverName : serverNames) { Node node = new Node(serverName); serverMap.put(node.getHashCode(), node); for (int i = 0; i < visualNodeNum; i++) { String visualServerName = serverName + i; VisualNode visualNode = new VisualNode(visualServerName); node.addVisualNode(visualNode); serverMap.put(visualNode.getHashCode(), node); } servers.add(node); } } public List<Node> getServers() { return servers; } public void printNodes() { List<Node> nodes = getServers(); for (Node node : nodes) { System.out.println(node.getServerName() + ":" + node.getHashCode()); List<VisualNode> visualNodes = node.getVisualNodes(); for (VisualNode visualNode : visualNodes) { System.out.println("\t" + visualNode.getServerName() + ":" + visualNode.getHashCode()); } } } /** * 测试放数据到服务，统计信息 * @param key 数据库的key */ public void putKeyCount(String key) { Node node = selectNodeByKey(key); totalCount++; if (countMap.containsKey(node)) { long count = countMap.get(node); countMap.put(node, count + 1); }else{ countMap.put(node,1L); } } /** * 根据数据的key值来选择数据落在哪台服务器， * hash值离服务器的Hash值最近 * @param key 数据的Key值 * @return 服务器节点 */ public Node selectNodeByKey(String key) { Long hashcode = HashMethod.hash(key, 0); // 所有大于 hash 的节点 SortedMap<Long, Node> tailMap = serverMap.tailMap(hashcode); //取大于数据key的哈希值的第一个服务器 Long fistKey = tailMap.isEmpty() ? serverMap.firstKey() : tailMap.firstKey(); return serverMap.get(fistKey); } /** * 打印统计信息 */ public void printStatistics() { for (Map.Entry<Node, Long> entry : countMap.entrySet()) { Node node = entry.getKey(); long hitsCount = entry.getValue(); long percent = (int) (100 * hitsCount / totalCount); System.out.println("服务器节点【"+node.getServerName()+"】数据命中个数：【"+hitsCount+"】 分布率：【"+percent+"%】"); } } private Node getNodeByHashCode(Long hashCode) { return serverMap.get(hashCode); } public static void main(String[] args) { long count = 10000000; String[] serverNames = new String[]{"192.168.1:8080", "192.168.2:8080", "192.168.3:8080", "192.168.4:8080", "192.168.5:8080", "192.168.6:8080", "192.168.7:8080", "192.168.8:8080", "192.168.9:8080", "192.168.10:8080"}; HashBalance hashBalance = new HashBalance(serverNames, 150); hashBalance.printNodes(); for(int i=0;i<count;i++){ hashBalance.putKeyCount(i+"asf"); } hashBalance.printStatistics(); }}测试数据100w条数据，10台服务器，每台服务器有160个虚拟服务器测试结果如下：
服务器节点【192.168.1:8080】数据命中个数：【1010415】 分布率：【10%】服务器节点【192.168.1:8080】数据命中个数：【1018206】 分布率：【10%】服务器节点【192.168.9:8080】数据命中个数：【1044003】 分布率：【10%】服务器节点【192.168.7:8080】数据命中个数：【1066576】 分布率：【10%】服务器节点【192.168.6:8080】数据命中个数：【1032550】 分布率：【10%】服务器节点【192.168.10:8080】数据命中个数：【908494】 分布率：【9%】服务器节点【192.168.8:8080】数据命中个数：【859942】 分布率：【8%】服务器节点【192.168.4:8080】数据命中个数：【1055379】 分布率：【10%】服务器节点【192.168.5:8080】数据命中个数：【1029161】 分布率：【10%】服务器节点【192.168.2:8080】数据命中个数：【931117】 分布率：【9%】服务器节点【192.168.3:8080】数据命中个数：【1054572】 分布率：【10%】
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 51
elfkingw
关注
还未添加个人签名 2018.02.04 加入
还未添加个人简介
评论 (1 条评论)