从Hash到一致性Hash原理(深度好文)
要讲一致性Hash原理,先从一般性Hash讲起,其实Hash的本质就是一个长度可变的数组,那为什么Hash的时间复杂度是O(1),而其他类型的数据结构查找都是要遍历来,遍历去,即便是树,二叉树,也是要经过几次比对,才能判定查找对象的位置,时间复杂度是O(Log(n)),那为什么Hash不用在数组里面遍历呢?
原因就在于Hash由存储的对象本身的HashCode以及数组的长度来决定在数组中的位置,这样一看到这两个条件就可以找到对象在数组中的位置而无需去遍历数组,但算出这个位置(即Hash值)在各个版本中是不同的,如HashMap就是各种位操作.一般我们自己是用HashCode对数组长度取模来算得对象的Hash值.但数组在位置不够的情况下会进行扩容,HashMap就是在3/4的时候进行扩容,但无论如何,扩容后,数组长度变化就要进行一次rehash,也就是重新计算每个对象在数组中的位置,即hash值.我们可以来看一下这段代码,虽然他没有HashMap那么复杂,但原理是一样,只不过计算Hash值的时候只用了最简单的取模.
public class SeparateChainingHashTable<T> {
private static final int DEFAULT_TABLE_SIZE = 10;
private List<T>[] theLists;
private int currentSize;
//调用带参构造器
public SeparateChainingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
//初始化一个数组,并把数组中每一个链表初始化
public SeparateChainingHashTable(int size) {
//初始化一个11位的数组
theLists = new LinkedList[nextPrime(size)];
for (int i = 0;i < theLists.length;i++) {
theLists[i] = new LinkedList<>();
}
}
private int myhash(T x) {
//取得对象的hash值
int hashVal = x.hashCode();
//hash值对数组长度取模
hashVal %= theLists.length;
if (hashVal < 0) {
hashVal += theLists.length;
}
return hashVal;
}
public void insert(T x) {
//从链表数组中取得第该对象哈希值位的链表.
List<T> whichList = theLists[myhash(x)];
//如果该链表不包含该对象,则链表添加该对象
if (!whichList.contains(x)) {
whichList.add(x);
//如果currentSize加1后大于数组的长度,扩容重新计算hash
if (++currentSize > theLists.length)
rehash();
}
}
public void remove(T x) {
List<T> whichList = theLists[myhash(x)];
if (whichList.contains(x)) {
whichList.remove(x);
currentSize--;
}
}
public boolean contains(T x) {
List<T> whichList = theLists[myhash(x)];
return whichList.contains(x);
}
public void makeEmpty() {
for (int i = 0;i < theLists.length;i++) {
theLists[i].clear();
}
currentSize = 0;
}
private void rehash() {
List<T>[] oldLists = theLists;
//进行一次扩容,扩容后长度为23,但是是一个新的数组
theLists = new List[nextPrime(2 * theLists.length)];
for(int j = 0;j < theLists.length;j++){
//初始化新数组中的每一个链表
theLists[j] = new LinkedList<T>();
}
//将新数组的currentSize归0
currentSize = 0;
//将原有的链表对象放入新数组中,并重新取模计算hash值
for (int i = 0; i < oldLists.length; i++) {
for (T item : oldLists[i]) {
insert(item);
}
}
}
private static int nextPrime(int num) {
if (num == 0 || num == 1 || num == 2) {
return 2;
}
if (num % 2 == 0) {
num++;
}
while (!isPrime(num)) {
num += 2;
}
return num;
}
private static boolean isPrime(int num) {
if (num == 2 || num == 3) {
return true;
}
if (num == 1 || num % 2 == 0) {
return false;
}
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) {
return false;
}
}
return true;
}
public void printTable() {
for(int i = 0;i < theLists.length;i++){
System.out.println("-----");
Iterator iterator = theLists[i].iterator();
while(iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Random random = new Random();
SeparateChainingHashTable<Integer> hashTable = new SeparateChainingHashTable<Integer>();
for (int i = 0; i < 30; i++) {
Integer tmp = random.nextInt(30);
hashTable.insert(tmp);
System.out.printf(tmp + "\t");
}
hashTable.printTable();
}
}运行结果:
0 17 15 20 14 8 7 2 28 12 10 5 25 11 22 13 9 17 20 8 8 14 28 28 24 4 11 26 9 15 ----- 0 ----- 24 ----- 2 25 ----- 26 ----- 4 ----- 5 28 -----
----- 7 ----- 8 ----- 9 ----- 10 ----- 11 ----- 12 ----- 13 ----- 14 ----- 15 -----
----- 17 -----
-----
----- 20 -----
----- 22
以上有两个数排在一起的是因为他们在rehash后有相同的hash值,并被放入链表的第一位和第二位.我们这里存储的对象是一个LinkedList的链表,而HashMap存储的是一个Map对象,至于你自己要写一个Hash要存储什么对象那是你自己的事.而他们的扩容方式也是不同的,至于如何扩容那也是你自己的事.
知道了普通Hash的原理,我们来看看一致性Hash.一致性Hash是由一个固定长度的Hash环构成,大小为2的32次方.一般用在服务器集群的增删节点的处理上,根据节点名称的Hash值（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。(以上斜体红色为次方).这里我们有一个问题,就是构建一致性Hash环用什么数据结构,难道也要用数组?当然不是,我们要根据我们的数据Key值进入Hash环的Hash值来查找服务器节点的Hash值的最短时间复杂度来决定,这就同样存在着查找的问题.
首先我们要对服务器节点的Hash值进行一个存储,是否要排序,如何查找他们最快,是解决这个问题的关键.一般在查找中的时间复杂度如下.
O(1) < O(log2N) < O(n) < O(N * log2N) < O(N2) < O(N3) < 2N < 3N < N!
我们知道查找最快的是树,比数组,链表都快.所以我们就选用红黑树来建立这个Hash环,而Java中已经有TreeMap和TreeSet都实现了红黑树.以TreeMap为例，TreeMap本身提供了一个tailMap(T fromKey)方法，支持从红黑树中查找比fromKey大的值的集合，但并不需要遍历整个数据结构。使用红黑树，可以使得查找的时间复杂度为O(logN).我们对ArrayList,LinkedList和TreeMap进行比对
可以看到，数据查找的效率，TreeMap是完胜的，其实再增大数据测试也是一样的，红黑树的数据结构决定了任何一个大于N的最小数据，它都只需要几次至几十次查找就可以查到。查找快,但是插入慢,这是红黑树的特点决定的.为了维护红黑树的平衡性,插入效率,红黑树在三种数据结构里是最差的.
定义出来的Hash环如下
private SortedMap<Long, T> circle = new TreeMap();重写HashCode的算法
为什么要重写HashCode算法,因为Java本身自带的HashCode算法连接太紧密.
public class StringHashCodeTest {
public static void main(String[] args) {
System.out.println("192.168.0.0:111的哈希值：" + "192.168.0.0:1111".hashCode());
System.out.println("192.168.0.1:111的哈希值：" + "192.168.0.1:1111".hashCode());
System.out.println("192.168.0.2:111的哈希值：" + "192.168.0.2:1111".hashCode());
System.out.println("192.168.0.3:111的哈希值：" + "192.168.0.3:1111".hashCode());
System.out.println("192.168.0.4:111的哈希值：" + "192.168.0.4:1111".hashCode());
}
}运行结果:
192.168.0.0:111的哈希值：1845870087 192.168.0.1:111的哈希值：1874499238 192.168.0.2:111的哈希值：1903128389 192.168.0.3:111的哈希值：1931757540 192.168.0.4:111的哈希值：1960386691
我们知道我们的Hash环是2的32次方,而这几个Hash值分布在这个环上面,简直挨的太紧,不利于进入服务器数据的均匀分布,因为进入服务器数据本身的Hash值可能在他们其间的很少很少,要么都进最大的的哈希值服务器,要么都进最小的哈希值服务器.所以我们要重写HashCode的计算方式使得服务器的Hash值在Hash环中均匀分布.以下是重写的两个计算Hash值的算法.
/**
* 使用MD5算法
* @param key
* @return
*/
private static long md5HashingAlg(String key) {
MessageDigest md5 = null;
try {
md5 = MessageDigest.getInstance("MD5");
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;
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
return 0l;
}
/**
* 使用FNV1hash算法
* @param key
* @return
*/
private static long fnv1HashingAlg(String key) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < key.length(); i++)
hash = (hash ^ key.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}虽然我们希望重写HashCode算法后,希望能够在Hash环中均匀分布服务器节点,但依然有可能分布不均匀.示例如下
public class ConsistentHashingWithoutVirtualNode {
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"};
private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
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();
}
private 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;
}
private static String getServer(String node) {
int hash = getHash(node);
Integer i;
//取得服务器Key大于传入数据的hash值的所有TreeMap节点
SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
//重新得到的TreeMap获得第一个Key
if (subMap.size() == 0) {
i = sortedMap.firstKey();
} else {
i = subMap.firstKey();
}
//得到该Key的服务器IP地址,端口号,即value.
return subMap.get(i);
}
public static void main(String[] args) {
String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
for (int i = 0; i < nodes.length; i++)
System.out.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
}
}运行结果:
[192.168.0.0:111]加入集合中, 其Hash值为575774686 [192.168.0.1:111]加入集合中, 其Hash值为8518713 [192.168.0.2:111]加入集合中, 其Hash值为1361847097 [192.168.0.3:111]加入集合中, 其Hash值为1171828661 [192.168.0.4:111]加入集合中, 其Hash值为1764547046
[127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111] [221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.4:111] [10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.4:111]
我们只有祭出终极必杀——虚拟节点
很明显上例中,有5个服务器节点,但是进入服务器集群的3个数据却有2个分配到了同一个服务器节点上,这分明就是负载不均.
现在我们将这些实体服务器节点进行虚拟化,给他们创造分身:虚拟节点.将一个物理节点拆分为多个虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布在Hash环上。
至于一个物理节点应该拆分为多少虚拟节点，下面可以先看一张图：
横轴表示需要为每台福利服务器扩展的虚拟节点倍数，纵轴表示的是实际物理服务器数。可以看出，物理服务器很少，需要更大的虚拟节点；反之物理服务器比较多，虚拟节点就可以少一些。比如有10台物理服务器，那么差不多需要为每台服务器增加100~200个虚拟节点才可以达到真正的负载均衡。
public class ConsistentHashingWithVirtualNode {
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"};
//真实节点,真实节点将不保存在Hash环中
private static List<String> realNodes = new LinkedList<String>();
//虚拟节点,Hash环
private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
//每个真实节点对应的虚拟节点数
private static final int VIRTUAL_NODES = 10;
static {
//添加真实节点
for (int i = 0; i < servers.length; i++)
realNodes.add(servers[i]);
//添加虚拟节点
for (String str : realNodes) {
for (int i = 0; i < VIRTUAL_NODES; i++) {
//给虚拟节点命名
String virtualNodeName = str + "&&VN" + String.valueOf(i);
//重写Hash算法后的虚拟节点的Hash值
int hash = getHash(virtualNodeName);
System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
virtualNodes.put(hash, virtualNodeName);
}
}
System.out.println();
}
private 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;
}
private static String getServer(String node) {
int hash = getHash(node);
String virtualNode;
Integer i;
SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
if (subMap.size() == 0) {
i = virtualNodes.firstKey();
virtualNode = virtualNodes.get(i);
} else {
i = subMap.firstKey();
virtualNode = subMap.get(i);
}
//返回真实节点的IP,端口,而不是虚拟节点名称
return virtualNode.substring(0, virtualNode.indexOf("&&"));
}
public static void main(String[] args) {
String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
for (int i = 0; i < nodes.length; i++)
System.out.println("[" + nodes[i] + "]的hash值为" + getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
}
}这样我们就可以得到密密麻麻的虚拟节点了(这里注意加入Hash环的只有虚拟节点,没有真实节点),运行结果如下:
虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1686427075 虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为354859081 虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1306497370 虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为817889914 虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为396663629 虚拟节点[192.168.0.0:111&&VN5]被添加, hash值为1220868525 虚拟节点[192.168.0.0:111&&VN6]被添加, hash值为213398042 虚拟节点[192.168.0.0:111&&VN7]被添加, hash值为1296671064 虚拟节点[192.168.0.0:111&&VN8]被添加, hash值为1718596903 虚拟节点[192.168.0.0:111&&VN9]被添加, hash值为1942098080 虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1032739288 虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为707592309 虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为302114528 虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为36526861 虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为848442551 虚拟节点[192.168.0.1:111&&VN5]被添加, hash值为779152590 虚拟节点[192.168.0.1:111&&VN6]被添加, hash值为105241177 虚拟节点[192.168.0.1:111&&VN7]被添加, hash值为391408881 虚拟节点[192.168.0.1:111&&VN8]被添加, hash值为1058221668 虚拟节点[192.168.0.1:111&&VN9]被添加, hash值为48793816 虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1452694222 虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为2023612840 虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为697907480 虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为790847074 虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为2010506136 虚拟节点[192.168.0.2:111&&VN5]被添加, hash值为866437122 虚拟节点[192.168.0.2:111&&VN6]被添加, hash值为149660808 虚拟节点[192.168.0.2:111&&VN7]被添加, hash值为1775912123 虚拟节点[192.168.0.2:111&&VN8]被添加, hash值为663860070 虚拟节点[192.168.0.2:111&&VN9]被添加, hash值为1126545273 虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为891084251 虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为1725031739 虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为1127720370 虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为676720500 虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为2050578780 虚拟节点[192.168.0.3:111&&VN5]被添加, hash值为490504949 虚拟节点[192.168.0.3:111&&VN6]被添加, hash值为2072852996 虚拟节点[192.168.0.3:111&&VN7]被添加, hash值为1058823147 虚拟节点[192.168.0.3:111&&VN8]被添加, hash值为2014386380 虚拟节点[192.168.0.3:111&&VN9]被添加, hash值为1763758471 虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为586921010 虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为184078390 虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为1331645117 虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为918790803 虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为1232193678 虚拟节点[192.168.0.4:111&&VN5]被添加, hash值为1322955826 虚拟节点[192.168.0.4:111&&VN6]被添加, hash值为922655758 虚拟节点[192.168.0.4:111&&VN7]被添加, hash值为1658127198 虚拟节点[192.168.0.4:111&&VN8]被添加, hash值为669639717 虚拟节点[192.168.0.4:111&&VN9]被添加, hash值为938227397
[127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.1:111] [221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.4:111] [10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.2:111]
由结果我们可以看出,进入服务器集群的3个数据被分配到了3个不同的真实服务器节点上面了.