# consistent-hash

**Repository Path**: luo_218/consistent-hash

## Basic Information

- **Project Name**: consistent-hash
- **Description**: 一致性hash算法
- **Primary Language**: Java
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-03-23
- **Last Updated**: 2024-02-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 普通Hash算法存在的问题
通过hash算法对客户端(ip等)进行转换, 转换后的结果对服务器节点值进行取模运算, 取模后的值就是服务请求对应的请求处理服务器, 如下图:  
![](https://luoblog.oss-cn-shanghai.aliyuncs.com/%E6%99%AE%E9%80%9Ahash.jpg)

当某个服务器节点宕机, 客户端可以通过重新取模运算并分配到其他可用的服务器上, 如下图:
![](https://luoblog.oss-cn-shanghai.aliyuncs.com/%E6%99%AE%E9%80%9Ahash%E6%9C%8D%E5%8A%A1%E5%99%A8%E7%BC%A9%E5%AE%B9.jpg)

但这使所有的客户端都重新进行取模运算, 造成大量的客户端请求被重定位到不同的服务器而造成请求所要使用的数据失效

### 一致性Hash算法
一致性Hash算法可以解决上面的问题. 当服务器增加或减少时, 不会对所有客户端产生影响.

#### 一致性Hash算法应满足的几个条件
> from百度百科
1. 平衡性: 指hash的结果应该平均分配到各个节点, 这样从算法上解决了负载均衡问题
2. 单调性: 指在新增或者删减节点时, 不影响系统正常运行
3. 分散性: 指数据应该分散地存放在分布式集群中的各个节点(节点自己可以有备份), 不必每个节点都存储所有的数据

#### Hash环
一致性哈希是将整个哈希值空间组织成一个虚拟的圆环, 如假设哈希函数的值空间为0-2^32-1(哈希值是32位无符号整形), 整个空间按顺时针方向组织, 0和2^32-1在零点中方向重合.

通过Hash算法将每个服务器节点映射到Hash环上的具体位置, 如下图:
![hash ring node](https://luoblog.oss-cn-shanghai.aliyuncs.com/hash%20ring%20serve%20node.jpg)

然后, 计算各个客户端的Hash值hash, 根据hash确定在环中的具体位置, 从此位置沿顺时针滚动, 遇到的第一个服务器节点就是其应该定位到的服务器.例如我们有A、B、C、D、E、F、G七个客户端, 经过哈希计算后, 在环空间上的位置如下:
![hash ring client](https://luoblog.oss-cn-shanghai.aliyuncs.com/hash%20ring%20client.jpg)

##### 减少服务器节点
假如节点3宕机了, 那么CilentD就会被定位到节点4, 而其他客户端均不会收到影响
![减少服务器节点](https://luoblog.oss-cn-shanghai.aliyuncs.com/%E5%87%8F%E5%B0%91%E8%8A%82%E7%82%B9.jpg)

##### 增加服务器节点
在如下位置增加节点5, ClientE、ClientF会被定位到节点5, 同样的其他节点不会受到影响
![增加节点](https://luoblog.oss-cn-shanghai.aliyuncs.com/%E5%A2%9E%E5%8A%A0%E8%8A%82%E7%82%B9.jpg)

##### 虚拟节点
以上均为服务器节点数多分布相对均衡的情况下, 若节点较少且分布不均匀, 就会出现客户端分配不均衡的问题. 如下图, 仅有两个服务器节点
![](https://luoblog.oss-cn-shanghai.aliyuncs.com/%E5%88%86%E9%85%8D%E4%B8%8D%E5%9D%87%E8%A1%A1.jpg)

为了解决这种数据存储不平衡的问题, 可以引入虚拟节点, 即对每个节点计算多个哈希值, 每个计算结果位置都放置在对应节点中, 这些节点称为虚拟节点.具体做法可以在服务器节点IP的后面增加编号来实现, 例如上面的情况, 可以为每个服务节点增加两个虚拟节点, 于是可以分为Node1、Node1#1、Node1#2、Node4、Node4#1、Node4#2具体如下图:

![虚拟节点](https://luoblog.oss-cn-shanghai.aliyuncs.com/%E8%99%9A%E6%8B%9F%E8%8A%82%E7%82%B9.jpg)


### 代码实现
#### 1. 普通Hash算法
```
public class Hash {

    public static void main(String[] args) {
        String[] clientArr = new String[]{"1.2.1.1", "2.3.3.2", "3.3.3.4", "4.3.5.4"};

        // 节点数
        int nodeNum = 5;

        for (String client : clientArr) {
            int hash = Math.abs(client.hashCode());
            int nodeIndex = hash % nodeNum;
            System.out.println("client: " + client + "\t" + "nodeIndex: " + nodeIndex);
        }
    }

}
```

#### 2. 一致性Hash算法
通过使用TreeMap代替Hash环
```
public class ConsistentHash {

    public static void main(String[] args) {
        // 初始化, 将节点hash映射到hash环上
        SortedMap<Integer, String> nodeMap = new TreeMap<>();
        String[] nodeArr = new String[]{"11.11.11.11", "22.22.22.22", "33.33.33.33", "44.44.44.44"};
        for (String node : nodeArr) {
            int nodeHash = Math.abs(node.hashCode());
            nodeMap.put(nodeHash, node);
        }

        // 客户端hash处理
        String[] clientArr = new String[]{"123.234.222.233", "147.12.23.3", "13.31.56.2", "10.22.34.56", "14.67.254.255", "10.2.2.1", "123.23.31.24"};
        for (String client : clientArr) {
            int clientHash = Math.abs(client.hashCode());
            // 顺时针最近的节点
            SortedMap<Integer, String> tailMap = nodeMap.tailMap(clientHash);
            // 可能为空, 取环中的第一个节点
            if (tailMap.isEmpty()) {
                Integer nodeIndex = nodeMap.firstKey();
                System.out.println("client: " + client + "\t" + "node: " + nodeMap.get(nodeIndex));
            } else {
                Integer nodeIndex = tailMap.firstKey();
                System.out.println("client: " + client + "\t" + "node: " + nodeMap.get(nodeIndex));
            }
        }
    }

}
```


#### 3. 一致性hash算法, 带有虚拟节点
```
public class ConsistentHashWithVirtualNode {

    public static void main(String[] args) {
        // 每个节点的虚拟节点格式
        int virtualNodeNum = 5;

        // 初始化, 将节点hash映射到hash环上
        SortedMap<Integer, String> nodeMap = new TreeMap<>();
        String[] nodeArr = new String[]{"11.11.11.11", "22.22.22.22"};
        for (String node : nodeArr) {
            int nodeHash = Math.abs(node.hashCode());
            nodeMap.put(nodeHash, node);

            // 虚拟节点处理
            for (int i = 0; i < virtualNodeNum; i++) {
                int virtualHash = (node + "#" + i).hashCode();
                nodeMap.put(virtualHash, node + "#" + i);
            }
        }

        // 客户端hash处理
        String[] clientArr = new String[]{"123.234.222.233", "147.12.23.3", "13.31.56.2", "10.22.34.56", "14.67.254.255", "10.2.2.1", "123.23.31.24"};
        for (String client : clientArr) {
            int clientHash = Math.abs(client.hashCode());
            // 顺时针最近的节点
            SortedMap<Integer, String> tailMap = nodeMap.tailMap(clientHash);
            // 可能为空, 取环中的第一个节点
            if (tailMap.isEmpty()) {
                Integer nodeIndex = nodeMap.firstKey();
                System.out.println("client: " + client + "\t" + "node: " + nodeMap.get(nodeIndex));
            } else {
                Integer nodeIndex = tailMap.firstKey();
                System.out.println("client: " + client + "\t" + "node: " + nodeMap.get(nodeIndex));
            }
        }
    }

}
```