图解一致性hash算法和实现( 二 ) _一致性hash算法

说明：这里所说的迁移并不是直接的数据迁移，而是在查找时去找顺时针的后继节点，因缓存未命中而刷新缓存。
计算方法：假设节点hash散列均匀（由于hash是散列表，所以并不是很理想），采用一致性hash算法，缓存节点从3个增加到4个时，会有0-33%的缓存失效，此外新增节点不会环节所有原有节点的压力。

一致性hash算法的结果相比传统hash求余算法已经进步很多，但可不可以改进一下呢？或者如果出现分布不均匀的情况怎么办？比如下图这样，按顺时针规则，所有的key都归属于统一个节点。

文章插图

一致性hash算法+虚拟节点为了优化这种节点太少而产生的不均衡情况。一致性哈希算法引入了虚拟节点的概念。
所谓虚拟节点，就是基于原来的物理节点映射出N个子节点，最后把所有的子节点映射到环形空间上。

文章插图

虚拟节点越多，分布越均匀。使用一致性hash算法+虚拟节点这种情况下，缓存节点从3个变成4个，缓存失效率为25% ，而且每个节点都平均的承担了压力。

一致性hash算法+虚拟节点的实现原理理解了，实现并不难，主要是一些细节：

hash算法的选择。JAVA代码不要使用hashcode函数，这个函数结果不够散列，而且会有负值需要处理。
这种计算Hash值的算法有很多，比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等，其中KETAMA_HASH是默认的MemCache推荐的一致性Hash算法，用别的Hash算法也可以，比如FNV1_32_HASH算法的计算效率就会高一些。
数据结构的选择。根据算法原理，我们的算法有几个要求：