分布式算法 - 一致性Hash算法

    一致性Hash算法是个经典算法，Hash环的引入是为解决单调性(Monotonicity)的问题；虚拟节点的引入是为了解决平衡性(Balance)问题。

    一致性Hash算法的原理主要分为两步：

    首先，对存储节点的哈希值进行计算，其将存储空间抽象为一个环，将存储节点配置到环上。环上所有的节点都有一个值。其次，对数据进行哈希计算，按顺时针方向将其映射到离其最近的节点上去。

    当有节点出现故障离线时，按照算法的映射方法，受影响的仅仅为环上故障节点开始逆时针方向至下一个节点之间区间的数据对象，而这些对象本身就是映射到故障节点之上的。

    当有节点增加时，比如，在节点A和B之间重新添加一个节点H，受影响的也仅仅是节点H逆时针遍历直到B之间的数据对象，将这些重新映射到H上即可，因此，当有节点出现变动时，不会使得整个存储空间上的数据都进行重新映射，解决了简单哈希算法增删节点，重新映射所有数据带来的效率低下的问题

一致性Hash算法的引入

    在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义:

• 平衡性(Balance): 平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
• 单调性(Monotonicity): 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
• 分散性(Spread): 在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
• 负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

Hash环

    使用常见的hash算法可以把一个key值哈希到一个具有2³²个桶的空间中。也可以理解成，将key值哈希到 [0, 2³²) 的一个数字空间中。 我们假设这个是个首尾连接的环形空间。

    若我们现在有4个key值，分别为k1、k2、k3、k4，通过一定的Hash算法将Hash到这个环形的Hash空间上，如下图所示：

    同样假设我们有三台节点机器分别为node1、node2、node3，我们依然将其Hash到这个环形空间中：

    接下来就是数据如何存储到服务器上了，key值哈希之后的结果顺时针找上述环形hash空间中，距离自己最近的机器节点，然后将数据存储到上面， 如上图所示，k1 和 k4 存储到 node3 上， k3存储到node1上， k2存储在node2上。用图表示如下:

删除节点

若node1节点宕机，这时候就需要将node1从集群中摘除，那么之前存储在node1上的key就需要顺时针寻找距离自己最近的节点，如下图所示，原先存储在node1上的k3将会存储到node2上：

添加节点

    有时候需要添加节点，在添加节点之后，只有在添加节点和其前一个节点之前的数据需要变动：

不平衡问题

    面的简单的一致性hash的方案在某些情况下但依旧存在问题: 一个节点宕机之后，数据需要落到距离他最近的节点上，会导致下个节点的压力突然增大，可能导致雪崩，整个服务挂掉。如下图所示若node3宕机，其数据将会全部转移到node1，若node1无法承受突如其来的大量数据也有可能挂掉：

虚拟节点

    “虚拟节点”( virtual node )是实际节点(机器)在 hash 空间的复制品( replica )，一实际个节点(机器)对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以hash值排列。

    若其中node1节点挂掉，那么数据将有以下变动：

• 原先由1-1存储的k1将由2-1接受
• 原先由1-2存储的k3将由3-2接受

    这样做的好处显而易见，不再是由一台机器完全接受数据，雪崩的可能性大大减小