一致性哈希算法原理和实现
在做服务器负载均衡时候可供选择的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法，比如在nginx+ats / haproxy+squid等CDN架构中，nginx/haproxy所使用的负载均衡算法便是一致性哈希。不仅如此在分布式系统中哈希算法也得到了广泛应用，研究过memcached缓存数据库的人都知道，memcached服务器端本身不提供分布式cache的一致性，而是由客户端来提供，使用一致性哈希的好处在于，增减集群的缓存服务器时，只有少量的缓存会失效，回源量较小。
1.问题的背景
假设一个分布式任务调度系统（负载均衡、分布式缓存服务器的常见该场景），执行任务的节点有n台机器，现有m个job在这n台机器上运行，这m个Job需要逐一映射到n个节点中一个，这时候可以选择一种简单的Hash算法来让m个Job可以均匀分布到n个节点中，比如:
hash(Job) % n
替换成分布式Cache也一样的有上述场景：有n个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到n个 cache 上呢
上面的公式看上去很完美，但考虑如下两种情形：
- n个节点中有一个宕掉了，这时候节点数量变更为
n-1，此时的映射公式变成hash(Job) % (n-1) - 由于Job数量增加，需要新增机器，此时的映射公式变成
hash(Job) % (n+1)
两种情形可以看到，基本上所有的Job会被重新分配到跟节点变动前不同的节点上，意味着需要迁移几乎所有正在运行的Job，想想这样会给系统带来多大的复杂性和性能损耗。缓存失效相当于少了一个调节池，对于服务器而言也是一场灾难，洪水般的访问都会直接冲向后台服务器；再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash 算法也做不到。有什么方法可以改变这个状况呢，一致性哈希的解决方案就出来了，它用于尽可能地降低节点变动带来的数据迁移开销。
2.一致性Hash性质
考虑到分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来，如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务，这是值得考虑的，尤其实在设计分布式缓存系统时，如果某台服务器失效，对于整个系统来说如果不采用合适的算法来保证一致性，那么缓存于系统中的所有数据都可能会失效（即由于系统节点数目发生动态变化时，客户端在请求某一对象时需要重新计算其hash值，由于hash值已经改变，所以很可能找不到保存该对象的服务器节点），因此一致性hash就显得至关重要，良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：
平衡性(Balance)
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。单调性(Monotonicity)
该性质是最需要考量的因素，单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区（简单理解：增加新节点，原有的部分内容可以映射过来）。简单的哈希算法往往不能满足单调性的要求，哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新，因此会带来极大计算和传输负荷。分散性(Spread)
好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。负载(Load)
负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。平滑性(Smoothness)
平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。
参考： 一致性哈希算法原理
3.一致性哈希算法原理
一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 ~ 232-1（即哈希值是一个32位无符号整形），整个空间按顺时针方向组织，0和232-1在零点中方向重合，整个哈希空间环如下：
下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下：
接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器。例如有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：
根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。
下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。
下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：
此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。
综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。另外，一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器，其环分布如下:
此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：
4.一致性Hash的java实现
1.确定哈希值空间
考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~232-1 次方的数值空间
2.计算节点哈希
将节点Node向这个值空间映射，取Node的Hash值，选取一个可以固定标识一个Node的属性值进行Hashing，假设以字符串形式输入，可以取Node标识的md5值，然后截取其中32位作为映射值。md5取值如下：
private byte[] md5(String value) {
MessageDigest md5;
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.reset();
byte[] bytes;
try {
bytes = value.getBytes("UTF-8");
} catch (UnsupportedEncodingException e) {
throw new IllegalStateException(e.getMessage(), e);
}
md5.update(bytes);
return md5.digest();
}
因为映射值只需要32位即可，所以可以利用以下方式计算最终值（number取0即可）：
private long hash(byte[] digest, int number) {
return (((long) (digest[3 + number * 4] & 0xFF) << 24)
| ((long) (digest[2 + number * 4] & 0xFF) << 16)
| ((long) (digest[1 + number * 4] & 0xFF) << 8)
| (digest[0 + number * 4] & 0xFF))
& 0xFFFFFFFFL;
}
3.有序缓存节点信息
把n个节点Node通过以上方式取得hash值，映射到环形值空间。算法中，将以有序Map的形式在内存中缓存每个节点的Hash值对应的物理节点信息。缓存于这个内存变量中：
private final TreeMap<Long, String> virtualNodes ;
4.数据向值空间映射
数据Job取hash的方式跟节点Node的方式一模一样，可以使用上述md5 => hash的方式同样将所有Job取得Hash映射到这个环中。
5.数据和节点映射
当节点和数据都被映射到这个环上后，可以设定一个规则把哪些数据hash值放在哪些节点Node Hash值上了，规则就是：沿着顺时针方向，数据hash值向后找到第一个Node Hash值即认为该数据hash值对应的数据映射到该Node上。至此，这一个从数据到节点的映射关系就确定了。顺时针找下一个Node Hash值算法如下：
public String select(Trigger trigger) {
String key = trigger.toString();
byte[] digest = md5(key);
String node = selectForKey(hash(digest, 0));
return node;
}
//根据数据的哈希值计算出所归属的节点Node
private String selectForKey(long hash) {
String node;
Long key = hash;
if (!virtualNodes.containsKey(key)) {
SortedMap<Long, String> tailMap = virtualNodes.tailMap(key);
if (tailMap.isEmpty()) {
key = virtualNodes.firstKey();
} else {
key = tailMap.firstKey();
}
}
node = virtualNodes.get(key);
return node;
}
Trigger是对Job一次触发任务的抽象，这里可忽略关注，重写了toString方法返回一个标记一个Job的唯一标志，计算Hash值，从节点Hash值中按规则寻找。
6.算法优化-虚拟节点
上述算法过程，会想到两个问题，第一，数据对象会不会分布不均匀，特别是新增节点或者减少节点时；第二，前文提到的如果想让部分节点多映射到一些数据对象，如何处理。虚拟节点这是解决这个问题。将一个物理节点虚拟出一定数量的虚拟节点，分散到这个值空间上，需要尽可能地随机分散开。
假设有4个物理节点Node，环上的每个色块代表一个虚拟节点涵盖的hash值区域，每种颜色代表一个物理节点。当物理节点较少时，虚拟节点数需要更高来确保更好的一致性表现。经测试，在物理节点为个位数时，虚拟节点可设置为160个，此时可带来较好的表现（后文会给出测试结果，160*n个总节点数情况下，如果发生一个节点变动，映射关系变化率基本为1/n，达到预期）。
具体做算法实现时，已知物理节点，虚拟节点数设置为160，可将这160*n的节点计算出Hash值，以Hash值为key，以物理节点标识为value，以有序Map的形式在内存中缓存，作为后续计算数据对象对应的物理节点时的查询数据。代码如下，virtualNodes中缓存着所有虚拟节点Hash值对应的物理节点信息。
public ConsistentHash(List<String> nodes) {
this.virtualNodes = new TreeMap<>();
this.identityHashCode = identityHashCode(nodes);
this.replicaNumber = 160;
for (String node : nodes) {
for (int i = 0; i < replicaNumber / 4; i++) {
byte[] digest = md5(node.toString() + i);
for (int h = 0; h < 4; h++) {
long m = hash(digest, h);
virtualNodes.put(m, node);
}
}
}
}
总结：
- 一致性哈希算法解决了负载均衡和分布式缓存中动态分配问题，使得节点的动态变化（服务器宕机、新增服务器节点）所造成的代价降到最低。
- 计算机的任何问题都可以通过增加一个虚拟层来解决，计算机硬件、网络和软件都是如此，网络的7层协议，每一层都可以看做是下一层的虚拟层，操作系统可以看做是计算机硬件的虚拟层，java虚拟机可以看做是操作系统的虚拟层。上述的解决节点负载不均衡的问题也采用了虚拟化的思路，将每台物理缓存服务器虚拟为缓存服务器，将虚拟服务器的hash值放在hash环上，数据key首先去寻找虚拟服务器节点，再映射得到真正的物理服务器的信息，这个思想可以在解决计算机问题上多多借鉴。
粘贴拷贝整理，如有侵权，请联系我删除
