一致性哈希consistent Hash的Java实现

在web架构中，分布式是个常见的架构设计。尤其是大家比较熟悉的Memcached，或者其他cache产品常常被设计成分布式集群。分布式往往采用hash(key)%n 的方式，但这种算法比较简单，便于实现和理解。但弊端是不能动态增删节点。比较合理的方法改用一致性哈希(consistent hashing)分布。一致性哈希，简单的说在移除 / 添加一个 cache 时，它能够尽可能小的改变已存在 key 映射关系，尽可能的满足单调性的要求。原理不再赘述，google和度娘都能得到答案。重点说一下最常见的实现方式。

 

Java中采用md5散列的方式，计算hash值，这样基本上能保证key散列出啦的hash不会重复。

private static long md5HashingAlg(String key) {
	MessageDigest md5 = MD5.get();
	md5.reset();
	md5.update(key.getBytes());
	byte[] bKey = md5.digest();
	long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)| (long) (bKey[0] & 0xFF);
	return res;
}

在对server节点初始化的时候，为了避免节点过少数据分布不均匀，都会初始化一些虚拟节点。具体方法上面计算hash值的方式类同，一把采用根据权重虚拟出来一些key，具体不过多介绍。

一致性哈希算法中，把哈希值想象成一个环状。有关一致性哈希算法，介绍里面说0~2^32-1的数据，不要误以为哈希环要保存2^32个数据。他只是说，哈希环存的key的哈希值范围是0~2^32-1，并不是key的哈希值要覆盖0~2^32-1所有数据。

既要保存hash值，又要保存对应的节点地址，貌似最简单的就是map，在Java中没有什么map可以满足是个环状。那就找一个排序的，0开头，2^32-1做尾。查找时查到尾没有结果，再返回头找这样可以理解为是个环状了。

在初始化的时候，把节点的hash和节点地址保存在TreeMap里，client查找时，根据key的hash值去treeMap得到自己应该查询的节点，往下查找比自己hash值大的，如果有则得到结果返回。如果没有，则回到treeMap的头，取第一个返回结果。

如图中所示：根据key计算出hash，去treeMap查找比key哈希大的那部分，取出第一个值就是结果。如果没有别key哈希大的部分，则取treeMap的第一个值。

代码的实现：

private final Long findPointFor(Long hv) {

		SortedMap<Long, String> tmap = this.consistentBuckets.tailMap(hv);

		return (tmap.isEmpty()) ? this.consistentBuckets.firstKey() : tmap.firstKey();
}