哈希算法在开发中有很常见的应用, 但是也仍然存在一些问题.
在 nginx 中作为一种路由策略, 如果添加或删除路由节点, 会导致路由发生大规模的变化;
在分布式缓存系统中, 如果添加或删除节点, 会导致缓存大规模的失效.
对于这些敏感的使用场景, 哈希算法并不能发挥很好的作用, 因此也就有了改良后的一致性哈希算法.
一致性哈希
Hash 环
一致性哈希将哈希值看作一个环(哈希环), 采用分片(范围)来代替单个的值进行路由, 因此才有了可能解决大规模的路由失效的问题.
通常哈希算法会生成一个32位的key, 哈希环的范围也就是: 0 - 2^32-1.
分片路由
将每个节点进行哈希取值, 将值映射到哈希环上对应的点.
对于每个需要路由的对象, 取其哈希值并映射到哈希环上对应的点, 然后按顺时针方向移动, 第一次遇到的节点就是该对象的目标路由节点了.
添加或删除节点测试
当在哈希环中添加一个节点时, 只有新添加节点的下一个节点的部分路由分配到新添加的节点上, 其他节点无影响;
当在哈希环中删除一个节点时, 被删除节点的按顺时针方向的下一个节点将要额外承担被删除节点的路由, 其他节点无影响.
路由平衡性
如果以节点的单个哈希值进行分片路由, 很可能会出现路由不均衡的现象, 某些节点路由负载太高, 某些节点路由负载又太低.
为了解决上述问题, 因此引入了虚拟节点的概念, 从而提高路由的平衡希.
也就是将一个节点根据哈希算法生成多个哈希值, 映射到哈希环上; 这样一个节点也就对应哈希环上的多个分片区间.
通常根据节点的复制个数, 对节点的 IP 地址加数字后缀的方式来生成其虚拟节点的哈希值.