[白话解析] 深入浅出一致性Hash原理

  0x00 摘要

  0x01. 概念&原理

  1. 与经典哈希方法的对比

•   经典哈希方法：总是假设内存   位置的数量是已知且固定不变 的。因为hash映射依赖节点/内存位置，所以如果需要变化集群，需要重新计算每一个key的哈希值。   哈希表(服务器数量)大小的变更实际上干扰了   所有映射 。  
• 
    一致性哈希：某种虚拟环结构。   位置数量不再固定，环有无限数量的点 ，服务器节点可以放置在环上的随机位置。哈希表(服务器数量)大小改变会导致    只有   一部分请求 （相对于环分配因子）会受到特定的环变更的影响  

  2. 通俗理解一致性哈希的关键点：

  3. 一致性哈希如何处理请求

  4. 异常处理/变化应对

  0x02. 具体应用场景(通过名著水浒传为例来阐释)

  1. 经典算法：

  2. 一致性算法：

  哈希函数(这个固定不变)：

  酒店/客人分配规则如下(这个会根据容量变化做相应微调)：

• 
    酒店1负责 hash(x)--> 1~20，即客人姓名笔画/100位于1~20之间。  
• 
    酒店2负责 hash(x)--> 21~40，即客人姓名笔画/100位于21~40之间。  
• 
    酒店3负责 hash(x)--> 41~60，即客人姓名笔画/100位于41~60之间。  
• 
    酒店4负责 hash(x)--> 61~100，即客人姓名笔画/100位于61~100之间。  

  客人住店规则如下(这个固定不变)：

• 
    客人来了，姓氏笔画/100，得到余数。去余数对应的酒店住。比如余数3住到酒店1，余数22则住到酒店2......  
• 
    如果该酒店出问题关门了，就去比所有 "比余数大的酒店" 中最小那个住。以此类推。比如酒店1挂了，就去酒店2，酒店2挂了去3。  
• 
    如果最大酒店也出问题关门了，就转圈回到最小酒店住。即如果酒店4挂了去酒店1.  

  异常处理(扩容或者宕机)：

• 
    减少酒店。如果酒店3挂了，则原来去酒店3的客人去酒店4，原来去酒店4的客人还是酒店4. 这样只有酒店4受到影响，1，2号酒店客人不用搬家。  
• 
    增加酒店。如果增加了一个酒店5.则需要对    酒店/客人分配规则  做改变。让4号酒店负责61~80，5号酒店负责81~100。这样4号点原有部分客人要迁移到5号。  

  关键点：

  0x03. 参考