几种数据分布算法

一、hash算法

hash算法的实质是对key进行hash，然后将hash后的值对节点个数取模。其运用场景包括、数据库分库分表等。相对来说，hash算法实现较简单。但是也存在一些问题，比如当节点个数扩容或者减少，那么存在原来节点中的所有数据需要重新对新节点个数取模，分配新的节点位置。如下图所示，假设当前有三个节点，现在有三个key，通过hash(key)%3后，key1路由到node3、key2路由到node2、key3路由到node1。

当增加或者减少node后，key1、key2、key3根据新的节点个数就很难保证还能路由到原来的节点，因此所有的key都会受到影响。

二、一致性hash 2.1 基本思想

hash算法的思想是对节点个数进行取模，一致性hash的思想则是将节点分布到圆环上，圆环的取值范围从0到.-1，当对key进行路由时，先计算key的hash值，然后将该值对应到圆环，再顺时针旋转遇到的第一个节点就是路由的节点。如图所示，假设key1,key2,key3经过hash后，hash(key1)落在node3~node1之间，hash(key2)落在node1~node2之间，hash(key3)落在node2~node3之间，那么经过顺时针旋转，key1路由到node1，key2路由到node2，key3路由到node3。

当其中某个节点损坏或者新增节点时，只影响部分key。具体看看，比如我们在node1和node2之间新增了节点node4。

同样还是key1、key2、key3，hash(key1)落在node3~node1之间，hash(key3)落在node2~node3之间，只有hash(key2)落在node1~node4之间，经过顺时针旋转，key1仍然路由到node1，key3路由到node3，key2从原来路由到node2改为路由到node4，也就是说，新增节点node4只影响了key2。

我们将node1~分为两段，node1~node4,node4~node2，那么影响的key实际上只有hash值落在node1和node4之间的key，而hash值位于node4到node2之间的key仍然路由到node2。

2.2 一致性hash的负载均衡

当大量的key经过hash运算后位于某个区间，即大量的key都路由到某个节点，而其他节点只有少部分key路由，造成某个节点数据过热怎么解决呢？即如下图的情况，key1、key2、key3的hash值均散落在node3~node1之间，那么导致这些key都路由到node1，造成node1数据过热：

一致性hash引入了虚拟节点的思想来解决这个问题。即在原来的节点之间散布代表某个节点的虚拟节点，当key经过hash后，顺时针遇到的第一个节点，如果是真实节点，则直接路由到该节点，如果是虚拟节点，则将key路由到虚拟节点对应的真实节点。比如，还是拿上文的key1、key2、key3来说，新增虚拟节点后，hash(key1)落在落在~node1之间，hash(key2)落在node3~之间，hash（key3）落在~之间，那么顺时针旋转，key1路由到node1，key2路由到虚拟节点对应的真实节点node2，key3路由到对应的真实节点node3，而未添加虚拟节点时，这三个节点都路由到node1，现在已经均匀分布到各个节点了。

三、redis hash slot算法

Redis 采用hash slot算法来路由key。实际上该思想和一致性hash是一样的，关键的点就在于key的hash值不与节点个数关联（取余），而是关联其他值。Redis固定分配了16384个slot，当集群存在n个时，它会将这些slot均匀分配到各个上。当对key取hash后，对slot的总数16384进行取余，从而将key路由到对应的slot。

当其中某个节点挂掉，redis会将这个节点上的slot重新分派到其他节点，而取余仍然是对slot总数16384取余，因此，也只会影响挂掉的节点上的slot还未分派到其他节点的这段时间的key。

以上，就是几种数据分布算法的简要介绍。