传统的Hash介绍
传统的Hash是对服务器进行取模(取余)操作。 假如服务器的台数是N,取模算法为: 1
hash (数据ID) % N
使用上述Hash算法时,会有一些缺陷。 当缓存服务器数量发生变化时,会引起缓存的雪崩或几乎所有的位置缓存改变。
一致性Hash介绍
一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,一致性哈希修正了使用的简单哈希算法带来的问题,当缓存服务器数量发生变化时可以尽量减少受影响的缓存。 采用一致性哈希算法时,服务器的数量如果发生改变,并不是所有缓存都会失效,而是只有部分缓存失效,缓存仍然能分担整个系统的压力,不至于同一时间集中到后端服务器上。
一致性哈希算法也是使用取模的方法,只是不是对服务器的数量进行取模,而是对 2^32 取模,算法如下。 1
hash (服务器的IP地址) % 2^32
或 1
hash (服务器的主机名) % 2^32
一致性Hash实现
不带虚拟节点
1 | package hash; |
带虚拟节点
1 | package hash; |