一致性哈希算法 - Consistent Hashing

步骤五：考察服务器的变动

前面讲过，通过 hash 算法然后求余的方法带来的最大问题就在于不能满足单调性，当服务器有所变动时，服务器会失效，进而对后台服务器造成巨大的冲击，现在就来分析Consistent Hashing 算法的单调性。

(1) 移除服务器。

考虑假设服务器 B 挂掉了，根据上面讲到的映射方法，这时受影响的将只是那些沿cache B 逆时针遍历直到下一个服务器(服务器 C )之间的对象，也即是本来映射到服务器 B上的那些对象。

因此这里仅需要变动对象 object4，将其重新映射到服务器 C 上即可，如下图所示。

(2) 添加服务器。

再考虑添加一台新的服务器 D 的情况，假设在这个环形 hash 空间中，服务器 D 被映射在对象 object2 和 object3 之间。这时受影响的仅是那些沿 cache D 逆时针遍历直到下一个服务器(服务器 B )之间的对象，将这些对象重新映射到服务器 D 上即可。 因此这里仅需要变动对象 object2，将其重新映射到服务器 D 上，如下图所示。

考量 hash 算法的另一个指标是 平衡性(Balance)，定义：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中，这样可以使所有的缓冲空间都得到利用。hash 算法并不能保证绝对的平衡，如果服务器较少，对象并不能被均匀地映射到服务器上，比如在上面的例子中，仅部署服务器 A 和服务器 C 的情况下，在 4 个对象中， 服务器 A 仅存储了 object1，而服务器 C 则存储了 object2、object3 和 object4，分布是很不均衡的。

为了解决这种情况，Consistent Hashing 引入了“虚拟节点”的概念，它可以如下定义：“虚拟节点”( virtual node )是实际节点在 hash 空间的复制品，一个实际节点对应若干个“虚拟节点”，这个对应个数也称为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。仍以仅部署服务器 A 和 服务器 C 的情况为例。现在我们引入虚拟节点，并设置“复制个数”为 2，这就意味着一共会存在4个“虚拟节点”，服务器 A1 和服务器 A2 代表服务器 A；服务器 C1 和服务器 C2 代表服务器 C，假设一种比较理想的情况如下图所示。

此时，对象到“虚拟节点”的映射关系为：objec1->服务器 A2；objec2->服务器 A1；objec3->服务器 C1；objec4->服务器 C2。 因此对象 object1 和 object2 都被映射到服务器 A 上，而 object3 和 object4 映射到 服务器 C 上，平衡性有了很大提高。引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 ->节点} 。

自此，一致性哈希算法的主要精髓就介绍完毕了，要想理解该算法，必然得亲自动手实现一个才能掌握。下面我们来实现一下Consistent Hashing算法。

二、实现一个简单的一致性哈希算法

1、在写Consistent Hashing算法之前，我们要先写一个对象和服务器共用的哈希函数，该哈希函数可以使对象和服务器都映射到同一hash数值空间区域。该hash算法我们用MD5压缩算法来实现。代码如下，关键地方参考注释：

package webspider.consistenthash;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
 * hash函数，根据key生成hash
 * 
 * @author typ
 * 
 */
public class HashFunction {
	/**
	 * 用MD5压缩算法，生成hashmap的key值
	 * 
	 * @param source
	 * @return
	 * @throws NoSuchAlgorithmException
	 */
	public String hash(String key) {
		String s = null;

		MessageDigest md;
		try {
			md = MessageDigest.getInstance("MD5");
			md.update(key.getBytes());
			// MD5的结果：128位的长整数，存放到tmp中
			byte tmp[] = md.digest();
			s = toHex(tmp);

		} catch (NoSuchAlgorithmException e) {
			e.printStackTrace();
		}
		return s;
	}

	/**
	 * 将二进制的长整数转换为16进制的数字，以字符串表示
	 * 
	 * @param bytes
	 * @return
	 */
	public String toHex(byte[] bytes) {
		// hexDigits的用处是：将任意字节转换为十六进制的数字
		char hexDigits[] = "0123456789abcdef".toCharArray();
		// MD5的结果：128位的长整数，用字节表示就是16个字节，用十六进制表示的话，使用两个字符，所以表示成十六进制需要32个字符
		char str[] = new char[16 * 2];
		int k = 0;
		for (int i = 0; i < 16; i++) {
			byte b = bytes[i];
			// 逻辑右移4位，与0xf（00001111）相与，为高四位的值，然后再hexDigits数组中找到对应的16进制值
			str[k++] = hexDigits[b >>> 4 & 0xf];
			// 与0xf（00001111）相与，为低四位的值，然后再hexDigits数组中找到对应的16进制值
			str[k++] = hexDigits[b & 0xf];

		}
		String s = new String(str);
		return s;
	}
}

package webspider.consistenthash;

import java.util.Collection;
import java.util.HashSet;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 利用一致性hash，计算得到对象要存放的服务器
 * 
 * @author typ
 * 
 * @param <T>
 */
public class ConsistentHash<T> {
	// 哈希函数类，这个类由自己定义，可以用MD5压缩法
	private final HashFunction hashFunction;
	// 虚拟节点个数
	private final int numberOfReplicas;
	// 建立有序的map
	private final SortedMap<String, T> circle = new TreeMap<String, T>();

	public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
			Collection<T> nodes) {
		this.hashFunction = hashFunction;
		this.numberOfReplicas = numberOfReplicas;
		for (T node : nodes) {
			add(node);
		}
	}

	/**
	 * map中添加服务器节点
	 * 
	 * @param node
	 */
	public void add(T node) {
		String key;
		// 虚拟节点所在的hash处，存放对应的实际的节点服务器
		for (int i = 0; i < numberOfReplicas; i++) {
			key = node.toString() + i;
			circle.put(hashFunction.hash(key), node);
		}
	}

	/**
	 * map中移除服务器节点
	 * 
	 * @param node
	 */
	public void remove(T node) {
		String key;
		for (int i = 0; i < numberOfReplicas; i++) {
			key = node.toString() + i;
			circle.remove(hashFunction.hash(key));
		}
	}

	/**
	 * 根据对象的key值，映射到hash表中，得到与对象hash值最近的服务器，就是对象待存放的服务器
	 * 
	 * @param key
	 * @return
	 */
	public T get(Object key) {
		if (circle.isEmpty()) {
			return null;
		}
		// 得到对象的hash值，根据该hash值找hash值最接近的服务器
		String hash = hashFunction.hash((String) key);
		// 以下为核心部分，寻找与上面hash最近的hash指向的服务器
		// 如果hash表circle中没有该hash值
		if (!circle.containsKey(hash)) {
			// tailMap为大于该hash值的circle的部分
			SortedMap<String, T> tailMap = circle.tailMap(hash);
			// tailMap.isEmpty()表示没有大于该hash的hash值
			// 如果没有大于该hash的hash值，那么从circle头开始找第一个；如果有大于该hash值得hash，那么就是第一个大于该hash值的hash为服务器
			// 既逻辑上构成一个环，如果达到最后，则从头开始
			hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
		}
		return circle.get(hash);
	}

	/**
	 * 测试
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		// 定义几个服务器的名称，存放到集合中
		Collection<String> nodes = new HashSet<String>();
		nodes.add("192.0.0.1");
		nodes.add("192.0.0.2");
		nodes.add("192.0.0.3");
		nodes.add("192.0.0.4");
		nodes.add("192.0.0.5");
		nodes.add("192.0.0.6");
		// MD5压缩算法实现的hash函数
		HashFunction hashFunction = new HashFunction();
		ConsistentHash<String> cHash = new ConsistentHash<String>(hashFunction,
				4, nodes);
		// 对象的key值为"google_baidu"
		String key[] = { "google", "163", "baidu", "sina" };
		// 利用一致性哈希，得到该对象应该存放的服务器
		String server[] = new String[key.length];
		for (int i = 0; i < key.length; i++) {
			server[i] = cHash.get(key[i]);
			System.out.println("对象 " + key[i] + " 存放于服务器： " + server[i]);
		}
	}
}