1. 传统哈希(硬哈希)
分布式系统中，假设有 n 个节点，传统方案使用 mod(key, n) 映射数据和节点。
当扩容或缩容时(哪怕只是增减1个节点)，映射关系变为 mod(key, n+1) / mod(key, n-1)，绝大多数数据的映射关系都会失效，需要re-hash所有的值。
2. 一致性哈希 Consistent Hashing
1997年，麻省理工学院(MIT)的 David Karger 等6个人发布学术论文《Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web（一致性哈希和随机树：用于缓解万维网上热点的分布式缓存协议）》，对于 K 个关键字和 n 个槽位(分布式系统中的节点)的哈希表，增减槽位后，平均只需对 K/n 个关键字重新映射。
评估一个哈希算法的优劣，有如下指标，而一致性哈希全部满足：
均衡性(Balance)：将关键字的哈希地址均匀地分布在地址空间中，使地址空间得到充分利用，这是设计哈希的一个基本特性。
单调性(Monotonicity): 单调性是指当地址空间增大时，通过哈希函数所得到的关键字的哈希地址也能映射的新的地址空间，而不是仅限于原先的地址空间。或等地址空间减少时，也是只能映射到有效的地址空间中。简单的哈希函数往往不能满足此性质。
分散性(Spread): 哈希经常用在分布式环境中，终端用户通过哈希函数将自己的内容存到不同的缓冲区。此时，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
3. 原理
3.1映射方案
3.1.1 公用哈希函数和哈希环
设计哈希函数 Hash(key)，要求取值范围为 [0, 2^32)
各哈希值 Hash 环上的分布：时钟12点位置为0，按顺时针方向递增，临近12点的左侧位置为2^32-1。
3.1.2 节点(Node)映射至哈希环
如图哈希环上的绿球所示，四个节点 Node A/B/C/D，
其 IP 地址或机器名，经过同一个 Hash() 计算的结果，映射到哈希环上。
3.1.3 对象(Object)映射于哈希环
如图哈希环上的黄球所示，四个对象 Object A/B/C/D，
其键值，经过同一个 Hash() 计算的结果，映射到哈希环上。
3.1.4 对象(Object)映射至节点(Node)
在对象和节点都映射至同一个哈希环之后，要确定某个对象映射至哪个节点，
只需从该对象开始，沿着哈希环顺时针方向查找，找到的第一个节点，即是。
可见，Object A/B/C/D 分别映射至 Node A/B/C/D。
4. 应用
一致性哈希是分布式系统组件负载均衡的首选算法，它既可以在客户端实现，也可以在中间件上实现。其应用有：
分布式散列表(DHT)的设计；
分布式关系数据库(MySQL)：分库分表时，计算数据与节点的映射关系；
分布式缓存：Memcached 的客户端实现了一致性哈希，还可以使用中间件 twemproxy 管理 redis/memcache 集群；
RPC 框架 Dubbo：用来选择服务提供者；
亚马逊的云存储系统 Dynamo；
分布式 Web 缓存；
Bittorrent DHT；
LVS。
