一致性哈希算法

现在“分布式”的概念越来越广泛，分布式db、分布式cache等，在设计的过程免不了牵扯到哈希算法。接下来介绍下一致性哈希算法。

首先举个栗子：比如我们开发一个网站，随着网站的规模和受众度的增加，使得我们不得不想出一些解决有效的方案来解决数据读写压力，于是我们引入了缓存机制。比如memcached、redis等可能都会成为我们的选择，不过关于这些选择我们该怎么使用确实不得不考虑的问题。

方案一、可以在web服务器前面增加三个甚至更多的缓存服务器，类似如下的结构

，采用最简单的策略机制：通过随机方式获取到对应的缓存服务器，这样的话就存在可能如下问题：1.数据冗余，同一份数据存在不同的服务器上； 2、缓存数据命中率低，比如可能数据已经缓存过，本次请求由于是随机到对应的缓存服务器，会导致数据不能命中。不能够保证同一个key的数据存放在同一台缓存服务器上，所以该策略不能空间上还是时间上都是比较低效的

 方案二：为了解决针对方案一中存在的问题，那么我们可能会想到使用哈希算法，来保证相同的key的请求发送到相同的缓存服务器上，比如hash(k)%3 这样 就可以保证对相同的key缓存请求转到同一台缓存服务器，与此同时问题也随之而来，一旦我们增加节点或者减少节点的时候，hash计算要重新计算了，会导致key数据的冗余、命中率低的问题；意味着这样的设计容错性、可扩展性差，也意味着我们需要实现hash一致性计算

方案三、一致性哈希算法

1、概念：一致性哈希算法就是将整个哈希值组织成一个虚拟的圆环，这样的话，安装顺时针方向这个哈希值范围的首值和末值重合；

2、使用：首先我们使用电脑的ip或者主机名称执行Hash，将其定位到圆环中对应的位置；

                然后对于key同样执行hash，也将其定位到圆环中的位置

                最后，沿着顺时针方向，逐一找到每一个key通过hash后，靠近的第一个服务器的hash，那么就将                  这个key归属于这个缓存服务器；

   减少节点：只需要将原属于该节点的key按照逆时针方向，找到第一个临近的缓存服务器（前一个缓存服务                    器）；而其他正常 的缓存服务器及其关联的key则不需要进行任何改变

   增加节点：同样采用逆时针方向，找到第一个临近的缓存服务器，这两个范围内的数据就隶属于新增的缓                         存服务器。

   这样的话，无论使用增加、还是减少节点，真正受到影响的数据都是很小的一部分，同样容错性和可扩展      都得到了很好的完善。

在使用第三种解决方案时，有一个问题值得我们深思，一旦整个圆环节点很少的时候 ，就可能存在节点分布不均匀，数据大量的集中某一台缓存服务器中，针对于此种情况，可以通过使用虚拟节点的方式来解决

这样可以对同一个节点执行多个hash，这样就形成了分布较为均匀的分布，注意虚拟节点格式 缓存服务器编号#自定义编号 比如cache server 1 #1 这样就代表隶属于server 1的一个分支；如此类推。在实际使用过程，建议使用超过32个虚拟节点，使得节点分布更加均匀些，可以很好解决服务节点较少，数据倾斜的问题。