一致性 hash
发布于: 2020 年 10 月 26 日
package org.seal.learn.learning.concurrent;import java.util.SortedMap;import java.util.TreeMap;/** * 一致性哈希算法 * * @author xiwang * @date 2020-10-25 00:00 */public class ConsistentHashMap { /** * 10个物理节点 */ private static String[] NODES = {"127.0.0.1:8001", "127.0.0.1:8002", "127.0.0.1:8003", "127.0.0.1:8004", "127.0.0.1:8005", "127.0.0.1:8006", "127.0.0.1:8007", "127.0.0.1:8008", "127.0.0.1:8009", "127.0.0.1:8010"}; /** * 使用SortedMap可以排序,再使用tailMap获取key比hashCode[client_ip]大的子map */ private static SortedMap<Integer, String> VIRTUAL_NODES; /** * 每个物理节点1个虚拟节点 */ private static int VIRTUAL_NODE_NUM = 1; /** * 模拟线上的10台服务器对应的10个虚拟节点 */ static { VIRTUAL_NODES = new TreeMap<>(); for (int i = 0, len = NODES.length; i < len; i++) { int hashCode; String virtualNode; for (int j = 0; j < VIRTUAL_NODE_NUM; j++) { // 计算节点的哈希值作为key,节点ip("127.0.0.1:8001|node|i")作为value virtualNode = NODES[i] + "|node|" + j; // 计算虚拟节点的hashCode hashCode = getHashCode(virtualNode); VIRTUAL_NODES.putIfAbsent(hashCode, virtualNode); System.out.println("add virtualNode:" + virtualNode + ", hashCode:" + hashCode); } } } /** * 使用32位FNV_1计算节点的hashCode * * @param node * @return */ private static int getHashCode(String node) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < node.length(); i++) { hash = (hash ^ node.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; } /** * 通过client_ip的哈希值路由一个虚拟节点,再映射到物理节点 * * @param clientIp * @return */ public static String routeServer(String clientIp) { int hashCode = getHashCode(clientIp); SortedMap<Integer, String> subMap = VIRTUAL_NODES.tailMap(hashCode); int firstKey = subMap.firstKey(); String virtualNode = subMap.get(firstKey); //寻找物理节点,把|node|x去掉 String actualNode = virtualNode.substring(0, virtualNode.length() - 7); System.out.println("clientIp:" + clientIp + ",hashcode:" + hashCode + ",virtualNode:" + virtualNode + ",actualNode:" + actualNode); return actualNode; } /** * @param args */ public static void main(String[] args) { String[] ips = {"127.0.0.1", "127.0.0.2"}; for (int i = 0, len = ips.length; i < len; i++) { String getNode = routeServer(ips[i]); System.out.println("放置节点:" + getNode); } }}
模拟获取了10个物理节点,每个节点1个虚拟节点,然后根据客户端ip利用hash算法计算所属节点,最终映射到物理节点
![](https://static001.geekbang.org/infoq/53/537b1ccc128d6dc2a7c9299794a4e368.png)
划线
评论
复制
发布于: 2020 年 10 月 26 日 阅读数: 12
![用户头像](http://static001.geekbang.org/account/avatar/00/12/6d/74/e5c94420.jpg?x-oss-process=image/resize,w_200,h_200)
袭望
关注
还未添加个人签名 2018.08.13 加入
还未添加个人简介
评论