Hash算法

  • 平方取中：对数据进行平方运算，再取中间若干位作为Hash值
  • 除留余数：对数据求余得到Hash
  • 斐波那契数列：对数据的每一位乘上斐波那契数的一个值，计算出Hash值
  • 伪随机数：选用某一个伪随机函数对数据的值进行计算得出Hash值
  • 数位分析：对数据为数值、位数进行分析计算得出Hash值
  • 直接定址：直接用数据某个字段作为Hash的值

解决Hash冲突

  • 链地址法：发生碰撞的节点使用链表储存在同一个Hash的值下面
  • 顺序寻址：若发生碰撞，则按一定算法不断下一个地址
    • 线性探测：直接探测下一个相邻的地址（+1，+2，+3，……）
    • 二次探测：在冲突Hash地址上加上一个平方数（，，，……）
    • 伪随机数：采用相同的伪随机函数生成下一个伪随机数
  • 再Hash：使用另一个Hash函数计算新的Hash
  • 公共溢出区：将发生碰撞的数据全部放到公共溢出区中

一致性Hash

情景

在n个分布式的服务器的环境中，使用的哈希算法是最后是%n的。

当某一个服务器宕机后，只剩下n-1台服务器能提供服务，此时使用的哈希算法需要%(n-1)。

如此一来，之前所有服务器的缓存数据都将失效，容易发生 缓存雪崩。

思想

将Hash地址看成一个首尾相连的环，如从1到2^32这段区间首尾相连成环。

将服务器作为节点映射到这段区间中。显然服务器的数量小于区间大小，即，区间中还是会有很多“空隙”。

当有数据前来访问时，如果其Hash的值没有恰好落在服务器的节点上，则在环中沿着某一个方向一直寻找，知道遇见服务器。

如此一来，如果再发生某一个服务器宕机的情况，该节点的数据也只会顺延到最相邻下一个服务器节点中，其他服务器并不会受到影响。在使用虚拟节点优化后，负载均衡的效果更好。

优化：虚拟节点

问题
如果服务器在环中的位置非常的集中，那么也难以达到负载均衡的效果。

解决：虚拟节点
将一个服务器，在Hash地址的环中映射多个虚拟节点，寻址到这多个虚拟节点的数据全部由同一个服务器处理。

这样，即使实际服务器的数量不多，也能在Hash地址的环中有较多的服务器节点，在原服务器哈希地址较为集中的情况下，通过多个虚拟节点也能使整体更为均匀、分散、随机的分布于Hash地址的环中。