通常的Sharding方案

我们假设现在有2台机器，我们需要把User表横向切分映射到这2台机器上。

一个简单的想法就是 userid % 2，余数可能是 0, 1 分别是2台机器的编号。

但是这样做存在一个巨大的问题，就是如果加一台机器怎么办？我们的算法肯定要有扩展性，能自由加减机器。假设我们现在加了一台机器，那么现在有3台，于是我们的sharding变成了 userid % 3。

这下可麻烦了，因为很多的数据这样计算完了之后 余数都变了，于是我们要把大量的数据进行迁移，而且这个迁移必须停机做，在迁移完成之前系统是不可用的。

这种哈希算法就叫不一致性哈希算法，那么显然这种方式是不可取的。

那么我们改进一下，这次我们取一个比较大的数，比如 500，然后 userid % 500 来计算一个值，因为我们只有2台机器，所以显然这个余数不是机器编号，而是我们把 0 ~ 499 分配给这2台机器。

这里我们做一个简单的均匀分配：

0 号机器： 0~249

1 号机器： 250~499

现在我们加一台机器的时候，编号为2，那么我们把2号机器插入到现有的两台机器之间，于是变成了这样：

0 号机器： 0~160

1 号机器： 161~320

2 号机器： 320~499

图示如下

可以看到现在全部机器的压力都降低了。

这么做的缺点是什么呢？

依然需要做一部分的数据迁移

每加入一台只能降低邻居两台机器的压力，这样很容易导致压力分布不均局。比如如果有5台机器，增加一台之后依然有三台机器压力不变。

如何将数据均匀的分散到各个节点中，并且尽量的在加减节点时能使受影响的数据最少呢？

一致 Hash 算法

一致 Hash 算法是将所有的哈希值构成了一个环，其范围在 0 ~ 2^32-1。如下图：

之后将各个节点散列到这个环上，可以用节点的 IP、hostname 这样的唯一性字段作为 Key 进行 hash(key)，散列之后如下：

之后需要将数据定位到对应的节点上，使用同样的 hash 函数将 Key 也映射到这个环上。

这样按照顺时针方向就可以把 k1 定位到 N1节点，k2 定位到 N3节点，k3 定位到 N2节点。

容错性

这时假设 N1 宕机了：

依然根据顺时针方向，k2 和 k3 保持不变，只有 k1 被重新映射到了 N3。这样就很好的保证了容错性，当一个节点宕机时只会影响到少少部分的数据。

拓展性

当新增一个节点时:

在 N2 和 N3 之间新增了一个节点 N4 ，这时会发现受印象的数据只有 k3，其余数据也是保持不变，所以这样也很好的保证了拓展性。

虚拟节点

到目前为止该算法依然也有点问题:

当节点较少时会出现数据分布不均匀的情况：

这样会导致大部分数据都在 N1 节点，只有少量的数据在 N2 节点。

为了解决这个问题，一致哈希算法引入了虚拟节点。将每一个节点都进行多次 hash，生成多个节点放置在环上称为虚拟节点:

计算时可以在 IP 后加上编号来生成哈希值。

这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。