一致性哈希算法 虚拟节点(比一致性哈希还好的算法)

采用固定哈希算法平衡负载

在大规模的缓存应用中，应运而生了分布式缓存系统。key-value如何均匀的分散到集群中？最常规的方式莫过于hash取模的方式。比如集群中可用机器适量为N，那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。但是在一些高速发展的web系统中，这样的解决方案仍有些缺陷。随着系统访问压力的增长，缓存系统不得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式，在增加机器节点的这一时刻，大量的缓存命不中，缓存数据需要重新建立，甚至是进行整体的缓存数据迁移，瞬间会给DB带来极高的系统负载，设置导致DB服务器宕机。

如果不是缓存数据，而是持久化的数据，那么当扩容的时候，绝大部分数据都要迁移(取模的基数N变化了)，这也是不能忍受的。

一致性哈希平衡负载

引入一致性哈希，解决以上增减机器导致负载瞬间整体增大问题

通过在整数范围内负责各区域的方式，节点负责区域的负载不会随着增减节点发生大规模的迁移

但是最简单的一致性哈希，在增减物理机的时候，似乎要增加一倍节点或减去一半节点才能保证各个节点的负载均衡

虚拟节点对一致性哈希的改进

对于一致性哈希的负载分布不平均问题，所以提出：虚拟节点对一致性哈希的改进

4个物理节点可以变成很多个虚拟节点，每个虚拟节点支持连续的哈希环上的一段。而这时如果加入一个物理节点，就会相应加入很多虚拟节点，这些新的虚拟节点是相对均匀地插入到整个哈希环上，这样，就可以很好的分担现有物理节点的压力了；如果减少一个物理节点，对应的很多虚拟节点就会失效，这样，就会有很多剩余的虚拟节点来承担之前虚拟节点的工作，但是对于物理节点来说，增加的负载相对是均衡的。

所以可以通过一个物理节点对应非常多的虚拟节点，并且同一个物理节点的虚拟节点尽量均匀分布的方式来解决增加或减少节点时负载不均衡的问题。

至于一个物理节点对应多少的虚拟节点才能达到比较好的均衡效果，有一个图

x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale)，y轴是实际物理服务器数，可以看出，当物理服务器的数量很小时，需要更大的虚拟节点，反之则需要更少的节点，从图上可以看出，在物理服务器有10台时，差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。

映射表与规则自定义计算方式

映射表示根据分库分表字段的值的查表法来确定数据源的方法，一般用于对热点数据的特殊处理，或者在一些场景下对不完全符合规律的规则进行补充。

可以通过自定义函数实现来计算最终的分库，举例来说，假设根据id取模分成了4个库，但是对于一些热点id，我们希望将其独立到另外的库，那么通过类似下面的表达式可以完成：

if (id in hotset) {

return nodes;

}

return hash(id);

参考：

http://www.iteye.com/topic/611976

http://www.iteye.com/topic/684087

《大型网站系统与Java中间件实践》

http://blog.csdn.net/sparkliang/article/details/5279393