什么是一致性哈希算法？

一致性哈希算法

什么是一致性哈希算法

一致性hash就是 计算每个分布式服务器落点的算法 假设，服务器都在一个线上或则环上，缓存请求落点顺时针寻找最近的服务器，这样的好处就是，如果一台服务器down了，只会影响一段缓存，其他的不受影响，加减服务器成本降到最低，如果是余数散列算法，只要down掉一台缓存失败率上升至少80%，所以memcache分布式，都是用一致性hash算法来计算服务器散列位置的，你用php的memcached扩展，add服务器，可以选择散列算法，默认是一致性hash，也可以选择余数。

一致性hash的使用在PHP中有三种选择分别是原生的memcache扩展，memcached扩展，还有一个是网上比较流行的 Flexihash类。前两者都适用于memcache 但不适合Redis

Flexihash 是一个小型PHP库，实现了一致的哈希，这在分布式缓存中最有用。

一致性哈希算法简介

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用

目前主要应用于分布式缓存当中，一致性哈希可以有效地解决分布式存储结构下动态增加和删除节点

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

1. 平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

1. 单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

1. 分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

1. 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

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

传统哈希方式

在分布式缓存系统中吗，需要将数据均匀的分布到缓存服务器集群的不同机器上。

需要对缓存的key做hash值计算，将hash值除以服务器节点的数量取模计算出数据需要落在哪台服务器节点上。

缓存策略的潜在问题是如果增加或删除机器时（N变化）代价会很高，所有的数据都不得不根据id重新计算一遍哈希值，并将哈希值对新的机器数进行取模操作，然后进行大规模的数据迁移为了解决这些问题，引入一致性哈希算法。假设数据的id通过哈希函数转换成的哈希值范围是232，也就是（0~232-1）的数字空间中。

我们将这些数字头尾相连，想象成一个闭合的环形，那么一个数字id在计算出哈希值之后认为对应到环中的一个位置上接下来，想象有三台机器也处于这样一个环中，这三台机器在环中的位置根据机器id计算出的哈希值来决定。那么一条数据如何确定归属哪台机器呢？首先把该数据的id用哈希值算出哈希值，并映射到环中的相应位置，然后顺时针找寻离这个位置最近的机器，那台机器就是该数据的归属。例如，下图有一个数据m，计算其hash值后映射到环上，那么他的归属就是2号机器

这种算法很简单，也可以实现数据的均匀分布。但是增加或者减少数据节点的时候会导致所有缓存数据失效。

举个栗子：

例如10条数据，3个节点，如果按照传统hash结构对3进行取模：

• node a：0，3，6，9
• node b：1，4，7
• node c：2，5，8

当增加一个节点的时候，数据分布变更为对4进行取模：

• node a：0，4，8
• node b：1，5，9
• node c：2，6
• node d：3，7

然后，我们就可以看到，我们需要迁移的节点：3，4，5，6，7，8，9成本是不是很高

一致性哈希方式

一致性Hash算法最关键的区别就是：对节点和数据，都做一次哈希运算，然后比较节点和数据的哈希值，数据存放在下一个的节点中，这样就会保证节点增加或者减少的时候，影响的数据最少。

例子

还是刚才的例子（使用简单的字符串 ascii码 做哈希key）

1. 求出数据的hash值
   • 0：192
   • 1：196
   • 2：200
   • 3：204
   • 4：208
   • 5：212
   • 6：216
   • 7 ：220
   • 8：224
   • 9：228
2. 求出节点的hash值
   • node a：203
   • node g：209
   • node z：228

这时候，我们就可以将整个Hash值看做一个环，比较数据和节点的hash值，如果大于228，那么就归到前面的203上

1. 求出节点的hash值
   • node a：0，1，2
   • node g：3，4
   • node z：5，6，7，8，9
2. 加入了node：n节点之后
   • node n：216
3. 这个时候对应的数据就会做迁移

• node a： 0，1，2
• node g：3，4，
• node n：5，6
• node z：7，8，9

于是我们可以看到：只有5，6节点需要迁移。

这个算法是厉害，但是若是服务节点过少的情况下，是不是会导致节点分配不均匀可能会导致数据倾斜的问题呢？

为了解决数据倾斜的问题，一致性哈希算法引入了虚拟节点机制：即对每一个服务节点计算多个哈希，每个计算得到的Hash位置都放置一个此服务节点，称虚拟节点。具体可以在服务器ip或主机名的后面增加编号来实现。

结点（机器）删除

以上面的分布为例，如果Node2（机器2）出现故障被删除了，那么按照顺时针迁移的方法，Hash值属于图中红色片段的所有数据将会被迁移到Node3（机器）中，这样仅仅是红色的一段映射位置发生了变化，其它的对象没有任何的改动。如下图：

结点（机器）添加

如果往集群中添加一个新的节点NODE4，通过对应的哈希算法得到KEY4，并映射到环中，如下图：

按照顺时针迁移的规则，数据Hash值处于红色段的数据被迁移到了Node4中，其它对象还保持这原有的存储位置。通过对节点的添加和删除的分析，一致性哈希算法在保持了单调性的同时，数据的迁移时间达到了最小，这样的算法对分布式集群来说是非常合适的，避免了大量数据迁移，减小了服务器的的压力

一致性哈希算法优化

其实上面的一致性哈希函数还存在一个很大的问题，我们说Hash函数是输入的样本量很大的时候，其输出结果在输出域上是均匀分布的，但是这里假如只有三个输入，就很难保证分布是均匀的，有可能产生下图所示的分布，就导致负载极其不均衡

更加优化的一致性哈希算法引入了虚拟节点机制，即对每一台机器产生多个结点，称为虚拟节点。具体做法可以在机器ip或主机名的后面增加编号或端口号来实现。假设一台机器有1000个虚拟节点，3台机器就有3000个结点，3000个结点映射到哈希域上就相对比较均匀了