应用背景
解决分布式环境中数据倾斜和容错问题解决普通Hash方法节点失效的造成的重Hash问题
一致性Hash原理
普通Hash在分布式环境中应用的问题
在数据并行的分布式系统中，上游算子实例的输出怎样分配到下游算子实例就涉及到Hash的应用。以Flink为例，如下图所示，下游算子有两个实例，上游的分发数据策略有——一对一转发、广播、基于键值、随机这四种。其中基于的键值的keyby()方法就是使用hash算法来对同一key值对应的键值对进行分配。
public static int computeKeyGroupForKeyHash(int keyHash
, int maxParallelism
) {
return MathUtils
.murmurHash(keyHash
) % maxParallelism
;
}
3. 这种直接hash的方式有个问题：如果下游的算子的并行度改变，上游节点hash值就会改变，导致“同一个key值分配在同一个实例中”不再成立，FLink对此采用的策略有三种： 1). 对于不同的键值组根据新的实例数量重新hash分配 2). 算子所有实例的键值对全部收集然后进行重新均匀分配 3). 算子将所有键值对发送到新的所有任务上，每个新的任务决定留下哪部分（根据状态为联合列表状态还是广播状态还有所不同，就不展开了） 这里就能看出，简单的hash方法会影响所有的已有算子。
一致性hash函数原理与普通hash对比
普通的Hash计算：Hash(key) % parallelism 并行度改变，原先分配的键值对需要重新计算然后分配一致性Hash函数：不再是通过单个hash值决定键值分配的节点，而是将整个hash域作为分配的区间，为不同的节点分配一定的长度区间，只要是hash计算结果在某个分区中的键值对就会被分配到同一个节点中。 就像是上图中描述的：一致性Hash算法也是使用取模的方法，只是，不再是对算子的并行度进行取模。 上图中，四个键值对对象ABCD根据计算出的hash值落在了整个hash阈的不同位置，从各自位置沿环顺时针，第一台遇到的节点就是其应该被分配的节点
一致性hash解决的问题
可以实现状态的多副本（例如将每个节点顺时针起的第一个节点作为备份节点），便于状态迁移（迁移到副本存在的节点就省去了迁移的开销）负载均衡的实现 如上图所示，假设这时一致性hash分配逻辑是逆时针区间分配即A到B区间的键值对分配到A节点中；如果这时A的负载过大，那么可以调整B在环空间逻辑位置，如上图右侧，使其键空间得到扩展，分担了来自节点A的一些负载；在此过程中如果B正好是A的副本节点，那么就不需要显式的状态转移，开销更小。扩缩容 扩容：在A和B节点之间增加一个节点（即增加一个算子并行度），该新节点将接管节点A的部分负载。在A继续处理传入的键值对的同时执行延迟的状态迁移转换（即到节点C的异步状态转移），并且仅在状态转移完成后才转移负载。（在新增的节点中是没有原先的备份节点的，所以不能够处理新的元组，只能是当A处理完之后将负载进行迁移）。 缩容：在这种情况下，由于节点A的负载很轻，检查相邻节点B看看是否有空闲周期来接管其所有负载。 如果满足条件，则可以将节点A从对等环中删除，并将节点B移动到其位置。不需要状态或元组传输即可完成转换。
总结
一致性Hash方法和普通的Hash相比关键就是将对应关系由“单值对应”转变为“区间对应”，减少了重映射的开销，更容易实现容错和扩缩容。
参考
面试必备：什么是一致性Hash算法？Kumbhare A, Frincu M, Simmhan Y, et al. Fault-tolerant and elastic streaming MapReduce with decentralized coordination[C]//2015 IEEE 35th International Conference on Distributed Computing Systems. IEEE, 2015: 328-338.
