一致性哈希算法

2019-01-29

1 概念

参见一致性哈希算法每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)一致性哈希

原理: 将哈希空间$[0, 2^n-1]$看成一个哈希环,每个服务器节点都配置到哈希环上。每个数据对象通过哈希取模得到哈希值之后,存放到哈希环中顺时针方向第一个大于等于该哈希值的节点上

一致性哈希算法

一致性哈希在增加或者删除节点时只会影响到哈希环中相邻的节点,例如下图中新增节点 X,只需要将它前一个节点 C 上的数据重新进行分布即可,对于节点 A、B、D 都没有影响。
一致性哈希算法

虚拟节点: 当服务器节点比较少的时候,会出现一个问题,就是此时必然造成大量数据集中到一个节点上面,极少数数据集中到另外的节点上面。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。

“虚拟节点” 的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前,计算 cache A 的 hash 值:
Hash(“192.168.1.100”);
引入“虚拟节点”后,计算“虚拟节点”NODE1-1和NODE1-2的hash值:
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2

2 实现

参见一致性哈希算法学习及JAVA代码实现分析对一致性Hash算法,Java代码实现的深入研究

/**
 * 不带虚拟节点的一致性Hash算法
 * @author 
 *
 */
public class ConsistentHashing {
	// 待添加入Hash环的服务器列表
	private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111","192.168.0.3:111", "192.168.0.4:111"};
	// key表示服务器的hash值,value表示服务器的名称
	// TreeMap默认是升序的,如果我们需要改变排序方式,则需要使用比较器:Comparator
	private static SortedMap<Integer, String> sortedMap = new TreeMap<>();
	// 程序初始化,将所有的服务器放入sortedMap中
	static{
		for(int i = 0; i < servers.length; i++) {
			int hash = getHash(servers[i]);
			System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
			sortedMap.put(hash, servers[i]);
		}
		System.out.println();
	}
	
	/**
	 * 得到应当路由到的结点
	 * @param data
	 * @return
	 */
	public static String getServer(String data) {
		// 得到待缓存数据的Hash值
		int hash = getHash(data);
		// 得到大于该Hash值的所有Map
		SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
		// 第一个Key就是顺时针过去离node最近的那个结点
		int i;
		String res;
		if (subMap.isEmpty()) {
			i = sortedMap.firstKey();
			res = sortedMap.get(i);
		} else {
			i = subMap.firstKey();
			res = subMap.get(i);
		}
		return res;
	}
	
	/**
	 * 重写hash算法,为了让数据分布均匀
	 * @param data
	 * @return
	 */
	public static int getHash(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;
		// 如果算出来的值为负数则取其绝对值
		if (hash < 0){
			hash = Math.abs(hash);
		}
		return hash;
	}
	
	public static void main(String[] args) {
		String[] datas = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
		for (int i = 0; i < datas.length; i++) {
			System.out.println("[" + datas[i] + "]的hash值为" + getHash(datas[i]) + ", 被路由到结点[" + getServer(datas[i]) + "]");
		}
	}
}