一致性hash
什么是一致性hash
- 传统hash的问题
在分布式环境下，我们可以通过 hash(id) % 机器数量 确定在哪一台机器上，这样做的缺点在于扩容的时候，需要重新计算数据的分布情况。
- 一致性hash
一致性hash算法解决的核心问题是，当solt数发生变化的时候能够尽量少的移动数据。
一致性hash是由 0 ~ 2^32-1 的值分布在一个环上。
一般的方法可以使用机器的 IP 地址或者机器名作为hash 输入，确定该机器在环上的哪个位置。
当数据存储时，根据hash值在hash环上的位置顺时针找距离最近的ip作为路由ip。
- 一致性hash数据倾斜（hash环偏移）
使用虚拟节点解决：
在hash环上分布虚拟的机器上，比如真实机器为A,B,C，我们在hash环上虚拟A1,B1,C1到环上，做到相对均匀。
- 一致性hash会出现hash碰撞的问题吗？
逻辑上是会出现hash碰撞的问题的，但我们可以通过业务代码控制hash的碰撞，比如ip的c段的控制等。
解决hash碰撞的方法：
- 开放地址法
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
- 再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
- 链地址法（拉链法）
将所有关键字为同义词的记录存储在同一线性链表中。可以近似的认为是筒子里面套筒子
- 建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
- 漂移问题
某个节点失效了，缓存都漂到下个节点了；然后一会它又恢复了，这时候它就有脏数据了。
解决办法一是每个节点引入集群。不用集群想彻底解决这个问题，可能需要引入第三方健康检查组件，如Consul，发现节点不稳定立即删除下线。