一致性hash

背景：

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

分布式遇到的问题是，在集群扩缩容的、有节点宕机的情况下，命中率下降的问题，实质是增加了服务器之间的数据拷贝，主从的问题。使用一致性hash算法，将分布式系统中的服务器虚拟成一个有2的32次方个节点的环。将数据对象通过特定的hash函数计算出对应的key值，然后散列到hash环上。服务节点按照相同的函数进行hash计算，逆时针分配到环上。然后以顺时针的方向将对象存储到最近的集群中。

节点（机器）的增减，一致性哈希算法在保持了单调性的同时，还是数据的迁移达到了最小，这样的算法对分布式集群来说非常合适的，避免了大量收数据迁移，减少了服务器的压力。

hash算法是不保证平衡性的，为了平衡性引入了虚拟节点。Virtual node是实际节点（机器）在hash空间的复制品（replica），一个实际节点对应了若干个“虚拟节点”，这个对应个数也称为“复制个数”，“虚拟节点”在hash空间中以hash值排列。虚拟节点”的hash计算可以采用对应节点的IP地址加数字后缀的方式。例如假设NODE1的IP地址为192.168.1.100。引入“虚拟节点”前，计算 cache A 的 hash 值：

Hash(“192.168.1.100”);

引入“虚拟节点”后，计算“虚拟节”点NODE1-1和NODE1-2的hash值：

Hash(“192.168.1.100#1”); // NODE1-1

Hash(“192.168.1.100#2”); // NODE1-2

注意：

1.hash环是虚拟的，是对服务器的ip或主机名进行hash函数计算。

2.目的是减少数据的迁移

3.数据顺时针查找服务器

4.命中率：1）一个用户访问一个缓存服务器，其中有session等数据信息。如在1个小时的session有效期内，增减了服务节点，用户继续访问缓存仍然使用的这个服务器，并没有命中其他的服务器，若是访问其他的服务器，那里没有他的session/数据等，需要重新登录。

数据库访问是100%的命中，缓存才有命中率。

5.缓存是为了提高读取效率，复制的一份数据，数据库的数据。