一致性哈希与虚拟节点

以前在做项目的时候简单的研究过一致性hash，后来看Dynamo的实现原理时，对里面的虚拟节点不是很理解，也一直没有找到好的资料解释这个问题，昨天在光谷书城偶然看到一本讲网络爬虫的书上分析了这个问题，今天再在网上找了些资料，加深了对这个问题的认识。

 

一致性hash原理：http://blog.csdn.net/sparkliang/archive/2010/02/02/5279393.aspx

Ketama一致性Hash算法Java实现代码：

Ketama的.net实现代码： http://www.cnblogs.com/daizhj/archive/2010/08/24/1807324.html

 

弄清楚了虚拟节点的问题后，我发现引入虚拟节点虽然使得key的分布均衡了（有节点推出时，该节点上的key也会均衡的分散到其它节点），而且仍然保持了一致性hash的特性。但对于Dynamo这样对每个key保持多个副本的系统，以前可以直接将副本放到连续的节点上，采用虚拟节点后，应该如何放置副本呢，连续的几个虚拟节点可能对应着一个物理节点，总不能把副本都放在一个物理节点上吧，最直观的方法当然时，绕着环轮询，直到找到N（副本数）个对应不同物理节点的虚拟节点，貌似Dynamo就是这样做的。