一致性哈希 Consitent Hashing
一致性哈希是分布式计算中最重要的概念之一，简单来说，分布式计算就是把一台机器没有办法完成的事情分给多台机器做，分给多台机器做有很多策略，比如随机分配，或者循环分配(round-robin)，这两种分配方法很简单，但是也有局限性，假如所有机器存的东西都一样，业务逻辑都一样，那么这样分配就没问题，但是，如果因为数据量太大，一台机器存不下需要分配到多台机器上，我们就不能简单地对请求进行随机或者循环分配，我们需要把请求分到存有请求数据的那台机器上。为了实现这种分配，简单直接的办法就是做一个哈希，通过key来找到。
假设我们使用传统哈希，现在有100台机器，当需要新增10台机器时就可能需要改变哈希表的容量，可能导致我们要把大部分的key都重新映射，key重新映射之后，一个key对应的机器可能改变了，这样就要把数据从原来那台机器上迁移到新的机器上，如果所有的key对应的机器都变了，各台机器数据都要重新交换，导致操作成本很高，效率很低。为了避免这样的问题，分布式计算往往使用一致性哈希。一致性哈希和传统的哈希最大的区别，就是哈希表在resize的时候不需要把所有的key都重新映射。
原理
一致性哈希首先定义一个圆环，然后把圆环看成是无数个点组成的，假设起点对应的是0，终点可以对应一个非常大的数字（比如2^32)，然后把每台机器映射到圆环上的不同位置。当查找某个key所对应的机器时，通过一致性哈希算法算出该key所对应的位置，然后从该位置顺时针/逆时针方向查找，遇到的第一台机器就是存有该key对应数据的机器。
举个例子，假设我们定义一个圆环，起点是0，终点是1000(也就是起点），在100，200，300 ... 900 的地方各有一台机器，这样就有10台机器。现在有一个请求，key = 536，哈希算法是 key mod 1000, 算出来的结果也是536，我们在圆环上从536开始找，直到600的时候发现有一台机器，那么600节点上的机器就是存有这个key所对应数据的机器。也就是说，600这台机器存的是501到600这个范围的key所对应的数据，或者是处理所对应的请求。写的过程也一样，找到所对应的节点写入。
增加删除机器
当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。
备份
还是上面的例子，假设我们定义一个圆环，起点是0，终点是1000(也就是起点），在100，200，300 ... 900 的地方各有一台机器，这样就有10台机器。当key = 536 的时候，顺时针找到的第一台机器是600，如果我们使用的是主从模式（master-slave)备份，那么就把600作为这个key所存的数据的主节点(master），然后继续顺时针寻找节点，把顺时针后面的k个节点(假设k=2，那么就是700和800的机器) 作为从节点（slave）。如果600 master节点出现故障，可以把700机器变成主节点，然后把800，900变成从节点。写入的时候可以只写入主节点，然后通过异步等方式来把数据同步到其他节点上。
优化
以上是是一致性哈希的基本理念，在以上的基础上，我们还可以做一些优化。因为实际操作中常常出现key分布不均的情况，在这种情况下如果每台机器负责处理一个很大的范围内的key，可能会造成负载不均衡。
同时，新增机器也会造成负载不均衡，比如机器600负责处理501-600范围内的key，机器500负责处理401到500范围内的key，当我们在新加一个550节点的时候，这个新节点负责501到550的key，机器600负责551-600的key，但是其他的机器比如500还是需要处理更大范围的key，导致了负载不均衡，这样新增机器的作用就不大了。
另外，如果减少一个节点，比如减少500节点，那么现在600节点要处理401-600范围内的key，可能会因为负载突然增加，导致故障，600节点故障之后700节点需要承受更大负载，如果还是无法处理，便造成雪崩。
虚拟节点 Virtual Node
为了解决这些问题，我们可以对一致性哈希做进一步的优化，也就是引进虚拟节点（Virtual Node）。
虚拟节点就是把物理机器（节点）再拆分成多个虚拟节点，让虚拟节点均匀分布在哈希圆环上，当使用key在圆环上找对应的节点的时候，我们找的是虚拟节点，然后再通过这个虚拟节点找到实际的加点，这样映射的时候让不同的key分布的更均匀。
举个例子，圆环的范围还是0 - 1000， 假设我们有四个节点A, B, C, D, 每个节点被拆分成A1 - A10, B1 - B10, C1 - C10, D1 - D10, 这样我们就有40个虚拟节点，把这40个节点均匀分布在圆环上，这样A1负责0-25，B1负责26-50，C1负责51-75，D1负责76-100，然后A2负责101-125，以此类推。
因为我们有大量的虚拟节点，而且均匀分布，每个节点处理的请求不多，删除节点的时候对顺时针方向的下一个节点影响不大，不容易引起雪崩。增加一个物理节点的时候相当于在圆环上均匀地增加k个虚拟节点，更能均衡地处理负载。
参考文章/图片引用