求求你别问我一致性hash了

面临的问题

首先，只有存储型的组件，我们才会使用一致性hash；计算型的服务增删节点对整个任务一般没影响，所以负载均衡直接用random就可以。那么像redis、memcache怎么实现负载均衡的呢? 和普通的hash对比核心要解决的问题是：增删机子，hash不失效，节点变动尽可能少。

求余hash算法：

hash(object)%N

一个缓存服务器宕机了，这样所有映射到这台服务器的对象都会失效，我们需要把属于该服务器中的缓存移除，这时候缓存服务器是 N-1 台，映射公式变成了 hash(object)%(N-1) ；由于QPS升高，我们需要添加多一台服务器，这时候服务器是 N+1 台，映射公式变成了 hash(object)%(N+1) 。

一致性HASH算法

1. 一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环.

hash环

1. 将存储服务器的ip或主机名作为关键字进行hash。

服务器hash

1. 将存储/查询对象hash进行hash, 确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器！

顺时针hash

扩容、缩容

现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器。扩容同理。

扩容、缩容

应用

很多存储组件都是用的一致性hash来做Partition，比如Apacha Cassandra(一种nosql数据库), Dynamo, CouchBase.