一致性哈希算法
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]) + "]");
}
}
}