本文不做深层次探究，仅为记录笔者在用一致性哈希实现动态路由层的一些想法

前情提要

当用户登录时，我们需要为用户分配netty服务实例，所以我们从nacos上拉下来了服务实例列表 实际只有一个…项目体量很小，现在需要把用户分配到实例上

技术选型

我们选用一致性哈希。首先来看为什么摒弃普通哈希

普通哈希的缺点

普通哈希的计算核心是$hashCode(id)$ % $实例数n$，这就意味着，当节点增删的时候，几乎所有连接都需要被重置，性能开销太大，连接也不稳定

一致性哈希实现（部分）

具体代码在文末

数据结构设计

变量名类型作用
NodesTreeMap<Integer, String>存储 “虚拟节点哈希值→物理节点 URL” 的映射。
TreeMap 的有序性（红黑树实现）是实现 “顺时针查找下一个节点” 的关键。
VIRTUAL_NODESint每个物理节点对应的虚拟节点数量（默认 160），用于解决物理节点分布不均导致的负载倾斜。
instancesList<ServiceInstance>存储真实的服务实例（如 Netty 服务器实例），记录系统中当前可用的物理节点。
mapHashMap<String, ServiceInstance>建立 “物理节点 URL→服务实例” 的映射，用于通过 URL 快速找到对应的服务实例（如获取 IP、端口）。

实现逻辑

  • 把整个哈希空间虚拟成环形的，首尾相接
  • 把物理节点和虚拟节点（的url计算出来的哈希值）映射到环形空间上，每个节点对应的url都是真实的物理节点对应的url
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void init() {
        for (ServiceInstance instance : instances) {
            String url = instance.getUri().toString();// 真实url
            Nodes.put(getHash(url), url);
            map.put(url ,instance);// url映射服务实例
            for(int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(url + "#" + i );
                Nodes.put(hash, url);
            }
        }
    }
  • 提供方法找到真实url
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public String getServer(String clientInfo) {
        // 1. 计算userId的哈希值（映射到环上的一个位置）
        int hash = getHash(clientInfo);

        // 2. 关键：获取“顺时针方向的节点集合”
        // TreeMap的tailMap(hash)返回所有键（节点哈希值）>= hash的子映射
        // 这等价于在环上，从hash位置开始“顺时针”往后的所有节点
        SortedMap<Integer,String> subMap = Nodes.tailMap(hash);

        // 3. 找“顺时针第一个节点”
        Integer nodeIndex = subMap.firstKey();
        // 如果subMap为空（即hash位置往后没有节点，相当于绕到了环的末尾）
        // 就取整个环的第一个节点（相当于从环的起点继续顺时针找）
        if (nodeIndex == null) {
            nodeIndex = Nodes.firstKey();
        }

        // 4. 返回这个节点对应的真实URL
        return Nodes.get(nodeIndex);
    }
  • 通过url即可O(1)的找到相应的服务实例

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package com.flypiggyyoyoyo.im.authenticationservice.loadBalancer;

import org.springframework.cloud.client.ServiceInstance;

import java.util.*;
@SuppressWarnings({"all"})
public class ConsistentHash {

    private TreeMap<Integer,String> Nodes = new TreeMap();

    private int VIRTUAL_NODES = 160;//虚拟节点个数，用户指定，默认160

    private List<ServiceInstance> instances = new ArrayList<>();//真实物理节点集合

    public HashMap<String,ServiceInstance> map = new HashMap<>();//将服务实例与url地址一一映射

    public ConsistentHash(List<ServiceInstance> instances){
        this.instances = instances;
        init();
    }

    public void init() {
        for (ServiceInstance instance : instances) {
            String url = instance.getUri().toString();
            Nodes.put(getHash(url), url);
            map.put(url ,instance);
            for(int i = 0; i < VIRTUAL_NODES; i++) {
                int hash = getHash(url + "#" + i );
                Nodes.put(hash, url);
            }
        }
    }

    //得到url地址
    public String getServer(String clientInfo) {
        // 1. 计算userId的哈希值（映射到环上的一个位置）
        int hash = getHash(clientInfo);

        // 2. 关键：获取“顺时针方向的节点集合”
        // TreeMap的tailMap(hash)返回所有键（节点哈希值）>= hash的子映射
        // 这等价于在环上，从hash位置开始“顺时针”往后的所有节点
        SortedMap<Integer,String> subMap = Nodes.tailMap(hash);

        // 3. 找“顺时针第一个节点”
        Integer nodeIndex = subMap.firstKey();
        // 如果subMap为空（即hash位置往后没有节点，相当于绕到了环的末尾）
        // 就取整个环的第一个节点（相当于从环的起点继续顺时针找）
        if (nodeIndex == null) {
            nodeIndex = Nodes.firstKey();
        }

        // 4. 返回这个节点对应的真实URL
        return Nodes.get(nodeIndex);
    }

    //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
    private int getHash(String str) {
        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;
    }

    public void addNode(ServiceInstance instance) {
        instances.add(instance);
        String url = instance.getUri().toString();
        // 添加物理节点和虚拟节点
        Nodes.put(getHash(url), url);
        map.put(url, instance);
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            int hash = getHash(url + "#" + i);
            Nodes.put(hash, url);
        }
    }

    public void removeNode(ServiceInstance instance) {
        String url = instance.getUri().toString();
        instances.remove(instance);
        map.remove(url);

        // 移除物理节点和对应的所有虚拟节点
        Nodes.remove(getHash(url));
        for (int i = 0; i < VIRTUAL_NODES; i++) {
            Nodes.remove(getHash(url + "#" + i));
        }
    }

}