一、普通hash

大数字取模分散不同桶，两个桶， 2、3、4、5 ，模 2 分桶：

扩容新桶，模 3 来结果：

每次扩展和收缩所有条目分布重新计算，某些场景不可接受。文件分布在哪台哈希算法决定，这个系统想要加一台机器时就需要停下来等所有文件重新分布一次才能对外提供服务，一台机器掉线尽管只掉一部分数据，所有数据访问路由都会出问题。无法平滑的扩缩容。

二、一致性哈希  

1、例子：

无状态化，用多个桶， 模 7个，开始只有两个 3 和 6。同样取模，分到不存在的桶，往下找第一个真实存桶。 2 和 3 分3 桶， 4 和 5分 6 桶。

添加新 编号4桶，还是模 7：

3 号桶取模小于等于 3，4 号桶只需从 6 号桶拿走属于它数字就可，只调整一个桶重新分布。即使有 1 亿个桶，增加减少一个桶也只会影响一个桶的数据分布。

只需和后面机器同步数据就可工作，同步到后一台机器再下线。实现中可以让每台机器同步一份自己前面机器的数据，即使掉线也不影响这部分数据服务。

问题：编号 6 的机桶下线了，没有后一个桶了，哈希空间做成环状，数据给 3 ：

一致性哈希还能实现部分的分布式系统无锁化，算法的确定性，分到哪个桶也是确定的就不存在争抢，不需要分布式锁了。

三、为啥主流的哈希都是非一致的呢？

查找效率：普通的哈希查询一次哈希计算就可以找到对应的桶了 O(1)，一致性哈希需要将排好序的桶组成一个链表，一路找下去k 个桶 O(k)

O(k) 对于哈希来说不能忍，这个量级了用哈希没意义，在排好序桶里查询，二分把时间复杂度降到 O(logk)，桶组合需不断增减，链表实现二分肯定不行，用跳转表快速跳转也能实现 O(logk) 

跳转表中，每个桶记录距离自己 1，2，4距离的数字所存的桶，不管查询落在哪个节点上，对整个哈希环上任意的查询一次都可以至少跳过一半的查询空间？，这样递归下去很快就可以定位到数据是存在哪个桶上。

上面只是一种，很多一致性哈希变体。如选桶：上面顺着数字选对面出现第一个桶，其实也可选距离数字最近桶，这样跳转表规则也变。同样跳转表不同算法实现： CAN，Chord，Tapestry，Pastry 这四种 DHT 

问题：

1、如果6号(里面有数据)桶突然宕机了，是不是里面的数据也丢失了？来不及将桶里的数据往前一个桶移？

答：实际情况会做冗余，画的是一个桶，实际可能是三个

2、「一致性」是扩缩容前后数据在桶里的分布是一致的

3、分布式系统中怎么实现服务间的事务，目前有哪些通用做法，比如dubbo?

用zk或者etcd这种分布式锁服务，让接口是幂等，可以反复重试

4、增加此类操作会拖慢集群的性能。如果某节点上一刻宕机，往后新数据会进入下一个节点，宕机节点恢复，下一个节点还要同步原属宕机的数据，复杂度为O(nlogn)，会不会代价略高？开源的ketama没有同步数据这一做法，所以本质上只是近似一致性哈希，是不是一个trade-off的选择？

答：这个场景不适合使用一致性哈希吧。以负载均衡为例，理论上是认为后台服务器是无状态的吧。所以宕机重启不应该有数据同步的问题。

处理数据同步，raft强一致方案

二、hash取模算法

对hash结果取余数 (hash() mod N)：机器编号从0到N-1，hash()值按N取模，余数i，分发到编号i机器。致命问题，宕机，落在该机器请求无法处理，有(N-1)/N服务器的缓存数据重新计算；为何是 (N-1)/N 呢：3 台机器，hash值 1-6 分布：

host 1: 1 4

host 2: 2 5

host 3: 3 6

挂掉一台，只剩两台，模数取 2：

host 1: 1 3 5

host 2: 2 4 6

位置不变2个： 1，2，位置改变4个，占共6个数据的比率是 4/6 = 2/3。

虚拟节点

N个真实节点,每个映射成M个虚拟节点, M*N个虚拟节点散列在圆环上. 真虚相互交错分布，真down后,平均分到所有节点

访问方法：

写入缓存请求，Key值为K，计算器hash值Hash(K)， Hash(K) 对应于环中的某一个点，没有映射到机器节点，顺时针查找，直到找到有映射机器的节点，确定目标节点，超过2^32找不到，命中第一个。

缺陷：server数量很少时，环中分布不均匀，导致cache到server不均匀

三、数据倾斜

例：用电话号码group by，如移动用户多，就会倾斜，reverse或加随机数解决

hash取模对模数有要求，用奇数不用偶数，数据量大的时模数不好选，用上面办法。

https://zhuanlan.zhihu.com/p/24440059

https://blog.csdn.net/hunandexingkong/article/details/70241933