Feb 10 2022

Java实现一致性哈希算法，并搭建环境测试其负载均衡特性（一）

阿里云代理

分类：linux图文教程阅读次数

已被围观 1226 次

一. 简述一致性哈希算法

这儿不详细介绍一致性哈希算法的来源了，网上能方便地搜到许多介绍一致性哈希算法的好文章。本文主要想着手完结一致性哈希算法，并搭建一个环境进行实战测验。

在开端之前先整理一下算法的思路:

一致性哈希算法经过把每台服务器的哈希值打在哈希环上，把哈希环分成不同的段，然后对到来的恳求核算哈希值然后得知该恳求所归属的服务器。这个方法处理了传统服务器增减机器时需求从头核算哈希的麻烦。

但假如服务器的数量较少，或许导致核算出的哈希值相差较小，在哈希环上分布不均匀，导致某台服务器过载。为了处理负载均衡问题，咱们引进虚拟节点技能，为每台服务器分配一定数量的节点，经过节点的哈希值在哈希环上进行划分。这样一来，咱们就可以依据机器的功能为其分配节点，功能好就多分配一点，差就少一点，然后到达负载均衡。

二. 完结一致性哈希算法

奠定了整体思路后咱们开端考虑完结的细节

哈希算法的选择

选择能散列出32位整数的 FNV 算法, 因为该哈希函数或许发生负数, 需求作取绝对值处理.

恳求节点在哈希环上寻觅对应服务器的战略

战略为：新节点寻觅最近比且它大的节点, 比方说现在现已有环[0, 5, 7, 10], 来了个哈希值为6的节点, 那么它应该由哈希值为7对应的服务器处理. 假如恳求节点所核算的哈希值大于环上的所有节点, 那么就取第一个节点. 比方来了个11, 将分配到0所对应的节点.

哈希环的组织结构

开端的时分想过用顺序存储的结构存放，可是在一致性哈希中，最频频的操作是在集合中查找最近且比目标大的数. 假如用顺序存储结构的话，时间复杂度是收敛于O(N)的，而树形结构则为更优的O(logN)。

但凡事有两面，选用树形结构存储的代价是数据初始化的功率较低，并且运转期间假如有节点刺进删去的话功率也比较低。可是在实际中，服务器在一开端注册后基本上就不怎样变了，期间增减机器，宕机，机器修复等事情的频率相比起节点的查询简直是微不足道。所以本事例决定使用使用树形结构存储。

贴合上述要求，并且供给有序存储的，首要想到的是红黑树，并且Java中供给了红黑树的完结TreeMap。

虚拟节点与实在节点的映射联系

如何确定一个虚拟节点对应的实在节点也是个问题。理论上应该维护一张表记录实在节点与虚拟节点的映射联系。本事例为了演示，选用简单的字符串处理。

比方说服务器192.168.0.1:8888分配了 1000 个虚拟节点, 那么它的虚拟节点称号从192.168.0.1:8888@1一直到192.168.0.1:8888@1000。经过这样的处理，咱们在经过虚拟节点找实在节点时只需求裁剪字符串即可。

计划定制好后, 下面是详细代码：

public class ConsistentHashTest {
/**
* 服务器列表,一共有3台服务器供给服务, 将依据功能分配虚拟节点
*/
public static String[] servers = {
"192.168.0.1#100", //服务器1: 功能指数100, 将取得1000个虚拟节点
"192.168.0.2#100", //服务器2: 功能指数100, 将取得1000个虚拟节点
"192.168.0.3#30" //服务器3: 功能指数30, 将取得300个虚拟节点
};
/**
* 实在服务器列表, 因为增加与删去的频率比遍历高, 用链表存储比较划算
*/
private static ListrealNodes = new LinkedList<>();
/**
* 虚拟节点列表
*/
private static TreeMap virtualNodes = new TreeMap<>();
static{
for(String s : servers){
//把服务器加入实在服务器列表中
realNodes.add(s);
String[] strs = s.split("#");
//服务器称号, 省掉端口号
String name = strs[0];
//依据服务器功能给每台实在服务器分配虚拟节点, 并把虚拟节点放到虚拟节点列表中.
int virtualNodeNum = Integer.parseInt(strs[1]) * 10;
for(int i = 1; i <= virtualNodeNum; i++){
virtualNodes.put(FVNHash(name + "@" + i), name + "@" + i);
}
}
}
public static void main(String[] args) {
new Thread(new RequestProcess()).start();
}
static class RequestProcess implements Runnable{
@Override
public void run() {
String client = null;
while(true){
//模仿发生一个恳求
client = getN() + "." + getN() + "." + getN() + "." + getN() + ":" + (1000 + (int)(Math.random() * 9000));
//核算恳求的哈希值
int hash = FVNHash(client);
//判断恳求将由哪台服务器处理
System.out.println(client + " 的恳求将由 " + getServer(client) + " 处理");
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
private static String getServer(String client) {
//核算客户端恳求的哈希值
int hash = FVNHash(client);
//得到大于该哈希值的所有map集合
SortedMap subMap = virtualNodes.tailMap(hash);
//找到比该值大的第一个虚拟节点, 假如没有比它大的虚拟节点, 依据哈希环, 则回来第一个节点.
Integer targetKey = subMap.size() == 0 ? virtualNodes.firstKey() : subMap.firstKey();
//经过该虚拟节点取得实在节点的称号
String virtualNodeName = virtualNodes.get(targetKey);
String realNodeName = virtualNodeName.split("@")[0];
return realNodeName;
}
public static int getN(){
return (int)(Math.random() * 128);
}
public static int FVNHash(String data){
final int p = 16777619;
int hash = (int)2166136261L;
for(int i = 0; i < data.length(); i++)
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash < 0 ? Math.abs(hash) : hash;
}
}
/* 运转结果片段
55.1.13.47:6240 的恳求将由 192.168.0.1 处理
5.49.56.126:1105 的恳求将由 192.168.0.1 处理
90.41.8.88:6884 的恳求将由 192.168.0.2 处理
26.107.104.81:2989 的恳求将由 192.168.0.2 处理
114.66.6.56:8233 的恳求将由 192.168.0.1 处理
123.74.52.94:5523 的恳求将由 192.168.0.1 处理
104.59.60.2:7502 的恳求将由 192.168.0.2 处理
4.94.30.79:1299 的恳求将由 192.168.0.1 处理
10.44.37.73:9332 的恳求将由 192.168.0.2 处理
115.93.93.82:6333 的恳求将由 192.168.0.2 处理
15.24.97.66:9177 的恳求将由 192.168.0.2 处理
100.39.98.10:1023 的恳求将由 192.168.0.2 处理
61.118.87.26:5108 的恳求将由 192.168.0.2 处理
17.79.104.35:3901 的恳求将由 192.168.0.1 处理
95.36.5.25:8020 的恳求将由 192.168.0.2 处理
126.74.56.71:7792 的恳求将由 192.168.0.2 处理
14.63.56.45:8275 的恳求将由 192.168.0.1 处理
58.53.44.71:2089 的恳求将由 192.168.0.3 处理
80.64.57.43:6144 的恳求将由 192.168.0.2 处理
46.65.4.18:7649 的恳求将由 192.168.0.2 处理
57.35.27.62:9607 的恳求将由 192.168.0.2 处理
81.114.72.3:3444 的恳求将由 192.168.0.1 处理
38.18.61.26:6295 的恳求将由 192.168.0.2 处理
71.75.18.82:9686 的恳求将由 192.168.0.2 处理
26.11.98.111:3781 的恳求将由 192.168.0.1 处理
62.86.23.37:8570 的恳求将由 192.168.0.3 处理
*/