高并发之Java实现一致性Hash负载算法

这里不解释一致性Hash是什么意思，仅提供一个一致性Hash实现方案

Hash工具类：

package com.liyong.hash.util;

public class HashUtils {
	/**
	 * 计算Hash值, 使用FNV1_32_HASH算法
	 * @param str
	 * @return hash值
	 */
	public static 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;
	}
}

该工具类生成一个0 ~ 2^32之间的Hash值。

第一种实现：

package com.liyong.hash.impl;

import java.util.HashMap;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.UUID;

import org.springframework.util.CollectionUtils;

import com.liyong.hash.util.HashUtils;

public class ConsistencySharding {
	/** 集群地址列表 */
	private static String[] addresses = { 
			"192.168.0.0:8080", 
			"192.168.0.1:8080", 
			"192.168.0.2:8080", 
			"192.168.0.3:8080",
			"192.168.0.4:8080",
			"192.168.0.5:8080",
			"192.168.0.6:8080",
			"192.168.0.7:8080"};

	/** 保存Hash环上的节点         地址的Hash值 -- 节点地址 */
	private static SortedMap<Integer, String> serverNodes = new TreeMap<>();

	static {
		// 将服务节点进行Hash
		for (String address : addresses) {
			int hash = HashUtils.getHash(address);
			serverNodes.put(hash, address);
		}
	}

	public static String getServer(String key) {
		int hash = HashUtils.getHash(key);
		// 取出所有大于hash值的部分
		SortedMap<Integer, String> subMap = serverNodes.tailMap(hash);
		if (CollectionUtils.isEmpty(subMap)) {
			// hash值在最尾部，应该映射到第一个group上
			return serverNodes.get(serverNodes.firstKey());
		}
		return subMap.get(subMap.firstKey());
	}

	public static void main(String[] args) {
		// 生成随机数进行测试
		Map<String, Integer> resMap = new HashMap<>();
		for (int i = 0; i < 1000000; i++) {
			String server = getServer(UUID.randomUUID().toString());
			if (resMap.containsKey(server)) {
				resMap.put(server, resMap.get(server) + 1);
			} else {
				resMap.put(server, 1);
			}
		}
		
		resMap.forEach((key, value) -> {
			System.out.println("server: " + key + " count: " + value + "(" + value / 10000.0D + "%)");
		});
	}
}

输出结果为： 

server: 192.168.0.5:8080 count: 318955(31.8955%)
server: 192.168.0.3:8080 count: 33351(3.3351%)
server: 192.168.0.6:8080 count: 26872(2.6872%)
server: 192.168.0.2:8080 count: 14853(1.4853%)
server: 192.168.0.7:8080 count: 24484(2.4484%)
server: 192.168.0.1:8080 count: 13730(1.373%)
server: 192.168.0.0:8080 count: 411076(41.1076%)
server: 192.168.0.4:8080 count: 156679(15.6679%)

说明：

1、在测试时，随机生成key值，通过key值进行hash，然后根据Hash查找最接近的那个Hash服务器节点。输出结果为整个过程分别负载到对应节点的概率，可以看到概率及其不均匀。

2、并且如果当一个负载高的节点突然挂掉，请求将全部落到下一个节点，及有可能造成服务器雪崩的情况。

3、减服务器时，由于数据漂移，会将全部流量漂移到下一个节点上。如果增加一台机器，也会让一个节点的一半请求漂移到新增节点上，对服务器的冲击非常大。

 

---

第二种实现：

引入虚拟节点概念 

package com.liyong.hash.impl;

import java.util.HashMap;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.UUID;

import com.liyong.hash.util.HashUtils;

public class ConsistencyShardingVirtualNodeDemo {
	/** 集群地址列表 */
	private static String[] groups = { 
			"192.168.0.0:8080", 
			"192.168.0.1:8080", 
			"192.168.0.2:8080", 
			"192.168.0.3:8080",
			"192.168.0.4:8080",
			"192.168.0.5:8080",
			"192.168.0.6:8080",
			"192.168.0.7:8080"};

	/** 虚拟节点映射关系 */
	private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();

	private static final int VIRTUAL_NODE_NUM = 1000;
	
	static {
		// 将虚拟节点映射到Hash环上
		for (int i = 0; i < groups.length; i++) {
			String group = groups[i];
			for (int j = 0; j < VIRTUAL_NODE_NUM; j++) {
				String virtualNodeName = getVirtualNodeName(group, j);
				int hash = HashUtils.getHash(virtualNodeName);
				virtualNodes.put(hash, virtualNodeName);
			}
		}
	}
	
	private static String getVirtualNodeName(String realName, int num) {
        return realName + "&VN-" + String.valueOf(num);
    }
	
	private static String getRealNodeName(String virtualName) {
        return virtualName.split("&")[0];
    }
	
	private static String getServer(String widgetKey) {
		int hash = HashUtils.getHash(widgetKey);
		// 只取出所有大于该hash值的部分而不必遍历整个Tree
		SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
		String virtualNodeName;
		if (subMap == null || subMap.isEmpty()) {
			// hash值在最尾部，应该映射到第一个group上
			virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
		} else {
			virtualNodeName = subMap.get(subMap.firstKey());
		}
		return getRealNodeName(virtualNodeName);
	}
	
	private static void randomTest() {
		Map<String, Integer> resMap = new HashMap<>();
		for (int i = 0; i < 1000000; i++) {
			String server = getServer(UUID.randomUUID().toString());
			if (resMap.containsKey(server)) {
				resMap.put(server, resMap.get(server) + 1);
			} else {
				resMap.put(server, 1);
			}
		}

		resMap.forEach((key, value) -> {
			System.out.println("server: " + key + " count: " + value + "(" + value / 10000.0D + "%)");
		});
	}
	
	public static void main(String[] args) {
		randomTest();
	}
}

输出结果：

server: 192.168.0.3:8080 count: 123243(12.3243%)
server: 192.168.0.5:8080 count: 132049(13.2049%)
server: 192.168.0.6:8080 count: 123281(12.3281%)
server: 192.168.0.2:8080 count: 124224(12.4224%)
server: 192.168.0.7:8080 count: 119611(11.9611%)
server: 192.168.0.1:8080 count: 121773(12.1773%)
server: 192.168.0.0:8080 count: 125197(12.5197%)
server: 192.168.0.4:8080 count: 130622(13.0622%)

 

说明：

1、引入虚拟节点后，代码中设置了一个节点会被虚拟成1000个节点，一个真实节点在一致Hash环上将占用1000个节点，让整个集群能更均匀的分布到一致Hash环上面。所以从统计结果可以看到Key落到各台服务器上非常均匀了。

2、在引入虚拟节点后，如果需要增减机器，都能将由于增减服务器而产生的请求漂移，均匀的落到其他机器上。