높 은 병발 자바 일치 성 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 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 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 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.테스트 할 때 키 값 을 무 작위 로 생 성하 고 키 값 을 통 해 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 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 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 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 링 에 더욱 고 르 게 분포 할 수 있 도록 한다.그래서 통 계 를 보면 키 가 각 서버 에 고 르 게 떨 어 졌 다.
2.가상 노드 를 도입 한 후에 기 계 를 증감 해 야 한다 면 서버 증감 으로 인해 발생 하 는 요청 을 표류 시 켜 다른 기계 에 고 르 게 떨 어 뜨 릴 수 있다.